Fast Full Search Algorithm For Motion Estimation

Abstract

Video compression is vital for efficient storage and transmission of digital signal. The hybrid video coding techniques based on predictive and transform coding are adopted by many video coding standards such as ISO MPEG-1/2 and ITU-T H.261/263. Motion estimation and motion compensation is an predictive technique for exploiting the temporal redundancy between successive frames of video sequence. Block matching techniques are widely used motion estimation method to obtain the motion compensated prediction. By splitting each frame into macroblocks, motion vector of each macroblock is obtained by using block matching algorithm (or motion estimation algorithm). In order to get motion vector of each macroblock, the most obvious and simplistic method is full search algorithm. All possible displacements in the search window are evaluated using block-matching criteria (cost function). The advantage of full search is that we can find the absolute optimal solution. However, its high computational complexity makes it impossible for real-time implementation. Because the computational complexity of video compression, the compression efficiency and the compression quality is determined by the motion estimation algorithm, development of Fast Motion Estimation Algorithm for real-time application becomes compelling. The computational complexity of a motion estimation technique can then be determined by three factors: 1. search algorithm. 2. cost function/evaluate function. 3. search range parameter p. Actually, we can reduce the complexity of the motion estimation algorithms by reducing the complexity of the applied search algorithm and/or the complexity of the selected cost function. An full search algorithm evaluates all the weights in the search window, and a more efficient, less complex search algorithm will decrease the search space. We will identify and evaluate the recent and widely used fast estimation algov rithms, especially in hybrid estimation algorithms: how they get the trade-off between video quality and compression efficiency? Based on this, we will propose our new motion estimation algorithm produced our new video encoder. To test its validation and its efficiency, we used the standard tested video sequences, which include three kinds of sequences: one is little motion sequences, second is moderate motion sequences, and third is the fast motion sequences.