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

块匹配算法研究与比较
--------以EBMA和TSS算法为例
1、 块匹配算法简介
运动估计是视频解决系统的一个重要组成部分，二维运动估计是其中一个大类，迄今已发展出一系列的二维运动估计算法，被广泛地应用于视频压缩、采样率转换等方面。二维运动估计算法重要目的是估计出相邻视频帧之间的二维运动向量。根据不同的运动表达方法，可以分为整体运动估计，基于像素的运动估计，基于块的运动估计，基于区域的运动估计，不同方法应用场合不同，各有优劣。本文重要研究基于块的运动估计算法。
块匹配算法是一种重要的基于块的运动估计算法。基于块的运动估计算法是在已估计的运动场上施加平滑约束，不图像分割为互不重叠的称为块的区域，并且假定每个块内的运动可以用一个简朴的参数模型（如恒定、仿射、双线性）特性化。令表达第m个图像块，M代表图像块数，，块的分割应满足
，
理论上，一个块可以表达成任意形状，事实上一般都表达成N*N的正方形。
在最简朴的情况下，假设每个块的整体运动是恒定的，即做整体平移。本文将采用这一假设，此时的估计问题是为每一个块寻找一个MV，这一类算法被称为块匹配算法(BMA)。
在锚定帧中给定一个图像块，此时估计问题是在目的帧中寻找一个匹配
块，使得两块之间误差最小，这两块之间空间位置的位移矢量是这个块的MV。在块平移模型下，，，误差公式表达为

对于每个块的MV估计只影响这个块的预测误差，因此只要使每个块估计时预测误差最小，从而使得累积误差最小，即

块匹配算法涉及简朴地穷尽块匹配算法及一些快速算法，快速算法有二维对数法，三步搜索法，钻石算法，MVFAST算法，其中钻石算法被列入MPEG-4标准。
2、 穷尽块匹配算法及其快速算法三步搜索法实现
2.1 穷尽块匹配(EBMA)算法
在1中的讨论使得已知，块匹配算法在估计每个块的MV目的在于使得最小，一种方法可以是在一个预定的搜索区域内，将与目的帧中所有候选块进行比较，并寻找具有最小误差的一个。这两个块之间的位移差即为所估计的MV。
为了减小计算量，令p=1。搜索区域取关于当前区域对称，左右上下各有R个像素，搜索的步长为d，搜索步长决定估计精度。令块大小为，图像大小为，块数目为。对于单像素步长，锚定帧每一块候选匹配块共(2*R+1)个。令一次运算定义涉及一个减法，一个绝对值和一个加法，计算每个候选块误差运算次数为，估计每个块MV的运算次数为，那么一帧的运算次数为。可见其运算次数不依赖于块大小。
该过程代码实现如下：
//为a块¨¦分¤?配?空?间?N*N并¡é赋3值¦Ì
char slice[N*N];
for(int s=0;s<N;s++)
for(int t=0;t<N;t++)
slice[s*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=1
{
if(p+i*N<0) continue;
if(p+N-1+i*N>height-1) break;
for(int q=-r;q<=r;q+=d)//p=-r:d:r共22*r+1在¨²d=1
{
if(q+j*N<0) continue;
if(q+N-1+j*N>width-1) break;

//获?得Ì?目?标À¨º帧?对?应®|块¨¦
char goal_slice[N*N];
for(int s=0;s<N;s++)
for(int t=0;t<N;t++)
goal_slice[s*N+t]=*(Y2+(p+s+i*N)*width+q+t+j*N);

//求¨®两¢?个?块¨¦间?距¨¤离¤?
double d_sum=0.0;
for(int s=0;s<N;s++)
for(int t=0;t<N;t++)
d_sum+=abs(goal_slice[s*N+t]-slice[s*N+t]);

//获?得Ì?最Á?小?间?距¨¤块¨¦
if(d_sum<min_dis) {min_dis=d_sum;
//COORDINATE(0,i,j)=i*N+N/2;
//COORDINATE(1,i,j)=j*N+N/2;
shift[i*width/N+j]=p;
shift[height*width/(N*N)+i*width/N+j]=q;}
}
}
在求得位移向量MV后，根据锚定帧和MV可以预测目的帧。
for(int i=0;i<height/N;i++)
for(int j=0;j<width/N;j++)
{

int i_index[N*N];
int j_index[N*N];//块¨¦（ꡧi,j）ê?的Ì?预¡è测a坐Á?标À¨º
for(int s=0;s<N;s++)
for(int t=0;t<N;t++)
{i_index[s*N+t]=shift[i*width/N+j]+i*N+s;
j_index[s*N+t]=shift[height*width/(N*N)+i*width/N+j]+j*N+t;}

for(int s=0;s<N;s++)
for(int t=0;t<N;t++)
{Frame[i_index[s*N+t]*width+j_index[s*N+t]]=*(Y1+(i*N+s)*width+j*N+t);}
}
2.1 三步搜索法(TSS)
三步搜索法是块匹配算法的一种快速算法，其重要是通过步长的改变来减少搜索次数，从而减少运算量。这种搜索算法初始步长等于或大于索范围的一半，在每一步中比较9个搜索点，涉及搜索正方形的中心及其边界上8个点。每一步后搜索步长减半，直至搜索步长为一个像素。在每一个搜索步中，搜索中心移到前一步所得到的最佳匹配点。设代表初始搜索步长，则最多L=[]=[]个搜索步。除了初始需搜索9个点以外，其它每步均搜索8个点。因此总搜索点为8L+1。C语言代码实现过程，与穷尽搜索法大体类似，就不再反复。
测试帧为yuv文献，420方式采样，帧大小为176*144，因此每帧前176*144字节为Y分量，剩余176*144/2字节为U、V分量。yuv文献只包含视频数据，无其他结构信息，因此只需要直接读取即可。本文只读取前两帧的Y分量进行算法分析，实现代码如下：
//为Y分¤?量¢?分¤?配?内¨²存ä?
this->Y1=new char[height*width];
this->Y2=new char[height*width];

//从䨮YUV文?件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）ê?
3、 实验结果比较分析
1、 不同搜索步长下穷尽块匹配算法性能比较
搜索范围
信噪比(dB)
运营时间(s)
32
3.040410
0.998
20
3.632601
0.452
16
3.632601
0.343
10
3.632601
0.156
表1 测试帧为foreman

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

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

foreman测试结果
搜索范围
信噪比(dB)
运营时间(s)
32
17.966834
0.062
16
17.966834
0.047
8
17.966834
0.031
表4 测试帧为akiyo

akiyo测试结果
采用三步搜索法进行估计时，观测比较foreman和akiyo测试结果可知，，搜索范围改变并未引起SNR及图像主观感受的改变，但小的搜索范围可以使得运算量减小。foreman与akiyo之间比较可以发现，质量好的视频帧同样会取得好的预测效果。
将三步搜索法与1中穷尽块匹配算法所得测试结果比较，可知对于质量较差的视频帧，三步搜索法在大的搜索范围时，预测效果优于穷尽搜索法，但在小的搜索范围时，预测质量有所减少（但主观感受上无差别），但运算量大大减小；对于质量好的视频帧，三步搜索法预测质量不变，但运算量大大减小。可见，三步搜索法综合性能较优，并且较稳定。
综上分析可知，块匹配算法性能与视频帧的质量相关：视频帧质量越好，预测效果越好。三步搜索法总体性能优于穷尽搜索法，只是在视频帧质量较差时预测质量会略劣于穷尽搜索法（无视觉感官上明显差别）。
4、 总结
通过实现穷尽块匹配算法及三步搜索法，加深了对运动估计算法的理解。上述两种算法只是基于块的运动估计算法的两种经典算法，这两种算法反映了视频运动估计的一种简朴的思绪，仍有许多待改善的地方，比如运算速度上，估计精度。可以通过改善鉴定准则来优化上述算法，甚至可以基于新的思绪去重新设计算法。事实上，已经发展出了大量优于上述两种算法的运动估计算法。