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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)22_Publication in policy or professional journal

56 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Journal / PublicationProceedings - IEEE International Symposium on Circuits and Systems
Publication statusPublished - 2004


Title2004 IEEE International Symposium on Cirquits and Systems - Proceedings
CityVancouver, BC
Period23 - 26 May 2004


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.

Research Area(s)

  • Cross-center biased characteristic, Kite-cross-diamond search, Motion estimation