The motion estimation and compensation techniques are widely used in video coding applications because of their capability to reduce temporal redundancies residing in successive frames. As a motion estimator, the block-matching algorithm(BMA) is widely used because of its simplicity and regularity. But the required computations for the BMA are so large that it is not possible to perform the BMA in a timely fashion. Therefore, developments of VLSI architectures or new fast search algorithms are indispensable. In this thesis, we discuss the adjustment of search window for the BMA to reduce the computational complexity, as a method for fast search algorithms in low bit-rate video coding.
We propose a dynamic adjustment of the search window with fixed size of blocks(DASWF) for the BMA to reduce the computational complexity of full search algorithm(FSA). The method uses block similarities and displaced block differences to adaptively adjust the size of search window. The technique can be easily applied to the FSA and several fast search algorithms to get more efficiency. The experimental results have shown that the mean square error(MSE) performance and the reduction of the number of search points with the proposed scheme are better than those of previous works.
The dynamic adjustment of the search window with variable size of blocks(DASWV) is also presented to improve the accuracy of the motion estimation. As similar to the DASWF, this method uses the segmentation information of current frame to divide the frame into variable size of blocks. The size of search window for each block is determined by using the correlation of block similarities of adjacent blocks and their motion vectors. We also proposed a new method for search window adjustment using the spatio-temporal correlations, especially block classification information. The method exploits the correlation of successive video frames and adjusts the size of search area depending on the displaced block difference and the block classification information in the previous frames of the block. Finally, we present the experimental results of each proposed method, that is implemented on the very low bit-rate video coding standard H.263. The performances are compared in terms of peak-to-peak signal-to-noise ratio(PSNR), bit-rate, and the number of search points. The experimental results show that the proposed methods can be adapted to the very low bit-rate video coding applications without significantly degradation of video quality at cost of only a half complexity.
비디오 코딩 응용 분야에서 움직임 추정 및 보상 기법은 비디오 프레임 내에 존재하는 시간적인 중복성을 줄이는데 큰 역할을 하기 때문에 널리 이용되고 있다. 움직임 추정기법으로는 블록 기반 기법, 경사법을 이용하는 방법, 주파수 영역에서의 움직임 추정 기법이 있으며, 계산량, 데이터의 흐름, 연산의 규칙성 등으로 인하여 블록 기반 움직임 추정 기법인 정합 알고리즘이 많이 사용되고 있다. 그러나 블록 정합 알고리즘을 실시간으로 수행하는데 필요한 계산량이 매우 크기 때문에 하드웨어 구조나 새로운 빠른 탐색 알고리즘 개발이 필요하다. 본 논문은 낮은 비트율 비디오 코딩을 위한 빠른 탐색 기법으로서, 블록 정합 알고리즘의 계산량을 줄이기 위해 탐색 영역의 크기를 적응적으로 조정하는 방법을 다룬다.
본 논문에서는 전역 탐색 블록 정합 알고리즘의 계산량을 줄이기 위해서 고정 크기 블록을 사용하는 동적 탐색 영역 조정 기법(DASWF)을 제안한다. 제안하는 알고리즘은 블록 유사도와 변위된 블록 오차를 이용하여 새로운 탐색 원점을 설정하고, 탐색 영역의 크기를 조정한다. DASWF는 전역 탐색 기법 뿐만 아니라 빠른 탐색 알고리즘의 탐색 영역 조정에 적용될 수 있다. 실험을 통하여, 평균 제곱 오차와 블록당 평균 정합 블록 수 측면에서 제안된 기법이 기존의 탐색 영역 조정 기법과 비교하여 우수함을 보인다.
본 논문에서는 고정 크기 블록을 사용하는 탐색 조정 기법의 움직임 추정 정확도를 높이기 위하여 가변 크기 블록을 사용하는 동적 탐색 영역 조정 기법(DASWV)을 제안한다. DASWV는 프레임을 가변 크기 블록으로 나누기 위하여 세그멘테이션 정보를 사용하며, 각 가변 크기 블록들의 새로운 탐색 원점과 탐색 영역의 크기는 블록 유사도와 인접한 블록의 움직임 벡터의 크기를 이용하여 결정된다. 실험을 통하여, 기존의 기법들 및 고정 크기 블록을 사용하는 DASWF 보다 평균 제곱 오차 측면에서 우수함을 보인다.
본 논문에서는 낮은 비트율 비디오 시퀀스의 특성을 분석하여, 비디오 영상의 시.공간적인 상관성을 이용하여 탐색 영역의 크기를 조정하는 기법(AASWSTC)를 제안한다. AASWSTC는 시간적으로 연속한 비디오 프레임의 상관성을 이용하며, 변위 블록 오차에 따라서 블록을 구분하여 탐색 영역의 크기를 블록의 특성에 따라 조정한다. 각 블록은 배경 블록, 움직임이 많은 블록, 다른 특성을 지닌 영역으로 변하는 블록으로 구분되며, 각 블록의 종류에 따라서 서로 다른 크기의 탐색 영역이 설정된다.
마지막으로, 본 논문에서는 제안한 탐색 영역 조정 기법들을 낮은 비트율 비디오 코딩의 표준안인 H.263에 구현하여 실험한 결과를 제시한다. 제안된 기법들은 PSNR, 비트율, 그리고 블록 정합 수 측면에서 서로 비교된다. 실험을 통하여 탐색 영역을 적응적으로 조정하는 기법들이 낮은 비트율 비디오 코딩에서 큰 화질 손상없이 많은 계산량을 줄일 수 있음을 보인다.
