贺艳春，林其伟

（华侨大学 信息科学与工程学院，福建 厦门 361021）

运动估计中的块匹配算法因运算简单、容易实现而成为目前运动估计的主流。其中的全搜索算法（FS），因其穷尽搜索每个像素点，搜索精度最高，但计算太复杂，不能满足实时性要求；而三步法（TSS）、四步法（FSS）以及交叉搜索法（CSS）等，相对FS，减少了搜索点数，满足实时性要求，但不利于小的运动块的搜索；新三步法（NTSS）、 六边形法 （HEX）、 钻石法 （DS）、 新四步法（NFSS）等，虽然提高了运动估计的速度，解决了早期算法不利于小运动块搜索的问题，但易陷入局部最优点，且不能很好地处理图像的运动类型[1]。针对这些问题，CHEN Z B等[2]人提出了UMHexagonS算法，它是一种混合型搜索算法，综合了非对称十字形法、六边形法、菱形法等，相对 FS，其均峰值信噪比（PSNR）保持基本不变，而运动估计时间减少了近90%，是目前运动估计搜索效率最高的快速搜索算法，己被JVT正式采纳。

1 UMHexagonS算法简介

UMHexagonS算法的搜索路径如图 1[3]所示，它主要分4步进行搜索：

（1）初始搜索点预测。包括中值预测、上层预测、前帧预测以及邻近参考帧预测，得到最佳的初始搜索点。

（2）以步骤（1）得到的最佳初始搜索点为中心，进行非对称的十字形搜索，取绝对差值和（SAD值）最小的点为当前最佳匹配点。其中水平方向的搜索范围为窗口宽度，垂直方向的搜索范围为窗口宽度的一半，如图1的step2所示。

（3）以步骤（2）得到的最佳匹配点为搜索中心，进行5×5共25点的正方形螺旋搜索，如图 1的 step3-1所示。接着进行多层六边形格点搜索，取最小SAD值所对应的点为最佳匹配点，如图1的step3-2所示。……