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

In order to fit the small cross-center-biased characteristic of the real world video sequences, an improved version of the well-known cross-diamond search algorithm (CDS) is proposed in this paper. Unlike traditional search pattern, such as square, diamond or cross - all are in vertically and horizontally symmetric shape, the kite-cross-diamond search (KCDS) algorithm adopts a novel asymmetric kite-shaped search patterns in the search step to keep similar distortion or even better in low-motion sequence while the speed of the motion estimation for stationary or quasi-stationary blocks is further boosted. Experimental results show that this KCDS algorithm could achieve 58% searching points reduction as compared with Diamond Search (DS) and 41% as compared with Cross Diamond Search (CDS) whereas similar prediction accuracy is preserved. Simulations show that KCDS is particularly faster and more accurate in some kinds of sequences. This algorithm is especially suitable for videoconferencing applications.