中期报告-块匹配算法比较研究

1、块匹配算法研究与比较-以EBMA和TSS算法为例块匹配算法简介运动估计是视频处理系统的一个重要组成部分，二维运动估计是其中一个大类，迄今已发展出一系列的二维运动估计算法，被广泛地应用于视频压缩、采样率转换等方面。二维运动估计算法主要目标是估计出相邻视频帧之间的二维运动向量。根据不同的运动表示方法，可以分为整体运动估计，基于像素的运动估计，基于块的运动估计，基于区域的运动估计，不同方法应用场合不同，各有优劣。本文主要研究基于块的运动估计算法。块匹配算法是一种重要的基于块的运动估计算法。基于块的运动估计算法是在已估计的运动场上施加平滑约束，不图像分割为互不重叠的称为块的区域，并且假定每个块内的运动

2、可以用一个简单的参数模型（如恒定、仿射、双线性）特征化。令Bm表示第m个图像块，M代表图像块数，=1,2,.M，块的分割应满足m=1MBm=，BmBn=0,mn理论上，一个块可以表示成任意形状，实际上一般都表示成N*N的正方形。在最简单的情况下，假设每个块的整体运动是恒定的，即做整体平移。本文将采用这一假设，此时的估计问题是为每一个块寻找一个MV，这一类算法被称为块匹配算法(BMA)。在锚定帧中给定一个图像块Bm，此时估计问题是在目标帧中寻找一个匹配块Bm，使得两块之间误差最小，这两块之间空间位置的位移矢量dm是这个块的MV。在块平移模型下，wx,a=x+dm，xBm，误差公式表示为Edm,m

3、M=mMxBm|2x+dm-1x|p对于每个块的MV估计只影响这个块的预测误差，因此只要使每个块估计时预测误差最小，从而使得累积误差最小，即Emdm=xBm|2x+dm-1x|p块匹配算法包括简单地穷尽块匹配算法及一些快速算法，快速算法有二维对数法，三步搜索法，钻石算法，MVFAST算法，其中钻石算法被列入MPEG-4标准。穷尽块匹配算法及其快速算法三步搜索法实现2.1 穷尽块匹配(EBMA)算法在1中的讨论使得已知，块匹配算法在估计每个块的MV目标在于使得Emdm最小，一种方法可以是在一个预定的搜索区域内，将Bm与目标帧中所有候选块Bm进行比较，并寻找具有最小误差的一个。这两个块之间的位移差

4、即为所估计的MV。为了减小计算量，令p=1。搜索区域取关于当前区域对称，左右上下各有R个像素，搜索的步长为d，搜索步长决定估计精度。令块大小为N*N，图像大小为M*M，块数目为(MN)2。对于单像素步长，锚定帧每一块候选匹配块共(2*R+1)个。令一次运算定义包括一个减法，一个绝对值和一个加法，计算每个候选块误差运算次数为N*N，估计每个块MV的运算次数为(2R+1)2N2，那么一帧的运算次数为(2R+1)2M2。可见其运算次数不依赖于块大小。该过程代码实现如下：/为a块分?配?空?间?N*N并赋3值char sliceN*N;for(int s=0;sN;s+)for(int t=0;tN;

5、t+)slices*N+t=*(Y1+(s+i*N)*width+t+j*N); /在-r,r*-r,r遍历for(int p=-r;p=r;p+=d)/p=-r:d:r共22*r+1在d=1if(p+i*Nheight-1) break;for(int q=-r;q=r;q+=d)/p=-r:d:r共22*r+1在d=1if(q+j*Nwidth-1) break;/获?得?目?标帧?对?应|块char goal_sliceN*N;for(int s=0;sN;s+)for(int t=0;tN;t+)goal_slices*N+t=*(Y2+(p+s+i*N)*width+q+t+j*N)

6、; /求两?个?块间?距离?double d_sum=0.0;for(int s=0;sN;s+)for(int t=0;tN;t+)d_sum+=abs(goal_slices*N+t-slices*N+t);/获?得?最?小?间?距块if(d_summin_dis) min_dis=d_sum;/COORDINATE(0,i,j)=i*N+N/2;/COORDINATE(1,i,j)=j*N+N/2;shifti*width/N+j=p;shiftheight*width/(N*N)+i*width/N+j=q;在求得位移向量MV后，根据锚定帧和MV可以预测目标帧。for(int i=0;

7、iheight/N;i+)for(int j=0;jwidth/N;j+)int i_indexN*N;int j_indexN*N;/块（i,j）?的?预测a坐?标for(int s=0;sN;s+)for(int t=0;tN;t+)i_indexs*N+t=shifti*width/N+j+i*N+s;j_indexs*N+t=shiftheight*width/(N*N)+i*width/N+j+j*N+t; for(int s=0;sN;s+)for(int t=0;tY1=new charheight*width;this-Y2=new charheight*width;/从YUV

8、文?件t中D读取?头两?帧?Y分?量?fseek(fp,0,SEEK_SET);fread(this-Y1,1,height*width,fp);/读取?参?考?帧?（帧?1）?fseek(fp,height*width*3/2,SEEK_SET);fread(this-Y2,1,height*width,fp);/读取?目?标帧?（帧?2）?实验结果比较分析不同搜索步长下穷尽块匹配算法性能比较搜索范围信噪比(dB)运行时间(s)323.0404100.998203.6326010.452163.6326010.343103.6326010.156表1 测试帧为foremanforeman测试

9、结果观察表1及foreman测试结果，可知当搜索范围过大时，三步搜索法预测效果反而变差，这是因为图片不满足衡亮度假设，大范围搜索时，满足MAD最小的最佳匹配块并非实际锚定块。在R=32时，虽然SNR上减少不大，但是主管视觉感受明显变差；在R=20,16,10时，SNR及主观感受无差异，但是小的R带来了极大的运算量上的减小，因此可以尽量选择较小的R=10或16。这也说明主管感受与客观标准之间虽然存在一定相关，但是并非理想上相关。搜索范围信噪比(dB)运行时间(s)3217.9668340.9912017.9668340.4371617.9668340.3121017.9668340.156表2

10、测试帧为akiyoakiyo测试结果观察表2及akiyo测试结果，预测效果极好，这可以体现在SNR及预测图像给人的主观感受上，明显优于foreman预测效果。可以看到，Akiyo预测效果与搜索范围无关，这是因为akiyo满足了恒亮度要求且块的位移向量很小(大多为0)，因此预测效果要优于foreman且不受R范围的影响。通过上述比较可知，预测效果与视频帧质量相关，对于视频帧质量较差视频，不适合采用块匹配算法；预测效果的主观感受与客观标准间并非完全吻合的，这是值得注意的。穷尽块匹配算法与三步搜索法测试效果比较下面测试在三步搜索法下两种图像表现出来的预测效果：搜索范围信噪比(dB)运行时间(s)32

11、3.6111030.063163.6111030.04683.6111030.031表3 测试帧为foremanforeman测试结果搜索范围信噪比(dB)运行时间(s)3217.9668340.0621617.9668340.047817.9668340.031表4 测试帧为akiyoakiyo测试结果采用三步搜索法进行估计时，观察比较foreman和akiyo测试结果可知，搜索范围改变并未引起SNR及图像主观感受的改变，但小的搜索范围可以使得运算量减小。foreman与akiyo之间比较可以发现，质量好的视频帧同样会取得好的预测效果。将三步搜索法与1中穷尽块匹配算法所得测试结果比较，可知对于质量较差的视频帧，三步搜索法在大的搜索范围时，预测效果优于穷尽搜索法，但在小的搜索范围时，预测质量有所降低（但主观感受上无差别），但运算量大大减小；对于质量好的视频帧，三步搜索法预测质量不变，但运算量大大减小。可见，三步搜索法综合性能较优，并且较稳定。综上分析可知，块匹配算法性能与视频帧的质量相关：视频帧质量越好，预测效果越好。三步搜索法总体性能优于穷尽搜索法，只是在视频帧质量较差时预测质量会略劣于穷尽搜索法（