비디오 압축에서 PDE기반 고속 움직임 추정기법에 관한 연구

Abstract

Video compression is an essential tool for video data storage and visual communication. The basic principle of video compression is to remove data redundancies, including spatial, temporal, statistical, and spectral redundancies. Motion estimation is an indispensable technique to reduce the temporal redundancy. In the motion estimation techniques for video sequence compression, the block matching method is the most popular in current international video coding standards such H.261, H.263 and MPEG-1/2/4 due to its simplicity and good error performance. Full search(FS) in the block-matching algorithm(BMA) based on the translational motion model finds the location with the minimum value of matching errors of all candidate displacements within a given search range. It has been popularly used in video coding applications because of its simplicity and easy hardware implementation. However, its heavy computational load for a large search range can be a serious problem in real-time video coding applications. Many fast motion estimation algorithms to reduce the computation of the full search have been studied in the last decade. We can classify these fast motion estimation methods into two main groups: The former is lossy motion estimation group has degradation of predicted images compared with the conventional FS, and the latter is lossless motion estimation group has no any degradation of predicted images compared with the conventional FS algorithm. A big problem of the lossy fast motion estimation algorithms can be falling into a local minimum, which is not optimal motion vector. The remaining limitation of the lossless fast motion estimation algorithms is low computational reduction ratio compared with the lossy ones. In this thesis, we propose fast motion estimation algorithms based on partial distortion elimination(PDE) to improve computational reduction ratio and speedup computational time of conventional PDE algorithm. Our algorithms are composed of three parts. The first algorithm identifies computational matching order from initial calculation of matching differences. According to the computational order identified, matching errors are calculated based on partial distortion elimination method. The proposed algorithm takes about 8∼20% of computations for block matching error compared with conventional FS algorithm. The second algorithm is based on selective matching scan and elimination of unlike candidate blocks from initial matching error. According to the obtained matching order, we proceed to calculate matching errors and remove unlike candidate vectors based on PDE method. Our algorithm takes about 4∼10% of computations for block matching error compared with conventional FS algorithm. The third algorithm is based on the prediction of threshold of sub-blocks regarding with the information of 3 neighbors block adaptively. We proposed a new block matching algorithm by sorting square sub-block and applying refining adaptive threshold for each block while keeping the same prediction quality compared with the original FS algorithm. Our algorithm takes about 2∼5% of computations for block matching error compared with conventional FS algorithm. If we cascade the successive elimination algorithm(SEA), multi-level successive elimination algorithm(MSEA) or hexagonal based search(HEXBS) algorithms to our proposed algorithm, we can further remove only unnecessary computation. Thus our algorithm will be useful to real-time video coding applications using MPEG-4 AVC or MPEG-2 video coding standards.