Typical motion estimation for block-based video coding schemes consists of two parts: the one at integer pixel accuracy and the other at half pixel accuracy. In this paper, integer pixel motion estimation algorithms are first discussed in terms of three technical categories: search step, search pattern and decision of the initial motion vector. With the development of the efficiency of integer pixel motion estimation, the computation load of widely used full half pixel search becomes relatively higher. In order to further improve the speed of half pixel search, this paper proposes a paraboloid prediction based fast half pixel search algorithm. Experimental results show that variable search step, search pattern with less points and predicted initial motion vector helps to improve the performance of fast integer pixel search and the proposed fast half pixel search increases the speed of half pixel search with almost not affecting the image quality.
"Comparative study of motion estimation for low-bit-rate video coding", Proc. SPIE 4067, Visual Communications and Image Processing 2000, (30 May 2000); doi: 10.1117/12.386543; https://doi.org/10.1117/12.386543