基于运动类型与多模板的运动估计算法

潘琢金，张俊祥，罗 振，杨 华

（沈阳航空航天大学 计算机学院，辽宁 沈阳110136）

0 引 言

H.264因其高压缩率和良好的网络适应性，已被广泛应用于视频监控、数字电视、网络交互媒体等领域，但其高压缩率是以高计算复杂度为代价的，不能满足低端编码设备和无线传输等应用领域。运动估计耗费的时间占整个视频编码过程的60%－80%［1］，它的优劣直接影响到编码的实时性和图像的重建质量，因此在保证压缩率和图像质量的前提下，减少运动估计时间对提高编码效率至关重要。研究者们在基于块匹配［2］的基础上提出了许多快速运动估计算法，这些算法主要通过以下3种方法来降低计算复杂度：第一种是结合运动矢量 （motion vector，MV）的时空相关性来快速预测起始点；第二种是利用统计规律，设定合理的阀值进行静止块判定或提前终止检测［3］；第三种是根据MV 的分布特性［4］，通过设计或改进匹配模板和策略来减少搜索点数。以上方法在一定程度上缩短了运动估计时间，加快了搜索速度。UMHexagonS算法是一种优秀的运动估计算法，其搜索时间比全搜索算法节省了90%［5］，但该算法却没有充分考虑视频序列的运动特征，搜索过程缺乏针对性。本文算法在UMHexagonS基础上，添加了准静止块判定、简化起始点预测、采用与运动分布相适应的模板和策略进行搜索。该方法有效避免了搜索冗余，缩短了运动估计时间，提高了编码效率。

1 UMHexagonS算法

UMHexagonS算法结合了三步法、新三步法、四步法等搜索方法的优点［6］，它先采用高精度的起点预测，然后利用混合模板 （如图1所示）进行全局和局部搜索，并在多处进行提前终止检测［7］。具体的搜索步骤如下所示。

图1 UMHexagonS算法

步骤1 起始点预测：首先通过5种［8］高精度的预测方式来获得候选MV 集合，其次从中选取码率和失真度代价函数值最小的点作为起始点。然后进行提前终止检测，如果满足终止条件，则转入步骤4，进行扩展六边形搜索；否则转入步骤2。

步骤2 非对称十字交叉搜索：以起始点为搜索中心，按图1 （a）所示的模板进行搜索，找出最佳匹配点，并进行提前终止检测，如果满足终止条件，则转入步骤4；否则转入步骤3。

步骤3 非均匀多层次六边形网格搜索：①以当前最佳匹配点为中心，在5＊5矩形区域内螺旋式搜索，找出最佳匹配点，如图1 （b）所示。然后进行提前终止检测，如果满足终止条件，则转入步骤4；否则进入下一步。②以当前最佳匹配点为中心，进行扩展的多层次六边形搜索，如图1（c）所示。在每次扩展之前先进行提前终止检测，如果满足终止条件，则转入步骤4；否则继续扩展，直至搜索窗边界。

步骤4 扩展的六边形搜索：①六边形搜索，以当前最佳匹配点为中心，按图1 （d）所示六边形模板反复搜索，直至最佳匹配点位于其中心为止。②小菱形搜索，按图1（e）所示小菱形模板反复搜索，直至最佳匹配点位于其中心为止，输出MV。

从UMHexagonS算法搜索步骤可以看到，高精度的起点预测可以提高算法的效率。但对一些静止块或运动幅度很小的块，则存在着搜索冗余。不同的视频序列运动剧烈程度各异，其运动矢量分布也不相同，但UMHexagonS算法并未对其运动块类型进行分类，均采用了混合模板依次搜索，其搜索缺乏针对性，搜索速度将会受到影响。

2 本文算法

本文借鉴了相关研究人员提出的优秀改进方法［9，10］，在准静止块判定、起始点预测、运动类型划分与多模板搜索这3方面对UMHexagonS算法进行了改进，降低算法的计算复杂度，下面分别从这3方面描述该算法。

2.1 准静止块判定

在中小运动视频序列中存在着大量运动幅度很小或几乎静止不动的块。对于这类块，其运动矢量主要分布在以零矢量为中心很小的范围内，若对其进行起始点预测会造成时间上的浪费。因此，在起点预测前，有必要进行准静止块的判定。为此，本文采用绝对误差和［5］（sum absolute difference，SAD）作为准静止块的判断依据，通过设定合理的阀值T1，将零矢量处的SAD 值与T1进行比较。如果SAD小于或等于T1，则当前块为准静止块，表明其偏移位置很小，只需在其周围进行简单搜索即可找到最佳匹配点。如果SAD 大于T1，则表明运动矢量产生了较大偏移，需要细化搜索。

2.2 起始点预测

文献 ［7］中对起始点的5种预测方式的准确度进行了统计，发现中值预测和上层模式预测获取的MV 准确度最高。为了进一步降低算法的复杂度，并使搜索中心位于最佳匹配点，本算法采用中值预测和上层模式预测方式选取具有最小码率和失真度代价的点作为起始点。

2.3 运动块类型划分与多模板搜索

自然界中物体的运动快慢各异，其运动矢量分布也不相同，因此针对不同的运动类型应该选择与其运动矢量分布相适应的搜索模板，这样可以有效减少搜索冗余。在视频序列中，物体在水平方向和垂直方向的运动占很大比例，并且存在着水平方向比垂直方向要剧烈的特性，为此可选用非对称十字形模板来提高搜索效率［12］。为了能够快速的判断当前块的运动类型，本文引入一个阀值T2，并与起始点预测中计算得到的最小码率和失真度代价函数值 （记为cost）比较，来判断当前块的运动幅度大小［11］。如果cost小于阀值T2，则当前块为平缓运动 （包括慢速和中速）块，否则判定为剧烈 （或快速）运动块。

本算法中使用到的搜索模板如图2所示。为了保证算法的搜索精度，采取了如下策略进行搜索：首先以起始点为中心选用十字形模板进行方向性搜索；然后再根据运动类型选择相应的模板进行细搜索；最后使用小菱形模板（如图2 （d）所示）进行精细搜索。同时设定终止阀值T3，在十字形搜索和扩展多层次八边形搜索时，通过与最佳匹配点的SAD 值进行比较判定是否满足终止条件。若小于T3，则终止当前搜索，转至小菱形模板搜索。

对于剧烈运动块，其运动矢量偏离起点较大，UMHexagonS算法的混合搜索模板可以较精确地定位运动矢量，本文在此基础上进行了改进以简化原混合模板，采用了非对称大十字形模板 （如图2 （a）所示）、扩展多层次八边形模板 （八边形更容易捕捉到运动矢量）［12］（如图2 （b）所示）和六边形模板 （如图2 （c）所示）。首先采用非对称大十字形模板进行偏移方向性搜索；然后利用扩展多层次八边形模板进行粗步定位，每次扩展前进行提前终止检测；最后利用六边形模板进行局部细化搜索。

图2 搜索模板

对于平缓运动块，其运动矢量偏离起点不是很大，先选用非对称小十字形模板 （如图2 （e）所示）进行初步定位，然后再选用菱形模板（如图2 （f）所示）进行细化搜索。

2.4 算法描述

通过以上分析，本算法的流程如图3 所示。具体的算法步骤如下：

步骤1 准静止块判断：计算当前块零矢量位置的SAD值，若该值小于等于T1，则以 （0，0）点为中心，按菱形模板进行搜索，找到最佳匹配点 （SAD 最小值点）后，转至步骤7；若大于T1，则转至步骤2。

步骤2 起始点预测：按照中值预测和上层预测方式搜索出代价函数值cost最小的MV 作为起始点，转至步骤3。

步骤3 运动块类型判断：将起始点的cost值与阀值T2进行比较。如果cost小于等于T2，则判定当前块为平缓运动块，转至步骤4 按平缓运动块策略搜索；如果cost大于T2，则判定当前块为剧烈运动块，转至步骤5按剧烈运动块策略搜索。

步骤4 平缓运动块搜索。

（1）以起始点为中心，按非对称小十字形模板进行方向性搜索，选取最佳匹配点。然后进行提前终止检测，如果满足终止条件，则转至步骤6；否则转至步骤4 （2）。

（2）以当前最佳匹配点为中心，按菱形模板进行细化搜索，选取最佳匹配点。如果最佳匹配点在菱形边上，则转至步骤6；否则转至步骤7。

步骤5 剧烈运动块搜索。

（1）以起始点为中心，按非对称大十字形模板进行方向性搜索，选取最佳匹配点。然后进行提前终止检测，如果满足终止条件，则转至步骤6；否则转至步骤5 （2）。

（2）以当前最佳匹配点为中心，按多层次八边形模板进行搜索，每次扩展前，进行提前终止检测，如果满足终止条件，则转至步骤6；否则判断是否继续扩展，直至搜索窗边界，转至步骤5 （3）。

（3）以当前最佳匹配点为中心，按六边形模板反复搜索，直至最优点位于其中心，转至步骤6。

步骤6 精细搜索，以当前最佳匹配点为中心，按小菱形模板反复搜索，直至最优点位于其中心，转至步骤7。

步骤7 输出MV。

图3 本文算法流程

3 实验结果和性能分析

为测试本文算法性能，利用参考软件JM18.6 所提供的编码框架实现了本文提出的算法。实验所用的PC硬件配置如下：AMD Athlon 64 X2 DualCore Processor 3800＋1.99GHz，2GB内存。操作系统为Windows XP SP3。实验中的主要编码参数如下：档次为基本档，编码帧数为50，帧率为30，量化参数为28，帧类型为IPPP，熵编码类型为CAVLC，搜索范围为32，参考帧数为5，其它参数为默认设置。

实验中选取了具有广泛代表性的6个标准视频测试序列：akiyo、news、foreman、mother－daughter、coastguard、mobile。所有测试序列格式为QCIF（176＊144），色度格式为yuv4∶2∶0，其中coastguard、mobile 为大运动序列，foreman、mother－daughter为中等运动序列，akiyo、news为小运动序列。对各个测试序列分别采用了UMHexagonS算法 （UMH）、EPZS算法和本文算法进行了实验，主要从信噪比（PSNR－Y）、比特率 （BR）和运动估计时间 （MET）3个方面进行了比较。测试结果见表1。从表1中可以发现，本文算法的ME－T 明显低于UMH 算法，但与EPZS算法相比，在大运动序列中，本文算法的ME－T 高于EPZS算法，而在中小运动序列中，要低于EPZS算法。

表1 实验结果记录

表2是本文算法与UMH 算法的性能比较结果。从运动估计时间比较来看，本文算法比UMH 算法缩短约了12%－28% （平均节省了19.31%），有效降低了计算复杂度。其中，对于中小运动序列的效果更加明显。从峰值信噪比来看，有的测试序列有所下降，有的测试序列略有提高，但变化幅度都不大，在0.04dB 范围内，对图像质量影响很小，可以忽略。从比特率方面来看，变化幅度也很小，增幅在0.3%范围内。

表2 本文算法与UMH 算法性能比较结果

为测试本文算法的实用性，在开源库X264基础上实现本文算法，并将其和JRTP实时传输协议移植到Android平台，并对接口进行封装，通过JNI调用，实现Android终端的视频采集和传输。测试使用的采集端为华为手机C8812，接收端为PC 机，实时播放效果如图4 所示。在Wi－Fi局域网环境下，画面播放流畅。

图4 实时播放效果

4 结束语

本文结合了视频序列中运动块的分布特点，提出一种基于运动类型与多模板的运动估计算法，通过准静止块判定和按运动分布进行针对性搜索，减少了搜索冗余，降低了算法的计算复杂度，满足低复杂度的视频编码对算法的性能要求。在保证编码质量的同时，该算法对于不同类型的视频序列，均从不同程度上缩短了运动估计时间，对中小运动序列的效果尤为明显。下一步将针对剧烈运动视频序列进行深入研究，降低计算复杂度，使其更好地适应移动视频实时传输。

［1］GAO Xiaomin，YAO Rui，LIU Zhiyue，et al.Efficient adaptive motion estimation algorithm based on motion intensity ［J］.Journal of Image and Graphics，2012，17 （4）：504－511 （in Chinese）.［郭晓珉，姚睿，刘智跃，等.利用运动强度判据的高效自适应运动估计算法 ［J］.中国图象图形学报，2012，17 （4）：504－511.］

［2］Arora SM，Rajpal N.Comparative analysis of motion estimation algorithms on slow，medium and fast video sequences［C］／／International Conference on Reliability，Optimization and Information Technology－ICROIT，2014：422－427.

［3］DUANMU Chunjiang.Motion estimation technology in video processing and coding ［M］.Nanjing：Nanjing University Press，2011 （in Chinese）.［端木春江.视频处理与编码中的运动估计技术 ［M］.南京：南京大学出版社，2011.］

［4］LIU Long，SONG Qijun，ZHAO Taifei，et al.Fast motion estimation based on the special and temporal characteristic［J］.Journal on Communications，2013，34 （1）：121－127 （in Chinese）.［刘龙，宋琦军，赵太飞，等.基于运动矢量时－空特性的快速运动估计算法研究 ［J］.通信学报，2013，34 （1）：121－127.］

［5］SHEN Zhou，LI Zhengming，PAN Tianhong.Motion estimation based on the partition and evaluation of the search a REA in H.264／AVC ［J］.Journal of Image and Graphics，2010，15 （2）：242－246 （in Chinese）. ［申舟，李正明，潘天红.H.264／AVC中基于搜索区域划分及评估的运动估计 ［J］.中国图象图形学报，2010，15 （2）：242－246.］

［6］LI Ziyin，YANG Qi.Fast motion estimation algorithm based on motion information adaptation ［J］.Journal of Image and Graphics，2012，17 （9）：1069－1074 （in Chinese）.［李子印，杨齐.基于运动信息自适应的快速运动估计算法 ［J］.中国图象图形学报，2012，17 （9）：1069－1074.］

［7］WU Yinhua，JIN Longxu，ZHANG Ning，et al.Improvement of fast integer pixel motion estimation algorithm for H.264［J］.Optics and Precision Engineering，2013，21 （4）：1017－1025 （in Chinese）. ［吴银花，金龙旭，张宁，等.针对H.264改进的快速整像素运动估计算法 ［J］.光学精密工程，2013，21 （4）：1017－1025.］

［8］WU Xiaojun，BAI Shijun，LU Wentao.Optimization on motion estimation algorithm based on H.264 ［J］.Acta Electronica Sinica，2009，37 （11）：2541－2545 （in Chinese）. ［吴晓军，白世军，卢文涛.基于H.264视频编码的运动估计算法优化 ［J］.电子学报，2009，37 （11）：2541－2545.］

［9］Ko Yun－ho，Kang Hyun－soo，Lee Si－woong.Adaptive search range motion estimation using neighboring motion vector differences［J］.IEEE Transactions on Consumer Electronics，2011，57 （2）：726－730.

［10］Ismail Y，Mcneely JB，Shaaban M，et al.Fast motion estimation system using dynamic models for H.264／AVC video coding ［J］.IEEE Transactions on Circuits and Systems for Video Technology，2012，22 （1）：28－42.

［11］YE Shitong，WAN Zhiping.Combination of motion estimation algorithm type with threshold value of block－based motion［J］.Computer Engineering and Design，2013，34 （6）：2093－2097 （in Chinese）.［叶仕通，万智萍，基于块运动类型与阈值相结合的运动估计算法 ［J］.计算机工程与设计，2013，34 （6）：2093－2097.］

［12］DING Xin，FAN Huijin.A mix－pattern motion estimation search algorithm based on direction adaptation ［J］.Journal of Image and Graphics，2011，16 （1）：14－20 （in Chinese）.［丁鑫，樊慧津.基于方向自适应的运动估计混合模板搜索 算 法 ［J］. 中 国 图 象 图 形 学 报，2011，16 （1）：14－20.］