基于H.264运动估 计算法的改进与优化

1.引言

H.264/AVC视频编码标准是由ITU-T和ISO/IEC MPEG在2003年共同制定的，与以往视频编码标准相比，H.264在相同编码质量的前提下，可节约50%以上的码率，但是其编码效率的提高是以增加编码的计算复杂度为代价的，运动估计作为视频编码的核心 技术，主要解决视频 图形中的时间冗余问题，通过运动估计技术可以使视频传输的比特数大大减少，在H.264中运动估计的计算复杂度占到了整个视频编码的60%-80%，因此对运动估计速度的优化是关键，可以有效地提高编码效率[1]。

运动估计算法性能最好的是全搜索算法（FS），但是其计算量太大，不适合于适时压缩，目前，H.264的标准采用UMHexagons，与全搜索算法相比，该算法在保持较好的率失真性能的同时，可以节约80%以上的运算量。UMH算法性能虽然比全搜索算法有很大提高，但是其运算量还是偏高，在很多方面需进一步优化，本文通过对UMH算法的搜索模板和搜索步长进行改进，提高了搜索速度。

2.UMHexagons算法

UMH算法的搜索过程有以下几步[2]：

(1)起始搜索点的预测：根据H.264采用多参考帧和7种分块模式，运用空间域的上层预测、中值预测、和时间域的对应快的预测、邻近参考帧来预测当前最优预测的起始点。

(2)非对称交叉十字型搜索：在搜索范围内垂直方向的搜索点数为水平方向的一般，图1为非对称水平十字型搜索。

(3)非均匀多层次六边形格点搜索：上一步产生的最优匹配点作为本次搜索的中心，进行包括5χ5区域的正方形搜索模板和16点的六边形搜索模板，如图2、3所示。

(4)在上一步产生的最优匹配点上进行扩展的六边形模版搜索：该过程包括多层次六边形搜索。

(5)小菱形模版反复搜索，得到最终的运动矢量。如图3。

3.UMHexagons算法的优化

3.1 十字型搜索模板的优化

上述的UMH算法在非对称交叉十字型搜索算法是只采用水平十字型搜索，没有采用垂直十字型搜索，统计表明，大多数视频序列在水平方向和垂直方向运动的几率较大，它们的运动矢量具有极强的水平和垂直偏移分布特性，因此将当前宏快的运动分为水平方向和垂直方向的运动，根据对当前宏块预测的运动方向类型在搜索过程中使用带方向的搜索策略，可以减少不必要的搜索，加快搜索速度。图1是水平十字搜索模板，当运动物体的运动估计具有水平运动特性时运用该模板，该模板在水平方向上的搜索速度快于垂直方向，可以加快水平方向的搜索速度，提高运动估计效率。同理图4是垂直十字型搜索模板，该算法在垂直运动特型的宏块中具有较高的运动估计效率。

为了在第二步搜索中能快速正确的选择水平搜索模板或垂直搜索模板，需要根据当前宏块的预测运动矢量获得当前宏块的运动方向，预测运动矢量V与水平直线的夹角为：

如果θ小于或等于π/4，则判定当前宏块的运动为水平方向，选用水平十字型搜索模板；如果θ大于π/4，我则判定当前宏块的运动方向为垂直方向，选用垂直十字型搜索模板。

3.2 5×5搜索模板的优化

UMH算法中，在进行非对称十字型搜索完成之后进行5×5正方形搜索模板的搜索是比较耗时的，统计实验表明[2]：运动矢量的概率分布是以(0，0)点位中心向四周递减的，其中80%的运动矢量在搜索中心5×5窗口内，约72%的运动矢量在搜索中心3×3窗口内；运动矢量分布在垂直方向和水平方向的概率为61%左右，而分布在相同半径的其他方向的概率为3%。

图1 非对称十字型搜索

图2 5χ5正方形搜索

图3 超六边形模版搜素、中六边形模版搜索、小菱形模版搜索

图4 垂直十字型搜索模板

图5 改进5×5模板

图6 改进后的超六边形搜索流程

由此可得，运动矢量的分布具有中心交叉偏置分布特性，依据运动矢量的中心交叉偏置特性，搜索模板的改进如图5所示，所有改进的模板都覆盖了搜索中心的3×3正方形区域；为了避免冗余搜索，小的块尺寸保持大的搜索半径，大的块尺寸减小搜索半径。如图5所示，改进后的模板比原模板最少可减少4个搜索点数，最多可减少16个搜索点，大大降低了运算复杂度，提高了搜索效率。

3.3 搜索步长的改进

在JM8.6的源代码中，UMH算法中(3)(4)都是使用的是多圈的六边形搜索，而在(5)小菱形搜索是以最佳点在模板中心为准则搜索的，在搜索到最佳点时，仍需要把其余的像素点搜索完，才结束搜索继续下一个模块，这3处都是非常消耗搜索点数的步骤，本文改进是基于提前结束搜索的思路。一般情况，视频图像序列都是以某一对象为单位的连续运动，那么对象内部每一块的像素点间的运动估计代价应该具有高度的相关性。实验表明，对象内部有非常相似的残差性，因此在对象内部各块的代价也具有相似性。

表1 测试序列的实验数据

在超六边形搜索算法中，另设一个整形变量last_mincost用来储存上一个像素点运动估计后的代价mcost，在下一个点的运动估计步骤第三步的超六边形搜索及第四步中若满足

则直接结束搜索，其中k是一个小于1的数，具体改进步骤如下：在改进第三步的超六边形搜索中，首先以search_range/4为半径进行预测点的搜索，然后使用(1)式的判决条件进行判决，若满足(1)式的条件，则结束搜索，若不满足则使用search_range/2进行预测点的搜索，再用(1)式判决，满足则结束搜索，不满足则用search_range，直至搜索结束，流程图如图6所示，在每次整个超六边形搜索算法接受前将当前块的最小记录下来，

对于第五步中的中六边形搜索也做了类似改进，经过测试也取得一定效果。

4.实验结果与分析

本文在JM8.6源代码上进行改进算法的验证，仿真以VC6.0作为开发平台，测试选用了3类比较有代表的标准CIF序列akiyo，foreman，mobile，其中akiyo代表运动变化相对平缓的视频序列，foreman代表空间细节中等序列，mobile是运动比较大，空间细节比较丰富的序列。所有测试序列Y、U、V4:2:0，CIF图像搜索范围search_range=16，实验对他们前50帧进行了编码，仅适用I帧和P帧，量化参数QP=28，评价标准主要选取了Y、U、V各分量的平均性噪比和运动估计时间MET，测试结果如表1所示。

从实验数据可知：改进后的算法对于Y、U、V分量影响不大，对不同的视频序列的运动估计时间的减少是不同的，视频序列akiyo是运动场景相对平缓的视频序列，在早期中止判断时就通过SAD指标跳过了一系列的搜索算法，所以许多可以通过搜索长度来降低运算量的算法根本就没有执行，这就导致运功估计改进的时间效果不太明显；而对场景运动一般的foreman和较剧烈的mobile序列，由于SAD的指标一直不符合提前终止条件，因此执行了大多数算法，改进后的算法在平均信噪比变化不大的情况下，运动估计时间显著减少，改进效果良好，从而提高了编码速度。

5.结论

本文通过对UMH算法进行详细分析，依据运动适量场的分布规律，从搜索模版和搜索步长两方面对UMH算法进行了改进和优化，实验结果表明：在保证视频序列的性噪比变化不大的情况下，运动估计搜索时间减少，尤其对运动剧烈的视频序列，有效地避免了冗余搜索，降低了搜索点数，效果良好。

[1]丁鑫,樊慧津.基于方向自适应的运动估计混合模板搜索算法[J].中国图形图像学报,2011,16(1):14-20.

[2]刘丽娟,王沛,应骏.JM模型中UMHexagons算法及改进方案[J].数字视频,2011,35(03):18-20.

[3]郑振东,王沛,应骏.H.264 JM模型中运动估计算法及改进方案[J].中国图象图形学报,2007,12(10):1978-1982

[4]刘云,孟岩,孙芳.JM模型中UMHexagons改进算法[J]系统仿真学报,2009,21(1):149-151.

[5]肖亮,梁亮理.基于H.264/AVC的快速运动估计改进算法[J].科学技术与工程,2009,9(15):4347-4350.

[6]毕厚杰.新一代视频压缩编码标准-H.264/AVC[M].北京:人民邮电出版社,2006.