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

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.