Fast integer-pel and fractional-pel motion estimation for H.264/AVC

Abstract This paper gives out a fast motion estimation algorithm for H.264/AVC, which has almost the same quality performance as that of the Full Search scheme and also provides a strategy to balance the quality performance and the search speed. Integer-pel search is the most time consuming module for motion estimation. In this paper a hybrid Unsymmetrical-cross Multi-hexagon-grid Search (UMHexagonS) algorithm is introduced, which well solves the false motion vector estimation problem because of the local-minimum. As results, it saves more than 90% on search time whereas the averaging PSNR loss is less than 0.056 dB for all tested sequences with different motion extent compared with the Fast Full Search scheme. Fractional-pel fast search is not negligible when the integer motion estimation has been extensively speeded up. By utilizing the property of uni-modal error surface inside the fractional-pel search window, a novel Center Biased Fractional-pel Search (CBFPS) algorithm is proposed in this paper, which can save 30–50% computation compared with the Full Fractional-pel Search scheme. Early termination is another problem discussed in this paper, to construct a complete motion estimation method, giving a uniform method which can cover a wide range of applications, terminating the program at early and right stage is certainly required. A model based on the Normative SAD Difference (NSD) is given to assist the termination decision-making, and a tradeoff between the search speed and the reconstructed quality can be achieved by changing a modulation factor.