摘 要：针对UMHexagonS算法计算复杂、耗时等问题提出改进算法。首先，通过在预测起始点处增加了准静止块阈值来判断是否可以立即停止搜索；然后，用扩展的菱形搜索代替原算法中的5×5的螺旋式全搜索以降低计算复杂度；最后，利用多层次8点八边形代替多六边形网格搜索。实验结果表明，改进算法在保证图像质量的前提下可以有效地减少10%~30%的运动估计时间，提高了总体的编码性能。
关键词：H.264；运动估计；UMHexagonS算法；中止判断
运动估计是视频压缩编码的关键部分，能有效地去除视频序列中时间域上的冗余度[1]。目前各种视频编码标准中广泛应用的运动估计算法是块匹配算法，匹配准则是块码率-失真度。最新的H.264标准采用的框架与先前的标准（如MPEG-2、H.263、MPEG4等）大致相同[2]，在这个框架下，运动估计和补偿是去除帧间冗余非常重要的方法，但同时也是编码中比较耗时的部分[3]。
目前，H.264已正式采纳了“非对称十字型多层次六边形格点搜索”（UMHexagonS）算法，它的运算量相对于快速全搜索算法可节约90%以上，同时能保持较好的性能。但是其也存在运算量大、耗时多等不足。因此，本文针对UMHexagonS算法的不足提出了改进算法，在预测起始点处增加了一个准静止块阈值判断，并用菱形搜索取代5×5的螺旋式全搜索以及对多六边形搜索模板进行了改进。在保证原算法图像质量的前提下，进一步降低运算量，从而提高整个H.264编码器的编码性能。
1 UMHexagonS算法
UMHexagonS算法的搜索路径如图1所示，基本步骤[4]如下。
（1）起始搜索点预测。在UMHexagonS算法中，采用了4种预测模式得到的矢量来估计当前块的初始运动矢量，分别为中值矢量预测、上层矢量预测、空间相关块矢量预测和参考帧对应块矢量预测。
（2）在步骤2中，算法进行一个水平搜索范围为S而垂直搜索范围为S／2的非对称十字搜索，其中，S为搜索窗的范围，搜索步长为2。取这些搜索位置中具有最小代价函数值（min_mcost）的点作为下一步的起始点。
（3）在步骤3-1中，进行一个5×5共25个点的螺旋式全搜索，并取具有min_mcost的点作为下一步的搜索中心。
（4）多层次大六边形格点搜索如步骤3-2所示。从中心开始在整个搜索窗中逐步进行非对称六边形搜索，直到搜索窗的边界，并取具有min_mcost的点作为下一步的搜索中心。
（5）小六边形模板反复搜索如步骤4-1和4-2所示。用一个扩展六边形和一个小菱形搜索模式循环进行六边形搜索，直到具有min_mcost的点位于六边形的中心，然后再进行一个小菱形搜索，这4个位置中具有min_mcost的点即作为当前块的运动矢量所指位置。
本文通过对不同标准序列的大量统计实验分析得出，T过大会对图像质量有明显的影响，而T过小则不利于搜索时间的提高，T=700时能够很好地区别出静止或准静止块，在不影响图像质量的情况下提高搜索速度。
2.2 5×5螺旋式全搜索的改进
在UMHexagonS算法的步骤3-1中，5×5螺旋式全搜索需要检查25个搜索点，这样不仅复杂度高、运算量大而且费时。因此，有必要对其进行优化。
通常来说，现实生活中的视频图像的运动矢量场通常是柔和平滑的，变化也比较平缓。参考文献[7]中统计研究发现，超过80%的运动矢量预测值位于中心5×5的网格区域内，但不是均匀分布，如图3所示。从图3可以看出，总的5×5网格区域内的菱形区域（也就是A+B+C+D区域）运动矢量分布概率为77.52%，相对5×5网格区域的运动矢量分布概率81.79%只减少了4.27%，而搜索点数减少了12个。因此，本文将用菱形搜索（如图4（a）所示）替换原来的5×5螺旋式全搜索（如图4（b）所示），能够在基本保证视频的质量的情况下减少搜索点数，提高搜索速度。
2.3 多六边形搜索的改进
本文提出的改进算法的搜索步骤如图5所示。本文利用多层次8点八边形搜索代替UMHexagonS算法中的非对称六边形搜索。将每层搜索的点数由原来的16个减少到8个，即能够减少约50%的计算量。同时经研究发现，虽然搜索点数减少了，但是新的搜索模板更接近于圆，从而保持了各方向的匀称，可以更有效地检测出最优运动矢量的位置，因此具有较好的搜索效率，同时也保持了良好的图像质量。
改进后的算法主流程图如图6所示。
3 实验结果与分析
本文在H.264的参考软件JM10.1上实现了原算法和改进后的UMHexagonS算法，选取3个具有代表性的标准QCIF测试序列和3个CIF序列的前100帧进行测试，编码模式为IPPP。测试序列如表1所示，实验参数设置如表2所示，其他参数设置为默认值。实验平台为：Windows7系统，Intel Core i3，2.2 GHz CPU，4 GB内存，VS2010。实验结果如表3~表5所示。
从表3可以看出，改进算法比原算法的运动估计时间减少了10%~30%，且随着运动程度由平缓到剧烈，算法节省的时间也随之增加。表4显示了图像的峰值信噪比，除了akiyo序列下降了0.01外，其他都不降反升，说明改进算法很好地保持了图像的质量。从表5显示的码率变化来看，码率平均增加了0.5%左右，最大的也不超过1%，对信道传输影响不大。
其中，对于变化区域小且缓慢的akiyo序列，改进算法速度提高相对较少，只有9.511%，而对于变化区域大且运动相对较剧烈的bus和football序列而言，速度提高较大，在30%左右。因此，本文提出的改进算法适合各种运动类型的视频序列，尤其对于运动剧烈的图像序列效果更好。
图7和图8分别显示了3个QCIF序列和3个CIF序列原算法和改进算法峰值信噪比的变化情况，原算法与改进算法在每帧的峰值信噪比变化很小，未出现大的波动，即改进算法没有影响运动估计的准确性。通过两幅图的对比可以看出，CIF图像比QCIF图像的峰值信噪比变化更加平稳，即对于CIF图像，改进算法的效果更好。
为了提高视频的总体编码性能，本文针对UMHexagonS算法的不足提出了3个方面的改进：（1）增加了准静止块的判断；（2）扩展的菱形搜索模型；（3）多层次的8点八边形格点搜索。实验结果表明，改进算法在PSNR和码率与原算法相近的情况下，减少了原算法中不必要的搜索点，运动估计时间减少了10%~30%，提高了编码性能。
参考文献
[1] 毕厚杰.新一代视频压缩编码标准H.264/AVC[M].北京：人民邮电出版社，2009.
[2] WIEGAND T， SULLIVAN G J， LUTHRA A， et al. Overview of the H.264 / AVC video coding standard [J]. IEEE Transactions on CSVT， 2003，13（7）：560-576.
[3] ISO/IEC JTC1 /SC29 /WG11 and ITU-T SG16 /Q. 6 Draft ITU-T， Recomm endation H. 264 and Final Draft International Standard[S].
[4] Chen Zhibo， Zhou Peng， He Yun. Fast motion estimation for JVT[C]. JVT- G016， 2003-03.
[5] DUANMU C J， Chen Xing. Mixed diamond， hexagon， and cross search fast motion estimation algorithm for H.264[C]. Proceedings of 2008 IEEE International Conference on Multimedia and Expo， 2008：761-764.
[6] Ding X， Fan H J. A mix-pattern motion estimation search algorithm based on direction adaptation[J]． Journal of Image and Graphics，2011，16（1）：14-20．
[7] LAM C H， PO L M， CHEUNG C H. A novel kite-cross-diamond search algorithm for fast block motion estimation[C]. Proceedings of 2004 IEEE International Symposium on Circuits and Systems， 2004：729-732.