Hierarchical stochastic fast search motion estimation algorithm

Many fast search motion estimation algorithms have been developed to reduce the computational cost required by full-search algorithms. Fast search motion estimation techniques often converge to a local minimum, providing a significant reduction in computational cost. The motion vector measurement process in fast search algorithms is subject to noise and matching errors. Therefore researchers have investigated the use of Kalman filtering in order to seek optimal estimates. In this work, the authors propose a new fast stochastic motion estimation technique that requires 5% of the total computations required by the full-search algorithm, and results in a quality that outperforms most of the well-known fast searching algorithms. The measured motion vectors are obtained using a simplified hierarchical search block-matching algorithm, and are used as the measurement part of the Kalman filter. As for the prediction part of the filter, it is assumed that the motion vector of a current block can be predicted from its four neighbouring blocks. Using the predicted and measured motion vectors, the best estimates for motion vectors are obtained. Using standard methods of accuracy measurements, results show that the performance of the proposed technique approaches that of the full-search algorithm.