According to the observation on the distribution of motion differentials among the motion vector of any block and those of its four neighboring blocks from six real video sequences, this paper presents a new predictive search area approach for fast block motion estimation. Employing our proposed simple predictive search area approach into the full search (FS) algorithm, our improved FS algorithm leads to 93.83% average execution-time improvement ratio, but only has a small estimation accuracy degradation. We also investigate the advantages of computation and estimation accuracy of our improved FS algorithm when compared to the edge-based search algorithm of Chan and Siu; experimental results reveal that our improved FS algorithm has 74.33% average execution-time improvement ratio and has a higher estimation accuracy. Finally, we further compare the performance among our improved FS algorithm, the three-step search algorithm, and the block-based gradient descent search algorithm.

An adaptive search order (ASO) algorithm is presented to speed up the block motion estimation in digital video coding. According to the motion trend, a table of the adaptive search order is defined. For each searching iteration, a better search order is derived and then the best matched block can be found in the early search stage. Some experimental results demonstrate the computational advantage of the proposed improved algorithm when compared to previous algorithms, such as the full search algorithm, the successive elimination algorithm, the block sum pyramid algorithm, and the multilevel successive elimination algorithm.