文章编号：1002－8692（2011）05-0025-04
一种基于贝叶斯决策的自适应运动估计算法
陈天壮1，梁久祯1，韩
军2
（1.江南大学物联网工程学院，江苏无锡214122；2.上海大学通信与信息工程学院，上海200072）
【摘
要】为了提高视频编码运动估计中运动矢量预测的速度和准确性，提出一种基于贝叶斯决策的视频自适应运动估计算法。
该算法充分利用贝叶斯理论、运动矢量的空间一致性和已编码帧对当前帧的影响，根据视频中前一帧和当前帧的已搜索宏块的运动信息，以目标宏块周围3个宏块的运动矢量与目标宏块的运动矢量空间距离最小为原则，利用贝叶斯决策来得到目标宏块运动矢量的预测值。实验表明，该方法在图像重建质量基本不变的情况下，比DS，ARPS和ARPS-3具有更快的搜索速度。【关键词】视频编码；运动估计；自适应；贝叶斯决策【中图分类号】TN919.8；TP391
【文献标识码】A
AdaptiveMotionEstimationAlgorithmBasedonBayesianDecision
CHENTianzhuang1,LIANGJiuzhen1,HANJun2
（1.SchoolofIoTEngineering,JiangnanUniversity,JiangsuWuxi214122,China;
2.SchoolofCommunicationandInformationEngineering,ShanghaiUniversity,Shanghai200072,China）
【Abstract】AnadaptivevideomotionestimationalgorithmbasedonBayesiandecisionisproposedtoimprovethespeedand
accuracyofthemotionvectorpredictioninvideomotionestimation.Bayesiantheory,spaceconsistencyofMVandtheencoded
frame′sinfluenceoncurrentframearemadefulluse.Basedontheknownvideoblocksofthepreviousframesandthecurrent
frame,
theprobabilitiesofminimumspacedistanceamongthemotionvectorofthetargetsearchblockandthethreesurrounding
blocksarecalculated,andtheMVpredictionisdeterminedaccordingtotheBayesiandecision.ComparedtotheDS,theARPSandtheARPS-3algorithms,experimentalresultsshowthattheproposedmethodprovidesfastersearchspeedwhilethe
reconstructionqualityholdsunchanged.
【Keywords】videocoding;motionestimation;adaptive;Bayesiandecision
0
引言
地确定搜索中心和搜索策略，很快逼近最小匹配位置，所运动估计是利用视频序列中相邻帧之间存在的时
以很大程度上提高了预测的速度和准确性。如运动矢量间相关性，建立它们之间表达上的相互关系，从而减少场自适应快速搜索（MVFAST）、预测运动矢量场自适应时间冗余、提高视频编码效率的一种重要方法。在视频技术（PMVAST）、自适应十字模式搜索（ARPS）[5-6]、非等臂压缩方案中，运动估计的计算量通常约占总计算量的
自适应十字搜索（ARPS-3）[7]等。
60%~80%，其结果直接影响图像的编码效率和图像恢复笔者分析了ARPS-3算法及其特点，提出一种基于的质量，因此寻找高效、快速的运动估计算法非常重要。
贝叶斯统计的自适应运动估计算法，充分利用已编码帧块匹配算法是运动估计中简单、实用的一种方法，所有宏块运动矢量的相关性统计信息，使用贝叶斯决策其中最简单的是全搜索算法（FSA）。FSA通过遍历所有的方法进行运动矢量预测，并自适应搜索运动矢量。实验搜索范围找到最佳匹配块，因此它产生的残差系数最表明，该算法搜索速度快，且能保持较好的图像质量。
小、搜索精度最高。但是因为其巨大的计算复杂度制约1
块匹配算法简介
它不能应用在实时视频编码方面，所以为了减少计算假设将图像序列的每一帧划分成大小为M×N的图
量，提出一些快速搜索算法：三步法（TSS）、新三步法像子块（宏块），并认为各宏块内所有像素的位移量都相（NTSS）、四步法（4SS）、梯度下降法（BBGDS）、菱形搜索同，然后对当前帧的每个宏块，在参考帧某一给定的搜索法（DS）[1]
以及六边形搜索法（HEXBS）[2]
。它们的不足之处
范围内根据一定的匹配准则寻求最优匹配块，这些宏块是，无论剧烈运动图像还是相对静止图像都使用固定搜也可被认为是从参考帧的最优匹配处平移得到的。常用索模式[3]
进行搜索，这样势必造成计算冗余。基于运动矢
的匹配准则[8]有阈值差别计数（NTD）、最小均方差函数
量预测[4]的算法能够利用运动矢量的时空分布，自适应
基金项目：江苏省自然科学基金项目（BK20080544）
2011年第35卷第05期（总第355期）
25Digitalvideo数字视频
（MSE）、归一化互相关函数（NCCF）和最小平均绝对值误差（MAD），其中MAD准则性能很好，而且对硬件要求相对简单，因而应用广泛。MAD定义为
M
N
加入了原点MV5=[0，0]。
初始Unequal-armARP搜索后，得到最小匹配误差（MinimalMatchingError，MME）点，再在这个位置上使用单位十字模式（Unit-sizeRoodPattern，URP）进行搜索，直到得到最终的MV。
MAD（i，j）=1ΣΣ[C（m，n）-R（m+i，n+j）]
MNm=1n=1
（1）
式中：C和R分别代表当前帧和参考帧中该位置的像素，式中（i，j）为匹配块与当前块的相对位移，即运动矢量（MotionVector，MV）。
ARPS-3算法虽然利用空间域中相邻宏块来预测目标宏块运动矢量，不过在以下几个方面还需要改进：1）ARPS-
3算法的运动矢量使用中值预测得到，即取邻近宏块运动矢量的中值作为当前宏块的预测运动矢量，而不是选择一个具体、准确的邻近宏块运动矢量作为预测值；2）ARPS-3的初始搜索模式使用Unequal-armARP，虽然其4个顶点的使用提高了预测的精度，但增加了计算量；3）在初始搜索后，直接使用URP进行搜索，直到搜索到最终的
2
非等臂自适应的十字模式搜索方法
非等臂自适应的十字模式搜索算法（Unequal-
armedAdaptiveRoodPatternSearch，ARPS-3）利用运动矢量的空间一致性，即相邻宏块有非常相似的运动趋势的特点，根据邻近宏块的MV来预测当前宏块的MV。
MV，但可能由于预测不准确使搜索陷入局部极小值点。
ARPS-3一般采用中值预测来进行运动矢量预测。
当得到预测MV后，ARPS-3的初始搜索使用非等臂自适应的十字模式搜索（Unequal-armARP），如图1所示。
210-1-2-3-4-5-3-1
0
1
2MV2
MV0
MV1
MV5
MV4预测MV
3
基于贝叶斯决策的自适应运动估计算法
针对ARPS-3算法中存在的上述问题，笔者提出一种
基于贝叶斯决策的自适应运动估计算法，主要采用了以下技术：1）基于贝叶斯决策的运动矢量预测，根据空间距离最小的原则，在前一帧中进行遍历，然后统计邻近宏块的MV分别预测目标宏块的MV概率，作为它们的先验概率。在当前帧已编码宏块中，也统计出上述概率，作为它们的条件概率。然后根据贝叶斯公式计算邻近宏块的后验概率，从而决定使用哪个邻近宏块的MV来预测目标宏块的MV。2）自适应的搜索模式，首先搜索原点位置和MV的预测位置[9]，使用小菱形模式（SmallDiamond
MV33
4
5
6
7
图1非等臂自适应的十字模式搜索
一般情况下，因为最终MV和预测MV有很大的相关性，所以Unequal-armARP的中心点MV0被放在预测位置上，这不同于ARP（将搜索的中心点放在原点
SearchPattern，SDSP）进行搜索，并且设定弹性系数K[10]决定是否进入大菱形模式（LargeDiamondSearchPattern，LD-
SP）进行搜索。3.13.1.1
贝叶斯决策的运动矢量预测支持区域构成的贝叶斯完备事件组
在空间域内，因为在一个视频帧中所有宏块都是以光栅扫描顺序来处理的，所以相邻宏块中左上、上、右上和左方向上的宏块可以很好地用来作为参考宏块。本算法中使用的支持区域如图2a所示，目标宏块D的预测
[0，0]），也不同于ARP中使用4个等臂长的顶点，Un-equal-armARP的4个顶点根据各个方向上的运动范围来动态赋值。对于当前宏块，邻近宏块运动矢量的最大和最小值被认为是其预测MV的偏差，并作为搜索模式各方向上臂长的精确估计，即
MV1=[max（MVx），MVpredicted_y]ΣΣMV2=[min（MVx），MVpredicted_y]Σ
MV3=[MVpredicted_x，max（MVy）]Σ
MV4=[MVpredicted_x，min（MVy）]Σ
（2）
MV由A，B，C3个宏块的MV决定。使用A，B，C宏块MV中的一个来预测目标宏块D的MV就构成了一个贝叶斯的完备事件组，这样就可以使用贝叶斯决策来得到D宏块的MV预测值。
式中：MVx，MVy是邻近宏块运动矢量的水平和垂直分量，max和min操作是求邻近宏块运动矢量的最大和最小值，MVpredicted_x和MVpredicted_y是预测运动矢量的水平和垂直分量。为了增加算法的稳健性，Unequal-armARP
3.1.2贝叶斯决策的运动矢量预测
如图2b所示，使用APRS-3算法遍历所有宏块，分别
计算D宏块搜索到的最终MV与A，B，C3个宏块MV的
262011年第35卷第05期（总第355期）
Digitalvideo数字视频
BC算法具体实现步骤如下：
AD
1）如果当前帧是第一帧或者是首行、列的宏块，那么使用ARPS-3对宏块进行遍历，得到最终的MV和由
BC
A，B，C宏块MV分别预测D宏块MV的先验概率；否则转入步骤2）。
A
D
2）通过式（4）和当前A，B，C3个宏块MV分别预
a支持区域
b统计过程
测D宏块MV的条件概率来计算由A，B，C3个宏块分图2统计预测值
别得到的后验概率，使用后验概率大的宏块的MV作为
空间距离，如式（3）所示。由此可得到运动矢量距离最小D宏块的预测MV，然后搜索预测MV位置和原点。
的宏块，并增加该宏块的概率
3）使用SDSP进行搜索，当SDSP连续搜索的次数Dis（i，D）=（MVi，x-MVD，x）2+（MVi，y-MVD，y）2（3）
超过2次时，转入步骤4），否则转入步骤5）。
式中：Dis（i，D）表示的是3个邻近宏块之一的MV与D宏4）使用LDSP进行搜索，直到最佳匹配点在搜索中块MV的空间距离，MVi，x，MVi，y分别表示各个宏块运动矢心位置，然后转入使用SDSP，搜索最终的MV。
量x，y方向上的大小，i=A，B，C。该方法的具体步骤如下：
5）如果所有宏块遍历完毕，则当前帧计算完成，记1）通过对前一帧的统计，根据空间距离最小的原则，录MV值，并更新先验概率值；否则，更新条件概率值并得到A，B，C宏块的MV分别预测D宏块的MV概率，作转入步骤2）。
为先验概率P（i），这里i=A，B，C。先验概率说明了前后两帧的时间关系。
4
实验结果与分析
2）在当前帧已编码宏块中进行统计，同样得到这3为了验证贝叶斯决策的自适应运动估计算法(Bayes
个宏块的MV分别预测D宏块的MV概率，作为条件概-ARPS3)的性能，在相同条件下对FS，TSS，SS4，ARPS，率P（D|i），说明了当前帧宏块间的空间关系。
ARPS-3和Bayes-ARPS3算法进行Matlab仿真实验。用3）根据贝叶斯公式，计算A，B，C3个宏块MV分平均峰值信噪比（PSNR）和平均搜索点数（SearchPoint
别作为D宏块的预测MV的后验概率P（i|D），即
perFrame）这2个参数作为算法性能的验证标准。实验
P（i|D）=P（D|i）P（i）P（D）
，i=A，B，C
（4）
以Mobile，Tennis和Flower（100帧CIF格式）3个标准序列作为测试序列。算法选取的宏块大小是16×16，搜索窗式中：P（D）=P（D|A）+P（D|B）+P（D|C）。选择后验概率口大小为水平和垂直方向±7个像素，匹配准则为MAD最大宏块的MV作为D宏块的预测MV。例如：计算得（取序列的平均值记录）。
到P（D|A）>P（D|B）>P（D|C），那么选择A宏块位置的MV表1为各个算法的平均搜索点数。可以看出，Bayes-
作为当前宏块D的预测MV，即MVpredicted=MVA。
ARPS3算法在各个序列中所用的平均搜索点最少，也就3.2自适应的搜索模式
是说它的搜索速度最快。表2为各个算法的平均峰值信经过贝叶斯决策得到一个准确的预测运动矢量，并
噪比。可以看出，在各种算法中FS的PSNR最高，说明其根据运动矢量的中心偏移特性可知在运动较少的图像性能最优，ARPS，ARPS-3和Bayes-ARPS3算法的PSNR序列中，运动矢量通常集中分布在宏块原点附近，所以差距不大，也就是说它们的搜索准确性相当接近。
初始搜索对预测MV位置和搜索原点（0，0）进行搜索。
表1
算法平均搜索点数
初始搜索得到最小匹配误差点之后，使用SDSP来平均搜索点数
进行精确搜索，这是因为在大范围搜索之后，检测小范算法
MobileTennisFlower围内的运动矢量时，SDSP搜索点数比全搜索要少，其收FS207.4109202.0485202.0485敛性好，实验效果也不错。当使用SDSP连续搜索次数大TSS23.727323.209523.3092于弹性次数K（本文K取2）时，搜索模式转入LDSP，当4SS19.650119.700719.8921最小匹配误差点出现在搜索中心时，再转入SDSP进行ARPS10.01549.920910.3108搜索ARPS-38.826910.05309.3914，直到得到最终MV的值。
Bayes-ARPS3
7.9023
9.0980
8.2114
3.3算法实现步骤
根据上述思想，基于贝叶斯决策的自适应运动估计
图3是对DS，ARPS-3和Bayes-ARPS3算法的仿真
2011年第35卷第05期（总第355期）
27Digitalvideo数字视频
表2
算法
算法平均峰值信噪比
PSNR/dBTennis25.533724.538724.296124.331124.070124.1369
Flower21.106720.322820.232020.608020.734820.6575
综合上述实验结果，得到Bayes-ARPS3算法比
FSTSS4SSARPSARPS-3Bayes-ARPS3
Mobile30.379726.265427.592427.482727.434627.3423
ARPS-3，DS算法更优的综合效果。
5
小结
提出一种基于贝叶斯决策的视频图像自适应运动估
计算法，首先对前一帧和当前帧的已编码宏块信息进行统计，然后利用贝叶斯理论，结合宏块间MV的空间一致性特点得到一个精确而快速的预测运动矢量。实验表明，相比DS，ARPS和ARPS-3，该算法减少了运动估计的平均搜索点数，从而节省了编码时间，同时在搜索质量上也有良好的效果。参考文献：
[1]
ZHUShan，MAKaikuang.Anewdiamondsearchalgorithmforfastblock-matchingmotionestimation[J].IEEETrans.ImageProcessing,2000，9（2）：287-290.[2]
ZHUC，LINX，CHAULP.Hexagon-basedsearchpatternforfastblockmotionestimation[J].IEEETrans.CircuitsSyst.VideoTechnology，2002，12（5）：349-355.[3][4][5]
张明，毕笃彦.块匹配算法研究进展[J].电视技术，2007，31（3）：8-11.童小平，曾孝平，李勇明.一种预测菱形运动估计算法[J].电视技术，2004，28（6）：19-20.
比较，实验序列为100帧的Mobile（CIF格式）和Flower（CIF格式）序列，图3a~3b是对算法平均搜索点数的比较，可以看出Bayes-ARPS3算法的搜索点数明显比DS和
ARPS-3少；图3c~3d是对算法平均峰值信噪比的比较，表明3种算法的搜索准确性大体一致。
18平均搜索点数16141210860
20
40
60
80
100
帧数
aMobile平均搜索点数比较
DS
ARPS-3
Bayes-ARPS3
2220平均搜索点数181614121080
20
40
DS
ARPS-3
Bayes-ARPS3
NIEYao，MAKaikuang.Adaptiveroodpatternsearchforfastblock-matchingmotionestimation[J].IEEETrans.ImageProcessing，2002，11（12）：1442-1449.
[6]
60
80
100
[7]
王晓燕，郑建宏.用于快速块匹配运动估计的自适应十字模式搜索[J].电子与信息学报，2005，27（1）：104-107.
22.0平均峰值信噪比/dB帧数
bFlower平均搜索点数比较
MAKaikuang，QIUGang.Unequal-armadaptiveroodpatternsearchforfastblock-matchingmotionestimationintheJVT/H.26L[C]//Proc.IEEEInt.Conf.onImageProcessing.[S.l.]：IEEEPress，2003：901-904.
21.521.020.520.019.5
0
20
DS
ARPS-3
Bayes-ARPS3
[8][9]
60
80
100
[10]
禹晶，苏开娜.块运动估计的研究进展[J].中国图象图形学报，
2006，12（12）：2031-2041.
王荃，鲍卫兵，张永智.搜索模式自适应快速运动估计算法[J].电视技术，2009，33（7）：16-17.
何宜宝，毕笃彦，许悦雷，等.基于时空相关性的自适应运动估计快速算法[J].计算机工程，2009，35（13）：228-231.
40
25平均峰值信噪比/dB帧数
cMobile平均峰值信噪比比较
2423222120190
20
DS
ARPS-3
Bayes-ARPS3
笕
作者简介：
陈天壮（1986-），硕士生，主研图像处理、视频编解码；
梁久祯（1968-），博士，教授，主研智能信息处理与模式识别、图像处理；
韩
军（1965-），博士，副教授，主研视频编解码、图像处理。
雪
收稿日期：2010-10-19
40
帧数
6080100
责任编辑：丁
dFlower平均峰值信噪比比较
图3算法性能比较
282011年第35卷第05期（总第355期）
因篇幅问题不能全部显示，请点此查看更多更全内容