基于SAD优化的运动估计搜索算法研究

易　葵,肖旭青

(1.中航工业南方航空工业(集团)有限公司机动分公司，湖南　株洲　412002；2.株洲市发展和改革委员会，湖南　株洲　412007)



基于SAD优化的运动估计搜索算法研究

易葵1,肖旭青2

(1.中航工业南方航空工业(集团)有限公司机动分公司，湖南株洲412002；2.株洲市发展和改革委员会，湖南株洲412007)

摘要：基于对运动估计SAD匹配准则缺陷和码量分配原理的分析，本文提出了针对影响运动估计效率的三个主要因素：搜索中心预测、匹配准则和搜索策略，提出了自适应双十字-钻石-六边形搜索算法。实验结果表明，该算法在失真度基本保持不变的情况下，搜索速度比MVFAST要提高78%，比PMVFAST要提高5.1%。

关键词：运动估计;块匹配;搜索算法

在帧间视频压缩技术中，块匹配运动估计因简单实用、便于VISL实现而被MPEG和H.26X标准普遍采用[1～3]，大部分块匹配算法主要采用SAD作为匹配准则，只考虑了残差块对编码的影响，忽视了运动矢量对编码的影响，主要目标就是搜索SAD值最小的预测块。事实上，SAD最小并不是最佳匹配块的充分条件，如何快速找到最有利于视频压缩的预测块才是运动估计的根本目标。

为此，本文在综合分析SAD准则缺陷和码量分配的基础上，提出了基于SAD优化的快速运动估计搜索算法(SOMEA)。其主要思路是：首先利用相邻块之间的时空相关性，预测搜索起点；其次设计符合运动矢量交叉-中心偏置分布特性的混合搜索模板，通过基于运动内容灵活处理不同的运动块，使其能够自适应选择模板进行搜索；最后采用高效的搜索中止准则，平滑运动矢量场，减少搜索复杂度和确保足够的搜索精度。

一、块匹配准则及码量分配分析

块匹配算法一般有三种匹配准则，即绝对差(SAD)、均方差(MSE)和归一化相关函数(NCCF)。

(1)

(2)

(3)

式中，(i,j)为位移矢量，fk,fk-N分别为当前帧和参考帧的灰度值，M×N为宏块大小。由于匹配准则对匹配精度的影响不是很大，为降低编码器的时间开销，在这三种算法中，不含乘除法的SAD准则成为最常使用的匹配准则。然而，运动估值的实时性和精度是相互矛盾的，SAD准则虽然运算量最小，但是用该方法寻求最佳匹配块存在较大的误差，可能导致SAD值最小的匹配块并非最优。例如，存在一个4×4当前块Bcur和两个参考块Bref1和Bref2，如下：

另外，在码率控制作用下，Btotal=Bintra+Binter=Bintra+∑(Binter＿re+Binter＿mv)， 其中Btotal(总编码量)、Bintra(帧内编码量)和Binter(帧间编码量)基本为常数，Binter＿re(残差系数编码量)和Binter＿mv(运动矢量编码量)相互制约，Binter＿mv增加，Binter＿re则相应减少。目前，视频编码标准对运动矢量通常采用差分编码方式，运动矢量场越均匀，运动矢量编码量就越小。因此，在保证一定匹配精度的前提下，适当平滑运动矢量场，降低Binter＿mv，使残差编码获得更多的比特数，进而可以提高图像质量。

综合以上分析可知，在运动估计过程中，没有必要花费过多的代价去寻找SAD最小的预测块，而通过高效的搜索中止策略，确保足够的搜索精度，使运动矢量场尽量平滑，就有可能获得更好的视频压缩效果。

二、SAD优化的快速搜索算法

1.搜索起点预测

为防止搜索陷入局部最小和有效降低搜索次数，运动估计算法一般都采用起点预测，使搜索起点距离最佳匹配点足够近。根据运动物体所具有的整体性和视频序列的连续性，可以利用时间和空间方向上的相邻块运动场预测当前块的运动场，图1显示相邻块的位置。

图1　相邻块位置关系图

文献[4]阐述了各相邻块的预测效果，指出当前块的运动矢量与B1，B2，B3，B4块的运动矢量相关性最大。综合考虑计算量和预测效果等因素，本文选择这B1，B2，B3，B4，B5块预测搜索起始点，预测公式为：

MVini为预测的起始点位移，MVBi为Bi块的运动矢量，MVm为B1,B2,B4,B5四个块运动矢量的平均值，T为门限值，SADMVBi为Bi块的SAD值，SAD0为当前块与B3块的失真度。我们提出该预测公式的理论依据在于：(1)如果B1,B2,B4,B5块属于同一运动物体，则argminMVBi‖MVBi-MVm‖所预测的起始点将非常靠近当前块的真实运动位置；如果不属于同一运动物体，那么选择最小的位移偏差作为预测的起点，则可以保持运动场的中心偏置特性。(2)ifmaxi=1,2,4,5‖MVBi-MVm‖T and SADMVBi⦤SAD0，通过SAD比较法得到的预测起点都是相邻块的运动矢量，这种预测也有助于使运动矢量场具有均匀性。(3)虽然当前块与B3块的运动矢量相关性大，但是当运动物体突然改变运动方向，或者运动速度不稳定时，把B3的运动矢量放入公式(4.1)中，将会带来较大的预测误差。所以我们仅把B3放入(4.2)中考虑。(4)由于零矢量非常有利于编码效率的提高，在起点预测时对它给予一定的倾斜。

2.双十字-钻石-六边形搜索模板

经过搜索起点预测后，一般情况下，匹配块运动矢量将非常接近MVini。为此，我们提出的双十字-钻石-六边形混合搜索模板的基本搜索步长为1，具体描述如图2，其基本思想主要来源文献[5,6]的结论：(1)运动矢量具有中心偏置特性；(2)运动矢量的概率分布是以(0，0)点为中心递减的；(3)运动矢量分布具有交叉偏置特性。

3.自适应搜索策略

视频序列中不同区域的运动剧烈程度往往不同，本文算法首先对当前块进行分类，分类准则为：(1)如果MVB1=MVB2=MVB4=MVB5，或者maxi=1,2,4,5‖MVBi-MVm‖⦤2，则称之为静态或准静态块(stationaryorquasi-stationaryblock)；(2)否则，称之为动态块。

图2　又十字—钻石—六边形搜索模板

其次，设置早期搜索终止准则。为提高运动估计速度，许多快速算法常采用SAD阈值作为搜索终止条件。由于当前块的SAD值与前一帧相同位置块的SADB3值具有很强的相关性，本文选择SAD

Step1：依据分类准则判断当前块运动类型，如果当前块是静态或准静态块，则进入step2；否则进入step3。

Step2：以SCSP模板进行搜索，如果最小SAD点在SCSP中心，或者最小SAD点的SADs值满足SADs

Step3：以LCSP模板进行搜索，如果最小SAD点的SADs值满足SADs

Step4：如果LCSP搜索得到的最小SAD点在(0±1),或(±1，0)，如图2(c)所示，搜索最靠近Step3最小SAD点的两个点，也就是位于四个候选点(±1，±1)中的两个点，如果这一步得出的新的最小SAD点和step3得出的一致，或者SADs

Step5：以Step4获得的最小SAD点作为新的HHSP(或VHSP)模板中心进行搜索，如果搜索得到最小SAD点位于新的HHSP(或VUHSP)中心，则进入step6；否则，这循环搜索。

Step6：用上一步找到的最小SAD点作为新的SCSP模板中心，搜索最小的SAD点作为运动矢量的最终解。

在整个搜索过程，我们加入了搜索排除准则来排除不需要进行匹配运算的块以减少搜索点数。具体描述如下：

fk(m,n)-fk-Ns(m+i,n+j)⦤|fk(m,n)-fk-Ns(m+i,n+j)|

(5)

fk-Ns(m,n)-fk(m+i,n+j)⦤|fk(m,n)-fk-Ns(m+i,n+j)|

(6)

对(5)、(6)两式的两边分别求累加和，可得

C-R(i,j)⦤SAD(i,j)

(7)

R(i,j)-C⦤SAD(i,j)

(8)

C-SAD(i,j)⦤R(i,j)⦤C+SAD(i,j)

(9)

在实际搜索过程中，只有候选块R(i,j)满足式(9)时才有必要进行计算，否则不予考虑，这样就大大降低了计算的复杂度。

三、实验结果及分析

为了评估本文提出的SOMEA算法性能，我们选择100帧Qcif序列Football、Coastguard和Mother_daughter进行实验仿真。三个序列分别代表了不同类型的运动，Football序列运动变化剧烈，Coastguard序列的运动变化平稳，Mother_daughter序列只有部分区域运动。实验参数设置如下：块尺寸16×16,搜索窗±16，T=7，t1=0.95，t2=1.07。

Table1和Table2分别列出了不同算法针对不同序列的平均每块搜索点数(ASPB)、速度提升比率(SIP)和平均每个像素MSE值(AMP)、MSE降低比率(DM)。从中可以清楚看到：(1)本文提出的算法与MPEG4推荐的两种算法MVFAST和PMVFAST相比，在MSE基本保持不变的情况下，平均SIP分别提升了78%和5.1%。(2)本算法对于包含平稳运动和静止背景的视频序列，其性能提升要好于运动剧烈的视频序列，主要原因在于运动剧烈使得前后帧相关度急剧下降，导致SAD

表1　平均每块搜索点数(ASPB)和速度提升比率(SIR%)

表2　平均每像素均方差(AMP)和MSE降低比率(DMSE%)

图3　平均每块搜索点数ASPB对比

图4　平均每个象素MSE值AMP对比

四、结论

本文在分析传统的SAD块匹配准则和码量分配对编码质量的影响的基础上，提出了一种新基于SAD优化的运动估计算法(SOMEA)。该算法根据视频运动的相关性，综合运动矢量场中心偏置特性与SAD比较法从当前块的时空位置相邻块的运动矢量中选择最佳的初始运动矢量；利用简单的运动分类准则和搜索转移条件，自适应选择搜索模式，并在搜索过程中加入搜索终止阈值和搜索排除准则，使搜索结果具有足够的精度和较低的复杂度。实验结果显示，本文算法在MSE基本保持不变的基础上，获得了比MVFAST和PMVFAST更高的搜索速度。

参考文献：

[1]HonglunJia.Anewcrossdiamondsearchalgorithmforblockmotionestimation,IEEEInternationalConference.ICASSP, 2004,3(5):17～21.

[2]Ma.K.K.Performancereportofmotionvectorfieldadaptivesearchtechnique(MVFAST)[S].In:ISO/IECJTC1/SC29/WG11MPEG99/m5851,Noordwijkerhout,NL, 2000,(3).

[3]Tourapis.A.M.Fastblock-matchingmotionestimationusingpredictivemotionvectorfieldadaptivesearchtechnique(PMVFAST)[S].In:ISO/IECJTC1/SC29/WG11MPEG2000/N3324,Noordwijkerhout,NL, 2000,(3).

[4]C.Hsieh.Motionestimationalgorithmusinginterblockcorrelation[J].Electron,1990,26(3):276～277.

[5]Chun-Ho.Cheung.Anovelcross-diamondsearchalgorithmforfastblockmotionestimation[J].IEEETrans.CircuitsSyst.VideoTechnol,2002,12(12): 1 168～1 177.

[6]Chun-Ho.Cheung.Novelcross-diamond-hexagonalsearchalgorithmsforfastblockmotionestimation[J].IEEETrans.Multimedia,2002,7(2).

文章编号：2095-4654(2016)05-0018-04

* 收稿日期：2015-12-28

中图分类号：TN911.73

文献标识码：A