Fast and Optimal Block Motion Estimation via Adaptive Successive Elimination

In this paper we propose a fast and optimal solution for block motion estimation based on an adaptive successive elimination algorithm (SEA). We first apply an fast approximate method likes adaptive rood pattern search (ARPS) method to obtain a good initial motion vector as well as a tight initial bound of distortion measure to be used in SEA. Then, we apply the multi-level SEA with the elimination order determined by the sum of the gradient magnitudes of each sub-block. Experimental results of applying different motion estimation methods to video compression show that the proposed adaptive MSEA method can achieve the same PSNR with full search with the speed faster than the diamond search (DS).