A fast hierarchical 1/4-pel fractional pixel motion estimation algorithm of H.264/AVC video coding

Motion estimation plays an important role in motion compensated video coding. Motion estimation is generally conducted in two steps: first integer pixel motion vector search and then followed with fractional pixel refinement. 1/4-pel fractional pixel search is adopted in H.264/AVC to further reduce residual coefficients. A fast hierarchical 1/4-pel fractional pixel motion estimation algorithm based on H.264/AVC is proposed in this paper. With the analysis of distribution characteristics of motion compensation error surface inside fractional pixel searching window, quadratic polynomial curve is used to fit the distribution of the sum of absolute transformed difference, along horizontal and vertical direction respectively. The proposed searching strategy needs to check only 5 points rather than 16 points, which are used in the Hierarchical Fractional Pel Search algorithm (HFPS) for 1/4 pel motion estimation. The experimental results show that a computation reduction about 64.5% can be achieved with adopting the proposed algorithm compared with HFPS algorithm and it shows an almost negligible effect on the image quality and bit-rate. Compared with other fast algorithm, the proposed algorithm also provides higher prediction quality and higher speed.