In this thesis, we have proposed an improved multi-resolution motion search algorithm, namely, multi-resolution motion search algorithm using multiple candidates and spatial correlation of motion fields (MRMCS) that is effective in terms of both performance and VLSI implementation, and extend it so as to cover field-based ME as well as frame-based ME. The main concept of the MRMCS is to combine both spatial correlation of motion vectors and the merit of hierarchical search or multi-resolution search using multiple candidates in a computationally simple way, maintaining a similar rate-distortion performance to that of full search block matching algorithm.
MRMCS can avoid the local minimum problem by using multiple candidates in the middle level; one among the causal motion vectors of spatially adjacent blocks and two predict predicted from the coarsest-resolution level based on the predefined distortion measure. The former and the latter contribute to finding a true motion vector in the region having continuous and discontinuous motion field, respectively. Furthermore, an adaptive prediction technique is of use to increase the accuracy of a candidate predicted from the causal motion vectors of spatially neighboring motion vectors.
In computer simulations, it is proved that the proposed algorithm had some effective features appropriate for real-time motion-estimator, especially with large search area. That is, 1) MRMCS reduced the computation for finding motion vectors to 1.0% compared with full search block matching algorithm, and this complexity reduction ratio is close to minimum bound for a realizable motion estimator. 2) MRMCS achieved the motion estimation performance close to upper bound. Compared with the full search block matching algorithm, the maximum performance degradation reach to only -0.2 dB, which did not affect on the subjective quality of reconstructed images al all.
최근, 실시간 부호화가 필수적인 통신, 방송 매체와 함께 저장 매체를 지원하기 위하여 MPEG-2 동영상 압축 표준이 제정되었고, 이를 구현하려는 노력들이 활발히 진행되고 있다. 블록 정합 알고리즘은 MPEG-2에서 움직임 추정방법으로 채택하고 있는 시간영역 중복성 제거 방법으로서, 일반적으로 전역 탐색 방법 혹은 고속 탐색 방법 등을 기반으로 구현되어 왔다.
본 논문에서는 움직임 탐색을 위해 요구되는 계산량을 줄이기 위하여, 전역 탐색 방법을 대치할 수 있는 고속 움직임 추정 알고리즘(Multi-resolution search using multiple candidates and spatial correlation of motion field, MRMCS)을 제안하였다. 고속 움직임 추정 알고리즘들이 가지고 있는 국부적 최소치 문제(Local minimum problem)를 해결하기 위하여, 제4장과 제5장의 전반부에서는 움직임 벡터의 공간적인 상관성을 이용하는 탐색 방법과 계층적 혹은 다 해상도 구조를 이용하는 탐색 방법을 결합하였다. 두 방법을 결합하는 수단으로는 계층적 혹은 다 해상도 탐색의 상위 수준에서 복수개의 움직임 벡터 후보를 이용하였다. 이때, 복수개의 후보 벡터들은 각각 계층적 혹은 다 해상도 탐색의 상위수준 탐색 결과와 주변 블록의 움직임 벡터들로부터 구성되었으며, 또한 움직임 벡터의 상관성을 효과적으로 이용하기 위하여 인접한 블록의 움직임 벡터로부터 후보 벡터를 선택할 때, 주위 움직임 벡터들의 상관관계를 적응적으로 이용하는 기법이 사용되었다. 제5장의 후반부에서는 움직임 벡터의 시간적인 상관성을 이용하여 실제 부호화기(MPEG2)응용 시에 제안된 방법의 계산량을 더욱 줄일 수 있는 방법을 제시하였다.
본 논문에서는 제안된 방법의 타당성을 검증하기 위하여 여러 가지 실험이 수행되었으며, 특히, 실제 부호화기에 응용될 때의 유용성을 검증하기 위하여 제안된 방법을 MPEG2 동영상 압축 표준에 적용하는 실험이 수행되었다. 제안된 방법은 부호화기에서 0.2 dB의 무시할 만한 성능의 저하를 보이지만, 움직임 추정의 계산량을 100배로 줄임으로써, 실제적으로 매우 유용함을 보여 주었다.
