块匹配准则（精选6篇）
块匹配准则 篇1
0引言
块匹配算法是最常用的一类运动估计方法,为H.261、H.263、H.264以及MPEG-1和MPEG-2等图像编码国际标准所采用,并发展出了各种快速搜索算法[1,2,3]。块匹配算法假设图像子块内各像素只做相同的平移。对当前帧的每一个子块,在上一帧某一搜索范围内依据一定的匹配准则寻找最优匹配块。当前块和匹配块之间的位移称为运动矢量;当前块和匹配块对应像素灰度值之差称为残差。编码残差的DCT变换系数和运动矢量所需的比特数越少,则整体的编码效率越高。为了得到较小的残差,运动估计是必须解决的关键技术,它采用的准则也很关键。
1常用的块匹配准则及其分析
记待搜索的当前块(灰度值)为fk(m,n),(m,n)为该块的坐标,块大小固定为M×N。块匹配的过程是,在前一帧中按一定的匹配准则搜索fk(m,n)的一个匹配块(灰度值)fk-1(m+i,n+j),使得结果是最优的。(i,j)即为运动矢量。文献中有很多最优匹配的搜索方法,如二维对数法、三步搜索法、四步搜索法、共轭方向搜索法、预测搜索法和金刚石搜索法等。搜索方法层出不穷,但它们采用的准则不外乎以下4种:
① 最小绝对差准则(Minimum Absolute Diffirence,MAD)
② 求和绝对误差准则(Sum of Absolute Diffirence,SAD)
③ 均方误差准则(Mean Square Error,MSE)
④ 归一化互相关函数准则(NCCF)
前一帧中的匹配块fk-1(m+i,n+j)使得以上各式最小化(i,j)的即为运动矢量。当块大小固定时,由式(1)和式(2)可以看出,MAD准则和SAD准则得到的搜索结果一般是一致的。这是因为2个式子只相差一个固定的比例因子MN,这显然不影响搜索结果。由于没有除以因子MN,式(2)的运算量较式(1)要小一点,所以一般很少使用式(1)而使用式(2),但它们的本质是一样的,不失一般性下面就只讨论其中一个。有些文献认为式(3)存在平方运算,所以运算量较式(2)都大,所以不予采用。
在下文的分析中采用以下3组数据(匹配块像素灰度值从左到右从上到下依次为):
第1组:当前待匹配块为60、60、60、60、60、60、60、60、60;参考匹配块1为65、65、65、65、65、65、65、65、65;参考匹配块2为60、70、75、60、70、75、60、70、75。
第2组:当前待匹配块为50、60、70、50、60、70、50、60、70;参考匹配块1为55、60、70、55、60、70、55、60、70;参考匹配块2为50、60、75、50、60、75、50、60、75。
第3组:当前待匹配块为50、50、50、50、50、50、50、50、50;参考匹配块1为45、50、55、45、50、55、45、50、55;参考匹配块2为55、50、55、55、50、55、55、50、55。
分析第1组给出的针对待匹配块的2个参考匹配块,依据式(2)计算得到的绝对误差大小是相等的,但若依据式(3)计算知道参考匹配块2较参考匹配块1有更大的均方误差。事实上,直观地看参考匹配块1较参考匹配块2的匹配效果好。由于使用式(2)不能给出这两个参考匹配块的优劣,而使用式(3)则能判断,所以认为式(3)给出的均方误差准则更合理。在图像编码和图像处理领域中,峰值信噪比(PSNR)由下式定义[4]:
观察式(3)和式(5)可以看出,2个定义式中对灰度值之差都取平方运算,即在数学表达式上是一致的,这启发从另外一个角度理解式(3)较式(2)更合理。
2惩罚相对均方误差准则及仿真
考虑第2组给出的针对待匹配块的2个参考匹配块,由式(3)计算得到的均方误差相等,但参考匹配块2的视觉效果更好,因为相对于原像素值70增大5比相对于原像素值50增大5,前者引起的视觉差别更小,所以在提出的准则中除以原像素的灰度值和256之和。再考虑第3组给出的针对待匹配块的2个参考匹配块,参考匹配块1给出的像素灰度值有的变大(由50增大为55)有的变小(由50减小为45),而参考匹配块2的像素灰度值都增大(由50增大为55)。显然,像素灰度值都变大或都变小较有的变大有的变小引起的视觉差别要小。考虑到这一点,在提出的准则中引入惩罚项,它是像素灰度值变化符号的函数。综合考虑以上这些,提出的惩罚相对均方误差准则(Penalty Relative Mean Square Error,PRMSE)如下:
式中,λ为大于零的参数,sgn(x)为符号函数,即
测试了标准视频序列,仿真结果表明,本文提出的准则较SAD准则得到的匹配块PSNR都有一定程度的提高;与此同时,仿真结果表明,通过本文提出的准则得到的匹配块,其视觉效果也更好。
3结束语
本文分析了常用块匹配准则的不足之处,提出一种改进的准则,在该准则的均方误差项中除以原始像素的灰度值;考虑了灰度值变化的符号,引入了惩罚项。通过这二者的结合,给出的所谓惩罚相对均方误差准则较SAD准则得到的匹配块PSNR有所提高,同时视觉效果更好。仿真实验证明了这一点。
参考文献
[1]LI R,ZENGB,LIOUML.ANewThree-step Search Algorithm for Block Motion Estimation[J].IEEE Trans.on CSVT,1994,4(4):438-443.
[2]PO M,MA WC.A Novel Four-step Algorithmfor Fast Block Motion Estimation[J].IEEE Trans.on CSVT,1996,6(3):313-317.
[3]ChEUNG C H,PO L M.A Novel Cross-diamond Search Algorithmfor Fast Block Motion Estimation[J].IEEE Trans on CSVT,2002,12(12):1168-1177.
[4]吴乐南.数据压缩(第2版)[M].北京:电子工业出版社,2005:19-21.
块匹配准则 篇2
关键词：分布式视频编码,边信息,代价值,块匹配
分布式视频编码(DVC)[1,2]就是为了解决传统视频编码在视频通信中遇到的编码器复杂等问题而提出来的。以Slepian和Wolf建立的分布式无损编码理论,Wyner和Ziv建立解码端辅助信息的有损编码理论为基础,在编码端将视频序列分为Key帧和WZ帧进行独立编码,Key帧采用传统的编码方式,WZ帧则采用Tuobo码或LDPC码进行信道编码。在解码端采用联合解码,利用时域相邻帧的高度相关性,通过对已解码Key帧的运动估计,进行时域内插求取边信息,再将生成的边信息用于当前WZ帧的重构。这就像耗时的运动估计和补偿技术从编码端移到了解码端,大大降低了编码端的复杂度。
分布式视频编码的主要效率很大程度上取决于所估计的边信息的质量,生成的边信息与原始的WZ帧越接近,解码端所需的校验码就越少,相应的码率也越小,并且重构的WZ帧质量也就越好。而在边信息估计中一般都是采用块匹配准则进行运动估计来求取运动矢量的,因此块匹配准则函数在分布式视频编码系统中起着非常重要的作用。文献[3]通过一个加权系数扩展搜索块的大小提出了一种加权MAD算法;文献[4]根据拉格朗日代价函数将相邻块的代价值相结合来进行匹配搜索;文献[5]中将平均绝对误差和与边缘绝对误差和相结合来进行匹配搜索。这3种方法在一定程度上都能减少方块效应,其中文献[3]实现比较简单,文献[4]和文献[5]中的算法复杂度比较高,然而当运动估计中搜索范围比较大的时候,上述3种方法估计的运动矢量与真实的运动矢量之间将会存在较大的偏差,因此使运动估计得到的运动矢量尽可能地接近实际运动矢量是很有必要的,而单纯地采用每个代价值函数作为匹配准则不是一种很有效的算法,因此本文在文献[3]的基础上增加了运动矢量的代价值作为约束条件来共同定义块匹配准则函数,实验表明该方法能有效地改善图像的主观质量,提高峰值信噪比。
1 问题描述
在采用插值法生成边信息的过程中,运动矢量的估计起着至关重要的作用,块匹配运动估计是一种简单易实现且高效的估计算法,因此这里采用块匹配算法来进行运动估计。
块匹配算法将当前帧分为大小为m×n的互不重叠的块,并假设每个块中的所有像素点的运动方向是一致的,以搜索块为基本单位,在参考帧内开辟大小为(m+2w)×(n+2w)的空间进行估计搜索,找到与其最为匹配的块,得到当前块与匹配块之间的运动矢量(dx,dy)。其中w为X和Y方向上的搜索范围。实际应用中通常取m=n,其搜索示意图如图1所示。
影响块匹配运动估计效果的因素除了搜索范围还有搜索步长、块大小和匹配准则。步长是相邻两次搜索之间的距离,合理地选择步长可以有效降低搜索的复杂度。块大小需要根据视频图像的大小和内容来进行选择。稍微大点的块(如16×16)在运动丰富的序列中估计不准确,比较适合于纹理简单而平坦的区域,小块(如4×4)在运动平缓或纹理简单的序列中不能很好地捕捉到运动矢量,相对而言比较适合于纹理比较丰富的区域,因此,本实验中块尺寸大小选取8×8。
块匹配准则是描叙两个块之间相似程度的误差函数,通常有绝对平均误差函数、互相关函数和均方误差函数等。误差函数对运动估计复杂度有着很大的影响。函数越复杂搜索也就越慢。因此,需对误差函数作研究,以求在不影响匹配精度的情况下减少匹配时间。误差函数越精确描述出的两块间差别也就越精确,两个子块之间的误差函数值越小就表示这两个块越匹配,块匹配运动估计算法也就是根据误差函数的最小值来得到运动矢量的。
2 算法研究
块匹配误差函数有很多,它们在复杂度和准确度等方面各不相同。分布式视频编码与传统视频编码中不同的是运动估计位于解码端,因此在前向运动估计边信息插值模块的运动矢量和宏块分割模式判决时,无须考虑运动信息的编码比特,即误差匹配函数只与原始数据和预测值之间的差值有关。其中最常用的就是平均绝对差(Mean Absolute Diference,MAD)。对于一个m×n块,使用下式作为运动矢量失真函数
式中:X2k-1(i,j)是前一参考中帧宏块的像素值,X2k+1(i+dx,j+dy)是后一参考帧中相应宏块的像素值,(dx,dy)为两宏块之间的运动矢量,(-w<dx<w,-w<dy<w),w是搜索范围。为了减少乘法运算,实际应用中也通常用绝对误差和(Sum of Absolute Diference,SAD)来代替MAD
然后根据估计得到的运动矢量进行时域内插得到边信息,若估计的运动矢量与真实的运动矢量有较大差距,则生成的图像会出现方块效应,造成解码图像质量下降,所以在Wyner-Ziv视频编码中,估计的运动矢量需要尽可能地和真实运动矢量相一致,一个好的匹配准则能够估计出最真实的运动矢量,因此,需要找到对当前帧最好的一个估计,并基于此来实现运动补偿。
文献[3]在原有MAD的基础上提出了一种加权MAD算法,假设当前块大小为8×8,该算法通过外扩4个像素即扩展块为12×12,然后对扩展的像素乘以一个加权值来进行运动估计,用公式描叙为
式中:x,y为当前块的左顶点坐标;dx,dy为当前块相对于参考块之间的距离,权值α(i,j)为
由于考虑到搜索块周围相邻的几个像素,因此该准则能够减少一定的方块效应。
文献[4]采用拉格朗日代价函数
Jλ(v)=Di(v)+λ(Dj(v)-Dj(vj)) (5)
式中:Di(v)=MAD(dx,dy);j为块i周围的8个邻块;vj为各个8邻块的对应的运动矢量;
由于在当前宏块的实际搜索中只能提前知道该宏块的左上宏块、上宏块、右上宏块以及左宏块,所以在拉格朗日代价函数中只计算该4个块的λ(Dj(v)-Dj(vj)),且N=4,β取值为10。
文献[5]中将平均绝对误差和与边缘绝对误差和相结合来进行匹配搜索,定义为
总的误差函数D=αBAD+(1-α)MAD,α取0.3时最佳。
这3种匹配函数都是利用当前块的相邻像素点或者相邻块来去除图像的方块效应的,其中文献[3]实现比较简单,文献[4]和文献[5]中误差函数的计算复杂度比较高,但他们估计的运动矢量与真实的运动矢量之间仍存在较大的偏差。文献[6]表明在MAD相同的情况下再经过运动矢量代价值的筛选能使估计得到的运动矢量更加精确,因此本文在文献[3]的基础上结合运动矢量的代价值进一步优化匹配准则,提高边信息的质量,又因为绝对值的稳定性大于平方,因此,本文所使用的匹配误差准则函数定义为
MV_COST(dx,dy)=KSAD(dx,dy)×
(1+K×(abs(dx)+abs(dy)) (7)
式中,K是一个平滑常数,是当运动矢量达到搜索范围的最大值附近时用来控制其代价值的,实验表明K取0.05的时候最恰当[7]。因为本文算法所采用的块匹配函数规范了运动估计中的运动矢量场,因此可以将搜索范围由8扩展到32。而当视频序列运动比较剧烈的时候或采用的搜索步长比较大的时候,新增加的搜索范围可以提高运动估计矢量的精度,从而提高内插帧的质量,另外本算法对KSAD中的权值α(i,j)也进行了修正,对于4个块共用的像素权值设为0.2,对于2个块共用的像素权值采用0.3[8]。
另外,在前向或后向运动补偿中,很容易存在叠补和漏补的情况,针对这种情况,本文采用文献[9]中的方法,在重构补偿之前先用X2k-1和X2k+1的平均值对Y2k赋初值,然后再根据重叠次数对每个像素点进行加权补偿。
3 实验结果及分析
实验采用具有代表性的QCIF(176×144)格式标准视频图像序列“Foreman”和“Football”共100帧进行研究,采用1∶1的比例,每两个关键帧之间一个WZ帧,关键帧采用原始图像,即采用无失真编码,采用文献[9]中叠补和漏补的补偿方法,用峰值信噪比(PSNR)来衡量生成的边信息图像质量。图2和图3分别给出了Foreman和Football使用几种不同匹配准则估计补偿的结果,表1给出了相应的平均PSNR。
图4a～e分别为使用SAD、文献[3]、文献[4]、文献[5]以及本文所论述的匹配准则对Foreman序列第74帧进行边信息估计的结果,图4f为原始WZ帧。由图可以看出本算法估计的图像与原始WZ帧最接近,即效果最好。
4 结论
边信息在分布式视频编码中起着非常重要的作用,边信息越精确,解码端所需的校验码就越少,相应的码率也越小;并且,重构的WZ帧质量也就越好。本文研究了几种匹配准则函数,并在此基础上将运动矢量的代价值应用到加权SAD中作为新的块匹配的估计准则。实验结果表明,采用本文的算法可以改善图像的主观质量,提高图像的峰值信噪比。
参考文献
[1]GIROD B,AARON A,RANE S,et al.Distributed video coding[J].Pro-ceedings of the IEEE,2005,93(1):71-83.
[2]PURI R,MAJUMDAR A,ISHWAR P.Distributed video coding in wire-less sensor networks[J].IEEE Signal Processing Magazine,2006,23(4):94-106.
[3]干宗良,朱秀昌.Wyner-Ziv视频编码中边信息估计改进算法[J].计算机工程与应用,2007,43(19):53-56.
[4]ASCENSO J,PEREIRA F.Advanced side information creation tech-niques and framework for Wyner–Ziv video coding[J].Vis.Commun.Image R.,2008(19):600-613.
[5]YE Shuiming,OUARET M,DUFAUX F,et al.Improved side informationgeneration for distributed video coding by exploiting spatial and temporalcorrelations[J].EURASIP Journal on Image and Video Processing,2009(1):1-15.
[6]宋彬,贺红,刘海华,等.Wyner-Ziv视频编码中边信息生成算法研究[J].通信学报,2010,31(12):97-103.
[7]ASCENSO J,BRITES C,PEREIRA F.Content adaptive Wyner-Ziv videocoding driven by motion activity[C]//Proc.2006 IEEE International Con-ference on Image Processing.Atlanta,USA:IEEE Press,2006:605-608.
[8]卿粼波,何小海,吕瑞,等.分布式视频编码中边信息的多策略优化[J].四川大学学报:工程科学版,2008(1):138-143.
运动估计中经典的块匹配算法比较 篇3
块匹配算法就是对两帧图像的同一个位置的运动通过分块比较得到其估计矢量。算法思想如下：每一帧图像都被分割为若干个大小为M×N的块，通过中心定位找到参考帧上像素点(x,y)的所在的图像块，通过某种匹配准则估计得到待匹配帧上最佳匹配图像块。则这两个图像块之间的位移即为(x,y)点的位移。
块匹配法的差异主要体现在匹配准则、搜索算法和块大小等方面。常用的块匹配准则有最小绝对差和函数、最小均方误差、最小平均绝对值差等。本文采用的是：
2 经典块匹配算法
2.1 四步搜索法FSS
(1）基本思想
四步搜索算法相对于三步搜索法,搜索窗口由9×9变成5×5的9个搜索点，FSS搜索的上一步的最佳匹配位置决定了下一步的搜索范围并且将搜索窗口的中心移向最小块距离MBD点处,搜索步长在前三步不改变,在最后一步改变步长,获得最后的最佳匹配位置,而且后两步搜索窗口的宽度由MBD点的位置来决定。
(2）算法步骤
step1：在7×7的搜索区域内，FSS搜索首先建一个5×5的搜索窗口并计算如图1所示9个点的匹配误差。如果最小匹配误差点MBD点出现在搜索窗口的中心，转到第四步，否则转到第二步。
step2：新的搜索窗口的中心定位在第一步中的MBD点，新建5×5的窗口。最小匹配误差点出现在四角，如图2所示，需要新增加5个点计算匹配误差，找到匹配误差最小的点。最小误差点出现在为四边，如图3所示，需要增加3个黑色点计算其匹配误差。如果这些点的匹配误差都比中心点大，转到第四步，否则转到第三步。
step3：搜索方法和第二步相同，但终将会转到第四步。
step4：搜索窗口缩小为3×3。最终结果由图4所示的9个点中的最小匹配误差点决定。
(3）性能分析
FSS的最少搜索点数为9+8=17，最大搜索点数为9+5+5+8=27个点，计算复杂度比TSS低，对于方向上的误导性比TSS要小很多，具有较好的搜索效果。
2.2 十字搜索法RPS
(1）基本思想
为了进一步提高效率减少检查点数目，RPS算法搜索利用四点十字方案。FSS在第一步搜索时需要计算9个点，而十字搜索只需要5个。如果十字中心不是最小的SAD点，十字搜索也只需要多计算3个点的SAD值。
(2）算法步骤
Step1:RPS搜索首先建立一个十字模板，计算十字模板的4个十字端点的SAD值，通过其最近的块预测一个运动矢量，如图5所示。
Step2:上一步得到的最小SAD点作为下一步搜索的新的十字中心，如图6所示，比较新的十字模板的4个端点和十字中心，得到新的最小SAD点。
Step3：重复第二步，直到十字模板的中心的SAD值最小为止。
(3）性能分析
十字搜索因为只计算十字模板的端点位置，有可能造成搜索方向的偏离，准确度较低，但是该搜索方法所需检测点的数目最少，计算复杂度比较低，从而搜索速度得到提高。
2.3 双十字搜索法DCS
(1）基本思想
双十字搜索算法是在十字搜素算法的基础上提出来的，采用了两个搜索模板，一个是4×4的大十字模板，一个是2×2的小十字模板，大十字搜索过程和十字搜索类似，不同的是在小十字精化时，为了得到最佳匹配点，它不仅检查小十字模板中心的四个端点，还增加了三个可能存在最小SAD点的位置检测。
(2）算法步骤
Step1:预测一个中心点位置作为初始搜索中心。
Step2:4×4大十字搜索，以第一步得到的搜索中心建立一个4×4大十字的大十字模板，把大十字模板的4个端点位置的SAD与中心点SAD比较，如果最小SAD出现在大十字中心则停止搜索，转到第四步，否则转到第三步，如图7所示。
Step3：重复第二步搜所，检查新的大十字模板的四个端点位置的SAD值。
Step4:2×2小十字搜索，以上一步得到的最小SAD点的位置作为新的2×2小十字模板的中心，如图8所示的4种情况下，多计算额外的3个可能的最佳点，检查2×2小十字模板其它三个端点的SAD值，。最终结果由这六个点和当前十字中心里的最小SAD点来决定。
(3）性能分析
双十字精化搜索与RPS相比仍然具有快速搜索的优点，在计算量没有明显增加的情况下，还提高了搜索的准确度。
3实验结果及分析
在matlab 7.0上进行仿真实验，采用了YUV格式的标准测试序列“foreman”和“highway”的前30帧对于四步搜索算法、十字搜索算法以及双十字搜索算法进行了测试并与全搜索算法FS进行比较。在测试过程中，采用SAD为匹配准则，运动估计的块大小为16×16，搜索步长为7。我们主要测试了每块的平均搜索点数和平均峰值信噪比PSNR,结果如下表所示：
表1表示foreman各种块匹配算法情况下的每块的平均搜索点数points、相对全搜索算法的加速率ratio以及平均峰值信噪比PSNR:
表2分别表示highway在各种块匹配算法情况下的每块的平均搜索点数points、相对全搜索算法的加速率ratio以及平均峰值信噪比PSNR:
4 结语
本文介绍了运动估计的原理以及一些经典的块匹配算法，通过3个不同视频序列的仿真结果可以看出,DCS算法在提高搜索速度的同时,性能PSNR与其他算法相比变化几乎可以忽略不计,这说明在达到相同搜索质量的前提下，DCS算法很能在很大程度上使搜索速度得以提高。
参考文献
[1]陈宫,牛秦洲.图像序列运动估计中经典块匹配算法研究[J].计算机应用与软件,2012,29(5):147-151.
[2]刘海华,雷奕,谢长生.双十字搜索算法的快速块匹配运动估计[J].计算机研究与发展,2006,43(9):1666-1673.
块匹配准则 篇4
图像序列中相邻两幅图像之间在内容上的差异不会太大,或者说后一帧的内容与前一帧重复的部分很多,二者是相关的。而消除这种时间的相关性(冗余度),是视频压缩编码的一条重要途径。运动估计ME(Motion Estimation)用于图像序列帧间编码,是一种利用视频信号参考帧的运动场来预测当前帧图像的技术,通过两帧图像的比较可求出运动矢量,并以此获得当前帧的预测值。其过程是把图像序列中的每一帧分成若干局部结构,并设法检测出每个局部结构在参考帧图像中的位置,得到帧中每一部分的运动矢量。运动矢量在参考帧上进行运动补偿MC(Motion Compensation),残差值(Difference)经DCT变化、量化、行程编码后与运动矢量共同经熵编码,然后以比特流形式传出去。运动估计可以比较有效地去除图像帧间冗余度而实现较高的压缩比,从而被广泛用于各种视频编码标准中,如MPEG-1/2/4、H.261、H.263和H.264/AVC等。
基于块匹配的运动估计算法是目前应用非常广泛的运动估计算法。块匹配算法有很多种,其中穷尽搜索法ES(Exhaustive Search)[1]精度高,硬件易实现,但由于它要对搜索区内的每个搜索点进行检测,因此计算量大。为了减少ES算法的计算量,又出现了许多快速的块匹配运动估计算法,其中有三步法TSS(Three Step Search)[2]、新三步法NTSS(New Three Step Search)[3]、菱形法DS(Diamond Search)[4]等。1999年10月,菱形法(DS)被MPEG-4国际标准采纳并收入验证模型(VM)。它最早是由S.ZHU和K.K.MA提出,是目前块匹配算法中性能较为优异的一种算法。经过研究发现,虽然它的综合性能较其他算法优越,但它不能根据图像的内容(运动模型)作出灵活处理。后来针对模板搜索快速算法的缺点,提出了起点预测、中止策略、分层搜索、可变块大小搜索等算法思想,并陆续出现了很多新型算法,在一定程度上解决了快速块匹配法遇到的难题。
1 经典块匹配算法分析
在众多搜索算法之中,穷尽搜索法精度最高。它穷尽参考帧搜索窗内所有可能的点进行比较,找到BDM(Block Distortion Measure)最小的匹配块。但其运算太复杂,不宜实时实现,因此相继提出了各种改进和快速搜索算法。下面将对一些典型的块匹配运动估计算法进行分析和研究。
1.1 穷尽搜索法
(1)基本思想
穷尽搜索法ES(Exhaustive Search)也称为全搜索法FS(Full Search),是对(M+2×dxmax)×N+2×dymax)搜索范围内所有可能的候选位置计算SAD(Sum of Absolute Difference)值SAD(i,j),从中找出最小SAD,其对应偏移量即为所求运动矢量。此算法虽计算量大,但最简单、可靠,找到的必为全局最优点。
(2)算法描述
第一步,从(0,0)点出发,按某种搜索路径由近及远,逐个像素点计算SAD值,直到遍历搜索窗内所有的点。第二步,在所有的SAD值中找到最小块误差MBD(Minimum Block Distortion)点,该点即最佳匹配点。核心编程如下:
%以宏块边长为单位步长,在每个宏块的上下左右四个方向上,寻找其最吻合的分块
for i=1:mb Size:row-mb Size+1
for j=1:mb Size:col-mb Size+1
%计算垂直(2p+1)个分块以及水平(2p+1)个分块
for m=-p:p
for n=-p:p
if(ref Blk Ver<1‖……)%判断搜索是否超出边界
costs(m+p+1,n+p+1)=cost Func SAD(…);%计算SAD值
end
end
[dx,dy,min]=min Cost(costs);%找到SAD最小值
end
end
motion Vect=vectors;%得到运动矢量
(3)模板及搜索图示
图1为穷尽搜索法的示意图。它在整个搜索窗范围内按螺旋搜索方式逐点搜索计算各位置的SAD值,从中找出具有最小匹配差值的块即为最佳匹配块。
(4)算法分析
ES算法是所有运动估计算法中最简单、最原始的块匹配算法。它对整个搜索窗口的每一个点进行块匹配计算,所以单从匹配的角度看,全搜索无疑是一种最好的匹配方法,通常是其他算法性能比较的标准。但它的计算量很大,需要计算的点数多,它在整个视频压缩编码过程中占有大部分的运算量,限制了在需要实时压缩场合的应用。
另外通过上述分析可以发现,在块匹配方法中最重要的两个问题是如何确定:(1)满足精度与速度要求的匹配准则;(2)计算量最小的搜索方法。对这两个问题的不同解决方案构成了下面不同的快速搜索算法。
1.2 三步搜索法
(1)基本思想
三步搜索算法(TSS)是由T.KOGA等人1981年提出的。由于早期的搜索范围为±7,搜索精度取一个像素,则步长为4、2、1,共需三步即可满足要求,故得此名。如果扩大搜索范围,实际搜索过程就不止三步了,此时称之为“Log-D搜索”更为确切。TSS算法采用一种由粗到细的搜索模式,从搜索窗口中心开始,按一定步长取周围8个点作匹配运算,初始搜索步长为4,得到MBD点后,每次利用上一步搜索得到的最佳匹配位置作为当前搜索的中心位置,每做一步,搜索步长减半,直至搜索结束。
(2)算法描述
第一步,以窗口中心点(0,0)为中心搜索点,步长为4,包括周围的8个像素点,计算各点SAD,根据最小SAD值得到一个MBD点,共搜索9个点。第二步,以上一步的最佳匹配点为中心,步长为2,继续搜索周围8个像素点,计算各点SAD,根据最小SAD值得到MBD点,共搜索8个点。第三步,同上一步,只是步长减小1,最后得到的MBD点就是需要的运动估计的点,从而得到运动矢量。核心编程如下:
%以宏块边长为单位步长,在每个宏块的上下左右四个方向上,寻%找其最吻合的分块
for i=1:mb Size:row-mb Size+1
for j=1:mb Size:col-mb Size+1%每走一步分析9个元素,在循%环运算之前,先单独算出中心点的代价,然后再循环计算中心点周围
%需要估计点的代价。
costs(2,2)=cost Func SAD(…);%计算SAD值
while(step Size>=1)
for m=-step Size:step Size:step Size
for n=-step Size:step Size:step Size
if(ref Blk Ver<1||……)%判断搜索是否超出边界
costs(cost Row,cost Col)=cost Func SAD(…);
%计算SAD值
end
end
[dx,dy,min]=min Cost(costs);%找到SAD最小值
step Size=step Size/2;%缩小搜索步长
end
end
end
motion Vect=vectors;%得到运动矢量
(3)模板及搜索图示
图2给出一个可能的搜索例子。图中点[+4,+4],[+6,+4]是第一步和第二步的最小块误差点。第三步得到的最终运动矢量为[+7,+3],每个点上的数字表明了每个阶段搜索时计算的候选块的位置,方块点表示每步的MBD点。
(4)算法分析
TSS是较早的搜索速度和搜索精度两者取得比较适当折衷的快速算法,因其搜索步骤简单固定而易于硬件实现,已经在很多视频压缩系统中得到了应用。其最大搜索点数为1+8log2w,针对一个16×16的像素子块,TSS算法共搜索25个点,而ES要进行15×15=225个点的搜索,运算时间明显减少。它还具有简单容易实现、每个块的搜索点数相同的优点。但是TSS算法搜索时,整个过程采用了统一的搜索模板,使得第一步的步长过大,容易引起误导,从而对小运动效率较低,容易跳出运动矢量存在可能性较大的区域,导致搜索方向的不确定性,因此很容易陷入局部最优。当搜索范围大于7时,仅用三步是不够的,搜索步数的一般表达式为log2(dmax+1)。
1.3 新三步搜索法
(1)基本思想
新三步搜索法(NTSS)由R.Li,B.Zeng和M.L.Liou于1994年提出的。它是在三步法的基础上利用了运动矢量中心偏置分布特性,并应用中止判别技术,减少了搜索次数。NTSS算法在第一步中通过搜索增加的中心8个点来修改搜索模板,同时NTSS使用半路中止技术来加速静止块的匹配,以此来减少搜索次数。NTSS算法与三步法的不同在于以下两点:(1)改进了原有三步法第一步中搜索固定9个点的方法,采用了基于中心偏置的搜索模式;(2)对静态子块或者准静态子块的搜索引入了中途停止的功能。
(2)算法描述
第一步,对搜索窗口中心9×9的矩形框和3×3的矩形框的17个点进行匹配运算,如果第一步搜索中最小SAD像素点发生在搜索窗中心相邻的8个点,则第二步的搜索模式有两种可能,分别添加5个点和3个点,如图3所示,其中白点是待搜索点。第二步,根据第一步得到的最小SAD值的位置决定第二步匹配的位置:(1)如果最小的SAD值在搜索窗口的中心位置,则停止搜索;(2)如果最小的SAD值在3×3的矩形框上得到,则搜索以此点为中心位置的3×3的窗口,并结束搜索;(3)如果最小的SAD值在9×9的矩形框上得到,则搜索的步骤与TSS算法相同,搜索完成后跳到第三步。第三步,以第二步得到的最佳匹配位置为中心,做最后的3×3窗口中九个点的匹配,得到最小SAD值的位置,就是最佳的匹配位置。核心编程如下:
%以宏块边长为单位步长,在每个宏块的上下左右四个方向上,寻找其最吻合的分块:
%然后再循环计算中心点周围需要估计点的代价。
找到外八点SAD最小的点;
找到内八点SAD最小的点;
if(x,y)仍然为中心点(j,i)
提前跳出计算循环;
elseif(min2<=min1)
进入新三步法模式NTSS
else
进入原三步法模式TSS
end
……
end
end
motion Vect=vectors;%得到运动矢量
(3)模板及搜索图示
图4为NTSS算法的一个可能搜索过程的示意图。每个点上的数字表明了每个阶段搜索时计算的候选块的位置。图中点(+1,+1)是第一个搜索阶段的MBD点,第二个阶段的MBD点为(+2,+2),最终运动矢量为(+2,+2)。方块点表示每步的MBD点。
(4)算法分析
运动矢量通常总是高度集中分布在搜索窗的中心位置附近,新三步法采用中心倾向的搜索点模式不仅提高了搜索速度,而且减少了陷入局部极小的可能性。而采用中止判断技术则大大降低了搜索复杂度,提高了搜索效率。新三步法在快速算法发展中具有重要意义,在它之后的所有算法都利用了运动矢量中心偏置特性。实验证明,新三步法的性能要高于三步法。新三步搜索算法考虑了块矢量中心偏移的特性,在初步搜索时对中心周围的位置同时做了匹配运算。在物体做小范围运动时,这种改进很有效,可以大大减少运算量。然而,在物体做大范围运动时,这种改进却带来了额外的运算量。现实的情况经常是物体既有小范围偏移,也有大范围运动。因此,在考虑块匹配算法时,既要照顾块的中心偏移特性,也要兼顾块的大范围运动。菱形搜索法能够兼顾两种情况,可以得到较好的性能。
1.4 菱形搜索法
(1)基本思想
菱形搜索算法(DS),最早由Shan Zhu和Kai-Kuang Ma两人提出,是目前快速算法中性能最优异的算法之一。在块匹配算法中,搜索窗口太小,就容易陷入局部最优;而搜索窗口太大,又容易产生错误的搜索路径。另外,根据运动矢量的中心偏置分布特性,在进行运动估计时,最佳运动矢量通常在零矢量周围(距离中心,半径为2像素的圆内),如图5所示。DS算法使用两种搜索模式,如图6所示,第一个称为大菱形搜索模式LDSP(Large Diamond Search Pattern),由九个检测点组成,围绕中心点的八个点形成一个大菱形形状。第二个称为小菱形搜索模式SDSP(Small Diamond Search Pattern),由五个检测点形成小菱形的形状。菱形法先使用大模板进行搜索,当其MBD点出现在中心点处时,认为找到了最优匹配点所在的区域,然后再用小模板进行更为精细的定位,最后这个小模板5个点中的MBD点即为最终获得的运动矢量。
(2)算法描述
第一步,初始化大菱形LDSP以搜索窗口的原点(0,0)为中心,测试LDSP的九个检测点。如果计算得到的MBD点位于中心位置,则转到第三步;否则,转到第二步。第二步,以上一次找到的MBD点作为中心建构新的LDSP并计算其8个搜索点的匹配误差,找到新模板的MBD点。若它位于模板中心,则转到第三步;否则重复第二步。第三步,以上一次得到的MBD点作为中心建构小模板SDSP,在其5个搜索点处进行匹配计算和比较,找出MBD点,该点所在位置即对应最终得到的运动矢量。主要代码如下:
%定义大钻石搜索图样
%以宏块边长为单位步长,在每个宏块的上下左右四个方向上,寻%找其最吻合的分块
for i=1:mb Size:row-mb Size+1
for j=1:mb Size:col-mb Size+1
%首次搜索将大菱形图样9个点的代价全部计算一遍
for k=1:9
costs(k)=cost Func SAD(…);end
%如果代价最小点为大钻石图样的中点,则开始小钻石图样搜索;
%小菱形搜索开始
end end
motion Vect=vectors;%得到运动矢量
(3)模板及搜索图示
图7给出了DS算法一种可能的搜索过程。图中(-2,0)、(-3,+1)、(-4,+2)、(-4,+2)分别是第一、二、三、四次LDSP搜索的MBD点,然后按SDSP模式搜索(-4,+2)周围的四个点,即可得到最后一步的MBD点,从而得到运动矢量为(-4,+2)。图中的数字代表搜索步数,带方块的点代表每一步的MBD点。
(4)算法分析
菱形法利用了运动矢量的中心偏置分布规律,选用了两种不同大小的搜索模板进行搜索。它首先使用搜索范围较大的LDSP进行粗定位,当粗定位的搜索结束后,认为最优点就在LDSP的8个点所在的菱形区域中,此时再利用SDSP来进行更为精细的定位,使搜索不致有较大的起伏,其性能优于之前的快速块匹配算法。此外,由于DS搜索时各步骤之间有很强的相关性,即相邻阶段的搜索模板之间会有一定数量的搜索点重叠,模板移动时只需在几个新的搜索点进行匹配计算,这也进一步减少了搜索的计算点数,提高了运算速度。DS算法不限制搜索的步数,既对各个方向进行搜素,又着重考虑水平竖直方向,所以这种算法可以使搜索避免找到局部最佳位置,得到更好的性能。
2 实验结果与分析
在配置为Pentium Intel D CPU 2.80Hz、1.00GB内存和操作系统为Windows XP的PC中,使用Matlab7.0作为仿真平台,对以上算法进行仿真实验。使用三种典型的视频序列Foreman、Coastguard、Caltrans,其均为标准QCIF序列图像的前30帧,分辨率为176×144,每一帧大小为75KB。其中Foreman是具有较小运动,空间细节不太丰富的视频序列;Coastguard是具有中等运动的序列,空间细节比较丰富或者不太丰富的视频序列;Caltrans是具有较大运动内容,空间细节很丰富或者较为丰富的视频序列。在测试过程中,使用SAD为匹配准则,运动估计的宏块大小为16×16,搜索范围为15×15,即±7个像素点,静止判定阈值T设定为512。为了验证算法在搜索速度和搜索精度两方面的性能,采用两个指标进行衡量:平均每块的搜索点数和平均峰值信噪比PSNR。
对于上述的3幅实验图像序列,ES、TSS、NTSS和DS的比较实验结果见表1和表2。从表1的实验结果可以看出:DS无论对于哪种运动类型的视频,相对于其他块匹配算法其搜索速度上都有很大的改善(以搜索点数衡量),而ES的搜索速度是最慢的。从表2的实验结果可以看出:对于运动较小的视频序列和具有剧烈运动的视频序列,DS不仅在搜索速度上,而且在搜索精度上也具有较大的优势,其平均PSNR高于TSS和NTSS算法;对于具有中等运动的视频序列,其平均PSNR与TSS和NTSS基本相当。
为了比较各种算法对每帧的效果,图8、图10和图12分别显示了序列Foreman、Coastguard和Caltrans的平均的搜索点数曲线图,这些曲线清楚地表明了DS的平均搜索点数比其他BMA减少很多。图9、图11和图13显示了Foreman、Coastguard和Caltrans序列中不同BMA的PSNR比较。可以看出,对于具有较小运动Foreman的视频序列和大运动Caltrans的视频序列,DS还是具有一定的优势。
3 结语
通过对运动估计中的ES、TSS、NTSS和DS等块匹配算法比较可知:单从匹配的角度看,ES无疑是一种最好的匹配方法,搜索精度最高,但计算量过大,效率低下。TSS在搜索速度和搜索精度两者之间取得了比较适当的折衷,但可能存在搜索方向的不确定性,容易陷入局部最优的误区。NTSS考虑了块矢量中心偏移的这一重要特性,提高了搜索速度,在它之后的算法都利用到了这一特性。但对于大范围运动,这一改进却带来了额外的运算量。DS兼顾了以上算法的缺点,取得了更好的性能,是公认的一种较好的搜索算法。后来所推出的块匹配算法往往都会和DS算法进行比较,以确定其算法的效果。
摘要：对图像序列运动估计中的穷尽搜索法、三步法、新三步法和菱形法等块匹配算法的基本思想、算法描述、搜索模板以及算法性能进行分析和研究,并在实验仿真中,采用平均每块搜索点数和平均峰值信噪比PSNR为衡量指标,测试了在三种典型的视频序列运动估计中每种算法的搜索速度和效果,得出菱形法综合性能更为优越的结论。
关键词：块匹配,运动估计,三步法,新三步法,菱形法
参考文献
[1]Yao Wang,等.视频处理与通信[M].杨喜,等译.北京:电子工业出版社,2003.
[2]唐泽鹏,秦雷,朱秀昌,等.运动估计算法分析[J].电视技术,2001(12):10-13.
[3]Li R,Zeng B,Liou M L.A new three-step search algorithm for blockmotion estimation[J].IEEE Trans.Circuits Syst.Video Technol,1994,4(8):438-442.
块匹配准则 篇5
帧内预测算法在视频压缩方面可以有效地减小空间冗余。H.264/AVC[1]是由国际电信联盟标准化组织 (ITU-T) 的视频图像专家组 (VCEG) 和国际化标准组织 (ISO/IEC) 的运动图像专家组 (MPEG) 共同组建的联合视频组 (JVT) 所开发的视频编码标准。
H.264/AVC标准在算法上分为两层, 视频编码层VCL (Video Coding Layer) 和网络提取层NAL (Network Abstraction Layer) 。视频编码层负责进行高效的视频内容处理;网络提取层则负责网络分段格式封装数据, 包括组帧、逻辑信道的指令、定时信息的利用和序列结束信号等。其码流结构具有网络适应性强、容错性好、对误码和丢包处理能力强的特点。
帧内预测算法[2]提供了4×4和16×16两种宏块预测模式, 4×4的亮度帧内预测共有9种模式, 模式2为DC模式, 模式0、1、3、4、5、6、7、8代表8个不同的预测方向。在一个4×4宏块中, a~p为16个待预测像素, 而A~M是临块中已经编码的13个像素值, 每个预测模式就是用相邻像素A~M中的一个或者一些值来预测a~p的像素值。为了提高帧内预测的准确度, 前人已经做了大量的工作, 他们大多仅仅通过临块中已编码的13个边界像素值来产生当前预测块[3,4]。块匹配算法最初被广泛用于图像重建从而恢复丢失的宏块。从这个算法中体现出一个主要概念, 在同一帧中研究者可以找到一些与当前预测块相似的宏块[5]。
本研究将基于块的帧内预测和块匹配算法相结合, 提出一种新的块匹配算法, 将帧内预测中的DC模式与BM (block-matching) 模式两种模式相结合, 形成一种新的预测模式, 以替代原有帧内预测中的模式2。并应用H.264标准的相关参考软件JM18.2[6]对算法性能做了测试。
1 基于块匹配算法的帧内预测算法
当某一帧中的一个宏块丢失时, 最一般的方式通过块匹配算法恢复。本研究采用一种搜索方式, 从当前帧中寻找一个匹配块, 使其边界像素值与丢失宏块的边界像素值最接近。利用匹配块信息, 可以预测丢失的宏块, 并完成宏块的重建过程。
帧内预测与恢复某一帧中的丢失宏块很相似。本研究称待编码的宏块为目标宏块。目标宏块就好比当前帧内丢失的宏块, 因此, 可以利用匹配块重建目标块, 以获得更好的帧内压缩结果。从这方面考虑, 本研究将块匹配算法融入到了帧内预测算法中, 用F表示当前帧, 用C表示已被编码的区域, 预测过程为通过匹配块P预测目标块T的过程。
本研究利用宏块搜索方式替代简单的方向预测方式实现帧内预测, 因此, 明显这种算法更耗时。但据统计, 相较距离远的宏块之间, 距离近的宏块之间更趋向于产生更强的空间相关性。因此对于一个宏块, 不必搜索C范围内的所有宏块去定位一个匹配块。本研究选择一个阈值τ作为宏块匹配的搜索范围参数, 根据经验, 同时考虑到复杂度和编码质量, 选择τ=24, 在距当前宏块左上角像素点24个像素点的半圆内进行搜索, 作为候选区域C′, 示意图如图1所示。以这种方式, 减少了候选模块, 同时将算法的复杂度降低到相当低的水平。
应用编解码器所定义的编码顺序, 没法获取目标宏块的所有边界信息, 所以只能利用部分边界像素信息来完成块匹配。更明确地讲, 对于H.264的4×4宏块预测, 研究者只能利用边界的9个像素值, 上侧的4个像素, 左侧的4个像素和左上角的1个像素, 边界像素的分布如图2所示。
如图2所示, 通过计算目标宏块T边界像素的灰度值 (用M1~M9表示) 与若干候选宏块P'边界像素的灰度值 (用M1′~M9′表示) 之间的均方误差。计算而得的均方误差值最小的候选宏块P被认为是目标宏块T的匹配宏块数学描述为:
这里, n=9, 代表与宏块匹配的像素个数。
当研究者选择了匹配宏块之后, 可以利用它的重建信息来直接预测。
2 编、解码器算法优化
2.1 编码器
本研究将基于块匹配的帧内预测算法整合到H.264/AVC中, 作为帧内预测的一种模式。为了方便实施又节省对于模式的额外编码, 笔者将帧内预测中的DC模式与BM模式两种模式相结合成一种新的预测模式, 替代了原有帧内预测中的模式2 (帧内预测中的DC模式[7]) 。编码器运用这种新的模式连同其他8种预测模式[8]一起实现4×4宏块的帧内预测, 选择率失真最小的模式为最佳预测模式。因为没有使用其他额外的模式, 本研究提出的算法可以与原H.264/AVC标准相兼容。
本研究选择改变DC模式的原因: (1) BM模式与DC模式一样, 在图片平滑区域有很好的预测性能; (2) 对于图片上的纹理区域或者单调的背景区域等区域, BM有着更优于DC模式的编码性能。
本研究利用DC模式来预测位于帧左边缘和上边缘的宏块, 是因为这些宏块只有4个边界像素点, 不足以进行准确的宏块匹配。利用DC模式来预测这些区域可以保持编码效率。
4×4亮度块帧内预测模式的选择, 采用率失真优化RDO[9] (Rate Distortion Optimization) 判优准则:
式中:QP—量化参数;λMODE—拉格朗日参数, ;Imode—9种预测模式中的一种;s—亮度4×4块的原始值;c—预测残差块经过DCT变换、量化、IDCT反变换、反量化得到的重构宏块;SSD—s和c的差值平方和;R—确定MODE和QP后的宏块编码比特数。
基于块匹配的帧内预测步骤如图3所示:
(1) 分别用9种模式对4×4亮度块进行帧内预测。
(2) 对预测残差块[10]进行DCT变换/量化、反DCT变换/反量化, 计算Intra 4×4代价JImode。
(3) 选择编码代价最小的模式:
(1) 若计算得代价最小的模式为模式2以外的8种模式之一, 即用此模式进行帧内预测;
(2) 若计算得代价最小的模式为模式2 (DC模式) , 则继续进行以下步骤:
(a) 若宏块位于当前帧上边缘或左边缘, 则用DC模式预测;
(b) 若宏块位于当前帧的其他位置, 则用BM (块匹配) 算法预测。
2.2 解码器
至于解码器端, 如果知道一个4×4的宏块已经通过模式2编码, 那么检查这个宏块, 如果该宏块位于该帧的左侧或者上侧, 通过DC模式解码该模块, 否则, 通过BM模式解码该模块。通过BM模式解码宏块, 解码器也要在当前帧内按照阈值τ (τ=24) 确定的一定范围做搜索, 然后利用匹配模块的信息做预测, 这样不仅提高了解码过程的速度, 同时也实现了与编码器端的同步。
3 实验结果
本研究将基于块匹配的帧内预测优化算法应用于参考软件JM18.2上, 在全I帧、RDO模型下, 分辨选用4个量化参数QP (16, 20, 24, 28) 分别对QCIF源序列Foreman、Carphone各100帧进行测试。
测试图如图4、图5所示。比较图4和图5, 可以主观观察到, 利用新提出算法实现的预测帧非常接近原帧, 尤其相较于标准的H.264预测算法, 在背景的边缘处更加平滑, 可直观地观察到图像质量有明显的改善。
通过优化算法 (Proposed) 和标准H.264/AVC帧内预测算法 (JM18.2) , 分别对源序列Foreman、Carphone处理后的测试结果如表1、表2所示, 由表2可以观察到, 和标准H.264/AVC帧内预测算法相比, 优化算法的峰值信噪比 (PSNR) 明显增加, 而比特率 (Bit Rate) 增幅控制在较小的范围内。
利用本研究提出的算法 (Proposed) 和标准H.264/AVC帧内预测算法 (JM18.2) , 对Foreman和Carphone两个序列处理后的RDO对比曲线图如图6、图7所示。实验结果表明, 本研究提出的优化算法曲线位于原标准算法的左上方, 在性能上优于标准H.264/AVC帧内预测算法0.1 d B~0.4 d B, 由此充分证明了本研究提出算法的有效性。
4 结束语
本研究提出了一种基于块匹配算法的帧内预测算法, 进一步提高了H.264/AVC的帧内预测性能。将帧内预测中的DC模式与BM模式两种模式相结合, 形成了一种新的预测模式, 替代了原有的帧内预测中的模式2。通过JM18.2来实现并测试性能。实验结果表明, 相较于标准的H.264/AVC算法, 这一方法可以总体上提高已经压缩的I帧性能0.1 d B~0.4 d B, 有效地改善编解码性能。
参考文献
[1]Joint Video Team (JVT) of ISO/IEC MPEG&ITU-T VCEG.Draft ITU-T Recommendation and Final Draft Inter national Standard of Joint Video Specification (ITU-T Rec.H.264 ISO/IEC14496-10AVC) [S].JVT-G050, 2003.
[2]苏奇, 张发存.H.264/AVC快速帧内预测模式选择新算法[J].计算机应用, 2011, 31 (2) :393-395.
[3]NOH D Y, KIM E, SOHN C B, et al.A fast luminance in tra 4×4 prediction mode decision method by statistical anal ysis of residual data in H.264/AVC[C]//Consumer Electron ics (ICCE) , 2012:151-152.
[4]LI Jian-hua, CHEN Li-hua.A fast intra mode decision al gorithm for H.264/AVC[C]//IEEE International Conference on Communication Technology (ICCT) , 2010:416-419.
[5]CHERIGUI S, GUILLEMOT C, THOREAU D, et al.Hybrid template and block matching algorithm for image intra pre diction[C]//IEEE International Conference on Acoustics, Speech, and Signal Processing, INRIA, Rennes, France, 2012:25-30.
[6]Heinrich Hertz Institute.H.264/AVC Software Coordination[EB/OL][.2013-05-13].http://iphome.hhi.de/suehring/tml/.
[7]SU Xiu-Qin, JI Lei, LI Xiang.A fast and low complexity approach for H.264/AVC intra mode decision[J].Multime dia Tools and Applications, 2011, 52 (1) :65-76.
[8]MILICEVIC Z, BOJKOVIC Z.H.264/AVC standard:a pro posal for selective intra-and optimized inter-prediction[J].Journal of Network and Computer Applications, 2011, 34 (2) :686-691.
[9]WANG Shi-qi, REHMAN A, WANG Zhou, et al.Rate-SSIM optimization for video coding[C]//IEEE International Con ference on Speech and Signal Processing (ICASSP) , 2011:833-836.
块匹配准则 篇6
1 块匹配搜索算法
数字散斑相关搜索法中多采用基于区域匹配的灰度匹配法,所以视频图像处理中的基于块匹配的运动估计快速搜索法的有关思想可以运用到该搜索算法中[4]。视频图像处理中是跟踪最小块误差(Minimum Block Deviation,MBD)点,在DICM中改为跟踪相关系数最大(Maximum Correlation Coefficient,MCC)点。本文选用标准化协方差相关函数,因为其相关系数矩阵呈单峰分布,且相关峰更尖锐,定位精度高。具体的形式如式(1)所示。
式(1)中,f(xi,yi)为参考图像中图像子区中点(xi,yj)处的灰度值;为变形后图像中图像子区中点()处的灰度值;为参考图像中图像子区的平均灰度;为变形后图像中图像子区的平均灰度。
典型的块匹配快速搜索算法有全搜索法(Full Search Method,FS)、三步搜索算法(Three Steps Search Method,TSS)、四步搜索法(Four Steps Search Method,FSS)和菱形搜索法(Diamond Search Method,DS)[5],这四种算法都是通过改变搜索方式,从而达到减小搜索区域提高搜索速度的目的。
2 仿真计算
2.1 仿真散斑的生成
为了对比不同算法的搜索效率,本文根据Peng Zhou提出的算法[6]以及上述四种块匹配搜索算法的基本原理利用MATLAB软件自行编制了一套针对木材变形测量的分析程序,该程序能够生成精确控制位移的数学仿真散斑图,并且可以准确地控制图像大小、散斑数量及散斑亮度;同时可以选取不同的块匹配搜索算法对生成的散斑图进行数字散斑相关分析,得到每像素点的位移。本文采用的仿真散斑大小为256×256 pixels,散斑数量为800,散斑大小为4 pixel。图1 (a)、(b)分别为MATLAB软件生成的散斑图及该散斑图在x正方向平移1 pixel后的散斑图。
2.2 仿真结果及分析
为了对比分析单一方向存在位移以及x方向和y方向均存在位移时的不同情况,首先生成如图1所示的四组散斑图,每组散斑图的x方向和y方向位移如表1,第一组和第二组表示单一方向存在位移的情况,第三组和第四组表示x方向和y方向均存在位移的情况。每组分别有10对平移前后的模拟散斑图,以考察算法的稳定性。
分别使用全搜索法、三步搜索法、四步搜索法和菱形搜索法计算每像素点的整像素位移,可以得到不同位移大小下四种搜索算法的搜索时间。表2给出了四种搜索算法搜索每组仿真散斑图对所用的平均搜索时间,由表2可以看出由于全搜索法的搜索区域最大,其搜索时间远远大于其他三种算法,如果处理较大的图像,全搜索法计算效率低的缺点将会更为明显。
3 试验验证
为了验证四种块匹配算法在木材弯曲变形测量中的有效性,本文首先进行了刚体平移试验,验证不同算法的精度,然后进行了木材三点弯曲验证试验。
3.1 试验材料及设备
试验材料为白桦,含水率约为10%,尺寸为200mm×20 mm×20 mm,设备为电子万能试验机(型号为RGM—2050),精度可达0.001 mm。本文利用黑色与白色的自喷漆,在试件表面交替喷涂形成随机分布的人工散斑场。试验过程中,试件表面由LED光源照明,被测试件的图像由放置在其正前方约0.1 m的图像采集系统采集。图像采集系统包括一个分辨率为1 280 pixel×1 024 pixel的CMOS数字摄像机(型号MV—130UM)和变焦镜头(AFT—0850ZMP)。调焦清晰成像后,图像中每像素所对应的空间尺寸约为25μm。
3.2 试验结果与分析
利用自行编制的MATLAB程序进行数字散斑相关处理,选取有效区域为研究对象,有效区域位于图像中间位置的128 pixel×128 pixel区域(如图2),得到搜索时间与搜索精度如表3(表中计算位移为通过块匹配算法计算得到的位移,试验位移为由试验机测得的实际位移),其中刚体平移试验中位移为128×128个像素点的平均位移,三点弯曲试验中位移为试件弯曲的挠度值。
对于刚体平移,其前后图像如图3所示。由表3可以看出,全搜索算法的搜索时间为3.179 9 s,远远大于其他三种算法;三步搜索算法虽然搜索时间最短,但是68.6%的相对误差说明其匹配错误率较高;四步搜索法和菱形搜索法位移相对误差仅为1.49%,表明在误差允许范围内,四步搜索算法和菱形搜索算法可以用于木材弯曲变形的测量。
木材三点弯曲前后的图像如图4所示,由表3可以看出,全搜索法搜索时间为2.991 3 s,远远大于其他三种算法,这点与仿真试验一致,表明全搜索法搜索效率低;三步搜索算法的搜索时间为0.141 9 s,在四种算法中计算速度最快,但是三步搜索算法的位移相对误差(69.7%)远大于全搜索法(1.99%)、四步搜索算法(1.99%)和菱形搜索算法(1.99%);四步搜索算法的搜索时间(0.286 3 s)略大于菱形搜索算法的搜索时间(0.261 9 s),但当处理较大的图像时,这种搜索时间上的差距会更加明显。因此综合考虑搜索时间与搜索精度,对于木材弯曲变形测量,菱形搜索算法最优,四步搜索算法次之。
4 结论
本文考察了四种常用的块匹配搜索算法在利用数字散斑相关方法进行木材弯曲变形测量的有效性。综合考虑仿真计算与木材三点弯曲验证试验,结果表明,对于木材弯曲变形测量,全搜索算法虽然搜索精度很高,但搜索时间远远大于三步搜索算法、四步搜索算法和菱形搜索算法,其搜索效率低;三步搜索算法虽然计算效率最高,但搜索精度较低;四步搜索算法和菱形搜索算法搜索精度较高,菱形搜索算法的搜索时间略少于四步搜索算法。因此在进行木材弯曲变形测量时,菱形搜索算法最优,四步搜索算法次之。
参考文献
[1]江泽慧,费本华,张东升,等.数字散斑相关方法在木材科学中的应用及展望.中国工程科学,2003;5(11):1-5
[2]孙艳玲,赵东,高继河.数字散斑相关方法在木材断裂力学上的应用分析.北京林业大学学报,2009;31(1):206-210
[3] Chen Yongsheng,Hung Yiping,Fuh Chioushann.Fast block matching algorithm based on the winner-update strategy.IEEE Transactions on Image Processing,2001;10(8 ):1212-1222
[4]伍卫平.图像相关技术的亚像素位移算法与实验研究.武汉:华中科技大学,2009
[5]杨高波,杜青松.MATLAB图像/视频处理应用及实例.北京:电子工业出版社,2010
[6] Zhou P,Goodson K E.Subpixel displacement and deformation gradient measurement using digital image/speckle correlation.Opt Eng, 2001;40(8):1613-1620
[7]王怀文,亢一澜,谢和平.数字散斑相关方法与应用研究进展.力学进展,2005;35(2):195-203