Abstract
In this thesis, 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. Adopt the accumulated distortion method to make the calculation of boundary values at adjacent levels more efficient. Experiments are shown the proposed AdaMSEA algorithm significantly outperforms other previous global motion estimation algorithms, including SEA, MSEA and FGSE, on a wide variety of video sequences. Furthermore, we also demonstrate the superior performance of the proposed AdaMSEA algorithm for multiple-reference-frame motion estimation. For some special application, we can easily modify the proposed AdaMSEA to an approximate motion estimation algorithm to achieve higher PSNR than DS with the same operation counts.