A novel kite-cross-diamond search algorithm for fast block matching motion estimation

In this paper, we propose a kite-cross-diamond search (KCDS) algorithm, which is an improved version of the well-known cross-diamond search (CDS) algorithm and small cross-diamond search (SCDS) algorithm. Unlike traditional search pattern in block matching algorithm, such as square, diamond or cross – all are in vertically and horizontally symmetric shape, the KCDS algorithm adopts a novel asymmetric kite-shaped search patterns in the search step to keep similar distortion while the speed of the motion estimation for stationary or quasi-stationary blocks is further boosted. Experimental results show that the KCDS algorithm could achieve 39 % searching point reduction as compared with CDS whereas similar and even better prediction accuracy is resulted in low-motion sequences. Simulations show that KCDS is the fastest algorithm and it performs more accurate in some kinds of sequences. This algorithm is especially suitable for videoconferencing applications. Index terms—Motion estimation, kite-cross-diamond search, cross-center biased characteristic. 1