一种利用预测运动矢量改进的H.264快速运动估计算法*

2017-04-27郭继昌邱琳耀

数据采集与处理 2017年2期

关键词：步长全局矢量

郭继昌邱琳耀张雪

(天津大学电子信息工程学院，天津， 300072)

一种利用预测运动矢量改进的H.264快速运动估计算法*

郭继昌邱琳耀张雪

(天津大学电子信息工程学院，天津， 300072)

针对H.264标准推荐使用的快速运动估计算法——非对称十字型多层次六边形格点搜索(Unsymmetrical cross multi-hexagon grid search, UMHexagonS)算法搜索速度慢的问题，提出了一种改进算法。在起始搜索点的预测环节，建立预测矢量集，并根据预测矢量集的长度信息决定后续的搜索策略；在全局搜索环节，利用预测运动矢量之间的相关性适当跳过某些搜索步骤，并更换一些搜索模板；并且，根据整数变换和量化的特性检测全零系数块，提前终止运动估计过程。实验结果表明，在量化步长为28时，本文算法比UMHexagonS算法平均减少了34.80%的运动估计时间，同时编码性能基本不变。该算法在不同量化步长的条件下能够适应不同运动强度的视频序列，是一种适合H.264的速度快且性能好的快速运动估计算法。

视频编码；运动估计；预测运动矢量；H.264；非对称十字型多层次六边形格点搜索

引言

运动估计是H.264编码器中最耗时的环节之一。块匹配法由于算法简单、易于硬件实现，成为应用最广泛的运动估计算法。在块匹配运动估计算法中，传统的全搜索法通过检查搜索范围内的每一个点，可以得到最佳运动矢量。全搜索法能够获得图像质量上的高性能，但是计算复杂度过高。采用全搜索法的运动估计过程占据了H.264编码器超过50%的编码时间[1]，为了解决编码器对计算能力和内存容量要求非常高的问题[2]，许多快速搜索算法被提出。这些快速搜索算法大体可以分为几类，第1类采用特定的搜索模板，其中比较有代表性的算法是菱形搜索算法、六边形搜索算法等。由于搜索模板较为简单，这类算法对于运动缓慢的视频序列能够取得比较好的效果，但其没有从全局考虑运动方向，容易陷入局部最优化。第2类快速搜索算法采用动态的搜索范围，其主要思想是根据当前块的运动状态自适应地选择搜索窗口的尺寸[3]。第3类快速搜索算法采用提前终止策略，提前终止策略有很多，包括零运动矢量检测、最佳运动矢量检测以及全零系数块的检测等[4-5]。近年来，基于宏块时域和空域上的特性，一些放宽匹配条件的算法涌现出来，比如：逐次消元算法[6]和局部失真搜索算法[7]等。这些算法能够在保持图像质量的同时降低运动估计的运算量，但是硬件实现较为困难。

目前H.264标准推荐采用的快速运动估计算法是非对称十字型多层次六边形格点搜索 (Unsymmetrical cross multi hexagon grid search, UMHexagonS)算法[8]。该算法是一种混合编码技术，相对全搜索法可节约90%的运算量，大大降低了计算复杂度，同时能够保持较好的编码效率和图像质量，比较好地兼顾了编码性能和编码速度的统一。但是UMHexagonS算法在全局搜索、提前终止策略等方面仍然存在一定的问题，因此针对UMHexagonS算法的改进成为近年来的研究热点[9-10]。本文以UMHexagonS算法为基础，利用预测运动矢量与最佳运动矢量的高度相关性，在起始搜索点的预测、全局搜索以及全零系数块的检测3个方面进行改进。

1 UMHexagonS算法

UMHexagonS算法是联合视频专家组(Joint video term ，JVT)提供的JM模型中推荐使用的运动估计算法，其采用多种预测方式进行起始搜索点的预测，并基于运动对象的特点，混合采用多种模板进行运动矢量的搜索。

UMHexagonS算法的第1步为起始搜索点的预测，采用5种方式预测起始的搜索中心。在这5种预测方式中，既有利用运动矢量时间相关性的预测方式(前帧对应块预测、相邻参考帧预测)，也有利用运动矢量空间相关性的预测方式(中值预测、上层块预测)，还有利用运动矢量中心偏移特性的预测方式((0,0)预测)。但是该算法并没有将这3种特性有效地结合起来，把这个标记为问题1。

在精确地找到起始搜索点之后，UMHexagonS算法进行全局搜索。全局搜索依次采用：(1)非对称十字型模板搜索； (2)5×5螺旋方形模板搜索；(3)多层次大六边形模板搜索。在全局搜索完成之后，UMHexagonS算法以得到的全局最优点为中心，进行局部搜索。局部搜索依次采用：(1)小六边形模板搜索；(2)小菱形模板搜索。全局搜索和局部搜索的模板如图1所示。UMHexagonS算法的全局搜索过程虽然很好地避免了局部最优化的问题，但是仍然会进行大量不必要的搜索，把这个标记为问题2。

另外，UMHexagonS算法还在多处进行了提前终止检测，具体来说就是设定阈值，将当前搜索点的拉格朗日(Lagrangian)编码代价与阈值相比较，如果小于阈值就跳过某些搜索步骤。具体的提前终止策略如下：

如果J

图1 UMHexagonS算法的搜索模板Fig.1 Search patterns of UMHexagonS algorithm

UMHexagonS算法虽然采用了提前终止策略，但是没有充分利用整数变换和量化的特点、预测MV处绝对之和(Sum of absolute difference, SAD)的分布特性以及率失真判决的条件，把这个标记为问题3。

2 UMHexagonS算法改进

2.1 预测矢量集

针对前文分析中提出的问题1，本文通过建立预测矢量集的方法将预测运动矢量的时间相关性、空间相关性以及中心偏移特性有效地结合起来。从空间、时间等维度选取预测运动矢量，建立预测矢量集的思想可以取得较好的预测效果[11]。

具体思路为：在起始搜索点预测之后，为当前块建立一个支持区域上的预测矢量集{MV1,MV2,MV3}，根据预测矢量集的长度信息决定后续的搜索策略，MV1从空间维度选取(中值MV)，MV2从时间维度选取(前帧对应块MV)，MV3为5个预测MV中最优的预测MV(其包含(0,0)MV)，这3个预测MV构成的集合充分利用了运动矢量的时空特性和偏移特性，是预测最佳运动矢量比较有效的基本预测矢量组合。计算预测矢量集中MV的最大长度L，长度信息可由式(1～3)得到

(1)

(2)

(3)

图2 小菱形模板和大菱形模板Fig.2 Search pattern of small diamond and large diamond

条件1 如果L≤1，表明当前编码块的运动状态缓慢，则跳过全局搜索，直接进入小菱形搜索；

条件2 如果1

条件3 如果L>2，表明当前编码块处于快速运动状态，则进入全局搜索。小菱形模板和大菱形模板如图2所示。

2.2 自适应的全局搜索

针对前文分析中提出的问题2，本文采用自适应的全局搜索方法进行改进。一般来说，相邻帧之间的相关性很大，这意味着精确的起始搜索点很有可能就是全局最优点，即使不是全局最优点，那么也有很大可能落入全局最优点的附近。因此在大部分情况下，全局搜索环节只需要进行5×5螺旋方形模板搜索。记准确度最高的两个预测MV的水平分量差和垂直分量差中的最大值为ΔMV，当ΔMV≤3时，可以认为这两个预测MV的差值非常小、起始搜索点的预测非常精确[12]。在这种条件下，可跳过非对称十字型模板搜索和多层次大六边形模板搜索，只进行5×5螺旋方形搜索。ΔMV由式(4)计算

(4)

式中：MV1和MV2分别为准确度最高的两个预测MV，x为MV的水平方向，y为MV的竖直方向。

在5×5螺旋方形搜索中，模板中每个点成为最佳点的概率并不相同[13]，因此本文采用改进的螺旋方形模板搜索：对16×16块取消搜索，对4×4块采用5×5螺旋方形模板搜索，其余尺寸的块均采用3×3螺旋方形模板搜索。

另外，本文根据当前编码块的运动状态为全局搜索过程自适应地选择搜索窗尺寸。搜索窗尺寸(Search range，SR)由式(5)计算[14]

(5)

式中：SADinitial是起始搜索点的SAD值；n1,n2分别为当前块的宽度和高度；Pmax表示配置文件中的搜索窗尺寸；a，b，c均为常量，分别设为1，0.75和0；[·]为取整操作,同时SR不能大于Pmax。

2.3 全零系数块检测

针对在前文分析中所提出的问题3，本文通过提前判定全零系数块来终止没有意义的运动搜索过程。全零系数块是指经过变换和量化之后系数全部变为零的块，对于全零系数块做运动估计不会提高编码效率。因此，如果在运动估计时检测到全零系数块，那么就没有必要搜索更精确的匹配块。

H.264标准采用基于拉格朗日优化算法的率失真优化技术实现对视频编码的控制。率失真优化的关键就是不断计算每个MV对应的Lagrangian编码代价，然后选出代价最小的MV。Lagrangian编码代价定义为

(6)

式中：SAD为当前块和候选块对应像素差的绝对值之和；λ为Lagrangian常数；MV为当前块的运动矢量；PMV为预测运动矢量。

H.264标准采用4×4整数变换对帧内和帧间预测的差值块进行编码[15]，经过整数变换和量化后4×4块内所有系数全部变为零的充分条件为

(7)

式中：xmn为差值块的系数，QP为量化步长。式(7)左边是运动估计时4×4块的SAD值，右边是全零块判决的阈值，如果当前块内所有的4×4块都满足式(7)，说明当前块经过变换和量化后系数全为零，对当前块进行运动估计没有意义。由式(6)可知，如果在预测MV处进行全零系数块的判决，这也是J(M,λ)上的最优判决。

因此，本文在中值预测结束、得到中值PMV之后，计算当前编码的差值块包含的所有4×4块的SAD，并与阈值比较，如果SAD全部小于阈值，那么将MV设成中值PMV，结束运动估计；否则进行正常的运动搜索过程。式(7)中的阈值过小，为了加速运动搜索，经过大量的实验，在综合考虑编码性能和计算复杂度之后，在一定误判率的基础上，将全零块判决的阈值设定为3QP+90[16]。

根据2.1～2.3节的描述，本文算法的流程如图3所示。

3 实验结果与性能分析

3.1 测试平台及其配置

实验计算机的配置如下：处理器为Intel Core 2，主频为2.93 GHz，内存为2 GB，操作系统为Windows

图3 改进算法的流程图Fig.3 Flow chart of improved algorithm

XP。实验软件平台为Visual Studio 2010，测试软件为H.264标准的参考校验模型JM10.2，改进算法用C语言实现。编码器配置采用JM10.2的主类别，主要编码参数设置如下：编码80帧，帧率为30 fps，使能哈达玛变换，运动估计搜索半径为16，参考帧为5帧，熵编码类型为CABAC，帧类型为IBPBP，其他参数为缺省设置。实验中选取了News(QCIF)，Foreman(QCIF)，Coastguard(QCIF)和Waterfall(CIF)4个视频序列作为编码器的输入。其中News代表慢速运动序列，Foreman代表中速运动序列，Coastguard代表快速运动序列，Waterfall代表垂直方向运动远大于水平方向运动的非常规运动序列。

3.2 测试结果与分析

全搜索法(Full search)简记为FS，UMHexagonS算法简记为UMHS，简化的UMHexagonS(Simplified-UMHexagonS)算法简记为S-UMHS，本文改进算法命名为IMP。在同一测试环境下，对这4种算法进行测试，结果如表1所示。表1中，QP(Quantization step)代表量化步长;PSNR(Power signal-to-noise ratio)代表峰值信噪比，BR(Bit rate)代表比特率，ENT(Encoding time)代表编码时间，MET(Motion estimation time)代表运动估计的时间。从表1可以看出，无论对于慢速、中速和快速运动序列，还是对于非常规运动序列，本文算法相比UMHS算法均能够大幅度地减少编码时间和运动估计时间。

表2是本文算法相对于FS算法以及S-UMHS算法的变化情况。由表2可知，相比FS算法，本文算法在PSNR平均减少0.022 dB的情况下，平均节省了79.62%的运动估计时间。相比S-UMHS算法，本文算法除了在慢速运动序列上运动估计的时间有所增加外，在其他序列上运动估计的时间都能取得不同程度的降低。表3是本文算法相对UMHS算法的变化情况以及文献[9]算法相对UMHS算法的变化情况。由表3可知，相比UMHS算法，文献[9]算法平均减少了23.16%的运动估计时间，本文算法平均节省了34.80%的运动估计时间，优于文献[9]算法。另外，文献[9]算法相比UMHS算法在PSNR上的波动性较大(最大0.05 dB)，本文算法在这方面保持了较好的性能。

表1 实验结果记录(QP=28)

表2 本文算法与FS,S-UMHS算法的编码性能比较(QP=28)

表3 本文算法与文献[9]算法的编码性能比较(QP=28)

为了分析本文算法在不同序列上的效果，对News，Foreman，Coastguard三个序列在不同量化步长(QP=24，28，32，36和40)下各编码80帧。在不同序列、不同量化步长的条件下，图4为相比UMHS算法，本文算法IMP在运动估计时间上的下降率。由图中可以看出，相比UMHS算法，本文算法针对运动强度不同的序列，能够减少不同比率的运动估计时间。具体来说，针对运动强度较大的视频序列(如Coastguard)，运动估计时间的下降率在量化步长从24至36的条件下均超过了30%；而对于运动强度较小的视频序列(如News)，运动估计时间的下降率大致分布在20%～30%之间。这是因为，针对运动强度较小的序列，各个预测MV的值以及各预测MV之间的差值均较小，而改进1和改进2主要是根据预测MV及其差值的大小做改进的；因此在运动强度较低的情况下，改进1和改进2所起的作用相对大一些。随着运动强度的增大，预测MV及其差值逐渐增大，满足阈值条件的概率不断下降，改进1和改进2的作用逐渐减小；相应地，改进3所起的作用也就越来越大。改进3中全零系数块的检测建立在一定误判率的基础之上。随着运动强度的增大，改进3所起的作用逐渐增大，在加速运动搜索的同时，全零系数块的误判率也随之增加，这是造成峰值信噪比下降的主要原因。同时，从表1～3等实验数据知，运动强度越大的序列，本文算法与UMHS算法的PSNR之差也越大，这也进一步验证了改进3设定的阈值建立在一定误判率的基础上，在加速运动搜索过程的同时造成了PSNR一定程度的损失。为了进一步比较IMP和UMHS算法的性能，选取运动强度较小的News序列和运动强度较大的Coastguard序列，对每个序列在不同量化步长(QP=24，28，32，36和40)下各编码80帧，分别绘制这两个序列下两种算法的率失真(Rate-distortion，R-D)性能曲线图，如图5，6所示。从图中可以看出，无论对于News序列，还是对于Coastguard序列，这两种算法的率失真性能曲线均相差无几，这表明改进算法在编码质量和编码效率方面损失很小。

4 结束语

在H.264编码器中，运动估计是最耗时的环节之一，其计算复杂度随着编码效率的提高成倍增加，这使得编码器的实时性很难实现。针对这个问题，本文利用预测运动矢量与最佳运动矢量的高度相关性，在起始搜索点的预测、全局搜索和局部搜索等环节适当跳过一些搜索步骤，并更换一些搜索模板，以达到简化搜索的目的；另外，本文还根据整数变换和量化的特性检测全零系数块，提前终止没有意义的运动搜索过程。实验结果表明，在重建图像质量和码率接近的情况下，相比UMHexagonS算法，本文算法平均减少了34.80%的运动估计时间(量化步长为28)。另外，在不同量化步长的条件下，本文算法针对不同运动强度的视频序列均能减少一定比率的运动估计时间，同时率失真性能与UMHexagonS算法相差无几，因此本文算法是一种适合H.264的搜索效率高且编码损失小的快速算法。最后要说明的是，本文改进3——全零系数块的检测环节建立在一定误判率的基础上，在加速运动搜索的同时造成了PSNR一定程度的损失，值得进一步的研究。

[1] Li L, Liu S, Chen Y, et al. Motion estimation without integer-pel search [J]. Image Processing, IEEE Transactions on, 2013, 22(4): 1340-1353.

[2] Wiegand T, Sullivan G J, Bjøntegaard G, et al. Overview of the H.264/AVC video coding standard[J]. Circuits and Systems for Video Technology, IEEE Transactions on, 2003, 13(7): 560-576．

[3] Ko Y H, Kang H S, Lee S W. Adaptive search range motion estimation using neighboring motion vector differences [J]. Consumer Electronics, IEEE Transactions on, 2011, 57(2): 726-730.

[4] Yang L B, Yu K M, Li J, et al. An effective variable block-size early termination algorithm for H.264 video coding [J] . Circuits and Systems for Video Technology, IEEE Transactions on, 2005, 15(6):784-788.

[5] Sarwer M G, Wu Q M J. Adaptive variable block-size early motion estimation termination algorithm for H. 264/AVC video coding standard [J]. Circuits and Systems for Video Technology, IEEE Transactions on, 2009, 19(8): 1196-1201.

[6] Choi C, Jeong J. Extended successive elimination algorithm for fast optimal block matching motion estimation [C] // The Sixth International Conferences on Advances in Multimedia. Nice, France: MMEDIA, 2014: 33-36.

[7] Chen H M, Chen P H, Lin C T, et al. An adaptive macroblock-mean difference based sorting scheme for fast normalized partial distortion search motion estimation [J]. Computers & Electrical Engineering, 2013, 39(5): 1409-1421.

[8] Chen Z, Xu J, He Y, et al. Fast integer-pel and fractional-pel motion estimation for H.264/AVC [J]. Journal of Visual Communication and Image Representation, 2006, 17(2): 264-290.

[9] 李子印，杨齐. 基于运动信息自适应的快速运动估计算法 [J]. 中国图象图形学报，2012，17(9)：1069-1074.

Li Ziyin, Yang Qi. Fast motion estimation algorithm based on motion information adaptation [J]. Journal of Image and Graphics, 2012, 17(9): 1069-1074.

[10] 刘英哲，王进祥. H.264中一种基于搜索范围自适应调整的运动估计算法 [J]. 电子与信息学报，2013，35(6)：1382-1387.

Liu Yingzhe, Wang Jinxiang. Motion estimation algorithm based on adaptive search range adjustment for H.264 [J]. Journal of Electronics & Information Technology, 2013, 35(6): 1382-1387.

[11] Zeng H, Cai C, Ma K K. Fast mode decision for H.264/AVC based on macroblock motion activity [J]. Circuits and Systems for Video Technology, IEEE Transactions on, 2009, 19(4): 491-499.

[12] 吴银花，金龙旭，张宁，等. 针对H. 264改进的快速整像素运动估计算法 [J]. 光学精密工程，2013，21(4)：1017-1025.

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.

[13] 丁燕，宋雪桦，闫述，等. 基于快速运动估计UMHexagonS算法的改进 [J]. 数据采集与处理，2009，24(5)：660-663.

Ding Yan, Song Xuehua, Yan Shu, et al. Improvements of UMHexagonS algorithm based on fast motion estimation [J]. Journal of Data Acquisition and Processing, 2009, 24(5): 660-663.

[14] Ismail Y, McNeely J B, Shaaban M, et al. Fast motion estimation system using dynamic models for H. 264/AVC video coding [J]. Circuits and Systems for Video Technology, IEEE Transactions on, 2012, 22(1): 28-42.

[15] 周欣，段哲民，周巍. 一种适用于H.264/AVC的新型整数变换与量化算法 [J]. 数据采集与处理，2011，26(6)：619-625.

Zhou Xin, Duan Zhemin, Zhou Wei. A new integer transform and quantization algorithm for H.264/AVC[J]. Journal of Data Acquisition and Processing, 2011, 26(6): 619-625.

[16] 方健，郑伟，王匡. 针对 H. 264 的自适应提前终止搜索算法 [J]. 浙江大学学报(工学版),2007，41(4)：411-415.

Fang Jian, Zheng Wei, Wang Kuang. ATETS: Adaptive early termination search algorithm for H.264 [J]. Journal of Zhejiang University(Engineering Science), 2007, 41(4): 411-415.

Improved Method of H．264 Fast Motion Estimation Using Predictive Motion Vector

Guo Jichang, Qiu Linyao，Zhang Xue

(School of Electronic Information Engineering, Tianjin University, Tianjin, 300072, China)

An improved algorithm is proposed based on unsymmetrical cross multi-hexagon grid search(UMHexagonS), which is a fast motion estimation algorithm recommended by H.264. In the prediction link for initial search points, predictive vector sets are established, and the follow-up search strategy is determined according to the length of prediction vector sets. In the global search link, the correlation between prediction motion vectors is used to skip some search steps, and some templates are replaced. In addition, the block of zero coefficients is detected to terminate the motion estimation process in advance, according to characteristics of integer transform and quantization. Experimental results show that, when the quantization step size is 28, the proposed algorithm reduces the motion estimation time by 34.80% compared with the UMHexagonS algorithm, while maintaining the performance. Finally, the algorithm can adapt to video sequences with different motion intensity under different quantization steps, which is a fast motion estimation algorithm with fast speed and good performance suiting for H.264.

video coding; motion estimation; predicted motion vector (PMV); H.264; unsymmetrical cross multi-hexagon grid search

高等学校博士学科点专项科研基金(20120032110034)资助项目。

2015-03-16；

2015-07-10

TN919.81; TP301.6