中文摘要：

在快速块匹配运动估计中,搜索模式对搜索速度和搜索质量有很大的影响。本文基于现实视频序列中运动向量的分布特征,提出了一种十字交叉六边形搜索算法（NHEXS）。首先用小十字模式进行预搜索,找到最小块匹配失真点（MBD）;以MBD为中心构造大十字搜索模式,找到MBD;然后以大十字模式的MBD为中心,开始六边形搜索。首先以搜索大六边形方式搜索,如果MBD在中心,则以小六边形方式搜索,找到的MBD点即为最终的块匹配失真点;否则继续大六边形搜索。十字交叉六边形搜索算法还采用了中途停止技术,对静止和半静止块的搜索速度有显著的提高。改进的部分块失真准则在不影响失真度的情况下降低了计算复杂度。实验结果表明,十字交叉六边形搜索算法比六边形搜索算法和新型十字菱形搜索算法在信噪比降低很少甚至不降低的情况下,分别节省32%和16%的搜索点,与其它流行的块匹配运动估计算法相比,本文算法有更快的搜索速度和更小的失真度。

英文摘要：

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 hy 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.