Fast Optimal Motion Estimation Based on Gradient-Based Adaptive Multilevel Successive Elimination

In this paper, we propose a fast and optimal solution for block motion estimation based on an adaptive multilevel successive elimination algorithm. This algorithm is accomplished by applying a modified multilevel successive elimination algorithm (SEA) with the elimination order determined by the sum of the gradient magnitudes of each subblock and the elimination process terminated by comparing the above sum with a threshold. In addition a fast approximate motion estimation method and the accumulated distortion scheme are employed to make the proposed algorithm even more efficiently. Experimental results show that the proposed adaptive multilevel successive elimination strategy (AdaMSEA) algorithm significantly outperforms other previous optimal motion estimation algorithms, including SEA, MSEA, and FGSE on a wide variety of video sequences. Finally, we modify the proposed AdaMSEA to an approximate motion estimation algorithm to achieve very fast computational speed, and the experimental results show superior performance of this approximate algorithm over some fast motion estimation algorithms.