Wavelet is known to be useful to represent image and video signals in terms of a multiresolution/multifrequency structure. In particular, wavelet coding schemes could avoid the block effect which occasionally occurred at the DCT coding scheme at low bit rate applications. Block matching motion estimation is popular in inter frame video coding, so that it has been adopted to implement several international video compression standards. In this paper, we present a multiresolution motion estimation (MRME) in the wavelet transform domain in cooperating with Hierarchical block matching to find a precise motion vector with fast estimation time and to reduce aperture problem which could occur in MRME.
Full search algorithm for motion estimation is widely used for the motion estimation in DCT domain. In MRME, full search motion estimation is employed at highest layer in DWT domain. Namely motion vectors are first estimated in the highest layer and further refined in the lower layers starting from the motion vectors obtained in the highest layer. In doing hierarchically, a large amount of computations to estimate could be saved.
However, block size of the highest layer is too small to estimate correct motion in the wavelet domain, and the resulted motion vector is obtained on the basis of the smallest MAD within the search range. Because of aperture problem caused by small block size, the estimated motion in highest layer is not precise so that it could deteriorate the performance of motion estimation in the other layers.
In order to obtain more reliable motion vectors in the highest layer, hierarchical block matching algorithm is adopted in the highest layer or approximation channel. Motion estimation using large block is robust for global motion and reduces the aperture problem in motion estimation caused by small block. On the other hand, motion estimation with small block could reduce block artifacts and the amount of error signals. So we propose a MRME adopted with hierarchical block matching so that the proposed method takes both advantages mentioned above.
The proposed algorithm is as follows.
1) hierarchical motion estimation at the approximation channel. i. First level : Search one motion vector with large block which is combined with 4 neighbors of small blocks.
ii. Second level : For each small block, find one motion vector which has the smallest MAD among candidate motion vectors of 8 neighboring blocks and current block.
2) Motion estimation at the remaing subchannels in the highest and other lower layers, which is referring to motion vectors obtained at the approximation. For each block of t he remaining subchannels, MAD is calculated based on the motion vectors from the approximation. If the MAD is smaller than predefined threshold value, then the motion vector is accepted. Otherwise the motion vector will be refined with further search strategy.
To verify the effectiveness of the proposed algorithm, we used 21 frames of “football”, “flower garden” and “ mobile calendar” sequences, respectively. Three sequences have different motion characteristics. The performance of the proposed algorithm is evaluated and compared with that of full search and Zafar’s algorithm in terms of PSNR, error image entropy, motion vector entropy and computation time. The proposed method has better performance for both PSNR and estimation time. Especially if the threshold is used in proposed algorithm, computational time as well as motion vector entropy is reduced.
웨이블렛 변환은 영상신호를 다중 해상도와 다중 주파수로 표현하는 데 유용하다고 알려져 있다. 특히 웨이블렛 변환은 DCT 부호화 방식의 저 비트율 응용에서 발생되는 블록킹 현상을 피할 수 있다. 화면간의 압축에 블록 매칭 움직임 추정은 매우 유용하며, 이 방식은 국제 영상압축 방식의 표준으로 정해져 있다. 본 논문에서는 MRME에서 발생하기 쉬운 틈새문제를 줄이고 움직임 추정 계산시간을 줄일 수 있는 웨이블렛 변환 영역에서의 계층적 블록매칭 MRME 방식을 제안한다.
전화면 탐색 움직임 추정 방식은 DCT 영역에서 움직임 추정하데 널리 사용된다. 그러나, 일반적으로 MRME에서는 DWT의 최상위 계층에서만 전화면 탐색 움직임 추정 방식을 사용한다. 즉, 웨이블렛 피라미드의 최상위 계층에서 움직임 벡터가 구해지면, 다른 서브 영상에서는 최상위 계층에서 구한 움직임 벡터를 기저 벡터로 사용하여 작은 탐색 범위 내에서 움직임 벡터들을 정제한다. 웨이블렛이 갖는 계층 구조를 이용한 이 방식은 계산시간을 많이 줄일 수 있는 장점을 갖고 있다.
그러나 정확한 움직임을 추정하기에 최상위 계층의 블록크기가 작으므로 실제의 움직임을 구하지 못하고 움직임 탐색 범위내에서 단지 화면간의 MAD가 가장 작은 위치만 찾는다 이러한 작은 블록크기 때문에 발생하는 틈새문제는 최상위 계층에서 얻어진 움직임 정보를 이용하는 다른 서브 영상들의 움직임 추정 성능을 저하시킨다.
최상위 계층에서의 정확한 움직임 벡터를 구하기 위하여 기초영상에서 계층적 블록매칭 알고리즘을 적용할 수 있다. 큰 블록을 이용하여 움직임을 추정하면 전체영상의 움직임(global motion)이나 큰 물체의 움직임을 정확하게 구할 수 있다. 반면에, 작은 블록을 이용하여 움직임을 추정하면 에러신호의 양과 블록킹 현상을 크게 줄일 수 있다. 본 논문에서는 앞에서 언급한 두 가지의 장점을 모두 지닌 계층적 블록매칭 방식을 이용한 MRME를 제안한다.
제안한 알고리즘은 다음과 같다.
1) 기초영상에서의 움직임 추정
i. 첫번째 단계 : 이웃한 작은 블록 4개로 구성된 큰 블록에서 하나의 움직임 벡터를 구한다.
ii. 두번째 단계 :작은 블록 단위애서 자기 블록을 포함한 8 개 이웃 블 록의 후보 움직임 벡터 중에서 MAD가 가장 작은 곳을 움직임 벡터로 선택한 다.
2) 다른 서브영상에서의 움직임 추정
기초영상에서 구해진 움직임 벡터를 기준으로 각 서브영상의 해당되는 블록에서 MAD를 구한다. MAD값이 미리 정해진 문턱값보다 작으면 그 움직임 벡터를 움직임 벡터로 이용한다. MAD 값이 문턱값보다 크면 그 움직임 벡터를 기저벡터로 사용하여 작은 탐색 범위 안에서 다시 한번 움직임을 추정한다.
제안한 방식의 성능을 검증하기 위하여 flower garden, football, 그리고 mobile calendar 시퀀스에 대하여 각각 21 프레임을 이용하여 실험하였다. 실험에 사용한 영상 데이터는 움직임 특성이 서로 다른 특성을 갖고 있다. 제안한 방식은 zafar 방식과 전화면 탐색방식의 PSNR, 에러 신호 엔트로피, 움직임 벡터 엔트로피 그리고 계산시간에 대하여 각각 비교하였다. 제안한 방식은 PSNR과 계산시간 면에서 기존 방식보다 우월한 성능을 나타냈었다. 특히, 제안한 방식 중에서 문턱값을 적용한 방식은 계산 시간은 물론 움직임 벡터 엔트로피 면에서 우수한 성능을 나타내었다.