基于时空预测向量相关性的运动估计算法

2014-09-15王佳利

计算机工程与科学 2014年3期

关键词：菱形非对称象限

王佳利，姜珊，双凯

(中国石油大学(北京)地球物理与信息工程学院，北京 102249)

基于时空预测向量相关性的运动估计算法

王佳利，姜珊，双凯

(中国石油大学(北京)地球物理与信息工程学院，北京 102249)

针对UMHexagonS算法体现出来的问题，利用时间预测向量和空间预测向量的位置映射关系，提出了一种新的运动估计算法——基于时空预测向量相关性的运动估计算法。该算法首先在小范围得到最优点后，继续利用预测矢量的时空方向相关性进行特定方向的扩展搜索，避免了提前落入局部最优点，并减少了搜索点数，从而提高了搜索质量。实验结果表明，与UMHexagonS算法相比，该算法在保持码率基本不变的情况下，能有效地减少运动估计时间，并且能一定程度地提高单帧的峰值信噪比。

视频压缩；运动估计；预测矢量相关性；时空预测向量

1 引言

随着多媒体技术的飞速发展，视频传输、视频点播等需求越来越多，而这些需求的技术支撑都是建立在高效的视频压缩技术之上的。H.264[1]作为当前视频领域广泛使用的压缩标准，是由国际电联(ITU-T)和国际标准化组织(ISO)联合提出的。H.264在运动估计部分也采用了基于块的运动估计算法，但就是将编码帧分成不同大小的块，这些块在参考帧中规定的位置进行搜索，然后利用计算的绝对差值和(SAD)来判断是否可取，最后保存运动矢量(MV)和残差等数据，达到压缩大量数据的目的。当前比较成熟的运动估计快速算法有三步搜索法TSS(Three Steps Search)、对数搜索法TDLS(Two-Dimensional Logarithmic Search)、共轭方向搜索法CDS(Conjugate Direction Search)[2]、四步搜索法FSS(Four Steps Search)[3]、菱形搜索法DS(Diamond Search)[4]、MVFAST(Motive Vector Field Adaptive Search Technique)算法、PMVFAST(Predictive Motion Vector Field Adaptive Search Technique)算法[5]、EPZS(Enhanced Predictive Zonal Search)[6]以及非对称十字多层六边形搜索UMHexagonS(Unsymmetrical cross Multi Hexagon Search)算法[7,8]等。其中，UMHexagonS算法采用多种不同的搜索模板，能适用于运动剧烈程度不同的场景，提高了运动估计的鲁棒性。但是，该算法搜索复杂度很高，特别是非对称六边形搜索需要搜索大量的不相关点，大大加重了处理器的负担，不适用于实时性的场合。本文针对以上问题，利用时间预测向量(当前块对应参考帧中相同位置块的预测MVpre)和空间预测向量(当前块周围宏块的中值预测向量MVmedian)的位置映射关系，提出了一种在小范围得到最优点后，继续利用相关向量的方向性进行扩展搜索的新方法。

2 非对称十字多层六边形搜索(UMHexagonS)算法分析

运动估计中效果最好的算法是全搜索算法，具有最高的精度，但搜索的时间长、运算量大，根本不可能实现实时应用。UMHexagonS是JM(Joint Model)[9]采用的快速算法，该算法相对于全搜索算法能降低90%的搜索运算量，并依然能保持很好的止失真性能，现已经被大多数厂商采用。

该算法的基本流程是：

首先对初始预测搜索点进行单点和上下左右四点的搜索，判断最优点SAD与阈值关系，选择跳出或继续进行如图1中Step-1的非对称十字搜索；接下来进行螺旋搜索，按图1 Step-2所示的25点正方形搜索；下面是在搜索范围内以四为步长，执行如图1中Step-3所示的超六边形模板搜索；最后用多圈的小六边形和小菱形模板(图1 Step-4)搜索得到最终的预测向量。

Figure 1 UMHexagonS search template图1 UMHexagonS搜索模板

从上述UMHexagonS算法流程可以看到，该算法相比DS、TSS和EPZS等算法能很好地避免落入局部最优点，提高了算法的鲁棒性。但是，我们也看到了Step-3和Step-4搜索的点数较多，特别是Step-3中的超六边形搜索具有一定的盲目性，只是不断地扩大全局搜索的范围，用增加搜索点数来换取精度的提高。Step-1搜索后的最优点并非就一定是实际的最优点，因为该算法假设最优点的搜索平面是单调性的，即搜索点的SAD越低，那么该点就离理想最优点越近，而实际上的极值分布只是在小范围内是单调的。针对上述问题，下面利用初始预测向量的时间空间相关性提出一种新的运动估计算法。

3 基于时空预测向量相关性的运动估计算法(CSTPS)

如上文所述，传统的运动估计搜索算法首先找到潜在的初始搜索点，然后利用一定的搜索方法，分别在不同初始点的周围进行搜索。这些算法在初始点之间的搜索是独立的，然而很多时候基于时间和基于空间的预测初始点具有很强的相关性，如果能有效地利用这种相关性来减少搜索的点数、提高搜索的精度，对提高运动估计算法的效率是很有帮助的。本文接下来提出的CSTPS(Correlation of Spatial and Temporal Prediction Vector Search)算法，就是一种利用时空预测向量的相关性，按照图2所示的四种搜索模板进行搜索的新的运动估计算法。

Figure 2 CSTPS search template图2 CSTPS搜索模板

3.1 初始预测点搜索

运动搜索的第一步关键是要找到准确的初始预测点。当前待预测宏块位置MVpic，中值预测向量MVmedian，对应于参考帧中与当前块相同位置的宏块的预测向量MVpre、上层宏块预测向量MVuplayer[6](如公式(1))。以上四个初始预测向量与结果预测向量有很高的相关性，所以本文采用以上预测初始点进行第一步预测。

CSTPS算法首先分别对上述四个预测向量进行初始预测：将每个预测运动矢量和它上下左右四点组成起始搜索矢量组合(如公式(2))，在该组合中搜索最佳预测起点。

S1={MVi|MVi=

MVpic,MVmedian,MVpre,MVuplayer}

(1)

S2={MVj|MVj=(MVi.x±1,MVi.y),

(MVi,x,MVi.y±1)}

(2)

H.264 中定义的匹配误差函数如下：

J(MV,λMOTION)=SAD(s,c(MV))+

λMOTION×R(MV-PMV)

(3)

其中SAD计算公式如公式(4)所示:

c[x-MVx,y-MVy]|,Bx,By=16,8, or 4

(4)

其中，s是当前进行编码的原始数据，而c是已经编码重建的用于进行运动补偿的参考帧的数据。MV为候选的运动矢量，λMOTION为拉格朗日常数，PMV为中值预测矢量，R(MV-PMV)代表了运动矢量差分编码可能耗费的比特数。由于在接下来的四种匹配误差预测方式中，匹配误差中的λMOTION×R(MV-PMV)部分通常很接近而抵消，SAD部分的预测特性基本上可以反映整个匹配函数的预测特性，因此J(MV，λMOTION)可近似用SAD来表示。本文提前终止搜索的标准也使用SAD阈值。

接下来对当前的最优点进行非对称的十字模板搜索(图2 Step-1)。因为自然界中的物体在水平和垂直方向的运动性远远高于其他方向，利用非对称的十字搜索模板，可以较大概率提前获取最优搜索点。

3.2 多层菱形模板搜索

经过非对称的十字模板搜索后，得到当前最优点，接下来利用多层的基于菱形的模板进行搜索，该多层模板如图3所示。在不同层间转换时，进行阈值比较判断是否可以提前退出搜索。运动矢量分布是由香港城市大学Lam Chi-wai提出的[10]，通过对六个不同测试序列使用全搜索方法和MAD匹配，得到平均运动矢量分布概率表。分析得出71.796%左右的运动矢量分布在当前最优点周围半径为2的范围内，而85.388%左右的运动矢量分布在如图2 Step-2所示的范围内。这样在当前最优点的周围进行多层的菱形模板(如图3)搜索时，能以很大概率得到准确的预测点。不同层间转换时加入了提前终止判断，在搜索过程中遇到相对最优点时，提前退出搜索，有效地减少了搜索点数，提高了搜索效率。

Figure 3 Step-2 search template in CSTPS图3 CSTPS的Step-2搜索模板

3.3 基于预测向量相关性搜索

下面利用基于时间和空间预测向量的相关性来继续搜索。这里提到的相关性主要包括两种情况：首先是MVmedian和MVpre映射到同一时空二维平面的绝对距离相关性；其次是MVmedian和MVpre相对于当前最优点的空间象限分布相关性。

如图4a所示，当MVmedian和MVpre距离很近时(如公式(5)，其中MVpre.x代表MVpre相对于当前宏块位置的横坐标，其它变量类似)，那么可以肯定它们之间的相关性很高，这样最优搜索点很可能就在两个预测MV相关区域的周围，而且当距离MVmedian的半径不超过4个像素时，则需重点对这个区域进行搜索。

这时，若非对称十字模板预搜索后得到最优点的SAD高于阈值，那该最优点很可能是局部极值点。尝试直接舍去，而围绕MVmedian继续进行三圈(因为初始点预测时已经搜索了MVmedian点和其周围四点)的菱形模板搜索。每次更换模板的时候要对上次模板搜索后的点进行SAD阈值比较，判断是否提前退出搜索。

|MVpre.z-MVmedian.x|+|MVpre.y-MVmedian.y|<4

(5)

DIRTX=MVpre.x-MVmedian.x

(6)

DIRTY=MVpre.y-MVmedian.y

(7)

SELECTION=

(8)

利用DIRTX和DIRTY的正负值来计算MVpre相对于MVmedian的象限位置。例如，当DIRTX>0和DIRTY≤0时(如图4b所示)，MVpre相对MVmedian在第四象限，这时就采用模板图2 Step-3中的上三角搜索点进行搜索。其他象限的情况类似(如公式(8))，只是将模板图2 Step-3中的上三角搜索点相对原点旋转到不同象限。

Figure 4 MV correlation chart图4 MV相关性图

如果MVmedian和MVpre距离很远(如图5a所示)，则它们的相关性较低。这时候就要加大搜索的复杂度来换取图像效果。当MVmedian和MVpre的位置相对于在多层菱形模板搜索后得到的最优点在同一象限时(以当前最优点为中心划分平面为四个象限)(如图5b所示)，那么就继续对该象限进行三层的5点单象限搜索(如模板图2 Step-3中所有搜索点所示)，共计15个点。当MVmedian和MVpre相对于在多层菱形模板搜索后得到的最优点不在同一象限时(如图5c所示)，那么就要分别对MVmedian和MVpre所在的象限进行三层的5点单象限搜索(如模板图2 Step-3中所有搜索点所示)，共计30个点。

Figure 5 Examples of MV quadrant distribution图5 MV象限分布图例

算法的最后一步采用在搜索范围内进行六边形搜索[11]。按照图2 Step-4，对当前的最优点进行穷尽的六边形搜索，然后用小菱形模板反复搜索，一直到最优点是小菱形的中点，该点就是最终的运动矢量。

3.4 基于时空预测向量相关性算法流程图

本文对CSTPS算法的验证是基于JM18测试模型的，编写了新的CSTPS运动估计算法模块，并且在开始的配置文件中加入该算法选项，而其它基于H.264标准的软件模块保持不变。图6是新编写模块的算法流程图。

Figure 6 CSTPS flowchart图6 CSTPS流程图

4 实验验证

本文实验在PC机上进行，硬件具体参数如下：Intel Core i3-2350 @ 2.30 GHz，3 GB内存，32位Windows 7 旗舰版，Microsoft Visual Studio 2010。实验参考视频测试模型：JM18.0 VC版；实验选取的参照算法是UMHexagonS；六个官方测试视频序列highway_cif.yuv、hall_cif.yuv、foreman_cif.yuv、mobile_qcif.yuv、foreman_qcif.yuv、silent_qcif.yuv；编码器的主要参数如表1所示。

Table 1 Encoder parameters

表2是参考序列在仅改变估计算法而其他参数不变的情况下得到的PSNR、Bitrate、MEtime对比数据。表格和图标中用UMHEX代表UMHexagonS，用CSTPS代表本文提出的算法。

Table 2 Comparison of the data

从表2中可以看到CSTPS算法相对于UMHEX算法，PSNR的提高在0.01～0.03 dB不等，码率的变化在-0.28%～0.26%，MEtime甚至可以减少5%～15%。

图7是针对不同序列的两种算法的MEtime时间的对比，可以从图中直观地看到CSTPS算法对每个序列MEtime都有一定程度的减少，特别对foreman序列最高有15%的下降。

图8是用两种算法对mobile_qcif.yuv，在QT=25情况下，选取200帧的逐帧MEtime对比图。可以看到,CSTPS算法的单帧MEtime相对于UMHEX算法普遍有一定的降低，而不是局部帧的突变，说明CSTPS算法的效率提高具有普遍性。

Figure 7 Comparison of the MEtime图7 MEtime对比

Figure 8 Frame by frame MEtime comparison图8 逐帧MEtime对比

5 结束语

本文研究了当前H.264采用的运动估计算法UMHexagonS，针对该算法的缺点，提出了一种全新的基于时空预测向量相关性进行搜索的运动估计算法CSTPS。经过实验验证，本文提出的算法在很好地保持了运动估计的准确性和图像质量的基础上，有效降低了运动估计的时间，减少了搜索的点数，说明本文提出的CSTPS算法相对于现有算法，可以有效提高H.264的实时性。本文的算法是在PC机上验证的，接下来的工作是将算法优化，实现该算法在DSP上的实时应用。

[1] JVTG050.TRE commendation and final draft international standard of joint video specification[S].ITU-T Rec H.264/ISO/IEC14496-10,2003.

[2] Cheung C, Po L M. A novel cross-diamond search algorithm for fast block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2003,12(12):1168-1177.

[3] Po L M, Ma W C. A novel four step search algorithm for fast block motion estimation[J]. IEEE Transactions on Circuits and System for Video Technology,1996,6(3):313-317.

[4] Tham J Y, Ranganath S, Kassim A A. A novel unrestricted center-biased diamond search algorithm for block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology,1998, 8(4):369-377.

[5] Tourapis A M, Au O C, Liou M L. Predictive motion vector field adaptive search technique(PMVFAST)-enhancing block based motion estimation[C]∥Proc of Visual Communications and Image Processing, 2001:883-892.

[6] Tourapis A. Enhanced predictive zonal search for single and multiple frame motion estimation[C]∥Proc of Visual Communications and Image Processing, 2002:1069-1079.

[7] Chen Zhi-bo, Zhou Peng, He Yun. Fast motion estimation for JVT[C]∥Proc of the 7th Meeting of ISO/IEC, JTCI/SC29/WG11 and ITU-T SG16 Q.6,2003:1.

[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] JM18.0. Reference software of H.264[EB/OL].[2012-04-01].http://iphome.hhi.de/suehring/tml/.

[10] Lam Chi-wai, Po Lai-man.Cheung Chun Ho. A novel kite-cross-diamond search algorithm for fast block matching motion estimation[C]∥Proc of the 2004 International Symposium on Circuits and Systems, 2004:Ⅲ-729-Ⅲ-732.

[11] Zhu C, Lin X, Chau L P. Hexagon-based search pattern for fast block motion estimation[J].IEEE Transactions on Circuits and Systems for Video Technology,2002,12(5):345-355.

WANG Jia-li,born in 1986,MS,his research interest includes information and communication engineering.

姜珊(1967-),女,北京人，硕士，副教授，研究方向为信息与通信工程。E-mail:jiangshan701@163.com

JIANG Shan,born in 1967,MS,associate professor,her research interest includes information and communication engineering.

双凯(1956-),男,北京人，博士，教授，研究方向为信息与通信工程。E-mail:Shuangkai815@163.com

SHUANG Kai,born in 1956,PhD,professor,his research interest includes information and communication engineering.

A motion estimation algorithm based on the correlation of spatial-temporal prediction vector

WANG Jia-li,JIANG Shan,SHUANG Kai
(College of Geophysics and Information Engineering,China University of Petroleum(Beijing ),Beijing 102249)

Using the mapping relationship of the temporal prediction vector and the spatial prediction vector, a new motion estimation algorithm is proposed to solve the shortcoming of UMHexagonS algorithm. In order to avoid the early fall into the local advantages, reduce the search points and improve search quality, it gets the most advantage of the algorithm on a small scale and continues to expand the search for a specific direction of using the directional prediction vector. The experimental results show that, compared with UMHexagonS algorithm, the new algorithm can generally improve the single frame peak signal-to-noise ratio and effectively reduce the time of motion estimation in case of almost the same bit rate.

video compression;motion estimation;correlation of prediction vector;spatial and temporal prediction vector

2012-09-04;

2012-12-20

国家自然科学基金资助项目(61072074)

1007-130X(2014)03-0502-06

TN919.8

10.3969/j.issn.1007-130X.2014.03.022