魏文振， 昂志敏

（合肥工业大学 计算机与信息学院， 安徽 合肥 230009）

运动估计是H.264 标准中一项关键核心技术，同时也是所有视频编码标准中的一项核心技术。 采用运动估计和运动补偿技术可以消除视频信号的时间冗余并提高编码效率。 从编码器整个计算过程来看， 运动估计占整个系统的计算量60%～80%。 因为在压缩过程中，运动估计能够很好地去除视频图像中存在的时间冗余、空间冗余，实现高效的编码效率。同时运动估计也是制约视频图像编码效率的关键原因之一。综上所述，改善运动估计的效率，使运动估计算法的搜索过程更快速、更高效具有重要的意义。

全搜索算法（FS）是一种搜索策略最全面的算法，找到的匹配点即全局最优点，但其计算量较大，限制了实时压缩的应用。 为了减少计算量，研究人员提出了很多基于固定模板的快速搜索算法，如三步搜索法（TSS）[1]、四步搜索法（FSS）[2]、基于块的梯度下降搜索法（BBGDS）[3]、菱形搜索法（DS）[4]和六边形搜索法（HS）[5]等。上述算法虽然提高了搜索速度，但是搜索容易陷入局部最优，得不到最优的运动矢量。 近些年又出现了一些基于预测矢量集的快速搜索算法，如非对称十字型多层次六边形搜索算法（UMHexagonS）[6]等。 这类算法利用运动矢量场的时相关性产生预测矢量集，通过搜索预测矢量位置产生搜索区域的中心位置，并根据运动类型自适应选择搜索模板，加入了提前终止搜素的判断策略，进一步提高了搜索速度。

在研究运动估计的过程中，利用提前终止策略来加速视频编码的编码效率，已经成为研究的热门问题。 块匹配运动估计算法由于简单、高效、开销小、易于实现等优点而被大多数视频编码标准所采用，该算法匹配的准则有3 种，即平均均方误差（MSE）、平均绝对差（MAD）和归一化函数（NC—CF）[7]。 为了降低计算复杂度，通常用绝对误差和（SAD）来代替MAD。

1 UMHexagonS 算法的基本流程及分析

UMHexagonS 算法即非对称十字形多层次六边形格点搜索算法，是H.264 标准所采纳的运动估计算法之一。 同全搜索算法相比，该算法在保持较好率失真性能的前提下，可以节约90%左右的计算量。 为了降低计算复杂度，在运动估计过程中，通常用绝对误差和（SAD）来代替MAD，SAD 的定义如下：

UMHexagonS 算法的基本步骤如下：

Step1 起始搜索点预测。 依次进行中值预测、原点预测、上层预测、对应块预测、相邻参考帧预测，接着判断SAD 值。若其很小，则跳至step6；

Step2 非对称十字形搜索模板搜索。 此时对SAD 值进行判断，若其值很小，判断其为很满意区，则跳至step6；若其值较大，判断为不满意区，则跳至step5；否则继续下一步；

Step3 利用5*5 正方形模板进行螺旋式搜索；

Step4 利用多层六边形模板进行搜索；

Step5 利用中六边形模板进行搜索；

Step6 利用小菱形模板进行搜索，得到最终的运动矢量MV。

通过上述流程可以看出，UMHexagonS 算法在起始搜索点预测的过程中，依次进行五种预测。 这在一定程度上影响了运动估计的搜索时间。 而且算法中用到了正方形模板，非均匀多层六边形模板和小菱形模板，也可以进行优化，以提升运动估计算法的效率。

2 UMHexagonS 算法的优化

通过对UMHexagonS 算法的分析和研究， 发现该算法在搜索效率上依然有可以提高之处，本文将从加入提前中止搜索的判断策略和在不影响图像整体质量前提下减少搜索点数两方面进行改进，具体改进如下：1）在起始搜索点的预测时加入阈值进行判断；2）根据运动剧烈程度的不同对运动类型进行自适应判断；3）对部分搜索模板进行改进，提高搜索效率。

2.1 起始搜索点预测的阈值判断

通过引入阈值来提前判断是否停止搜索，从而更高效的对预测运动矢量MV 进行预测。 引入的阈值定义如下：

式中：m—阈值的自由项；Blocksize—当前编码尺寸；blocktype—模式1 至模式7 可供选择；αstop—常数组（α1=0.30，α2=0.33，α3=0.33，α4=0.27，α5=0.13，α6=0.13，α7=0.44）。

在对预测运动矢量MV 进行预测时， 首先采用中值预测， 得到当前搜索点A。 假设A 点为最佳点min_cost，对min_cost 进行判断。

若min_cost＜Thred0 时，则停止搜索，得到最终MV；否则依次进行原点预测、uplager 预测、相邻参考帧预测，接着进行非对称十字模板搜索。 此时得到的min_cost1 需要同阈值Thred1，Thred2 进行判断；

若min_cost1＜Thred1 时，则中止搜索；

若TH1＜min_cost1＜Thred2 时， 跳转至改进型正方形模板继续进行搜索；

若min_cost＞Thred2 时，则跳转至下一步。

2.2 运动类型的自适应判断

在UMHexagonS 算法中加入对运动类型的自适应判断，来缩小运动估计过程中的搜索范围。 视频通常可以根据运动幅度的大小来进行划分，划分如下：块的运动幅度较小的，可看做处于相对静止的运动状态。 其运动矢量通常是以（0，0）为中心向外进行扩散， 发生的概率随着远离中心越来越小；块的运动幅度中等的，其运动矢量一般出现在距离中心位置较远的地方，呈环形分布。 离中心位置越近，出现概率越小；块的运动幅度较大的， 其运动矢量一般分布在外侧范围，离中心位置较块运动幅度中等的运动矢量更大。

为了更好的判断视频的运动剧烈程度，引入阈值TH[8]。实验研究表明， 当TH=800 时能够较好的区分运动类型。通过cos t[9]与TH 的比较作为依据。 cos t的定义如下：

其中SAD—绝对误差和；B—根据情况不同， 可选4、8、16；γ—平衡码率与失真度的因子；s—当前编码的数据；c（m）—编码重建的参考帧数据。

2.3 正方形搜索模板的优化

原算法采用的是5*5 的搜索模板中，一次螺旋搜索共有25 个搜索点，计算量较大。 通过对不停的的视频序列的运动向量进行分析后发现，大约有80%的运动向量预测中心落在5*5 区域内， 而其中又有70%落在3*3 的区域内。同时3*3 搜索模板的搜索点数是5*5 搜索模板的搜索点数的1/3 左右。 故本文采用3*3 的正方形模板进行搜索，提高搜索效率。

图1 3*3 正方形模板Fig. 1 3*3 square template

2.4 多层六变形搜索模板的优化

根据搜索模板圆形最优理论， 八边形更符合圆形最优理论。故将原算法中多层六边形模板利用八边形模板进行代替。八边形的八个顶点到中心点的距离都是。 虽然在垂直方向和水平方向相比六边形各多出两个点， 但是在模板总搜索点数上却减少了16 个点，故可有效减少搜索点数，提高搜索速率。 搜索模板如图2 所示。

2.5 小菱形搜索模板的优化

原算法中采用的小菱形模板搜索时搜索的只是图2 中小菱形的4 个顶点， 同正方形模板搜索相比， 图形质量较低。 但是若采用正方形搜索模板势必将导致搜索的点数增加。现在依然采用正方形模板，但通过利用SAD 值之和作为判断标准的方法来减少搜索点数，同时图像质量也会高于小菱形搜索。 将六边形的相邻两个点看成一个小组，如图3 所示，共A、B、C、D、E、F 六组。在六边形模板搜索结束前，分别计算每一小组中两个点的SAD 之和。 若SAD 和最小的是水平方向上的组，即E 组或F 组，则只需搜索图2 中小正方形模板中的水平方向上的3 个点。 若SAD 和最小的是斜方向上的组， 则只需搜索小正方形模板中最靠近该斜边的两个点。 从上述分析可看出，无论采用这两种搜索方法中的任意一种， 都比利用小菱形模板搜索和正方形模板搜索时所搜索的点数要少。

图2 多层八边形模板Fig. 2 Multilayer octagon template

图3 改进型正方形模板Fig. 3 Improved square template

3 UMHexagonS 算法改进后的流程

3.1 改进算法基本流程描述

Step1 首先采用中值预测，得到当前搜索点A，假设A 点为最佳点min_cost。 若min_cost＜Thred0 时，则停止搜索，得到最终MV；否则依次进行原点预测、uplager 预测、相邻参考帧预测，接着进行非对称十字模板搜索[10]。 继续引入阈值Thred1，Thred2 进行判断。 若min_cost1＜Thred1 时，则中止搜索； 若Thred1 ＜min_cost1 ＜Thred2 时， 跳 转 至STEP6；若min_cost＞Thred2 时，则跳转至STEP2；

Step2 对视频运动剧烈程度进行自适应判断。 若时，跳至STEP 3；若时，直接跳至STEP 4 继续进行搜索；

Step3 采用3*3 正方形搜索模板；

Step4 多层八边形模板进行搜索；

Step5 中六边形模板进行搜索；

Step6 改进型正方形模板搜索。

3.2 改进后算法的整体流程图

图4 改进后UMHexagonS 算法流程Fig. 4 Improved UMHexagonS algorithm process

4 实验结果及分析

本文基于JM18.4 平台对上述改进方法进行实现， 选取QCIF 的6 个 标 准 视 频 测 试 序 列：akiyo_qcif、mobile_qcif、coastguard_qcif、news_qcif、bus_qcif、football_qcif 进 行 仿 真 测试。 其中akiyo_qcif、news_qcif 的运动较为缓慢，可看做运动幅度小的运动序列；mobile_qcif、bus_qcif 可看做是运动幅度中等的运动序列；coastguard_qcif、football_qcif 可看做是运动幅度较大的运动序列。 本文在编码帧数为60，参考帧数为5，帧率为30，量化参数QP 为28 的参数设定情况下进行测试，并将改进后的算法同UMHexagonS 算法在运动估计时间和亮度信号峰值信噪比两方面进行比较。 通过表1 可以看出，改进后的算法较原算法在运动估计时间都有提升，平均节省时间比为20.15%，尤其对运动剧烈的视频序列效果更佳。 通过表2 可以看出，改进后算法同原算法相比，亮度信号峰值信噪比基本持平[11]，说明峰值的变化范围很小。 由此可见，本文对UMHexagonS 算法进行改进后，在保持原算法率失真性能的前提下，减少了运动估计的编码时间，达到提高工作效率的目的。

表1 UMHexagonS 算法与改进算法的运动估计时间比较Tab. 1 Time comparison of motion estimation between UMHexagonS algorithm and the improved UMHexagonS algorithm

表2 UMHexagonS 算法与改进算法的亮度信号峰值信噪比（PSNR）比较Tab. 2 PSNR comparison of motion estimation between UMHexagonS algorithm and the improved UMHexagonS algorithm

5 结束语

本文通过对UMHexagonS 算法的研究，首先在运动估计的起始搜索点预测阶段增加阈值来提前判断是否中止搜索。若起始点一开始就是最优点，通过阈值判断策略可以大大节省搜索时间。 然后在算法的过程中，通过加入对运动类型的自适应判断来缩小搜索范围，同时优化搜索各阶段的搜索模板，最终达到了提高运动估计效率的目的。 从实验结果可以看出， 在保持PSNR 基本不变的前提下， 搜索时间提高了20.15%。

[1] 王艳营，冯进玫. 基于EPZS 的H. 264 运动估计算法的改进[J]. 计算机技术与发展，2012，22（1）:100－107.

[2] Po L M，Ma W C. A novel four-step search algorithm for fast block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology，1996，6（3）:313-317.

[3] Liu L K， Feig E. A block-based gradient descent search algorithm for block motion estimation in video coding[J]. IEEE Transactions on Circuits and Systems for Video Technology，1996，6（4）:419-422.

[4] Zhu S， Ma K K. A new diamond search algorithm for fast block-matching motion estimation[J]. Image Processing，2000，9（2）:287-290.

[5] Zhu C，Lin X，Chau L P. Hexagon-based search pattern for fast block motion estimation [J]. Circuits and Systems for Video Technology，2002，12（5）:349-355.

[6] Chen Z，Zhou P，He Y. Hybrid unsymmetrical-cross multihexagon-grid search strategy for integer pel motion estimation in H.264[C]//Proc. Picture Coding Symposium，2003:17-22.

[7] Wang Q，Zhuo L，Zhang J，et al. Frame layer rate control method for stereoscopic video coding based on a novel ratedistortion model [C]//The Era of Interactive Media. Springer New York，2013:205-216.

[8] 朱小龙，罗星，陈祖爵. 带有模式选择的改进的方向性菱形搜索算法[J]. 计算机应用研究，2010，27（1）:393-395.

[9] Kim C G，Lee I J，Kim S D. Reduced uneven multi-hexagongrid search for fast integer pel motion estimation in H.264/AVC [C]//Proc. Image Analysis and Recognition. Berlin Heidelberg: Springer Verlag，2007，4633:708-714.

[10]黄婷，黄伟. 基于不同算法求解子问题的Benders分解法在无功规划中的应用[J]. 陕西电力，2013（3）:23-26.

[11]施先旺，王鹏武. 发动机工况实时调节软件设计[J]. 火箭推进，2012（5）:70-76.