H.264标准是由视频联合工作组JVT(Joint Video Team)组织提出的新一代数字视频编码标准,与其他标准相比，H.264具有更高的编码效率[1],能够节省大约50%的码率。但是对H.264性能的改进是以增加复杂性为代价的，其编码的计算复杂度大约相当于H.263的3倍。运动估计是视频压缩编码的关键部分,能有效地去除序列图像的帧间冗余[2],在H.264的编码过程中，由于H.264编码器采用了高精度运动矢量，计算量迅速增长，运动估计消耗了整个编码时间的80%左右,是复杂度和运算量最高的部分[3]。如何有效地减少运动估计的消耗,对提高编码的效率和实时性编码具有重大的意义。
1UMHexagonS算法分析
非对称十字型多层次六边形格点搜索算法(UMHexagonS算法)由Chen Zhibo等人[4]提出，由于该算法的运算量相对于快速全搜索算法可节约90%以上，同时能保持较好的率失真性能，因此，UMHexagonS算法已经被H.264的参考软件JM正式采纳,成为H.264标准专利库中的一部分。
UMHexagonS算法的基本步骤[5]如下：

(1)起始搜索点预测。使用多帧参考、中值预测、上层预测、相应块预测和邻近参考帧预测五种方法来进行预测。在起始搜索矢量的集合中,以拥有最小代价预测的运动矢量作为起始搜索点,然后用EARLY_TERMINATION判断是否提前截止，如果绝对误差和SAD较大则跳到步骤5,SAD很小则跳到步骤6。
(2)非对称十字搜索，如图1中步骤2。EARLY_TERMINATION判断是否提前截止,SAD较大则跳到步骤5，SAD很小则跳到步骤6。
(3)螺旋搜索5×5区域如图1中步骤3-1。以目前最佳点为中心,搜索(-2, 2)方形区域内的25个点。
(4)多层次大六边形格点搜索如图1中步骤3-2。在1/4 search_range的范围内,用不断扩大一倍直径的大六边形模板进行搜索。

(5)小六边形模板反复搜索如图1中步骤4-1。以小六边形为模板，在search_range范围内搜索，直到最优点出现在模板中心才停止搜索。
(6)菱形模板反复搜索如图1中步骤4-2。以菱形为模板，在search_range范围内搜索，直到最优点出现在模板中心才停止搜索，得到最终的运动矢量。
2 UMHexagonS算法的改进
2.1 对称十字搜索模板
在UMHexagonS算法的步骤3中使用的是螺旋搜索5×5区域。螺旋搜索是一种全搜索的搜索策略,需要计算整个搜索范围内所有点的SAD值,也就是要搜索25点。这样不仅复杂度高、运算量大而且费时。
自然的视频序列的运动矢量场通常是柔和平滑的，变化也比较缓慢。参考文献[6]中对典型的平缓和运动复杂的自然视频序列的运动矢量的统计研究发现，超过80%的运动矢量预测值位于中心5×5的网格区域内，但不是均匀分布。从图2中可以看出,总的5×5网格区域内的运动矢量是81.79%，而以原点为中心的半径为2的对称十字型区域（也就是A+B+C区域）运动矢量为74.74%。对称十字模板和螺旋搜索模板如图3所示。从5×5网格区域到半径为2的对称十字型区域，虽然运动矢量减少了7.05%，但是搜索点数减少达到64%，如图3(b)所示搜索点数从25点减少到9点。所以本文用对称十字型模板的9点搜索来取代螺旋搜索5×5区域的25点搜索。

2.2自适应搜索长度
搜索长度search_range在UMHexagonS算法中用来控制搜索候选搜索点的范围。主要体现在以下几个步骤：步骤(4)(多层次大六边形格点搜索)中，以1/4 search_range做为搜索长度。步骤(5)(小六边形模板反复搜索)中，以search_range作为搜索长度；步骤(6)(菱形模板反复搜索)中，以search_range作为搜索长度。可见，在UMHexagonS算法中搜索长度是固定不变的，合理地设定搜索长度能有效地减少UMHexagonS算法的复杂度。
场景中一般都是以某一对象为单位的运动，因此该对象内部的代价（mcost）应该具有很高的相关性[7]。据此，本文利用前两个搜索步骤的min_mcost之比，提出自适应搜索长度的方法。
设利用变量pre_min_mcost1、pre_min_mcost2、pre_min_mcost3、 pre_min_mcost4来分别保存步骤(2)、(3)、(4)、(5)的min_mcost，其定义公式如下：
ki=pre_min_mcosti/pre_min_mcost(i+1) (1)
search_range=search_range/ki (2)
式(1)中，ki表示前两个搜索步骤的min_mcost之比，式(2)中search_range是搜索长度。根据ki来相应地缩短改进后的搜索长度，本文的改进方法分别用在步骤(4)、(5)、(6)。
3实验结果与分析
3.1 实验环境
本文在H.264的参考软件JM10.1上实现改进后的UMHexagonS算法，选取3个具有代表性的标准QCIF测试序列进行测试。
　 实验平台：Windows XP SP3系统，Intel Core 2 Duo CPU（T6400）2.00 GHz,内存2 GB。
　　实验测试序列：akyio_qcif.yuv、foreman_qcif.yuv、mobile_qcif.yuv,其场景运动快慢鲜明，运动剧烈程度由左到右依次加强。
　　实验参数设置：FramesToBeEncoded=20,FrameRate=30.0,SearchRange=16,NumberReferenceFrames=5,其他参数设置为默认值。
3.2 实验数据与分析
　　本文主要采用Y、U、V各分量的峰值信噪比( PSNR)、运动估计时间(MET)和比特率作为算法性能评判的标准。Y、U、V 各分量的PSNR表明压缩后图像的质量，“+”为改善；MET表明运动搜索的时间，“-”为改善；比特率表明压缩率，“-”为改善。改进率=（改进后算法-原算法）/原算法×100%。实验结果比较如表1所示。
从表1中可以看出，改进后算法对Y、U、V各分量的峰值信噪比和比特率影响不大，但运动估计时间减少很显著(从7.4%~20.5%)，平均减少了15%。实验中,改进算法对于不同视频序列的运动估计时间的减少幅度不同，主要由视频场景运动的激烈程度不同所造成。视频序列akiyo运动场景相对平缓，起始点预测的精度较高，在早期判断EARLY_TERMINATION时,因为SAD很小，直接跳到步骤(6),也就是说,没有执行对称十字模板步骤(3)和通过自适应搜索长度来降低运算量的步骤(4)和步骤(5)所以运动估计时间减少的效果不是很明显。而对于场景运动一般和场景运动激烈的foreman和mobile序列,由于SAD指标不符合早期判断EARLY_TERMINATION条件, 执行了对称十字模板步骤(3)和自适应搜索长度搜索步骤(4)、(5)、(6)，因此运动估计时间减少显著。

本文在结合JM10.1模型的基础上分析了H.264中运动估计算法(UMHexagonS算法),针对该算法的不足之处提出了两处改进。首先，利用对称十字模板9点搜索替换原来的5×5螺旋搜索，减少了64%的搜索点数；其次，利用对象内部代价的相关性提出自适应搜索长度方法。在保证视频序列各分量的信噪比和比特率的情况下，使运动估计时间平均降低了15%,增强了编码的实时性，有利于视频图像实时编码传输的实现。
参考文献
[1] Yang Enhui, Xu Xiang. Rate distortion optimization for H.264 interframe coding: a general framework and algorithms[J]. IEEE Transactions on Image Processing,2007,16(7):1774-1784.
[2] 毕厚杰.新一代视频压缩编码标准-H.264/AVC[M].北京：人民邮电出版社，2005:33-45.
[3] WIEGAND T, SULLIVAN G J.Overview of the H. 264/AVC video coding standard[J].IEEE Transactions on Ciruits and Systems for Video Technology,2003,13(7):560-576.
[4] CHEN Z, ZHOU P, HE Y. Fast motion estimation for JVT [S]. JVT-G016,7th Meeting[C]. Thailand, Pattaya II: JVT of ISO/IEC MPEG & ITU-T VCEG, 7-14 March, 2003.
[5] CHEN Z, ZHOU P, HE Y. Fast integer pixel and fractional pixel motion estimation for JVT[S].JVT-F017,2002,6th Meeting[C].Awajilsland,Japan:JVT of ISO/IEC MPEG & ITU-T VCEG,2002,5-13.
[6] 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. Canada:IEEE, 2004:729-732.
[7] 郑振东,王沛,应骏. H.264 JM模型中运动估计算法及其改进方案[J].中国图像图形学报，2007,10(12):1798-1780.