Fast Block-Matching Motion Estimation Based on a Dual-Cross Search Algorithm

In block motion estimation, search patterns with different shapes and/or sizes have a large impact on the searching speed and quality of performance. By statistical analysis of motion vector probabilities distribution, directional characteristic is found besides cross center-biased characteristic. A novel dual-cross search algorithm (DCS) is proposed. The proposed algorithm first employs the small cross search pattern (SCSP) and large cross search pattern (LCSP) to find small motion vectors with fewer search points based on cross-center-biased property. In addition, the algorithm uses no-full-symmetrical cross search pattern (NFSCSP) in the subsequent steps based on direction characteristic of motion vector probabilities distribution for large motion vectors. The improvement of DCS over DS and CDS can be a 70% and 40% gain on speedup, respectively, while maintaining comparable search quality. Experimental results show that the DCS is much more effective and robust.