동영상 부호화에서 효과적인 조기 종결 기술을 이용한 고속 움직임 추정 방법

Abstract

Video compression reduces the quantity of the digital video data exploiting the redundancies. Motion estimation has been widely used in order to reduce the temporal redundancy. The computational complexity of motion estimation is generally more than 50% in the whole encoding procedure when full search using sum of absolute difference or sum of squared difference. In order to overcome the computational complexity problem of motion estimation, many fast and efficient algorithms have been researched. However, it is still far from the optimal solution and the problem is open for further research. The researches that solve the problem stated above can be classified into three groups: lossless motion estimation algorithms, fast search algorithms, and motion estimation algorithms exploiting modified matching criteria. Lossless motion estimation algorithms give us the optimal results in terms of mean squared error while the computational complexity is less than full search using sum of absolute difference or sum of squared difference. However, their performance in motion estimation speed is far from the optimal solution. Fast search algorithms check a few probable candidate blocks or no candidate block in the search range differed from the way of full search algorithm. Since fast search algorithms just check a few candidate blocks in the search range, they can reduce the motion estimation complexity of the full search algorithm while the visual quality degradation is generated during fast search. A problem in fast search algorithms is their inconvenience in hardware realization. While most pixel domain motion estimation algorithms use the full bits representation of a pixel in the matching distortion calculation, there are some motion estimation algorithms which use the lower bits representation. Low bit representation algorithms can use the specific hardware architecture such as single instruction multiple data or parallel processing in the bit-level. The basic algorithm in this category that uses one-bit transform was proposed and many modifications have been researched so far. In this dissertation, a fast search algorithm using discrete cosine transform coefficients are proposed. It modifies the conventional adaptive matching scan algorithm with the relationship between discrete cosine transform coefficients and matching distortion of an image block. Furthermore, an early termination algorithm is applied and the proposed algorithm turns into fast search in order to reduce the computational complexity. Also, motion estimation using one-bit transform is merged with the Bayesian classifier and implemented in the latest video encoder, H.264/advanced video coding. In detail, a single feature is derived and a simple threshold is used to reduce the computational complexity of one-bit transform based motion estimation algorithm. It is further developed using the characteristic features from encoding and the Bayesian classifier, which is powerful and easy to implement. The proposed algorithms have been tested on several sequences and found to provide better computational complexity or better visual performance than the conventional motion estimation algorithms. The experimental results prove that the visual quality of the proposed algorithms is similar to the conventional motion estimation algorithms while the computational loads are dramatically reduced.