A non-uniform pattern-based partial distortion search algorithm for motion estimation

In this paper, an effective pattern-based normalized partial distortion search (NPDS) algorithm is proposed for fast motion estimation. The proposed algorithm is composed of the two parts: pattern-based NPDS scheme and dynamic search range determination scheme. In the conventional NDPS, the pixels in a marcoblock (MB) are uniformly selected for the calculation of the partial distortion while in the proposed scheme; the 16 fixed patterns that non-uniformly select the pixels from an MB such as diagonal line and anti-diagonal line are employed to calculate the partial distortion. Furthermore, the proposed dynamic search range determination scheme by the information of the neighboring coded MB is proposed to early terminate the calculation of the partial distortion. Experimental results show that the proposed algorithm achieves the better PSNR performance than that of NPDS algorithm with almost the same computations. By the dynamic search range determination, the proposed algorithm can significantly reduce computational complexity of the calculation of the partial distortion with slight PSNR degradation compared to the full search algorithm.