| Block-matching motion estimation is very important to many motion-compensated video-coding techniques/standards, such as ISO MPEG-1/2/4 and ITU-T H.26x, and is aimed at exploiting the strong temporal redundancy between successive frames. By partitioning a current frame into nonoverlapping rectangular blocks/macroblocks of equal size, a block-matching method attempts to find a block from a reference frame (past or future frame) that best matches a predefined block in the current frame. Matching is performed by minimizing a matching criterion, which in most cases is the mean absolute error/difference between this pair of blocks. The block in the reference moves inside a search window centered arounds the position of the block in the current frame. The best-matched block producing the minimum distortion is searched within the search window in the reference frame. The displacement of the current block with respect to the best-matched reference blocks in the x and y directions compose the motion vector assigned to this current block. However, the motion estimation is quite computationally intensive and can consume up to 80% of the computational power of the encoder if the full search (FS) is used by exhaustively evaluating all possible candidate blocks within the search window. Therefore, fast algorithms are highly desired to significantly speed up the process without sacrificing the distortion seriously. Many computationally efficient variants were developed, among which are typically the three-step search (TSS), new three-step search (NTSS), four-step search (4SS), block-based gradient descent search (BBGDS), and diamond search (DS) algorithms. In TSS, NTSS, 4SS, and BBGDS algorithms, square-shaped search patterns of different sizes are employed. On the other hand, the DS algorithm adopts a diamond-shaped search pattern, which has demonstrated faster processing with similar distortion in comparison with TSS, NTSS and 4SS. In block motion estimation, search patterns with different shapes or sizes and the center-biased characteristics of motion-vector distribution have a large impact on the searching speed and quality of performance. Therefore, some novel algorithms were proposed. In this thesis, two new fast search algorithms are proposed, based on extensive study of the contradiction of reduction of complexity and improvement of precision in the process of search of MPEG4 coding. The first algorithm is trend-diamond-search algorithm (TDS) based on the improvement of diamond search. TDS is designed for fast full-pixel motion estimation. The second algorithm is trend-halfpixel-search algorithm (or THS), which is designed for fast half-pixel motion estimation. These two algorithms have been successfully applied in dealing with videos of various complexity motions. Experiment data obtained by the proposed algorithms shows very close image quality, less search time and fewer search points compared with that obtained by conventional diamond and full search algorithm. This shows that these two new algorithms are correct and have great advantages in image coding engineering application.Another work carried out in this thesis is the design of video analyzation tool and improving function of VPROVE in supporting decode and analyse interlace bitstream of MPEG4, based on the study and analyse of the MPEG4 bitstream decoding and intrinsic flaws of VPROVE. This work promotes the value of video analyzation tool and its applications in engineering greatly. |
PDF Full Text Request