Adaptive partial distortion search for block motion estimation

Block motion estimation using the exhaustive full search is computationally intensive. Fast search algorithms offered in the past tend to reduce the amount of computation by limiting the number of locations to be searched. All of these algorithms produce some quality degradation of the predicted image. To reduce the computational complexity of the full search algorithm without introducing any loss in the predicted image, we propose an adaptive partial distortion search algorithm (APDS) by selecting the most representative pixels with high activities, such as edges and texture which contribute most to the matching criterion. The APDS algorithm groups the representative pixels based on the pixel activities in the Hilbert scan. By using the grouped information and computing the accumulated partial distortion of the representative pixels before that of the other pixels, impossible candidates can be rejected sooner and the remaining computation involved in the matching criterion can be reduced remarkably. Simulation results show that the proposed APDS algorithm has a significant computational speed-up for all kinds of sequences and is the fastest when compared to the conventional partial distortion search algorithms.