Fast motion estimation scheme based on Successive Elimination Algorithm for applying to H.264
Chan Seok Lim, Kim Young-Moon, Jae-Eun Lee, Kang Hyun-Soo · Journal of the Institute of Electronics Engineers of Korea · 2005
In this paper, we propose a new fast motion estimation algorithm based on successive elimination algorithm (SEA) which can dramatically reduce heavy complexity of the variable block size motion estimation in H.264 encoder. The proposed method applies the conventional SEA in the hierarchical manner to the seven block modes. That is, the proposed algorithm can remove the unnecessary computation of SAD by means of the process that the previous minimum SAD is compared to a current SAD for each mode which is obtained by accumulating sum norms or SAD of blocks. As a result, we have tighter bound in the inequality between SAD and sum norm than in the ordinary SEA. If the basic size of the block is smaller than , the bound will become tighter but it also causes to increase computational complexity, specifically addition operations for sum norm. Compared with fast full search algorithm of JM of H.264, our algorithm saves 60 to of computation on average for several image sequences.