A novel kite-cross-diamond search algorithm for fast video coding and videoconferencing applications

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 patterns in block matching algorithms, such as square, diamond or cross, which are all in vertical and horizontal symmetric shapes, the KCDS algorithm adopts a novel asymmetric kite-shaped search pattern 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% search point reduction as compared with CDS, whereas there is similar and even better prediction accuracy in low-motion sequences. Simulations show that KCDS is the fastest algorithm and it performs more accurately in some kinds of sequences. This algorithm is especially suitable for videoconferencing applications.