Adaptive matching scan algorithm based on gradient magnitude for fast fullsearch in motion estimation

Block-based full search algorithm of motion estimation has a major drawback of significant computational load in video coding. Due to the problem, ext ensive research in fast motion estimation algorithms has been carried out. To reduce an amount of significant computation of the full search algorithm , we propose a fast block-matching algorithm based on gradient magnitude of reference block without any degradation of predicted image. By using Taylo r series expansion, we show that the block matching errors between referenc e block and candidate block are proportional to the gradient magnitude of m atching block. With the derived result, we propose fast full search algorit hm with adaptively determined scan direction in the block matching. Experim entally, our proposed algorithm is very efficient in terms of computational speedup and is fastest among all the conventional full search algorithms. Therefore, our algorithm is useful in VLSI implementation of video encoder with large search range.