Prediction Error Prioritizing Strategy for Fast Normalized Partial Distortion Motion Estimation Algorithm

A prediction error prioritizing-based normalized partial distortion search algorithm for fast motion estimation is proposed in this letter. The distortion behavior of each pixel in a macroblock is first analyzed to point out the priority/order of sum of absolute difference calculation. Afterward, the normalized partial distortion search algorithm is applied for half-stop of the distortion calculation. In addition, a dynamic search range decision algorithm is adopted for automatically changing the size of the search range to further increase the motion estimation speed. The computational complexity can be reduced significantly through the proposed algorithm, though leaving a PSNR degradation that could be dismissed.

I. Introduction

The block-based motion estimation technique also known as the block matching algorithm (BMA) plays an important role in video coding applications [1], and has been widely adopted by many video coding standards such as H.261, H.263, H.264, MPEG-1, MPEG-2, and MPEG-4, mainly for temporal redundancy reduction. Motion estimation puts into testing several candidate motion vectors, which appears in a restricted area called the search window in the previous reference frame. The motion vector with minimum matching distortion is then encoded for the purpose of transmission or storage.