(A) new block matching algorithm for fast block motion estimation in video coding

Abstract

In block motion estimation, search patterns with different shapes or sizes and the cross-center-biased characteristics of motion-vector distribution have a large impact on the searching speed and quality of performance. The cross-diamond search (CDS) algorithm was designed to fit the cross-center-biased characteristics of motion-vector distribution in real-world video sequences. Two improved versions of the CDS were proposed recently: the kite-cross-diamond search (KCDS) algorithm and the cross-diamond-hexagonal search (CDHS) algorithm. Our proposed algorithm employs a new scheme to find small motion vectors with the smallest checking points and proposes two novel search patterns (modified large diamond-shaped patterns (1VILDSPs) and large kite-shaped patterns (LKSPs)) so as to reduce checking points efficiently for large motion vectors without falling into the local minima. The speed improvement of the proposed algorithm can be up to 61% faster than the diamond search (DS) algorithm, 44% faster than the CDS, 25% faster than the CDHS, and 13% faster than the KCDS while providing similar prediction accuracies. This algorithm is especially suitable for videoconferencing applications.