块匹配算法（通用7篇）
块匹配算法 篇1
1 块匹配算法简介
块匹配算法就是对两帧图像的同一个位置的运动通过分块比较得到其估计矢量。算法思想如下：每一帧图像都被分割为若干个大小为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.
[3]张艳.空间域超分辨率图像重建技术研究[D].中国人民解放军信息工程大学.2007.
块匹配算法 篇2
图像序列中相邻两幅图像之间在内容上的差异不会太大,或者说后一帧的内容与前一帧重复的部分很多,二者是相关的。而消除这种时间的相关性(冗余度),是视频压缩编码的一条重要途径。运动估计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.
块匹配算法 篇3
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
块匹配算法 篇4
关键词：电子稳像,块匹配法,DM642
电子稳像技术是用图像处理算法对抖动的视频图像序列进行稳像处理的方法。目前,电子稳像算法在硬件平台上的实现主要用C6000系列的DSP。C6000系列的DSP适合于实现图像处理算法,这种系列的DSP工作主频高,运算速度快,且带有实时的BIOS操作系统,适合图像处理时要求数据量大、实时输出图像的特点。杨光宇、朱丹等人用灰度投影算法在FPGA+DSP架构的嵌入式平台上进行了电子稳像[1]。本文则采用块匹配算法在DM642上进行电子稳像。块匹配算法是电子稳像中测量图像平移抖动的经典算法,它原理简单,易于编程实现。本文先将块匹配法在MATLAB软件上仿真,然后将算法移植到DM642上。
1 块匹配法的原理
传统的块匹配算法是固定参考帧的小块,移动与参考帧处于同一位置当前帧的小块,直到得到最小的SAD值[2]。本文则是固定当前帧的小块,移动参考帧的小块。如图1所示。
在当前帧的某一位置选取大小为M×N的小块block1,在参考帧同样的位置也选取大小为M×N的小块block2。图像没有抖动静止时,block1与block2是完全重合的。视频存在抖动时,block1运动到其他的位置,block1与block2不再重合。固定block1,在(M+2×dx,N+2×dy)的范围内,搜索到某一点(dxmin,dymin)时,当前帧和参考帧的SAD值最小,则该点对应的匹配块就是最佳匹配块。SAD为
式中:qt,qt-1分别为当前帧和参考帧的灰度值;dx,dy为X,Y方向运动位移[3]。
2 DSP的硬件配置
本实验采用合众达公司的SEED-DTK-VPM642开发箱,DSP硬件由CCD摄像头、解码芯片TVP5150、DM642、编码芯片SAA7105、液晶显示屏构成[4]。如图2所示。
DM642的工作频率可由内部倍频器设置,可以设置为500 MHz,600 MHz,720 MHz,本实验设置为600 MHz。DM642采用两级储存器分层结构:L1储存器和L2储存器。L1储存器包括16 kbyte的高速程序缓存和16 kbyte的高速数据缓存。DM642的L2容量为256 kbyte,设置CCFG寄存器中的L2MODE[2:0]字段为(011)2,把128 kbyte分配给SRAM,剩余的128 kbyte设置为外部储存空间CE00和CE01的高速数据缓存。设置高速数据缓存,可以大大提高数据从外部储存空间到内存的搬移速度,从而提高图像的实时性。DM642有3个可编程视频口,VP0,VP1和VP2,本实验采用VP0采集视频,VP1和VP2这2个视频口不使用。
3 块匹配算法设计
3.1 基于BIOS的程序设计框架
编程时采用了多线程的操作系统BIOS,从而提高了图像输出的实时性。块匹配算法的程序分为3个任务:视频采集任务、视频处理任务和视频显示任务。这3个任务互相分开,互不干扰,3个任务间相互循环,大大加快了程序的运行速度,如图3所示。
视频采集任务将图像采样成YUV 4∶2∶2格式的数据帧[5],并转换成4∶2∶0格式,然后将参考帧和当前帧的数据传递给视频处理任务。视频处理任务接收到参考帧和当前帧的数据后,进行块匹配运算,并将YUV 4∶2∶0格式的数据传递给视频显示任务。视频显示任务接收到数据帧后,将YUV 4∶2∶0格式的图像重新采样为YUV 4∶2∶2格式的图像,最后将YUV 4∶2∶2格式的视频按照参考帧和补偿帧的顺序在液晶屏上显示。
3.2 程序的设计思路
液晶显示屏的大小为576×720,显示屏的长宽比例为720/576=1.25,所以在水平方向上取3个小块,垂直方向上取2个小块,以符合显示屏的长宽比例。在图像上,均匀地取6个小块,块与边界的水平距离、块与块之间的水平距离是相等的,块与边界的垂直距离、块与块的垂直距离也是相等的。均匀选块,可以充分利用图像的运动信息,比较客观地得出图像运动的位移值,如图4所示。
实验时,要充分利用DSP的硬件资源,同时要兼顾图像输出的实时性与运动矢量的准确性。块选取的越大,得出来的位移值越准确,但输出图像的实时性越差;块选的太小,则运动估计位移值的准确度会下降。编程时块的大小选为60×60。块的选择过程如下:如果块的大小为80×80或70×70,则块匹配算法处理的数据量太大,输出图像的实时性太差;取50×50或40×40的块,从视觉效果上看,输出图像的实时性与60×60的块差不多;而选取60×60的块,基本上能达到图像显示实时性的要求,因此选择60×60的块。块的搜索范围与块边长相匹配,须选取合适的值。同样,如果搜索范围选取的太大,则程序运行时数据量大而造成图像输出的滞后,太小则运动估计的位移范围太小。选定X方向的搜索范围是±30像素,Y方向的搜索范围是±30像素。得出X,Y方向的运动位移后,需剔除不准确的运动矢量。根据多数运动位移值方向相同的原则,剔除少数的方向相反的运动位移值。方向相反的运动位移值是由于图像内包含运动物体造成的,或是手持摄像头时,包含旋转运动造成的。剔除后对余下的运动位移值求平均值,得出X方向的运动位移值。剔除不准确的运动位移值过程如下:第一种情况是如果5个运动位移值都大于0,1个小于0,则除掉小于0的那个运动位移值,反之亦然;第二种情况是4个运动位移值大于0,2个运动位移值小于0,则除掉2个小于0的运动位移值,反之亦然[6]。运动估计得出运动位移值后,进行当前帧图像的运动补偿。运动补偿采用相邻帧补偿法,运动补偿时将运动位移值符号取反,得出当前帧的抖动位移。补偿时将当前帧整幅图像的像素按照X,Y方向的运动位移的反方向进行平移,对移动留下的空白边缘处的像素灰度值赋0即可。由于像素的面积太小,且在边缘处,所以像素灰度值赋为0的边缘区域基本上不影响视觉,图像边缘不会出现明显的空白。对当前帧进行运动补偿后,先输出参考帧的图像,然后输出补偿帧的图像。
3.3 编写程序的调试过程
由于DM642的L2的容量为256 kbyte,存储空间很小,所以将程序、变量等放在程序的外部储存空间SDRAM。由于采用了多线程的BIOS,所以并不影响图像输出的实时性。亮度分量Y、色度分量Cr与Cb存放于外部储存空间SDRAM中。色度分量Cr,Cb需清零,如果不清零,数据量太大造成SDRAM的溢出,导致图像无法显示。液晶显示屏的大小为576×720,需定义576×720个像素。编写程序时,需将单个像素定义为char型,如果定义为int型,则由于576×720个像素是一个庞大的数组,占有的存储空间太大,导致无法显示图像。编程时,根据CCS的Watch Window中的变量值调试程序,如果变量值不正确,则返回去修改程序,反复进行,直到变量值正确为止。
4 实验结果及分析
设参考帧和当前帧的信噪比为PSNR1,补偿帧与参考帧的信噪比为PSNR2,实验时,手持摄像头小范围的剧烈平移抖动,以获得平移抖动的图像。连续取任意时刻的10组PSNR值,如表1所示。
从PSNR1和PSNR2的两组对比值,可以看出:块匹配算法对抖动图像有一定的稳像效果。可以看出:大部分数据是正常的,只有第4组和9组的数据是错误的。错误的数据是因为摄像头抖动的范围太大超出了运动估计的范围,或因为手持摄像头抖动时,包含了旋转抖动,或因为图像中包含运动物体引起的。理论上,抖动的频率越高,两幅图像的差异越大,PSNR越小。实验时发现:抖动的频率越高,PSNR1与PSNR2越小,符合PSNR的定义。快速抖动时,PSNR1与PSNR2的范围在20 dB以下;缓慢抖动时,PSNR1与PSNR2的范围在25 dB以上,摄像头静止时,PSNR1与PSNR2相等。这些数值结果也符合PSNR的定义。
5 结论
本文在DM642上实现了块匹配算法。该算法在当前帧上选取小块,在参考帧上设置搜索范围,得到与当前帧小块匹配的小块,从而得出X,Y方向的运动位移值,将X,Y方向的运动位移值符号取反后,得出当前帧的运动位移值,然后对当前帧进行运动补偿,输出参考帧和补偿帧视频序列。实验结果表明:对抖动视频序列用块匹配算法进行稳像后,参考帧与当前帧图像的PSNR有明显的提高。
参考文献
[1]杨光宇,朱丹,佟新鑫,等.基于灰度投影法的电子稳像平台设计与实现[J].电视技术,2011,35(19):115-118.
[2]高晓明.电子稳像系统主要算法研究[D].西安:西安科技大学,2008.
[3]朱娟娟.电子稳像理论及其应用研究[D].西安:西安科技大学,2009.
[4]陆勤锋.电子稳像技术在DM642上的实现[J].山西电子技术,2011(3):19-23.
[5]王绥学.实用的电子稳像系统设计[J].计算机测量与控制,2009,19(7):1696-1698.
块匹配算法 篇5
关键词：BM3D,块匹配
1 Block-Matching简介
BM3D(块匹配和3D去噪)算法[1]是目前降噪性能最高的通用图像/视频降噪算法,这种算法利用的视频的空间相关性和时间相关性进行有效的降噪。BM3D算法的步骤包括三个步骤:第一步是块匹配,第二步是三维降噪,第三步是集合。对于块匹配而言,已经有很过关于视频编码协议(如H.264)的文章[2,3]介绍过各种方法, 但是BM3D的块匹配和视频编码算法最大的区别就是可以完全并行完成,因此可以更有效地完成块匹配。
Block-Matching又称块匹配。块匹配模块在当前场以及参考场中搜索与当前块类似的块,并将其集合为组。计算相似的时候,为了简化,不需要把每个块转换到时间域来比较相似,只需要计算当前块和匹配块的SSD(差的平方和),SSD小于阈值τht的最相似的Sxr个块组成一个集合,τht和噪声成正比。根据BM3D算法,每个块需要在当前场的Ns范围,参考帧的Npr范围内查找(Npr<=Ns)。由于搜索出来的块越匹配,最后的去噪效果越好,通常在Ns,Npr的范围内采用全搜索比较合适。由于前后场还依靠运动矢量,如果不加约束,匹配块和当前块有可能相距太远。
通常在搜索的时候还限定了每场的最大搜索范围Nmax。Nmax的限制可以在几乎不降低质量的情况下降低了搜索范围,节约了时间和带宽,但是搜索引擎的性能和带宽都要求还是比较高。比如720*576的PAL场格式BT656的视频,每场大小是720*288,50场/s,当 N1=8,Nstep=6的时候,一场的block总数是Nb=5760块。如果搜索范围是当前场和前2后2总共Nf=5场,最大搜索半径Ns=Npr=15,那么搜索的带宽至少是Nb*N1*N1*(2Ns)* Nf*50(场)=2636MB/s,另外测试了BM3D的Matlab算法(http://www.cs.tut.fi/～foi/GCF-BM3D),在2.4G的PC完成QCIF的视频10帧就运行了30分钟,可见该算法的计算量相当大,而块匹配的计算量就占据了相当大的比例。对于实时的应用而言,必须要使用硬件进行加速。本文提出了一个BM3D 块匹配的架构,该架构只需要系统频率为98MHz,带宽为177MB/s的硬件就可以实现720*576的PAL场格式BT656的视频的实时块匹配。
2 并行的块匹配的ASIC架构
根据文献[4],块匹配是一种广泛应用于视频压缩中的运动估计中的匹配算法,如MPEG-1,MPEG-2,MPEG-4,H.26x[5]。BM3D的块匹配的块和块之间没有相关性,可以完全并行处理,本文提出的结构就是利用这个特点来优化架构设计的。
固定一些参数来说明这个架构,当前块是按照Nstep从左往右,从上往下,再从右往左,再往下的顺序搜索匹配块。这样的结构有助于减少重复的视频数据的读入。搜索范围是前后两场,在当前场内,块匹配以当前块的位置为中心,搜索Ns范围内的所有块,找出最匹配的2块(当前块本身除外),然后以这两个运动矢量为中心,在前1场,后1场中以Npr为半径各搜索出最匹配的两个块,又得到两个运动矢量,再把这两个运动矢量传递给前2场和后2场,在前2场和后2场中各自再搜索出最匹配的两个块,这样总共搜索出11个块。
从时间上来看,这5个部分搜索的不是同一个块的匹配块,其流水线结构如图1所示。根据这个流水线结构,最慢的一帧的搜索决定了系统的性能,比如对于D1,Ns一般为15,Npr=10,这样当前帧就需要搜索大约(2*15)2=900个块,参考帧有两个运动矢量,总共需要搜索大约2×(2×10)2=800个块,当前场的搜索是瓶颈。
在对每场Ns,Npr范围内搜索时候,不需要一个像素一个像素的移动,可以参考文献[6]中计算SAD的结构,同时进行m个块的比较,该结构如图2所示。m个SSD并行计算,在搜索范围内从上往下,再从左往右,在从下往上,再从左往右移动。这样有m个SSD就可以把系统频率降低m倍,代价是增加一个SSD会带来面积的增加。最后一级流水线出两个最好的比较结果。等搜索结束后存储的就是搜索范围内的最好结果。
把Ncol*Nstep个相邻的块组合在一起,构成一个大的宏块,每个宏块在进行搜索时所需要的参考像素需要保存在片内SRAM里。这个SRAM称为滑窗。每个宏块都对应一个滑窗,当一个宏块做完以后,需要更新滑窗的数据以进行下一个宏块的搜索。滑窗结构可以按照(2Nmax+(N1-Nstep)+Ncol*Nstep)*8 比特宽度, (2Nmax+(N1-Nstep)+Nrow*Nstep)比特深度,存储在SRAM中。这样就能保证并行的m个SSD运算单元都能在同一个clock读取到计算需要的数据。
如果Ncol=4,Nmax=30,其他参数参照前面给出的,这个SRAM的宽度就需要(2*30+(8-6)+4*6)*8=688比特, 通常SRAM的深度可以比较大,宽度是有限制的。 虽然可以用多块SRAM并行排列来增加宽度。这样会导致很多块SRAM, SRAM块太多既会增加面积,又影响芯片的布局布线。因此考虑到每次读取的数据是N1+m比特,可以把整个滑窗分成A,B两块,每块的宽度>(N1+m)*8比特就可以了。
图3是N1=8,m=4的情况。这样SRAM的宽度只要12*8=96比特就够了,这样的滑窗结构的宽度可以不随搜索范围Nmax的提高而提高,大部分的memory compiler都能够满足该宽度的需要,深度需要相应的增加。根据这个结构每次m个SSD运算单元需要的N1+m个点的数据都可以通过读取A的一个地址和B的一个地址得到。
3 系统频率和带宽分析
以D1为例,N1=8,Nmax=30,Nstep=5,Ns=15,Npr=10, 搜索当前场的范围是2Ns×2Ns=900。滑窗在完成Nrow*Ncol=4*4个块的匹配后再从外部存储器更新数据。搜索前后场是两个MV,范围是2×2Npr×2Npr=800。当前场的范围大于前后场,当前场的搜索是瓶颈。当4个搜索引擎同时工作的时候,当前场中找相似块的运行时间是(2Ns+8)*(2Ns/4)=38*8=304个clock。前后场中找相似块的运行时间是:2*(2Npr+8)*(2Npr/4)=2×28×5=280个clock。切换当前块的时候,当前块需要8个clock读入,那么4×4相似块需要128个clock,每次4×4相似块匹配都查找完毕后滑窗,滑窗的数据可以先读入到内部buffer,滑窗更新的时候,再写入到滑窗中,一次读,一次写,AB同时进行,地址深度是96*4,滑窗的数据更新时间为96*4=384个clock。这样完成一个4×4相似块匹配总 的时间 是304*16+128+384=5376个clock。一个场有360个4×4相似块,一场的时间需要5376*360=1.94M clock,PAL是50场,这样系统频率要达到96.77M。
对于带宽,计算公式是:
50*Nf* [Nb/(Ncol*Nrow)]*(Nstep*Ncol)*[Nstep*Nrow+(N1-Nstep)+2*Nmax]=
50*5*[5760/(4*4)]*(6*4)*[6*4+(8-6)+2*30]=177MB/s
4 结束语
文中提出的结构,实现了BM3D的块匹配的实时处理,本设计是根据项目Science and Technology Commission of Shanghai Municipality. project No:10706201300来设计的,该项目的目标是在sigma=25的情况下,实现PSNR提高10的D1的实时去噪。降低带宽和系统频率是设计的关键。可以通过提高并行搜索的引擎数目来提高性能,还可以同时进行n场的同时搜索,场切换导致的重复数据的读写就降低n倍。这样实现高清HD的实时BM3D去噪设计是可以实现的。
参考文献
[1] Kostadin Dabov, Alessandro Foi, Karen Egiazarian .Video Denoi-sing by Sparse 3D Transform-domain Collaborative Filtering[C]. 15th European signal processing conference(eusipco) ,September 3-7,2007.
[2] Shiping Zhu, Yangshuan Hou, Zaikuo Wang, et al. A novel fractal video coding algorithm using fast block-matching motion estimation technology[C]. International Conference on Computer Application and System Modeling. 8, 2010:360-364.
[3] Shiping Zhu, Yangshuan Hou, Zaikuo Wang, et al. A novel fractal video coding algorithm using fast block-matching motion estimation technology[C]. International Conference on Computer Application and System Modeling. 8, 2010:360-364.
[4] Kostadin Dabov, Alessandro Foi, Vladimir Katkovnik, et al. Image denoising by sparse 3D transform-domain collaborative filtering[J]. IEEE Trans. Image Process., 2007, 16(8): 2080-2095.
[5]Tung-Chien Chen,Chung-Jr Lian,Liang-Gee Chen.Hardware Ar-chitecture Design of an H.264/AVC Video Codec[C].Desin Auto-matic Asia and South Pacific Conference on 24-27 Jan 2006.
一种改进的块匹配准则 篇6
块匹配算法是最常用的一类运动估计方法,为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.
块匹配算法 篇7
合成孔径雷达(Synthetic Aperture Radar,SAR)是一种可以产生高分辨率图像的主动式微波遥感器,具有全天时、全天候、多波段、覆盖面积大和穿透性强等优点,广泛应用于军事侦察、灾情估计、森林环境监测等军事和民用领域。但是,由于其特殊的相干成像机制,使得SAR图像不可避免地含有相干斑噪声,这会严重的影响SAR图像质量,对后续的特征提取、分割、目标检测、识别带来很大的困难。因此,SAR图像的相干斑去噪具有重要的应用价值。
SAR图像去噪方法主要可以分为两大类,一种为空间域滤波技术,如Lee滤波[1]、Kuan滤波[2]、Forst滤波[3,4],这些方法一般基于图像的局部统计特性进行噪声抑制,通过固定窗口,利用图像的局部信息进行去噪。虽然在平滑区域有着较好的去噪效果,但是对于图像的边缘以及一些纹理信息特别丰富的区域,容易过度平滑造成图像细节信息的丢失。另一种为频域滤波技术,比如小波变换[5],它具有时频局域化特性,从不同的分辨率空间描述图像的局部特性,但是小波变换只有有限的方向;针对此,M.Vetterli等提出了一系列基于多尺度几何分析的方法,如Contourlet[6]、Curvelet[7]。这些方法能够有效地处理图像的边缘信息,可以取得更好的SAR图像去噪效果。但是,频域去噪算法仍然是固定窗口,基于局部信息的滤波,没有考虑其他区域的结构信息。A.Buades等提出了非局部均值(Non-local means,NLM)[8]去噪方法。该方法将传统利用局部特性去噪延伸到了非局部区域,通过对图像中相似块的加权平均来估计真实图像的像素值,得到了很好的去噪效果。之后,人们提出了很多对于NLM的改进算法。2007年K.Dabov等人提出了一种非局部方法和变换域滤波方法相结合的三维块匹配(BM3D)[10]算法,这种方法具备了两者的优点,拥有比NLM更好的去噪效果。2008年和2009年K.Dabov等人相继提出了基于BM3D的两种改进算法,形状自适应块匹配三维滤波(SA-BM3D)[11]和基于主成分分析的形状自适应块匹配三维滤波(BM3D-SAPCA)[12],虽然经过进一步的改进,但是BM3D算法仍然会在去噪图像中引入虚假的纹理,影响SAR图像的相干斑抑制效果。本文针对BM3D算法引入虚假纹理的问题,拟采用基于块匹配的迭代滤波方法,进行SAR图像噪声去除。
1 三维块匹配(BM3D)方法
三维块匹配(BM3D)方法的基本思想是通过块匹配构建一个三维矩阵,利用每组图像块之间的相似性来估计图像块的真实像素值。主要可分为基本估计和最终估计两个阶段。
首先图像通过窗口化得到多个图像块,把相似结构的图像块组合在一起得到一个三维矩阵Z。然后对三维矩阵进行可分的三维变换,收缩变换系数减少噪声,再对矩阵进行逆三维变换:
其中:h表示硬阈值收缩系数,T3d表示三维变换,T3d-1表示T3d的逆变换。之后对每一组Y中所有的图像块进行加权平均,得到基本估计的去噪图像y。
对去噪图像y分组得到三维矩阵yw,利用yw的坐标信息对含噪图像分组得到三维矩阵Zw。对两个三维矩阵执行三维变换和经验维纳滤波。通过三维逆变换得到去噪的图像块:
其中:W表示维纳滤波,T3d表示三维变换,T3d-1表示T3d的逆变换。最后将Ywie中的图像块通过加权平均放回原始的位置,得到最终的去噪图像。
2 本文方法
2.1 BM3D 算法引入虚假纹理分析以及改进
在BM3D算法基本估计阶段,SAR图像分组之后对矩阵进行三维变换,通过联合滤波去除噪声。但此三维变换是一个可分的三维变换,即每一个图像块首先自身执行二维变换,然后再执行块间一维变换,在二维变换阶段,其实质仍是局部变换。因此使得去噪图像仍然存在局部变换域方法中引入虚假纹理的问题。
当前BM3D算法中的二维变换主要采用小波变换或者DCT变换,两者都是通过一个局部区域的所有像素值来估计中心的像素值。在硬阈值收缩变换系数阶段,为了保留图像的细节信息,阈值一般不能选的太大,此时执行阈值滤波以后就容易残留个别单独的噪声点,对其进行逆变换以后,这些单独的噪声点就会影响周围的像素值,在去噪图像中引入虚假纹理。比如小波变换产生的振铃效应,DCT变换之后引入的周期性假信号。
图1为SAR图像基本估计结果以及局部细节的对比图,从图1(a)和图1(b)中的局部细节对比图可以看出在平滑区域,图像的去噪效果不是很好,这正是由于存在的局部变换影响了基本估计的去噪效果。
针对BM3D算法在基本估计阶段引入虚假信号的现象,本文在变换域滤波的过程中,略过图像块的二维变换,直接执行图像块间的一维变换。由于图像块间的像素都是由非局部方法得到的,这样能够很好的解决局部变换所产生的信号干扰,但是每个图像中相似块的数量是有限的,仅仅通过块间的一维变换不能很好的去除图像中的噪声。为了取得更好的去噪效果,本文提出了迭代滤波的方法,在经过第一次一维滤波之后,通过减小阈值,再一次进行一维变换滤波。这样不仅避免了二维变换中虚假信息的引入,而且很好的去除了图像中的相干斑噪声,得到了一个更好的基本估计结果。从图1(c)中可以看出,相比于原始算法的基本估计结果,本文方法在平滑区域取得了更好的去噪效果。
经过基本估计阶段的迭代滤波,图像中的噪声基本去除。为了更好地保留图像的细节信息,本文在最终估计阶段仍然采用三维变换以增强基本估计中过度平滑的图像细节。
2.2 块匹配迭代滤波 SAR 图像去噪
本文提出的块匹配迭代滤波SAR图像去噪算法流程图如图2所示。BM3D算法提出时是用来去除自然图像中的加性高斯白噪声的,针对SAR图像的乘性噪声模型[13],本文方法在原图像上先进行对数变换,将乘性模型转变为加性模型。当去除噪声以后,再进行指数变换,均值修复,得到最终的SAR图像去噪效果。块匹配迭代滤波SAR图像去噪算法也分为基本估计和最终估计两个阶段。
2.2.1 基本估计
首先将输入图像z窗口化,得到多个对应的图像块,计算图像块Xi与其他图像块Xj之间的距离。当两者之间的距离小于给定的阈值时,就认为Xj是Xi的相似块,之后将Xj并入Xi的图像块组中,对每一个图像块进行上述操作,这样就得到了一个三维矩阵Z。如式(3)所示:
其中:d(Xi,Xj)表示图像块Xi与图像块Xj之间的距离,? 表示所给定的阈值,S表示所得到的图像块组。之后对三维矩阵Z执行块间变换,通过迭代滤波去除噪声,再对矩阵进行逆变换,如式(4)、(5)所示:
其中:h表示硬阈值收缩系数,T表示块间变换,T-1 表示T的逆变换,Ys表示第一次滤波后的结果,Yf表示最终的基本估计结果。
对每一组Yf中的图像块加权平均,聚集得到基本估计的去噪图像y,如式(6)所示:
其中:Yf(x)为基本估计结果图像块,xxm(x)为输入图片的分组信息,w为权值,具体公式为
其中:σ表示原始图像的噪声标准差,N表示矩阵变换硬阈值化之后非零系数的个数。
2.2.2 最终估计
通过第一阶段分组方法对基本估计的图像分组得到三维矩阵ywie,记录下各个图像块匹配结果的坐标,利用这些坐标对原始输入的含噪声图像进行分组得到另一个三维矩阵Zw。对两个三维矩阵执行三维变换,利用ywie三维变换的能量谱为经验值,对Zw执行经验维纳滤波。最后通过三维逆变换得到去噪的图像块:
其中:W表示维纳滤波,其表达式:
其中:T3d表示三维变换,T3d-1表示T3d的逆变换。
将Ywie中的图像块通过加权平均放回原始的位置,得到最终的去噪图像:
其中:Ywie(x)图像块,w表示权值:
3 实验结果与分析
3.1 去噪质量评价标准
评价一种去噪算法的好坏,除了主观视觉质量评价之外,还需要一些客观的评价参数。针对SAR图像的特性,本文从以下两个方面考虑对去噪后的图像进行评价。1) 相干斑噪声抑制程度,即平滑程度;2)图像边缘结构的保持能力。
3.1.1斑噪声抑制程度评价
等效视数(Equivalent Number of Looks,用NENL表示)是评价SAR图像相干斑噪声强度指标,定义如下:
其中:μ和σ 分别表示图像块灰度值的均值和标准差。NENL越大,表明相干斑噪声程度越弱,图像越平滑。
3.1.2 边缘结构保持能力评价
噪声等效视数(Noise ENL,用NNENL表示)可用来评价SAR图像去噪的细节信息保持能力。SAR图像的相干斑噪声为乘性噪声,记为y=xf,记去噪后得到的RCS(Radar Cross Section)为xr,则噪声等效视数为
当噪声等效视数与原图等效视数越接近,说明去噪得到的噪声越接近真实的噪声,则表明细节结构信息保持的越好。为了更形象的表示结构保持能力,本文采用噪声等效视数与原图等效视数的比值即:NNENL/NENLs来评价边缘保持能力,其值越接近1,则说明该去噪算法边缘结构保持能力越好。
3.2 实验结果
本文的实验数据图像,像素大小为256x256,位深度为8 bits。实验结果对比了传统的局部滤波算法CHMT(Contourlet Hidden Markov Tree)算法和BLS-GSM算法,以及经典的非局部算法NL-means(Non Localmeans)算法和BM3D(Block-Matching and 3D filtering)算法。
上述4种算法以及本文的算法应用于桥梁场景SAR图像上的实验结果如图3所示,实验结果的客观参数评价如表1所示。
由表1的结果可知,针对斑噪声的抑制程度,CHMT算法和NLM算法得到的NENL相对较小,从图3(b)和图3(d)中也可以看出,其去噪后的图像还残留着明显的相干斑噪声,可见这两种算法的平滑效果不够理想。而本文方法得到的NENL为74.303 6,不仅远远大于这两者,而且明显大于BLS-GSM的32.304 9以及原始BM3D算法的38.198 1。从主观视觉上观察,本文方法得到的结果图像平滑效果最好,说明本文方法对SAR图像的相干斑噪声抑制效果最好。观察去噪图像的边缘结构保持评价可以看出,虽然本文方法的1.248略逊于NLM的1.223 9和BLS-GSM的1.189 7。但是明显少于在平滑效果方面表现较好的BM3D算法。对比BM3D算法和本文方法的去噪结果图,其边缘都很连续,在去噪效果上优于其他3种算法,但从客观评价指标可以看出无论是斑噪声抑制能力还是边缘结构的保持方面,本文算法相比BM3D算法都有较大的提高。对比图3(e)和图3(f)中桥梁右侧的平坦区域,可以看出图3(e)中的平滑区域仍然存在着一些细小的纹理,这正是由于BM3D算法在基本估计阶段中局部变换所引入的虚假纹理,而影响到了最终的去噪效果。而从图3(f)中可以看出,在相同的平滑区域,本文方法由于很好的避免了虚假纹理的引入,使得最终的去噪效果更平滑,同时还较好的保存了图像的细节信息。实验表明:本文方法在相干斑去噪方面的效果很好,在结构信息的保持方面也只是略逊于NLM和BLS-GSM。
下面将这5种算法分别应用于河流场景的SAR图像上。得到的实验结果如图4所示,客观参数评价如表2所示。
表2的结果显示,在NENL的参数,即平滑效果的表现上,本文方法依旧取得了很好的效果,远远优于同样采用非局部思想NLM的43.690以及局部滤波方法BLS-GSM的42.878 8。从噪声NENL的评价结果来看,本文方法仍然略大于NLM以及BLS-GSM。同样比较BM3D与本文方法,从主观表现方面,在图4(e)河流的右侧平坦区域中其仍然存在着一些虚假的纹理,这影响了平滑区域的去噪效果,而从图4(f)中的相同区域可以看出,本文方法的结果更加平滑,避免了虚假纹理信息的干扰。从客观评价指标也可以看出不管是在平滑区域的去噪效果上还是边缘结构信息的保持上,相对于原始的BM3D方法,本文的方法都有很大的提高。实验结果再次说明了,本文方法在抑制SAR图像相干斑噪声方面取得了很好的效果,同时边缘结构的保持也取得了不错的效果。
4 结 论