一种改进的UMHexagonS运动估计算法

杨 齐，李子印

（中国计量学院光学与电子科技学院，浙江杭州 310018）

H.264是最新的国际通用的视频编解码标准，由动态图像专家组（MPEG）和视频编码专家组（VCEG）联合开发并于2003年正式发布。H.264因其高精度的运动估计、多参考帧预测、多宏块划分模式等特点而具有高效的编码性能，得到了广泛的应用，并将在无线多媒体传感器网络、高清数字电视、远程视频教学等诸多领域发挥很重要的作用［1］。运动估计是H.264视频编码器结构中的核心部分，它和运动补偿占据着整个编码过程总运算量的70%以上。目前UMHexagonS［2］算法已被H.264编码标准正式采纳为其整像素运动估计算法，其运动估计精度较高，但同三步法、新三步法、四步法等快速算法相比，该算法的搜索点数还较多，搜索速度还不够快。

为了能在保持较好的率失真性能的同时，进一步降低算法的复杂度，提高编码效率。本文从起始搜索点预测、运动类型自适应搜索选择、搜索模板和提前终止判断四个模块对UMHexagonS算法进行了改进。

1 UMHexagonS算法介绍

UMHexagonS是一种混合的多层次运动估计算法，主要的搜寻步骤［3］可分为以下6步:

1）起始搜索点预测。分别采用4种不同的起始点预测方法（中值预测、对应块预测、上层预测和临近参考帧预测）来搜索出一个使得对应的代价函数J（m，λmotion）最小的候选运动矢量作为起始搜索点，并执行提前终止判断。

2）不对称的十字交叉搜索。由于自然界中常见运动场景的水平方向的运动要比垂直方向的剧烈一些，故使用如图1a所示的不对称的十字交叉搜索方法，并执行提前终止判断。

3）正方形搜索。以当前最佳点为中心，搜索如图1b所示的25点方形区域。

4）多层次的六边形搜索。以正方形搜索所获得的最优点为中心，在搜索窗中执行直径不断扩大一倍的16点六边形模板（如图1c所示）的搜索。

5）扩展六边形模板搜索。采用图1d所示的搜索模板反复进行搜索，直至最优点位于六边形的中心点时结束搜索。

6）小菱形搜索。以当前最优点作为中心，反复采用小菱形模板（如图1e所示）进行搜索，当最优点处在小菱形的中心点时结束搜索，并把此时对应的运动矢量选定为最终的运动矢量。

图1 UMHexagonS算法中使用的各种搜索模板

2 对UMHexagonS算法的改进

2.1 起始搜索点预测的优化

起始搜索点预测是依据运动物体的整体性和序列运动的连续性，利用待估计块和其周边块的时空相关性，用周边已编码块的运动矢量进行当前块的运动矢量的起始点预测［4］。本文在此基础上，进一步考虑到中心偏移特性和固定背景上物体边界的情况，在经中值预测得到mvpred_MD、上层预测得到 mvpred_UP、对应块预测得到mvpred_CB、临近参考帧预测得到mvpred_NRP的同时，也对原点（0，0）进行搜索预测并计算出J0（m，λmotion），其对应的预测矢量为mv=（0，0）。然后通过比较这5个运动矢量各自对应的值，选取J（m，λmotion）最小的运动矢量作为起始搜索的最终预测运动矢量。

2.2 运动类型自适应的搜索选择

同一视频帧中的不同区域块有着不同的运动类型，可将物体运动类型区分为静止或慢速运动、中速运动、快速运动三种。本文通过利用起始预测运动矢量的运动信息对当前块的运动类型进行划分，对静止或慢速运动块采用小模板进行一步停止法搜索、对中速运动块也适当减少搜索步骤、对快速运动块则仍采用多步的详尽搜索［5］。

图2 改进算法的流程图

2.3 搜索模板的改进

UMHexaongS算法在不对称十字交叉搜索之后，再搜索当前最优点周边的25点正方形区域，并对一些较为剧烈的运动场景采用多层次的六边形模板进一步搜索，以获取最佳的匹配点，这种方法可以比较准确地找到当前块的匹配块，但其搜索点数还比较多［7］。本文在保证重要区域的点得到精确搜索的同时，除去了对一些不重要区域的点的搜索，从而进一步减少搜索点数、提高编码效率。

2.3.1 正方形搜索模板的改进

根据运动矢量中心偏移特性及大量的实验表明，最佳运动矢量落在以半径为2的圆形区域内的可能性高达80%以上［8］，UMHexagonS算法中采用的25点正方形搜索区域中有不少点是落在该圆形区域的外面。基于此，采用含有该圆形区域内的所有整像素位置的13点菱形搜索模板代替正方形搜索模板，如图3a所示。这种搜索模板能够确保对重要搜索区域进行搜索，并可为该搜索步骤节省12个搜索点。

2.3.2 多层次大六边形模板的改进

考虑到常见视频序列的水平、垂直方向较其他方向运动更加剧烈，采用多层次大菱形搜索模板代替UMHexagonS算法中所采用的多层次大六边形搜索模板，如图3所示。这种改进可使该步骤中的搜索点数变为原来的一半。

图3 改进后的模板

2.4 提前终止判断的优化

本文沿用了UMHexagonS算法所采用的提前终止判断方法［9］。具体如下

如果满足条件（1），其SAD值判定为很小，执行第6步;如果满足条件（2），其SAD值判定为较小，跳至第5步;若满足条件（3），其SAD值判定为很大，执行下一步。

UMHexagonS源算法中，在正方形搜索和多层次大六边形搜索后均未进行提前终止的判断。本文在改进后的13点菱形搜索和8点多层次菱形搜索的步骤后均加入了提前终止判断（阈值判断）条件。

结合以上四个方面对改进算法的描述，将整个改进算法的实现流程［10-11］绘制如图2所示。

3 实验仿真及分析

为了测试改进算法的性能，采用H.264的参考软件JM10.2在Visual C++6.0实验平台上实现该算法。编码帧数为80，参考帧数为5，搜索范围为±16，量化参数为28，熵编码为CABAC，编码类型为IBPBP，帧率为30 Hz，其他参数为缺省默认设置。

实验中选取了akiyo，foreman，coastguard三个 QCIF格式的不同运动类型的序列进行测试。其中akiyo代表慢速的运动序列，foreman代表中速运动序列，coastguard代表快速运动序列［12］。分别使用全搜索算法（FS）、UMHexagonS算法（UMH）和本文改进的算法进行实验，实验结果及分析如表1～3所示。

表1 实验结果记录

表2 改进算法相对FS算法的变化

表3 改进算法相对于UMHexagonS算法的变化

通过对表2、表3的观察和分析可知，改进算法相比于全搜索算法而言，信噪比平均降低0.015 dB，码率变化率为-0.7% ～+0.8%，运动估计时间节省60% ～80%;改进算法相比于UMHexagonS算法而言，信噪比平均增加0.008 dB，码率变化率为-0.3% ～+1.1%，运动估计时间节省10%～25%。由此可知，改进后的算法在保持信噪比和码率基本不变的情况下，大大节省了运动估计的搜索时间，有效地提高了编码器的实时性能。

4 小结

本文提出的改进算法利用运动矢量的运动信息对视频序列的运动类型进行划分，并结合原点预测、模板替换和提前终止，从四个方面对UMHexagonS算法进行改进和优化。仿真结果表明，新改进的算法在维持图像质量基本不变甚至略有改善的情形下，较大幅度地减少了搜索点数，使得运动估计的时间节省了10% ～23%，能够更好地满足许多实时场合（如实时视频监控、可视电话、物联网）的应用要求，具有较强的实用价值。

：

［1］毕厚杰，王健.新一代视频压缩编码标H.264/AVC［M］.北京:人民邮电出版社，2009.

［2］CHEN Zhibo，ZHOU Peng，HE Yun.Fast integer pel and fractional pel motion estimation for JVT［C］//Proc ISO/IEC MPEG&ITU-T VCEG 6th Meeting.［S.l.］:JVT，2002.

［3］罗哲.基于快速运动估计算法UMHexagonS的改进和优化［J］.研究与开发，2011（3）:29-31.

［4］熊承义，白云.基于方向信息的快速整像素运动估计优化［J］.中南民族大学学报，2010，29（1）:62-67.

［5］杨晓珍，吴延海，王锋.基于块运动类型的自适应菱形运动估计搜索算法［J］. 计算机工程，2007，33（23）:220-222.

［6］丁鑫，樊慧津.基于方向自适应的运动估计混合模板搜索算法［J］.中国图象图形学报，2011，16（1）:14-20.

［7］申舟，李正明，潘天红.H.264/AVC中基于搜索区域划分及评估的运动估计［J］. 中国图象图形学报，2010，15（2）:242-246.

［8］LIN C C，LIN Y，HSIEH H J.Multi-direction search algorithm for block motion estimation in H.264/AVC［J］.IEEE Trans.Image Processing，2009，3（2）:88-99.

［9］杨晓琴，季晓勇.基于H.264的快速运动估计算法［J］.计算机工程与应用，2011，47（4）:174-175.

［10］卢政，卢俊.基于UMHexagonS的快速运动估计算法优化［J］.电视技术，2011，7（35）:29-31.

［11］SHI Zhiru，FERNANDO W A C，DE SILVA D V S X.A motion estimation algorithm based on predictive intensive direction search for H.264/AVC［C］//Proc.2010 ICME.［S.l.］:IEEE Press，2010:667-672.

［12］WU Xiaomin，XU Weizhang，ZHU Nanhao.A fast motion estimation algorithm for H.264［C］//Proc.2010 ICSAP.［S.l.］:IEEE Press，2010:112-116.