An adaptive and fast fractional pixel search algorithm in H.264

Fractional pixel motion estimation is applied in H.264 to achieve more accurate motion vectors and higher compression efficiency. It, however, distinctly increased complexity in the procedure of motion estimation. In this paper, we propose an adaptive and fast fractional pixel search algorithm (AFFPS) to reduce the computation load of motion estimation in H.264. Since the sum of absolute difference (SAD) surface is unimodal within the range of ±1 pixel, it can be approximated by line functions in a small area around the optimum motion vector. A novel bypass strategy for fractional pixel search based on these line functions is first proposed to skip unnecessary fractional pixel search. Then, an all-zero block (AZB) detection-based strategy is proposed to terminate ineffective fractional pixel search early. The proposed fractional search algorithm is presented, which adopts the two strategies and greatly improves the center-biased fractional pixel search (CBFPS) method. Simulation results show that the proposed algorithm can reduce more than 71% of the fractional pixel search points and still maintain similar coding efficiency.