A fast full-search motion-estimation algorithm using representative pixels and adaptive matching scan

Abstract

A full-search based block-matching algorithm for motion estimation has a major problem of significant computational load. To solve this problem, extensive research in fast-motion estimation algorithms have been carried out. However, most of them have some degradation in the predicted image from the reduced computation. To decrease the amount of significant computation of the full-search algorithm, we propose a fast block-matching algorithm based on an adaptive matching scan and representative pixels without any degradation of the predicted image. By using Taylor series expansion, we obtain the representative pixels and show that the block-matching errors from the reference block and candidate blocks are proportional to the block complexity. With the derived result, we propose a fast full-search algorithm with adaptive scan direction in block matching. Experimentally, our proposed algorithm is very efficient in terms of computational speedup, and is the fastest among all the conventional full-search algorithms. Therefore, our algorithm is useful in VLSI implementation of video encoders for real-time encoding.