An adaptive partial distortion search for block motion estimation

Fast search algorithms for block motion estimation reduce the set of possible displacements for locating the motion vector. All 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 a Hilbert-grouped partial distortion search algorithm (HGPDS) by grouping the representative pixels based on pixel activities in the hilbert scan. By using the grouped information and computing the accumulated partial distortion of the representative pixels before that of other pixels, impossible candidates can be rejected sooner and the remaining computation involved in the matching criterion can be reduced remarkably. In addition, we also suggest a smart search strategy which is an excellent complement of the HGPDS to form an efficient partial distortion search algorithm. The new search strategy rearranges the search order such that the most possible candidates are searched first and this rearrangement will increase the probability of early rejection of impossible motion vectors. Simulation results show that the proposed algorithm has a significant computational speed-up and is the fastest when compared to the conventional partial distortion search algorithms.