Video compression plays an important role in transmission and storage of digital video data. The main idea to achieve compression is to remove temporal and spatial redundancies existing in video sequences. One effective method commonly used in reducing temporal redundancy is motion-compensated predictive coding. For motion-compensated coding, block matching algorithms (BMA) have been widely used as a motion estimation technique in most video coding systems due to its simplicity and effective compromise between prediction quality and motion information overhead.
To improve the coding performance, multiple frame motion estimation (MFME) has been recently developed to extend the motion search range by using multiple decoded frames as the reference, instead of using only one decoded frame as in the conventional motion compensation scheme. It provides a high coding performance, however, its computational complexity is significantly increased as compared to the single frame motion estimation (SFME).
In this thesis, we propose a fast block matching algorithm for MFME. Its major objective is to perform a fast search while maintaining a PSNR performance similar to a full search block matching algorithm (FSBMA). For reduction of computational complexity, we adopt a multi-resolution search with three resolution levels. Then, we adaptively modify the framework of the multi-resolution search according to the type of motion vector (MV), which is determined by using the MV information of neighboring macroblocks (NMBs). We also effectively reduce the number of MV candidates at the original resolution level by utilizing the sum of absolute difference (SAD) previously obtained.
In computer simulation, it is proved that the proposed algorithm provides a similar PSNR performance with dramatically reduced computational complexity as compared to the FSBMA. In particular, for sequences with fast motion or frame skipping, the proposed method provides more prominent PSNR performances with very fast search speed. Also, it can be a useful solution for the variable block motion estimation (VBME) as in 11.264.
디지털 비디오 데이타의 효율적인 전송과 저장을 위해서 다양한 응용 분야를 목적으로 한 H.263, MPEG-1, MPEG-2, MPEG-4 등의 여러 가지 동영상 압축 국제 표준들이 개발되어 왔다. 동영상을 압축하는데 사용되는 주된 원리는 동영상에 존재하는 시간적, 공간적인 중복성을 제거하는 것이다. 시간적인 중복성을 제거하기 위해 가장 널리 사용되는 효과적인 방법은 움직임 보상 부호화 방식 (motion compensated predictive coding)이다. 움직임 보상 부호화 방식의 비디오 코덱에서 가장 핵심적인 부분은 움직임 추정 (motion estimation)이다. 대부분의 동영상 압축 표준들에서는 움직임 추정을 위해 간단한 연산을 사용하는 블록 정합 기법 (block matching algorithm: BMA)을 채택하였다. 블록 정합 기법은 현재 프레임의 블록과 가장 유사한 블록을 이전 프레임의 미리 정의된 일정한 크기의 탐색 영역 내의 후보 블록들 중에서 찾아내는 것이다. 이 방법은 움직임 정보 비용과 추정 정확도의 타협에 의해 H.263, MPEG-1, MPEG-2, MPEG-4 등의 여러 가지 동영상 압축 국제 표준들에 사용되고 있다. 최근에 압축 성능의 향상을 위해 한 장의 이전 프레임을 쓰는 대신에 여러 장의 이전 프레임들을 사용함으로 탐색영역을 늘이는 다중 프레임 움직임 추정 (multiple frame motion estimation)이 개발되었다. 이 방법은 높은 코딩 성능을 가지지만 한 장의 이전 프레임을 쓰는 기존의 방법에 비해 계산량의 부담이 상당히 증가한다. 다중 프레임 움직임 추정의 계산량 증가 문제를 해결하기 위해 많은 연구가 진행되어 왔다. 본 논문에서는 다중 프레임 움직임 추정을 위해 고속 블록 정합 알고리듬을 제안한다. 제안하는 방법의 주목적은 전역 탐색 블록 정합 기법 (full search block matching algorithm)과 비슷한 PSNR 성능을 유지하면서 고속 탐색을 수행하는 것이다. 계산량 부담을 줄이기 위해 세가지 해상도 레벨 (원 해상도의 레벨 0, 하위 해상도를 가지는 레벨 1과 2)을 가지는 다해상도 탐색을 이용한다. 또한 인접한 매크로블록의 움직임 정보를 이용하여 현재 매크로블록의 움직임을 추정함으로써 다해상도 탐색방법의 구조를 바꾼다. 레벨 1과 0로부터 얻어진 정보를 이용함으로써 레벨 0에서 계산량을 줄인다. 다양한 실험을 통해 제안하는 방법이 전역 탐색 방법과 비슷한 PSNR 성능을 유지하면서 계산량을 상당히 줄임을 보였다. 빠르고 복잡한 움직임 및 프레임 스키핑 (frame skipping)을 가지는 비디오에 대해서도 제안하는 방법은 기존의 고속 움직임 추정 방법에 비해 비슷하거나 더 적은 계산량을 가지고 더 좋은 PSNR성능을 제공한다. 또한 다양한 크기를 가지는 블록에 대한 움직임 추정에 대해서도, 다른 고속 알고리듬에 비해 더 좋은 성능을 가진다. 그러므로 본 논문에서 제안하는 고속 움직임 추정 알고리듬은 탁월한 코딩 성능으로 인해 최근에 주목 받고 있는 H.264에서 채택하는 다중 프레임 움직임 추정 및 다양한 크기를 가지는 블록에 대한 움직임 추정에 대해 유용한 방법이 될 수 있다.
