A search patterns switching algorithm for block motion estimation

Abstract — Center-biased fast motion estimation algorithms, e.g., block-based gradient descent search and diamond search, can perform much better than coarse-to-fine search algorithms, such as 2-D logarithmic search and three-step search. The latter type of algorithms, however, is more suitable for handling large motion content. To combine the advantages of both types of algorithms, an adaptive algorithm performing search patterns switching (SPS) is proposed in this paper. The proposed SPS algorithm classifies the motion content of a block using a simple yet efficient motion content classifier called error descent rate. Unlike other classifiers with heavy overhead, this classifier requires only the searching of a few points in the search window and then a division operation. Experimental results show that the proposed SPS algorithm is very robust. Index Terms — Block matching, motion estimation, video coding