基于方向信息的快速整像素运动估计优化

熊承义,白 云

(中南民族大学电子信息工程学院,武汉430074)

在视频编码应用,如H.264等视频编码标准中,基于块匹配的运动估计和运动补偿能有效去除序列图像的帧间冗余,使得视频传输的比特数大为减少[1],因而成为视频压缩编码标准的关键部分.全搜索 (FS)算法通过对搜索区域内的所有点进行匹配运算,从而达到全局最佳估计,但是其搜索点数过多,运算量非常大,成为视频编码实时实现的主要瓶颈.多年来,运动估计的快速实现一直成为许多研究者关注和研究的重要问题.

目前,典型的基于块匹配的快速运动估计算法主要有:新3步搜索法(N TSS)[2],4步搜索法(FSS)[3],基于块的梯度下降搜索法(BBGDS)[4],十字搜索法(DS)[5],六边形搜索法(HEXBS)[6]等.这些算法通过限制搜索位置的数目来减少计算量.在相对小的搜索范围和图像尺寸时,这些算法可以达到比较好的效果,但是在搜索步长较大,以及在处理某些大的图像尺寸和较大的搜索范围时,以上快速搜索算法很容易落入局部最小点,从而严重影响编码效率.非对称十字型多层次六边形格点搜索方法(UM H exagonS)[7],结合采用多层次和多模板的搜索技术,在保持较好的率失真性能的同时,它的运算量相对于快速全搜索算法可节省90%以上,因此有效实现运动估计的快速计算.UM HexagonS算法目前已被H.264/AVC标准正式采用.

为了进一步有效地减少运动估计时间,本文在分析运动估计成本的统计分布特征的基础上,提出了一种改进的UM HexagonS算法.通过探索和利用在非对称十字型搜索阶段的运动估计成本的大小及方向信息,自适应地调整原始25点正方形搜索和16点非均匀多层次六边形格点搜索的搜索区域,有效减少搜索点数,节省运动估计的时间.大量实验结果表明,改进的UM H exagonS算法在大大降低编码时间的同时,能有效保持原算法的率失真性能.

1 UM HexagonS算法

UM HexagonS算法的基本思想是采用多层次多种形状的模板进行宏块匹配,同时利用时空相关性进行运动矢量场的预测,搜索时针对不同的运动类型采用了大范围粗搜索混合模板、细搜索中六边形模板和精细搜索十字模板完成搜索[7].该算法率失真性能明显优于其它快速算法,能较好地满足低码率和实时性要求.

UM HexagonS算法的示意图见图1,其实现的4个主要步骤包括.

Step1 起始搜索点预测.

起始搜索点预测是依据待估计块与周边块的时空相关性,利用周边已编码块的运动矢量进行当前块运动矢量的起始点预测.预测模式有4种:中值预测、上层预测、对应块预测、相邻参考帧预测.

Step2 非对称十字型搜索.

由于自然界图像序列在水平方向的运动比垂直方向的运动更加普遍,因此非对称十字型搜索可以比较精确的预测到最佳的运动矢量[8].如图1中Step 2,非对称十字型搜索使用一个水平搜索范围为垂直搜索范围2倍的非对称十字型搜索模式,获得当前块运动矢量的最佳预测起点.

Step3 非均匀多层次六边形格点搜索.

此步分为2个子步骤:如图1中的Step 3-1,以当前最优点为中心,在范围为-2到2的方形区域进行25点的正方形搜索;如图1中的Step 3-2,进行16点非均匀多层次六边形格点搜索.通过利用伸缩系数对六边形进行扩展,可以更好地处理大范围和不规则的运动,避免过早的落入局部最优[9].

Step4 扩展的六边形搜索.

此步分为2个子步骤:如图1中的Step 4-1,以当前最佳点为中心,进行六边形搜索,直至最佳点在六边形的中心时为止;如图1中的Step 4-2,以当前最佳点为中心,进行十字型搜索,直至最佳点在十字型模板的中心时为止.

2 UM H exagonS算法的改进

原始UM H exagonS算法中的Step 3采用了25点的正方形搜索和16点的非均匀多层次六边形格点搜索,其搜索过程并未充分考虑运动估计成本的统计分布特性,因此存在较大的搜索冗余.本文通过分析和探索运动估计成本存在的大小和方向信息,提出一种自适应地搜索技术,有效减少Step 3中的搜索点数,从而实现进一步减少运动估计的时间.

图1 UM HexagonS算法Fig.1 UM HexagonS algo rithm

2.1 运动估计的成本大小与方向分布

将UM HexagonS算法中非对称十字型搜索的预测起始点坐标记为(cen tra l-x,cen tra l-y);将水平方向搜索获得的匹配点的坐标记为(horizon ta lx,horizon ta l-y),最小运动估计成本记为(m costhorizon ta l);将垂直方向搜索获得的匹配点的坐标记为(vertica l-x,vertica l-y),最小运动估计成本记为(m cost-vertica l).将水平与垂直方向上匹配点的运动估计成本进行比较,最小者为当前的最佳匹配点,其坐标记为(best-x,best-y),运动估计成本记为(m cost).horizon ta l为水平方向上与预测起始点的偏移量,vertica l为垂直方向上与预测起始点的偏移量,即:

基于以上定义,将运动估计成本分布分为以下几种情形.

当前的最佳匹配点为水平方向上的匹配点.水平方向上搜索获得的匹配点在X的正半轴,见图2中的实心三角▲;垂直方向上搜索获得的匹配点在Y的正半轴,见图2中阴影三角.此时,运动矢量落在第2象限内的概率最大.

当前的最佳匹配点为水平方向上的匹配点.水平方向上搜索获得的匹配点在X的负半轴,垂直方向上搜索获得的匹配点在Y的正半轴.此时,运动矢量落在第1象限内的概率最大.

当前的最佳匹配点为水平方向上的匹配点.水平方向上搜索获得的匹配点在X的负半轴,垂直方向上搜索获得的匹配点在Y的负半轴.此时,运动矢量落在第4象限内的概率最大.

当前的最佳匹配点为水平方向上的匹配点.水平方向上搜索获得的匹配点在X的正半轴,垂直方向上搜索获得的匹配点在Y的负半轴.此时,运动矢量落在第3象限内的概率最大.

当前的最佳匹配点为垂直方向上的匹配点.水平方向上搜索获得的匹配点在X的正半轴,垂直方向上搜索获得的匹配点在Y的正半轴.此时,运动矢量落在第4象限内的概率最大.

当前的最佳匹配点为垂直方向上的匹配点.水平方向上搜索获得的匹配点在X的负半轴,垂直方向上搜索获得的匹配点在Y的正半轴.此时,运动矢量落在第3象限内的概率最大.

当前的最佳匹配点为垂直方向上的匹配点.水平方向上搜索获得的匹配点在X的负半轴,垂直方向上搜索获得的匹配点在Y的负半轴.此时,运动矢量落在第2象限内的概率最大.

当前的最佳匹配点为垂直方向上的匹配点.水平方向上搜索获得的匹配点在X的正半轴,垂直方向上搜索获得的匹配点在Y的负半轴.此时,运动矢量落在第1象限内的概率最大.

2.2 25点正方形搜索改进

运动矢量有超过80%的概率是落在以(0,0)为中心,半径为2的圆内[10].这也是UM H exagonS算法要在Step 3-1中采用25点正方形搜索的基本原因.在UM HexagonS算法中Step 3-1中以最佳预测起始点为中心,进行25点的正方形搜索.本文提出的算法是根据非对称十字型搜索获得的运动估计成本的不同分布情况自适应选择搜索区域.图3为在mcost=mcost-horizon ta l,horizon ta l＞0,vertica l＞0的条件下的搜索区域自适应选择示意图.图3中实心三角▲为经过非对称十字型搜索获得当前最佳预测起始点,为垂直方向预测的最佳点.由于此阶段的运动矢量落在第2象限内的概率最大,因此调整运动矢量搜索为只对图中的7个空心圆对应点进行搜索匹配.由于避免了搜索其它实心圆●对应点,因此有效减少了运动估计的时间.在运动估计成本分布在(1)～ (8)情况下的搜索示意图分别见图4中(a)～(h).

图2 运动矢量分布区域示意图Fig.2 M E vecto r distribu tion location

2.3 16点非均匀多层次六边形格点搜索的改进

在UM HexagonS算法中,Step 3-2以最佳预测起始点为中心,进行多层次六边形格点搜索.同样基于以上在非对称十字型搜索阶段得到的运动估计成本分布的不同,提出自适应地选取对应六边形搜索点的方法如下.图5给出了在mcost=mcosthorizon ta l,horizon ta l＞0,vertica l＞0的条件下的六边形搜索点选择示意图.图中的实心三角▲为Step 2非对称十字型搜索获得最佳预测点,阴影三角为垂直方向预测的最佳点.此步搜索也调整为只对图5中4个空心矩形点 对应点进行搜索.同样由于避免搜索其它实心矩形点对应点,从而有效的减少了运动估计的时间.图6中(a)～ (h)分别给出了在运动估计成本在(1)～ (8)分布情况下多层次六边形格点第一层的搜索点选择,其它扩展层同样按此规律进行搜索.

图3 正方形搜索区域的自适应选择示意图Fig.3 Search po intso f square search

图4 不同运动估计成本分布情况下正方形搜索区域选择示意图Fig.4 Search po intso f square search under differentM E cost distribution

图5 非均匀多层次六边形格点搜索点选择示意图Fig.5 Search po in tsofm u lti-hexagon-grid search

图6 不同运动估计成本分布情况下非均匀多层次六边形格点搜索点选择示意图Fig.6 The search po in tsofm u lti-hexagon-g rid search under differentM E cost distribution

3 实验结果及分析

为了验证本文算法的有效性,基于H.264参考代码JM 12.2对该算法的性能进行了大量的比较实验.实验采用的主要测试条件见表1,其它参数的设置采用JM 12.2版本中的默认值.采用的测试序列描述见表2.本文提出的算法在选取Q P分别为8,18,28,38下进行测试,并与UM H exagonS算法进行比较.为了避免PC运行不稳定的影响[11],本文将同一个序列,在相同条件下,进行20次实验,取其平均的整像素运动估计的时间减少的百分比来比较速度,采用信噪比下降的大小和码率上升的百分比来比较算法的率失真性能.

表3～8给出了在不同尺寸、格式的测试序列的条件下本文算法与原始UM HexagonS算法的性能比较结果.从表9比较结果可见:不同的Q P值下均能较好的保证原有UM HexagonS算法的码率失真性能.表10结果表明:不同测试序列在Q P为8,18,28,38时,运动估计时间平均节省32.85%,PSNR平均上升约0.002dB,码率平均增加约为0.25%.测试结果表明,对于不同测试序列其运动估计时间的减少幅度是不同的,主要原因在于视频场景运动变化的激烈程度不同所造成的.其中对运动复杂的序列M ob ile有更好的效果:运动估计时间平均下降了42.36%.由于M ob ile运动场景的相对激烈导致了运动估计成本门限判断一直不符合提前终止条件,因此几乎执行了改进后算法中的所有步骤,运动时间也就下降更多.

由以上实验结果表明,在不同的Q P、图像尺寸、运动复杂度的情况下,改进后的算法都能够很好地适应,并保持了原始UM H exagonS算法的率失真和码率等性能.

表1 测试条件Tab.1 Testing conditions

表2 测试序列描述Tab.2 Descip tion o f test video sequences

表3 Silen t序列在不同QP值下的性能Tab.3 R-D Pefo rm ance under d ifferen tQP(Silen t)

表4 N ew s序列在不同QP值下的性能Tab.4 R-D Pefo rm ance under differen tQP(N ew s)

表5 Fo rem an序列在不同QP值下的性能Tab.5 R-D Pefo rm ance under d ifferen tQP(Fo rem an)

表6 Paris序列在不同QP值下的性能Tab.6 R-DPeformanceunderdifferentQP(Paris)

表7 Mobile序列在不同QP值下的性能Tab.7 R-DPeformanceunderdifferentQP(Mobile)

表8 Tempete序列在不同QP值下的性能Tab.8 R-DPeformanceunderdifferentQP(Tempete)

表9不同QP值下的性能比较Tab.9 R-DPeformanceunderdifferentQP

表10 各种不同测试序列的性能比较Tab.10 R-DPeformanceunderdifferentsequence

4 结语

提出了一种改进的UMHexagonS算法.基于运动估计的成本大小和方向性信息,自适应地调整原算法中的25点正方形搜索和16点非均匀多层次六边形格点搜索的搜索区域,有效地实现减少运动估计的搜索点数.测试结果表明,对于不同运动变化的序列以及在选取不同QP时,改进后的算法在保证率失真性能的同时,能节省大约23%～42%的整像素运动估计时间.

[1] W uegand T,Su llivan G.O verview o f the H.264/AVC video cod ing standard[J]. IEEE T ransactions on C ircu its and System fo r V ideo Techno logy,2003,13(7):560-576.

[2] L iR,Zeng B,L iou M L.A new th ree-step search algo rithm fo r b lock m o tion estim ation[J]. IEEE T ransactions on C ircuits and System fo r V ideo Techno logy,1994,4(4):438-442.

[3] Po LM,M aW C.A novel fou r-step search algo rithm fo r fast b lock m atch ing[J]. IEEE T ransactions on C ircuits and System fo r V ideo Techno logy,1996,6(3):313-317.

[4] L iu L K,Feig E.A b lock based g radien t descen t search algo rithm fo r b lockm o tion estim ation in video cod ing[J]. IEEE T ransactions on C ircuits and System fo r V ideo Techno logy,1996,6(4):419-422.

[5] Zhu S,M a K K.A new d iam ond search algo rithm fo r fast b lock m atch ing m o tion estim ation[J]. IEEE T rans Im age Processing,2000,9(2):287-290.

[6] Zhu C,L in X,Chau L.Hexagon-based search pattern fo r fast b lock m o tion estim ation [J]. IEEE T ransactions on C ircuits and System fo r V ideo Techno logy,2002,12(5):349-355.

[7] Zhibo C H,Peng Z H,Yun H.Fast in teger pel and fractionalpelm o tion estim ation in fo r JV T[A].Jo in t V ideo Team (JV T)o f ISO/IEC M PEG&ITU-T VCEG,Aw aji,2002.

[8] 夏金祥,黄顺吉.基于VOP的块特性的自适应十字搜索模式运动估计法[J].通信学报,2005,26(8):117-121.

[9] 李 荣,张其善,杨东凯.基于方向自适应菱形搜索的运动估计算法[J].北京航空航天大学学报,2008,34(9):1065-1069.

[10] L in C C,L in Y,H sieh H J.M u lti-d irection search algo rithm fo r b lock m o tion estim ation in H.264/AVC[J]. IEEE T rans Im age Processing,2009,3(2):88-99.

[11] Xu X Z,He Y.Im p rovem en tson fastm o tion estim ation strategy fo r H.264/AVC[J].IEEE T ransactions on C ircuits and System fo r V ideo Techno logy,2008,18(3):285-293.