Motion estimation using two-stage predictive search algorithms based on joint spatio-temporal correlation information

Motion estimation is one of the major problems in developing a real-time software-based video codec since it has high search complexity. In the motion estimation process, the motion field of the current block can generally be tracked from the motion fields of the neighboring blocks in the spatial and temporal directions. In this paper, two efficient fast motion estimation algorithms with a two-stage predictive search based on joint spatio-temporal correlations are proposed to reduce the search complexity. In the first stage, a rough search from the given motion vectors associated with six spatially and temporally correlated blocks attempts to find a starting point of the adequate search range that is closer to the global optimum. In the second stage, block-based gradient descent search (Liu & Feig, 1996) and predictive partial search (proposed) algorithms are used for fine search to elaborately search the adequate range from the starting point for the best motion vector. Simulation results demonstrate that our algorithms effectively reduce the average number of checked points to only 1.55% and 0.78% as compared to the full search method and yield a great performance improvement in terms of computational complexity, PSNR and bit rates as compared to full search and some well-known fast search methods. (C) 2011 Elsevier Ltd. All rights reserved.