Cross-hexagon search algorithm for fast block-matching motion estimation
Xiaodong Shen · Optics and Precision Engineering · 2009
In a fast block-matching motion estimation, search patterns have a large impact on searching speed and searching quality. Based on the motion vector distribution characteristics of real video sequences, a new cross-hexagon search algorithm (NHEXS) is proposed. Firstly, a pre-search is performed by using the small cross search pattern to find the Minimum Block Distortion (MBD) point. Then, the MBD point found in the first step is used as the center to construct the big cross search pattern to find the new MBD point. Finally, the MBD point found in the second step is used as the center to construct a hexagon search pattern.In the hexagon search, the big hexagon is searched firstly. If the MBD point is at the center,the small hexagon is searched and the MBD point to be found is the final motion vector. Otherwise, the big hexagon is searched continually.The NHEXS employs a halfway stop technique to significantlly improve the search speed for stationary and quasi-stationary blocks,and the Modified Partial Distortion Criterion (MPDC) in the NHEXS reduces the computational complexity in the similar distortion. Experimental results indicate that by the same PSNR,the NHEXS has reduced the search points by 32% and 16%,respectively,as compared with the Hexagon Search (HEXS) and New Cross Diamond Search (NCDS).Moreover,the NHEXS shows a faster searching speed and smaller distortion than other popular fast block-matching motion estimation algorithms.