A novel cross-hexagon search algorithm for fast block motion estimation

Search patterns and the center-biased characteristics of motion vector distribution have large impact on both searching speed and quality of block motion estimation. In this paper, we propose a new cross-hexagon search algorithm (NCHEXS) using two cross-shaped search patterns as the first two initial steps and large/small hexagon-shaped patterns as the subsequent steps for fast block motion estimation (BME). NCHEXS employs halfway stop technique to achieve significant speedup on sequences with stationary and quasi-stationary blocks. To further reduce computational complexity, NCHEXS employs Modified Partial Distortion Criterion (MPDC). Experimental results indicate that the improvements of NCHEXS over Hexagon Search (HEXS) and Cross-Diamond Search (CDS) can save 45% and 28% of search points while keeping similar PSNR, and NCHEXS provides faster searching speed and smaller distortion than other popular fast block-matching motion estimation algorithms.