A novel rood-diamond search algorithm for fast block motion estimation

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

6 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Journal / PublicationICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Publication statusPublished - 2002


Title2002 IEEE International Conference on Acoustic, Speech and Signal Processing
PlaceUnited States
CityOrlando, FL
Period13 - 17 May 2002


Search patterns and the center-biased characteristics of motion vector distribution (MVD) have large impact on both searching speed and quality of block motion estimation. In this paper, we propose a novel algorithm using a rood-shaped search pattern as the initial step and large/small diamond search patterns as the subsequent steps for fast block motion estimation (BME). The rood-shaped pattern is to fit the rood-center-biased MVD characteristics of the real-world sequences by evaluating the 9 relatively higher probable candidates located as a rood-shaped pattern at the search-grid center. The proposed rood-diamond search algorithm (RDS) employs halfway-stop technique and could find small motion vectors with fewer points than the diamond search algorithm (DS) while maintains similar or even better quality. The speedup improvement of RDS over DS can be up to 40%. Simulations show that RDS is much more robust, provides faster searching speed and smaller distortions than other fast algorithms.