运动估计中UMHexagonS的研究与改进

林永，杨印根，杨柳，许大姐

江西师范大学 计算机信息工程学院，南昌 330022

运动估计中UMHexagonS的研究与改进

林永，杨印根，杨柳，许大姐

江西师范大学 计算机信息工程学院，南昌 330022

H.264是新一代视频压缩编码标准[1]，运动估计是视频压缩编码中的一个关键部分，能有效地减少图像序列的帧间冗余。在H.264整个编码过程中，运动估计在编码时间中占据了相当大的比例，因此，缩短运动估计时间是一个非常重要的环节。为了减少运动估计的时间，近年来国内外学者针对运动估计的快速搜索提出了很多经典的算法，其中包括：全局搜索算法（FS）、三步搜索算法（TSS）、新三步搜索算法（NTSS）、四步搜索算法（FSS）、菱形搜索算法（DS）、六边形搜索算法（HS）、非对称十字型多层次六边形搜索算法（UMHexagonS）[2-3]。其中，UMHexagonS结合了其他算法的部分优点，在保证了较好的率失真性能的情况下，与FS算法相比较，节省了90%以上的运算量。目前，H.264已经正式采纳了非对称十字型多层次六边形搜索算法。虽然如此，但对该算法的分析与研究可以发现UMHexagonS还存在一些不足之处，如起始点的预测复杂，整个搜索过程的搜索点数较多，运算复杂度较高，从整体来说，编码时间还是较长，影响了编码效率。

本文针对UMHexagonS算法的不足，在原算法基础上，加入提前终止策略和搜索模板象限区域分割法，并且对UMHexagonS的螺旋搜索模板和多层次六边形搜索模板进行了改进，减少了许多不必要的搜索点数，在保证较好的率失真性能的情况下，有效地节省了运动估计时间。

1 UMHexagonS算法介绍

（1）起始搜索点的预测，利用较高精度的起始点预测，计算得出预测运动矢量MVpred。

（2）非对称十字型模板搜索，如图1（a）所示。

（3）螺旋模板搜索，以上一步搜索的匹配点作为搜索中心，搜索坐标[-2，2]正方形区域内的25个候选点，类似于全局搜索，如图1（b）所示。

（4）以非对称十字型模板搜索的匹配点作为搜索中心，进行多层次大六边形模板搜索，如图1（c）所示。

（5）以上一步搜索的匹配点作为搜索中心，进行六边形模板搜索，如图1（d）所示。

（6）小菱形模板反复搜索，如图1（e）所示，搜索得到最终的最佳匹配点。

图1 UMHexagonS算法的主要搜索模板

2 UMHexagonS算法的改进方案

2.1 起始搜索点的预测

UMHexagonS算法中，起始搜索点的预测包括空间域预测方式和时间域预测方式两种。空间域预测方式包括运动矢量中值预测、上层块模式运动矢量预测和原点预测，时间域预测方式包括前帧对应块运动矢量预测和时间域的邻近参考帧运动矢量预测。其中的时间域预测会消耗大量的存储空间，因此为了降低存储空间，本文的优化方法仅仅使用空间域预测方式，从而简化了起始点的预测，减少了起始点预测的时间。

2.2 部分搜索模板的改进和搜索模板象限区域分割法

由上述UMHexagonS搜索过程得知，该搜索算法在搜索过程中，搜索的候选点数较多，可以通过一些改进的方法减少搜索点数。本文采用了搜索模板象限区域分割法，根据文献[4]得知预测运动矢量和最佳运动矢量落入某同一象限的平均概率在95%以上，准确度很高。因此，首先，利用混合时空域起点预测方法，找到起始点的运动矢量方向，由于起点运动矢量方向和最佳运动矢量方向所落入的象限范围基本一致，所以在后面的搜索阶段只需要在一个约定的象限区域内进行搜索，其他四分之三的区域都不用搜索，这样就可以大大减少搜索点数，节省搜索时间。

如图2所示，整个宏块可划分为4个象限区域，分别是A1、A2、A3、A4，如果将当前宏块运动估计的起始点的最佳预测运动矢量记为MVpred(pred_x，pred_y)，则通过该运动向量计算得出：

图2 预测矢量所属4个区域

由式（1），可判断得出预测运动矢量方向落入在哪个象限内：

同时，根据运动矢量中心偏移特性[5]，在螺旋搜索模板中，靠近中心的搜索候选点的匹配点的概率更高，针对这点，下面对螺旋搜索模板进行了适当的改进。提出了一种菱-八边形搜索模板，该模板首先是进行小菱形搜索，再进行菱形搜索，最后进行小八边形搜索，如图3所示。

图3 菱-八边形搜索模板

由图3可知，采用改进后的菱-八边形搜索模板比原螺旋搜索模板减少了4个搜索点，而靠近中心的候选点不变，只是减少了远离中心点的边缘点，既符合运动矢量中心偏移的特性，又减少了搜索点数，同时节省了搜索时间。

而且，多层次六边形搜索模板搜索点数较多，搜索的范围较大，由于运动矢量中心偏移特性，在多层次六边形搜索模板中，最外层六边形候选点作为匹配点的概率极小。因此，下面提出一种多层次八边形搜索模板，可以大大减少搜索点数，如图4所示。

图4 多层次八边形搜索模板

由图4可知，多层次八边形搜索模板只需要搜索36个候选点，而原多层次六边形搜索模板需要搜索64个候选点，因此，大大节省了搜索点数。同时，与图1（c）比较后可知，多层次八边形搜索模板不需要搜索边缘的候选点，搜索的层次数更少，同时搜索的范围更加靠近中心点，因此，不仅增强了搜索的精度，而且进一步节省了搜索时间。

由图2给出的4种运动矢量所属象限的不同划分，以及式（1）和式（2）的判断，再结合改进后的菱-八边形搜索模板和多层次八边形搜索模板，可以得出在原UMHexagonS算法改进后，对非对称十字型搜索模板、菱-八边形搜索模板、多层次八边形搜索模板、六边形模板搜索和菱形模板搜索进行了象限区域的划分，如图5所示。

图5 改进后的搜索模板

以16×16搜索范围为例，只搜索一个象限区域，从图5（a）可以看出，原搜索模板需要搜索24个候选点，采用象限划分后，搜索点数只有原搜索算法的一半，将该改进后的搜索方法记为M1；如图5（b），原算法需要搜索25个候选点，改进后的螺旋搜索模板需要搜索21个候选点，再同时采用象限划分后只需要搜索8个点，将该改进后的搜索方法记为M2；如图5（c），原多层次六边形搜索模板需要搜索64个候选点，改进后的多层次八边形搜索模板只需要搜索36个点，再同时采用象限划分后只需要搜索12个候选点，将该改进后的搜索方法记为M3；如图5（d），原搜索模板需要搜索6个候选点，改进后只需要搜索2个点，将该改进后的搜索方法记为M4；如图5（e），原搜索模板需要搜索4个候选点，改进后只需要搜索2个点，将该改进后的搜索方法记为M5。因此，采用改进后的搜索模板以及象限区域划分策略之后，与原算法相比较，优化及改进后，在整个搜索过程中总共减少了一半以上的搜索点数，极大地节省了搜索时间。

2.3 搜索提前终止策略

提前终止搜索策略的方法是设定阈值，在保证率失真的情况下，选择合理的阈值T可以较好地提前终止搜索，减少不必要的搜索点数，节省搜索时间。在H.264标准中，采用块匹配准则方式计算搜索点的最小绝对差值和（Sum of Absolute Differences，SAD），如果SAD值小于或等于设定的阈值T，则提前结束搜索。在基于块匹配算法的运动估计中，宏块分为16×16，16×8，8×16，8×8，8×4，4×8，4×4共 7种块模式，各种块模式的SAD值各有不同，为了减少计算量，可以根据不同块模式的需求，设定7个不同的阈值。阈值T定义如下式：

其中，数组Bsize为当前宏块尺寸，blocktype为块模式1（16×16）到块模式7（4×4）。α[blocktype]通过多次实验按其概率分布规律得到：α[1]=0.30，α[2]=0.30，α[3]=0.33，α[4]=0.27，α[5]=0.13，α[6]=0.13，α[7]=0.44。

2.4 算法改进的具体流程

（1）进行简化了的起始搜索点预测，判断该起始点SAD值是否大于阈值T（2.3节中已定义），如果小于阈值T，则转入步骤（7）；否则，转入步骤（2）。

（2）通过式（1）和式（2）计算后得到预测运动矢量方向落入所属的象限区域，采用M1的方法进行搜索，同时判断各候选点SAD值是否大于阈值T，如果小于阈值T，则转入步骤（7）；否则，转入步骤（3）。

（3）以上一步最小候选点为中心，在预测的象限区域内采用M2的方法进行搜索，同时判断各候选点SAD值是否大于阈值T，如果小于阈值T，则转入步骤（7）；否则，转入步骤（4）。

（4）在预测的象限区域内采用M3的方法进行搜索，同时判断各候选点SAD值是否大于阈值T，如果小于阈值T，则转入步骤（7）；否则，转入步骤（5）。

（5）以上一步最小候选点为中心，在预测的象限区域内采用M4的方法进行反复搜索，同时判断各候选点SAD值是否大于阈值T，如果小于阈值T，则转入步骤（7）；否则，转入步骤（6）。

（6）在预测的象限区域内采，用M5的方法进行反复搜索。

（7）得到最佳匹配点，结束搜索。

算法改进后具体流程，如图6所示。

图6 UMHexagonS算法改进流程图

表1 文献[7]的算法改进与本文算法改进的实验数据对比

表2 仿真实验的差值及变化率对比

3 仿真实验结果与分析

3.1 仿真实验平台与配置

为了测试改进后的算法，本文在VC++6.0的平台上，将H.264标准测试JM10.1[6]集成到平台上进行了算法改进后的测试。实验所用PC机配置：Windows XP，CPU 1.68 GHz，内存为1 GB。选用的测试序列集为5个176×144的QCIF格式序列，所有序列都为Yuv4：2：0。采用Baseline编码，编码器主要参数配置：FramesToBeEncoded=100，FrameRate=30.0，UseHadamard=1，SearchRange=16，NumberReferenceFrames=5，其他参数为默认值。

3.2 实验结果与分析

本仿真实验主要针对文献[7]中UMHexagonS算法的改进进行以下对照与比较。

文献[7]的算法改进与本文采用改进方法后的仿真实验数据对比，如表1所示。

文献[7]的算法改进与本文采用改进方法后的仿真实验数据的差值及变化率对比，如表2所示。

从表2的实验数据中可以发现，本文改进后的算法与文献[7]改进算法相比，只有Foreman序列的SNRY值降低了，其他SNRY值都没有改变，同时在码率变化不太明显的情况下，运动估计时间（MET）却减少了4%～26%。其中，对于运动比较缓慢的序列News而言，运动估计时间节省了4.66%，对于中度运动的序列Foreman而言，运动估计时间节省了10.27%，对于剧烈运动的序列Highway、Coastguard和Mobile而言，运动估计时间分别节省了14.82%、23.17%和26.62%。从实验结果可以看出，改进后的算法相对于原算法，搜索速度随运动序列剧烈强度的增加而提高。因此，本文算法在保证编码性能的基础上，可以大幅地减少原算法的运动估计时间，整体上提高编码效率。

4 结束语

本文对运动估计UMHexagonS算法进行了分析和研究，针对其不足之处提出了一些改进。针对原搜索模板提出了菱-八边形搜索模板和多层次八边形搜索模板，同时引入预测运动矢量方向性判别搜索区域从而降低搜索点数，以及设定阈值提前终止搜索。实验结果表明，本文算法在PSNR值和码率与原算法相近的情况下，运动估计时间得以大幅减少。因此，本文的改进算法与原算法相比，具有明显的优势。

[1]Wiegand T，Sulivan G J，Luthra A.JVT of ISO/IEC JTC1/SC29/ WG11 and ITU-T SG16/Q.6，Doc.JVT-G050r1 Draft ITU-T recommendationH.264andfinaldraftinternationalstandard 14496-10 AVC[S].Geneva，Switzerland，2003-05.

[2]Yang P，He Y，Yang S.An unsymmetrical-cross multi-resolution motionsearchaigorithmforMpeg4-Avcm.264coding[C]// Proceedings of the IEEE International Conference on Multimedia and Expo（ICME），2004：531-534.

[3]Yang P，Wu H，Yang S.Fast motion estimation algorithm for H.264[J].Journal of Tsinghua University，2005，45（4）：527-531.

[4]李桂菊，刘刚，梁静秋.H.264快速运动估计算法的改进[J].光学精密工程，2010，18（11）：2489-2496.

[5]李会宗，陈雷霆，卢光辉，等.基于起点预测的不连续十字形快速搜索算法[J].计算机应用研究，2008，25（10）：2929-2931.

[6]JVT reference software of H.264[EB/OL].[2011-10].http：//iphome.hhi.de/suehring/tml/.

[7]卢文涛，樊滨温.基于H.264运动估计的空间预测算法[J].计算机工程，2010，36（7）：236-238.

LIN Yong,YANG Yingen,YANG Liu,XU Dajie

College of Computer Information Engineering,Jiangxi Normal University,Nanchang 330022,China

As the UMHexagonS algorithm exists problems such as excessive searching points,complicated computation and consuming time etc.,this paper puts forward some improving plans.On the one hand,to some of the searching template,a diamondoctagon searching template and a multi-level-octagon searching template are proposed;on the other hand,in the whole searching process,when using quadrant regional segmentation method,searching points and searching time can be effectively reduced. The experimental results show that the improved algorithm in the situation of guaranteed Peak Signal to Noise Ratio（PSNR）and bit rate,compared to the original algorithm,saves the 4%～26%of the motion estimation of time.

motion estimation;UMHexagonS algorithm;octagon;quadrant segmentation;threshold

针对UMHexagonS算法搜索点数较多，运算量较大以及耗时等问题，提出了改进方案。一方面，对部分搜索模板提出了一种菱-八边形搜索模板和一种多层次八边形搜索模板；另一方面，在整个搜索过程中，结合象限区域分割法，可以有效减少搜索点数和搜索时间。实验结果表明，改进后的算法在保证较好的PSNR和码率情况下，比原算法减少了4%～26%的运动估计时间。

运动估计；UMHexagonS算法；八边形；区域分割；阈值

A

TN919.81

10.3778/j.issn.1002-8331.1111-0071

LIN Yong,YANG Yingen,YANG Liu,et al.Research and improvement on UMHexagonS for motion estimation.Computer Engineering and Applications,2013,49（13）：207-210.

林永（1984—），男，硕士研究生，主要研究领域为视频压缩编码技术；杨印根（1962—），男，教授，江西师范大学计算机信息工程学院副院长，主要研究领域为计算机网络；杨柳（1988—），女，硕士研究生，主要研究领域为计算机网络；许大姐（1987—），女，硕士研究生，主要研究领域为自然语言处理。E-mail：linyong516@126.com

2011-11-07

2012-02-29

1002-8331（2013）13-0207-04

CNKI出版日期：2012-04-25http://www.cnki.net/kcms/detail/11.2127.TP.20120425.1722.084.html