一种快速整像素运动估算算法研究

肖敏连

(湖南人文科技学院 计算机科学技术系,娄底 417000)

一种快速整像素运动估算算法研究

肖敏连

(湖南人文科技学院 计算机科学技术系,娄底 417000)

在对已有快速整像素运动估计算法中使用的模板进行分析和实际测试的基础上，提出了一种新的适合于大运动矢量搜索的搜索模板，然后把该模板和小菱形模板结合起来而形成了一种新的快速运动估计算法。该算法充分利用了相邻块运动矢量的相关性以及运动矢量的中心偏置特性，显著减少了运动估计的运算量。把该算法运用到视频编码标准H.264/AVC中，取得了良好的编码效果，实验结果表明，新的运动估计算法和FS及DS算法相比平均搜索速度分别提高了98.08%和48.71%；重建图像的信噪比比DS算法平均提高了0.001875dB ，更接近FS算法的编码质量。

视频编码；运动估计；模板

运动估计与补偿技术是视频编码中一个非常重要的组成部分，利用该技术可以有效去除视频序列相邻帧间存在的时间冗余，极大地提高编码效率[1]。块匹配运动估计算法(BMME，Block-Matching Motion Estimation)是目前应用最广泛的一种运动估计算法，它已被许多视频编码标准所采纳，如MPEG-1/2/4、H.261、H.263及H.264/AVC等等[2, 3]。最基本的块匹配算法是全搜索(FS，Full Search)算法，虽然它能通过对搜索范围内所有的点进行搜索而找到最佳匹配点，但其计算量非常巨大。为了加快运动估计速度，多年来许多研究人员对此进行了大量的研究，提出了多种快速的块匹配算法，这些算法可以归为三类：(1)通过减少搜索点数的快速算法；(2)快速块匹配误差计算方法；(3)运动场下采样方法，其中第一类是最常用的快速搜索算法[4]。

在第一类快速搜索算法中，一般是通过使用一定的模板来完成对最佳运动矢量的搜索，如二维对数下降法(TDLs，Two-Dimensional Logarithmic Search)[5]在搜索过程中使用了“十”字交叉形模板；交叉搜索法(CSA，Cross Search Algorithm)[6]、动态窗口搜索算法(DSWA，Dynamic Search-Window adjustment and interlaced search)[7]通过使用“X”形交叉和“十”字形交叉模板来完成对最佳运动矢量的搜索；三步法(TSS, Three-Step Search)[8]、新三步法(NTTS, New TTS)[9]、四步法(4SS，Four-Step Search)[10]、基于块的梯度下降搜索算法(BBGDS，Block-Based Gradient Descent Search)[11]使用的都是正方形模板，钻石法(DS，Diamond Search)使用了大钻石和小钻石模板[12, 13]；在基于六边形的快速块运动估计算法中使用了六边形模板[14，15]；在基于八边形的快速运动搜索算法使用了八边形模板[16]；而一些改进的快速算法往往是不同模板的综合使用，如基于中心偏置的混合块匹配算法(CBHS，Center-biased Hybrid Search)算法[17]中综合使用了“X”形交叉模板与钻石模板；交叉——钻石算法(CDS，Cross Diamond Search)及其改进算法[18, 19, 20]综合使用了“十”字交叉模板与钻石模板；正方形——菱形搜索(SDS，Square-Diamond Search)算法[21]、PCP(Prediction and Combinative Pattern )算法[22]及文献[4]综合使用了正方形与钻石模板等等。

纵观各种在快速算法中使用的模板，可以分为两类，(1)适合于对静止或小运动矢量进行准确定位的模板，如小钻石模板(SDSP，Small Diamond-Shaped Pattern)、步长为1的正方形模板(SSP，Square-Shaped Pattern)、步长为1的“X”形交叉及“十”字交叉模板等。(2)适合于对大运动矢量进行粗定位的搜索模板，如八边形模板(OSP，Octagon-Shaped Pattern)、六边形模板(HSP，Hexagon-Shaped Pattern)、大钻石模板(LDSP，Large Diamond-Shaped Pattern)、步长大于1的正方形模板、步长大于1的“X”形交叉及“十”字形交叉模板等。从目前的发展趋势来看，新的快速运动估计算法一般都会综合使用两类搜索模板以适应对具有不同运动水平的视频序列进行快速的运动估计。

本文在对各种模板进行的分析与测试的基础上，提出了一种新的适宜于进行大运动矢量粗定位的模板——三角形模板(TSP, Triangular-Shaped Pattern)，该模板充分利用了前面的搜索结果，是一个简化了的正方形模板，因此，其特性与正方形模板相似，但比正方形模板少了2个搜索点，因此它比正方形模板的搜索速度更快。把三角形模板和小钻石模板结合起来，就可以形成一种新的快速运动搜索算法——基于菱形——三角形模板的快速运动估计算法(DTS，Diamond-Triangular Search)，我们把该算法运用到最新的视频编码标准H.264/AVC中，实验结果表明，和DS算法相比，DTS算法具有更快的搜索速度和更好的编码性能。

本文第二部分介绍了运动矢量的相关性及中心偏置特性，第三部分介绍基于菱形——三角形模板的快速运动估计算法，第四部分给出了实验结果并进行了分析，最后给出了结论。

1 运动相关性及运动矢量的中心偏置特性

图1 最优点分布规律

一些新的快速运动估计算法如DS等都是基于运动相关性及运动矢量的中心偏置特性提出来的，所谓运动相关性是指图像序列中一帧图像内的不同部分之间以及相邻图像之间运动的相似性。图像的全局运动造成不同块之间运动的空间相关性；由于运动在时间上的连续性，相邻帧图像之间的运动具有相似性，称为运动的时间相关性。这就意味着可以利用相邻块的运动矢量来预测当前块的搜索起点[22, 23]。而所谓的运动矢量的中心偏置特性是指图像序列中绝大多数运动矢量都是集中在(0，0)点附近，如S. Zhu和K.K. Ma在文献[13]中指出运动估计的最优点通常分布在以搜索中心为圆心，两象素为半径的圆内(如图1所示)。

许多的研究工作[4, 12, 13, 18-23]都说明了在运动估计中可以充分利用运动的相关性及运动矢量的中心偏置特性来加快搜索的速度,本文也将利用了这些特性来加快DTS算法的运动估计速度。

2 基于菱形——三角形模板的快速运动估计算法

根据以上分析，本文提出了一种基于菱形-三角形模板的快速运动估计算法DTS，该算法有以下几个技术要点，首先是通过相邻块来对待编码块进行运动预测，形成初始搜索中心；其次，利用率失真优化作为块的匹配准则，并且利用可切换的模板来适应对不同的视频序列进行编码的需要，分别详述如下。

2.1根据相邻块预测起始搜索点

图2 块的相邻关系

前面已经指出，可以根据相邻块的运动信息来预测待编码块的运动矢量。H.264/AVC中块的相邻关系如图1所示。由于H.264/AVC的帧间编码允许有16×16、16×8、8×16、8×8、8×4、4×8、4×4等7种不同的块大小编码模式，假设E是当前的待编码块，A、B、C、D分别表示其左侧、上侧、右上侧及左上侧的相邻块，显然，A、B、C、D、E各块的大小不一定都相等，为了保证预测的准确性，通常取左侧(A)、上侧(B)及右上侧(C)的最小块(也即4×4)所对应的运动矢量的中值作为待编码块E的预测运动矢量，因为块E的运动矢量与其最临近的象素的运动矢量最相近。如果块A、D不在当前编码的图像片层(slice)里，则在求中值时块A的运动矢量被0取代；如果块D、B、C不在当前编码的图像片层里，则把块A的运动矢量作为块E的预测运动矢量；如果块C不在当前编码的图像片层里，或者说虽然在当前编码片层里，但由于编码的顺序问题尚没有被编码，就用块D的运动矢量来代替块C的运动矢量后再求中值；而如果块A、B、C都不在当前编码的图像片层时，则由上一预测帧中同一位置块所对应的运动矢量作为待编码块的预测运动矢量。

2.2使用率失真优化作为块匹配准则

传统的快速块匹配算法中在确定最佳匹配块时其使用的块匹配准则往往只考虑了参考块和待编码源块的绝对误差和(SAD，Sum of Absolute Differences)：参考帧中那个和源块的SAD值最小的块就是最佳的匹配块，其对应的运动矢量就是最佳运动矢量。但是，通过研究，我们发现：在实际的编码过程中，SAD值最小所对应的块不一定真正就是最好的匹配块，因为当运动矢量很大时，即使SAD值非常小，只需要很少的二进制位就可以表示下来，但对大运动矢量的编码势必要占据很多的二进制位，所以，假如运动矢量很大，即使匹配很准确，从编码效率的角度来说不一定就是最好的，正是基于这样的考虑，在进行块匹配搜索时，应该从SAD值和对运动矢量差值进行编码所需使用的二进制位数两方面来综合考虑，而事实上一些视频编码标准在进行运动搜索时也正是这样考虑的，如H.264/AVC中的最佳块匹配运动矢量，就是在所有的候选运动矢量中使式(1)达到最小值的那个候选运动矢量[24]：

J(m,λMOTION)=SAD(s,c(m))+λMOTIONR(m-p)

(1)

式中J(m,λMOTION)为总的运动估计耗费值；m=(mx,my)T为候选运动矢量；p=(px,py)T为预测运动矢量；λMOTION是拉格朗日(Lagrange)乘数因子，它和待编码块所在的片层(slice)编码类型(如P_slice，B_slice等)及量化参数QP有关；R(m-p)为表示运动矢量差值(候选运动矢量-预测运动矢量)所需的二进制位数；而SAD(s,c(m))的定义则如式(2)所示。

(2)

式中s表示待编码的源视频信号，c表示参考帧中已解码的视频信号。

使用基于率失真的块匹配准则不仅在编码效率方面具有更大的优势，而且可以加快编码的速度，因为对于一些很大的候选运动矢量，其λMOTIONR(m-p)部分的值往往已经很大，如果它超过了前面已经得到的最小运动耗费值，那么这个候选运动矢量立即可以淘汰，因此，对这一块的SAD值的计算自然也就不用再进行了，从而可以节省大量的编码时间。

2.3综合使用菱形、三角形模板完成最佳运动矢量的搜索

图3 小菱形模板

我们知道，搜索模板的形状和大小将直接影响搜索的速度和性能，好的搜索模板应该在不陷入局部最优的条件下尽可能减少搜索点数。考虑到视频对象在水平和垂直方向上的运动概率比较大，所以本文选用了如图3所示的小菱形模板(SDSP)来完成对小运动矢量的聚焦搜索；对于大运动矢量的搜索，目前趋向于使用正方形模板，这主要是因为正方形模板搜索点数较少且具有良好的向外扩展性[4, 20, 21]。

图4 三角形模板

为了更进一步减少搜索点数，同时又不影响搜索结果的准确度，本文通过分析各种模板的特点以及进行大量的测试实验之后，提出了一种新的大运动矢量搜索模板：三角形模板(TSP， Triangular-Shaped Pattern)，如图4所示。该搜索模板充分利用了前面的搜索结果，既保持了正方形模板的向往扩展特性，又比正方形模板减少了2个搜索点，从而可以获得比正方形模板更快的搜索速度。

为了能以最快的速度加快完成对小运动块的搜索，DTS算法首先使用菱形模板进行聚焦，如果初始搜索中心点就是最佳匹配点，则搜索一步结束；如果最佳匹配点不在中心点，则根据所得到的最小SAD值判断运动矢量差值的大小：SAD小于判决阈值TH的，说明运动矢量差值已经很小，只需按菱形模板继续搜索就可以找到最佳匹配点；否则为大运动矢量，根据上一步MMC点所处的位置选择一个以中心点为顶点，包含了上一步MMC点在内的三角形模板来对继续对是否需要进行大运动矢量搜索作出判断：如果MMC点位于中心点周围菱形的四个顶点上，则说明是小运动矢量，把当前的MMC点作为新的搜索中心后继续使用菱形模板进行聚焦搜索，直到找到最佳匹配点；而如果最佳匹配点位于三角形的2个顶点上，则说明是大运动矢量，把当前的MMC点作为新的搜索中心点后继续进行由小到大的判断搜索，以后不断重复这一过程，直到找到最佳运动矢量为止。

按视频图像运动矢量的统计规律，假设最佳点就在图1所示的圆内，对DS[13]、SDS[20]、PCP[21]和DTS四种算法需要检测的点数进行比较，如表1所示，从表中可以看出， DTS算法比PCP算法少0～2个搜索点，比SDS算法总少2～4个搜索点，比DS算法总少5～8个搜索点。

DS、SDS及DTS对最佳匹配点(-4，-2)的可能搜索路径分别如图5[12]、图6[20]和图7所示，其中DS算法需要五步，使用了四次LDSP和一次SDSP，总共搜索了24个点；SDS算法需要四步，使用两次SDP(Square-Diamond Pattern)和两次SDSP，总共22个点；DTS算法需要五步，使用一次TSP和四次SDSP，每一步检测的新点数分别为5，2，4，3，3，总共17个点，可见DTS算法的搜索速度比DS和SDS算法都有较大的提高。

表1 DS、SDS、PCP与DSS在零矢量周围的搜索点数比较

图5

图6

图5:用DS算法搜索到(-4，-2)的可能路径,共24个点;

图6 用SDS算法搜索到(-4，-2)的可能路径，共22个点

图7 用DTS算法搜索到(-4，-2)的可能路径，共17个点

2.4算法的具体实现步骤

DTS算法的实现较为简单，下面给出其具体实现步骤：

Step1 以预测运动矢量所在位置作为当前块搜索的起始点(即作为SDSP的中心)，在SDSP上5个点处分别进行匹配计算，找出MMC点(Min-Motion Cost，最小运动耗费值)，若MMC点位于中心，说明预测运动矢量就是最佳运动矢量，DTS算法一步结束，进行Step4；若MMC点不在中心，则对其SAD值进行判断，如果小于判决阈值T1，说明运动矢量差值已经很小，可以在小范围里进行聚焦搜索即可找到最佳匹配点，转step3；否则进行step2。

Step2 分别对以中心点为顶点的包含上一步MMC点在内的等腰三角形底边上的2个顶点处进行匹配计算，找出新的MMC点，若MMC点位于菱形的顶点上，说明运动矢量差值已经很小，转step3，否则以上一次找到的MMC点作为中心点，进行与step1相同的运算。

Step3 以上一次找到的MMC点作为中心点，对SDSP上尚没有搜索过的点进行匹配计算，找出新的MMC点，若MMC点是中心点，说明最佳匹配点已经找到，进行step4；否则重复step3。

Step4 运动搜索结束，以该中心点作为最佳匹配点，得到最佳运动矢量。

本算法与DS算法一样，对搜索的步长及搜索范围均没有限制，是因其收敛性是有保证的，但是我们也注意到，一般的视频编码标准都会对最大的运动搜索范围作出限制，以免造成运动矢量编码部分占据太多的码字，所以在算法的实现中我们也加入了边界约束条件。

3 实验结果与分析

为了便于比较基于菱形-三角形模板的DTS算法对运动估计的加速效果，在H.264/AVC参考平台JM7.6的基础上，对不同的测试序列进行了一系列的测试，这里选取其中4个具有不同运动水平的视频序列，其中Akiyo和Foreman序列的运动较为简单，而Mobileamp;Calendar和Coastguard序列的运动则较为复杂 ；量化参数(QP)选取20、28，34，40；帧间采用全部7种块搜索模式；运动搜索范围为33×33矩形窗(即在初始搜索中心点周围±16个整象素范围内)，参考帧数为2，采用率失真优化算法及CABAC编码。为了突出DTS算法与其它算法的比较效果，在所有的测试序列中，只有第一帧被编码为I帧，其它的帧都被编码为P帧，且在P帧的编码中取消了帧内编码选项(即P帧中只有帧间编码的块，而不会有帧内编码块存在)。经过实验一个4×4亮度块的小运动矢量判决阈值TH确定为10Qstep(Qstep为与量化参数QP有关的一个常数)。

表2—5是本文算法(DTS)与FS及DS算法实验结果的比较，这里比较了搜索点数、SAD计算点数、重建图像峰值信噪比(PSNR)和P帧中平均每个象素所用的编码位数。凡是被计算过全部(SAD(s,c(m))+λMOTIONR(m-p))或部分(λMOTIONR(m-p))运动耗费值的点都被称作搜索点，表中的搜索点数是指每个块的平均搜索点数；SAD计算点数是指在搜索过程中每个块的计算了全部运动耗费值的平均搜索点数，其值通常会比平均搜索点数要小，这是由于在运动搜索时使用了率失真优化这一匹配准则而引起的：那些运动矢量偏大的候选运动矢量由于其λMOTIONR(m-p)部分的值已经超过了当前的最小运动耗费值而必须被舍弃掉，因此再对这些点求SAD值已没有必要，从而可以大大加快编码的速度。

从表2—中可以看出， DTS算法每个块的平均搜索点数和SAD计算点数均只有DS算法的一半左右，虽然有个别信噪比比DS算法略低的情况出现，但如果我们观察一下P帧中平均每象素所用的编码位数就可以知道，DTS的编码效率比DS算法高，且与FS算法的编码效率比较接近。对于所有的测试序列，DTS算法的搜索速度比FS算法平均提高了98.08%，比DS算法平均提高了48.71%；DTS算法中的信噪比比FS算法平均下降0.04875dB，比DS算法平均提高0.001875dB。

表2 Foreman(30fps/100frames)序列的实验结果

表3 Akiyo(30fps/150frames)序列的实验结果

表4 Mobile(30fps/250frames)序列的实验结果

表5 Coastguard(30fps/300frames)序列的实验结果

4 结束语

本文在对已有快速算法中的模板进行分析和实际测试的基础上，提出了一种新的适合于大运动矢量搜索的搜索模板――三角形模板，并把该模板和小菱形模板结合起来而形成了一种新的快速运动估计算法――DTS算法，该算法在性能上和SDS算法相近，但速度比SDS算法稍快，和DS算法相比在速度上体现了较大的优势，而编码效率则只是略有提高，总的来说，该算法是一个相当快速的近似最优运动估计算法，可广泛应用于各种实时的视频编码中。

[1]沈兰荪，卓力，等.视频编码与低速率视频传输[M].北京：电子工业出版社，2001:56.

[2] RAO K. R., HWANGJ. J. Techniques and standards for Image, video and audio coding[M]. Englewood Cliffs, NJ: Prentice Hall, 1996:126.

[3]WIEGAND T, SULLIVAN G. Joint video team (JVT) of ISO/IEC MPEG and ITU-T VCEG. Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification(ITU-T Rec. H.264|ISO/IEC 14496-10 AVC)[S].document JVT-G050d35.doc,7th Meeting: Pattaya, Thailand, March,2003.

[4]薛金柱，沈兰荪.一种基于H.264/AVC的高效块匹配搜索算法[J].电子学报，2004，32(4)：583-586.

[5]J. JAIN, A. JAIN. Displacement measurement and its application in interframe image coding [J]. IEEE Trans.Commun., 1981,29:1799-1808.

[6]M. GHANBARI. The cross-search algorithm for motion estimation[J]. IEEE Trans. Commun., vol. 38, pp.950-953, July 1990.

[7]LEE L. W, WANG J. F, J. Y. LEE, and J. D. SHIE. Dynamic search-window adjustment and interlaced search for block-matching algorithm[J]. IEEE Trans. Circuits Syst. Video Technol., vol. 3, pp. 85-87, Feb. 1993.

[8]T. KOGA, K. IINUMA, A. HIRANO, Y. LIJIMA etal. Ishiguro, “Motion compensated interframe coding for video conferencing,” in Proc. Telecommun. Conf., New Orleans, LA, Nov. 29-Dec. 3 1981, pp. G5.3.1-G5.3.5.

[9]LI R, ZENG B, and LIOU M. L. A new three-step search algorithm for block motion estimation[J]. IEEE Trans.Circuits Syst. Video Technol, vol. 4, pp. 438-442, Aug. 1994.

[10]Po L. M, MA W. C. A novel four-step search algorithm for fast block motion estimation[J]. IEEE Trans. Circuits Syst. Video Technol, 1996(6):313-317.

[11]LIU L. K, Feig E. A block-based gradient descent search algorithm for block motion estimation in video coding[J]. IEEE Trans. Circuits Syst. Video Technol, 1996(6):419-423.

[12]THAM J. Y, Ranganath S, M. Ranganath, et al. A novel unrestricted center biased diamond search algorithm for block motion estimation[J]. IEEE Trans. Circuits. Syst. Video Technol, 1998(8):369-377.

[13]ZHU S. and MA K K. A new diamond search algorithm for fast blockmatching motion estimation[J]. IEEE Trans. Image Processing, vol. 9, pp.287-290, Feb. 2000.

[14]Ce Zhu, Xiao Lin, et al. Hexagon-based search patter for fast block motion estimation [J].IEEE Transactions on Circuit and Systems for video technology, 2002, 12(5):349-355.

[15]Zhibo Chen, Peng Zhou, et al. Fast Integer Pel and Fractional Pel Motion Estimation for JVT[S]. JVT-F017.doc. 6th Meeting: Awaji, Island, JP, December, 2002.

[16]L. P. Chau, C. Zhu. A fast octagon-based search algorithm for motion estimation [J]. Signal Processing 2003,83:671-675.

[17]SHIN SC, BAIK H, et al. A center-biased hybrid search (CBHS) method for block motion estimation [C]. Proceeding of the fifth International Conference on Computer Science and Informatics, March 2000, Atlantic City, New Jersey:

[18]CHEUNG C H, PO L M. A novel cross-diamond search algorithm for fast block motion estimation [J]. IEEE Transacitons on Circuits and systems for video technology, 2002, 12(12):1168-1177.

[19]CHEUNG C H, PO L M. A novel small-cross-diamond search algorithm for fast video coding and videoconferencing applications [C]. IEEE ICIP 2002, Vol.1:681-684.

[20]LAM C W, PO L M, et al. A new cross-diamond search algorithm for fast block matching motion estimation [C]. IEEE Int.Conf. Neural Networks amp; Signal Processing, Nanjing, China，2003：1262-1265.

[21]刘海峰，郭宝龙，等. 用于块匹配运动估值的正方形：菱形搜索算法[J].计算机学报，2002，25(7)：747-752.

[22]向友君，郭宝龙.基于起点预测的快速运动估计算法[J].西安电子科技大学学报：自然科学版，2003，30(3)：386-390.

[23]李炜，乐立鸾，等. 基于起点预测和SAD分布的快速运动估计算法[J].计算机学报，2001，24(10)：1110-1114.

[24]G. SULLIVAN, T. WIEGAND, K.P. Lim: Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG. Joint Model Reference Encoding Methods and Decoding Concealment Methods[S], document JVT-I049d0.doc, San Diego, USA, September, 2003.

(责任编校：光明)

ResearchonaFastIntegerPixelMotionEstimationAlgorithm

XIAOMin-lian

(Department of Computer Science and Technology, Hunan Institute of Humanities, Science and Technology, Loudi 417000, China)

Based on the analysis of patterns used in some fast algorithms for motion estimation and a great deal of tests about those patterns, a new search pattern was proposed in this paper. By combing the proposed search pattern with small diamond search pattern, a simple, fast and efficient integer pixel motion estimation algorithm was proposed in this paper. The proposed algorithm exploits the center-biased characteristic of motion vector and the correlation of motion between those adjacent blocks to decrease the computing of motion estimation greatly. The proposed algorithm achieves expected encoding effect when it is used in the video coding standard H.264/AVC. Experiment results indicate that the proposed algorithm provides PSNR 0.001875dB gain compared to DS and is closer to that of FS with speedup ratio of 98.08% and 48.71% on average compared to FS and DS respectively.

video coding; motion estimation; pattern

2011-03-21.

湖南省科技厅科研条件与创新专项(No. 2010TC2006)，湖南省教育厅科技项目(No. 09A046,11C0701),娄底市科技计划项目.

肖敏连(1969— )，女，湖南涟源人，湖南人文科技学院计算机科学技术系实验师，研究方向：视频编码。

TP391

A

1673-0712(2011)05-0129-05