In fast block-matching motion estimation

search patterns have a large impact on searching speed and searching quality. Based on the motion vectors distribution characteristics of real world video sequences

we propose a new cross-hexagon search algorithm (NHEXS): First

a pre-search is performed by using the small cross search pattern to find the Minimum Block Distortion (MBD) point; Second

the MBD point found in first step is used as the center to construct the big cross search pattern to find the new MBD point; Third

the MBD point found in second step is used as the center to construct the hexagon search pattern: big hexagon search is employed firstly

if the MBD point is at the center

then small hexagon search is performed and the found MBD point is the final motion vector; otherwise

the big hexagon search is continued. NHEXS employs halfway stop technique to achieve significant speedup on sequences with stationary and quasi-stationary blocks. NHEXS employs Modified Partial Distortion Criterion (MPDC) which results in less computational complexity with similar distortion. Experimental results indicate that the improvements of NHEXS over Hexagon Search (HEXS) and New Cross Diamond Search (NCDS) can save 32% and 16% of searching points while keep similar PSNR

and NHEXS provides faster searching speed and smaller distortion than other popular fast block-matching motion estimation algorithms.