基于H.264的UMHexagonS算法研究

张 凡， 唐作其， 张正平

(贵州大学 计算机科学与信息学院，贵州 贵阳 550025)

0 引言

H.264使用更加高效和精确的运动估计技术,但是其相当高的运算复杂度使其难以实现实时编码的要求[1]。

运动估计是视频编解码的一个关键技术，其所耗费的代价占据了整个编码过程中相当大的比重。诸多新的快速算法被提出来，有新三步法、四步法[2]、六边形搜索[3]、钻石搜索[4]。但是这些算法容易掉入局部最优，故而也需要进一步的改进，在这些算法的基础上,很多学者进行了进一步的优化[5-6]。

H.264官方测试软件JM采用了“非对称十字型多层次六边形格点搜索”(UMHexagonS)算法。相比于全搜索（FS，Full Search）算法，该算法在保持较好的率失真性能的同时，可以节约90%以上的运算量，展现了良好的编码效果，但是在进行搜索匹配的过程中仍然会偶尔落入局部最优。改进后的优化算法使用了动态搜索窗口，多层次六边形提前终止策略，在码率和图象质量几乎没有改变的同时，一定程度上节省了运动估计时间，使编码器的实时性得到了提高。

1 UMHexagonS算法介绍

如图1所示，UMHexagonS算法步骤如下：①起始点预测；②非对称十字的区域搜索；③5 5×的正方形全搜索；④多层次六边形搜索；⑤小六边形搜索；⑥小区域十字搜索。

并且，该算法在某些搜索步骤根据一定的判断条件来调整搜索流程甚至提前终止算法。其搜索窗口的大小通过配置文件由参数search_range设置：

H.264标准中有7种分块方法，最大块为16 16×，最小块为44×。7种不同大小的块都在固定大小的参考窗口中搜索是不科学的，比如对44×块会增加额外的搜索，而对16 16×的大块可能由于运动比较剧烈而在固定大小的窗口中无法找到最佳匹配的块，这是可以改进的一个点。其次，55×的全搜索所耗费代价太大，也是可以改进的地方。第三，在多层次六边形搜索中，首先以search_range/4为半径的六边形进行搜索，然后以search_range/2进行搜索，直到搜索半径为search_range，搜索结束。搜索需要搜索的点数为N=16×4=64，也可以进一步减少搜索点数。

图1 UMHexgonS算法

2 优化后的UMHexagonS算法

2.1 动态搜索窗口

对上述提到的搜索窗口的大小问题，引入动态搜索窗口[7]来解决。动态搜索窗口针对不同大小的当前块每次动态新生成搜索窗口。由运动矢量的中值预测值（MVPmedian）和上层预测值（MVPuplayer）来计算动态搜索窗口（DSR）大小，如图2所示。

A是固定搜索窗口大小,即input_search_range；B是动态窗口大小prpsd_DSR；C是实验值，为fixed_part=(input_search_range)/8；D是dynamic_part，由式(3)计算。

动态搜索窗口由式(2)计算：

另外，如果当前块是16×16，那么上层预测MVPuplayer不存在，此时搜索窗口的大小按文献[8]的方法计算。

图2 动态搜索窗口的计算

2.2 全搜索的优化

六边形搜索较全搜索算法减少了搜索点数，算法复杂度也有所降低，而信号信噪比并无很大差别，图像质量变化不大。故而可用六边形搜索算法代替全搜索算法，从而解决上述提出的全搜索优化问题。

2.3 多层次六边形搜索的优化

对于多层次六边形搜索，可以引入一个提前终止条件来减少搜索点数[9]。另外建立一变量pred_cost，将上一次搜索后的代价min_mcost赋值给pred_cost，下一次搜索时，如果满足式(6)：

则跳出循环，其中percent=0.8，是经过大量实验后得出的经验值。此时min_mcost即为步骤④的最佳点。

3 实验结果与分析

3.1 测试硬件及软件

首先将改进算法用C语言实现，并将其集成到测试软件JM中.实验所用计算机的硬件配置如：Intel(R)Pentium(R)D CPU 3.00 GHz处理器,512 M内存.操作系统为WindowsXP 2002+SP2.测试序列集为5个QCIF(176 144×)格式序列,所有序列格式都为Yuv4:2:0.编码器配置文件选用JM10.1的基本类（encoder_baseline.cfg）。实验中的编码参数如：FramesToBeEncoded=100，FrameRate=30，Use_Hadamard=1，search_range=16，NumberReference Frames=5。其他参数为默认设置。

3.2 测试结果与分析

测试中原算法UMHexagonS用UMHS表示，优化UMHexagonS算法后的算法用UMHS-AD表示，并且选择5个标准测试序列用以测试，它们代表了不同特点的运动类型。实验数据见表1、表2，从实验结果可以看出，改进的算法UMHS-AD比原算法UMHS平均节省了8.512%的编码时间，和15.56%的运动估计时间,并且基本保持了原有视频质量.峰值信噪比(PSNR，Peak Signal to Noise Ratio)最大提高0.01 dB或最大下降0.02 dB。

表1 测试结果比较

表2 不同搜索算法性能比较

从表2可以看出，优化后的算法UMHS-AD针对各种的标准测试序列均能保持较好的性能。可以得出3点结论：①与FS算法比较，平均损失了0.01 dB亮度信号的PSNR，但是最大损失不大于0.02 dB;与增强预测区域搜索（EPZS，Enhanced Predictive Zonal Search）算法比较，平均损失了0.02 dB亮度信号的PSNR，最大损失不大于0.05 dB，重建视频的质量与原有图象质量基本持平；②与FS算法比较，比特率有了极微小的增加，平均值为2.43%，与EPZS比较，平均值为0.83%，基本保持了编码效率；③编码和运动估计部分的耗时有一定的下降，与FS比较，运动估计速度大概为FS的3倍左右，与EPZS比较，运动估计时间有12%左右的下降.UMHS-AD与FS和EPZS相比，在重建图象质量和码率变化不大的情况下，实时性有了一定的提高。

4 结语

H.264相对已有的编解码标准能够有效的提高编码效率，但是其运动估计模块的算法也变的相当复杂，使得编码器计算量有了很大的增加。优化算法建立在对运动估计UMHexagonS算法进行分析的基础上，用动态自适应搜索窗口替换固定搜索窗口，用六边形搜索代替了原算法的螺旋搜索，并且在进行多层次六边形搜索时引入了提前终止条件，一定程度上降低了搜索点数，由实验结果可以看出，该算法在保证图像重建质量的基础上，能够有效地减少H.264运动估计模块的时间消耗.使得编码器的实时性有了较好的提高。

[1]WIEGAND T, SULLIVAN G J, LUTHRA A.Overview of the H.264/AVC Video Coding Standard[J].IEEE Transactions on Circuits and System for Video Technology,2003,13(07):560-576.

[2]POLAMAN C.A Novel Four Search Algorithm for Block Motion Estimation[J].IEEETransactions on Circuits and Systems for Video Technology,1996,6(03):313-317.

[3]ZHU C,LIN X,CHAU L P. Hexagon based Searh Pattern for Fast Block Motion Estimation[J]. IEEE Transactions on Circuits and System for Video Technology,2002,12(05):349-355.

[4]THAM J Y,RANGANATH S,KASSIM A A.A Novel Unrestricted Center-biased Diamond Search Algorithm for Block Motion Estimation[J]. IEEE Transactions on Circuits and System for Video Technology,1998,8(04):369-377.

[5]李白萍,陈方飞.H.264中一种新型算法的研究[J].通信技术,2009,42(12):43-45.

[6]王艳营. 基于节点交叉搜索的可变形块匹配运动估计算法[J].通信技术,2008,41(06):314-318.

[7]XU X Z,HE Y.Modification of Dynamic Search Range for JVT[S]. USA:[s.n.],2002.

[8]CHEN Z X,SONG Y,IKENAGA T, et al.A Dynamic Search Range Algorithm for Variable Block Size Motion Estimation in H.264/AVC Information[C]. Singapore:[s.n.], 2007:1-4.

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