数字视频设计报告

1、成绩评阅人中国矿业大学2015-2016学年第一学期数字视频技术课程小设计考核运动估计算法的实现（FS和TSS算法）专业班级：信息12-3班学生姓名：_徐冰洁、刘瑞航、李子龙学生学号：04121409、04121408、04121388指导教师：成绩：本人郑重声明：本人认真、独立完成了查找资料、完成作业、编写程序等考核任务无抄袭行为。签字：徐冰洁日期：2015/11/12一、设计任务、目的和要求设计任务:设计视频压缩系统中的运动估计算法要求：在两帧图像间实现多种运动估计算法。我们组选用的算法是全搜索算法(FS)和三步算法(TSS)。目的：培养学生科学理论结合实际工程的能力。通过该课程设计，让学

2、生掌握多媒体通信系统的应用技术。二、总体方案设计系统运行环境及编程软件平台：Intel(R)Core(TM)i3-2310MCPU2.10Ghz2.10GhzWindow7旗舰版的PC平台下，使用Matalab2009a作为仿真平台进行仿真。FS编码算法原理：从原点出发，按顺时针螺旋方向由近及远，在逐个像素处计算MAD值，直到遍历搜索范围内听有的点，然后在计算的所有点的MAD中找到最小值，该点所在位置即对应最佳运动矢量。TSS编码算法原理：d=7,它是通过三步搜索,逐步减小搜索步长。每次搜索都是以上一步的搜索结果为中心,进行周围一定步长的3*3像素的搜索。第一步,以窗口中心为中心,步长为4,进

3、行周围8个点搜索,根据匹配准则得到一个最佳匹配点,共搜索了9个点;第二步,以上步最佳匹配点为中心,步长为2,继续搜索周围8个点得到匹配点,共搜索了8个点;第三步,同上一步,只是步长为1,最后得到的最佳匹配点就是要得到的运动估计的点,从而得到运动矢量。进行图像预测共进行了25次块匹配，同样情况下，采用FS则需做225次块匹配。一般地,TSS的运算量为获取图像三步搜索法图解8log2d+1次块匹配。TSS运算时间明显减少,性能比FS有所下降，但它在硬件上容易实现,是一种很常用的快速搜索算法。全搜索算法流程图三、设计实现小组分工：李子龙负责查找资料,徐冰洁负责根据资料编写程序代码以及仿真刘瑞航负责测

4、试和整理报告程序代码如下：FS算法I1=imread(C:UsersAdministratorDesktop运动估计算法11.bmp);%读取第一帧图像I1=rgb2gray(I1);%将第一帧图像转换为灰度图l2=imread(C:UsersAdministratorDesktop运动估计算法22.bmp);I2=rgb2gray(I2);%将第二帧图像转换为灰度图dm=7;%给图像扩边，每个边都扩大dm大小I1=double(I1);I2=double(I2);rownumcolnum=size(I1);II=zeros(rownum+2*dm,colnum+2*dm);%生成零矩阵II(

5、dm+1:dm+rownum,dm+1:dm+colnum)=I1;fori=1:dmII(i,dm+1:dm+colnum)=II(dm+1,dm+1:dm+colnum);II(rownum+dm+i,dm+1:dm+colnum)=II(dm+rownum,dm+1:dm+colnum);endforj=1:dmII(1:rownum+2*dm,j)=II(1:rownum+2*dm,dm+1);II(1:rownum+2*dm,colnum+dm+j)=II(1:rownum+2*dm,dm+colnum);end%下面进行全搜索算法tic%开始运行计时blocksize=16;row

6、blocks=rownum/blocksize;colblocks=colnum/blocksize;A=99999999999999999999;Eij=0;xrecord=ones(16,16);矢量%为了找到最小的均方误差，A用于设定一个很大的初值yrecord=ones(16,16);diff=zeros(256,256);forx=0:(rowblocks-1)row=x*blocksize;fory=0:(colblocks-1)col=y*blocksize;forp=-dm:dmforq=-dm:dm%这幅图的大小为256*256%x表示行中第几个子块%y表示列中第几个子块%（

7、p,q）表示x,y对应子块在前一帧的搜索位置%xrecord,yrecord用于存放匹配块的块号，即运动Eij=0;Eij=sum(sum(I2(row+1:row+blocksize,col+1:col+blocksize)-II(row+dm+p+1:row+dm+p+blocksize,col+dm+q+1:col+dm+q+blocksize).A2)/(blocksizeA2);ifEijAA=Eij;xrecord(x+1,y+1)=p;yrecord(x+1,y+1)=q;endendendA=999999999999999999;formx=1:blocksizeforny=1

8、:blocksizediff(row+mx,col+ny)=I2(row+mx,col+ny)-II(row+mx+dm+xrecord(x+1,y+1),col+ny+dm+yrecord(x+1,y+1);endendendendtoc%结束计时figure,imshow(I1,);title(第一帧图像);figure,imshow(I2,);title(第二帧图像);IIII=I2-I1;figure,imshow(IIII,);title(帧间误差);figure,imshow(diff,);title(预测误差);forx=0:(rowblocks-1)row=x*blocksiz

9、e;fory=0:(colblocks-1)col=y*blocksize;III(row+1:row+blocksize,col+1:col+blocksize)=II(row+dm+xrecord(x+1,y+1)+1:row+dm+xrecord(x+1,y+1)+blocksize,col+dm+yrecord(x+1,y+1)+1:col+dm+yrecord(x+1,y+1)+blocksize)+diff(row+1:row+blocksize,col+1:col+blocksize);endendfigure,imshow(III,);title(第二帧恢复图像);ERR=di

10、ff;numberarray=0:1:255;form=1:255numberarray(m+1)=0;end;zeronumber=0;forn=1:rownumform=1:colnumdif=abs(ERR(m,n);if(dif=0)temp=zeronumber;zeronumber=temp+1;elsenumberarray(dif)=numberarray(dif)+1;end;end;end;figure;plot(0,zeronumber,k*);holdon;plot(numberarray,r*),title(预测误差分布);holdoff;ERR1=zeros(16,

11、16);fori=0:15forj=0:15ERR1(i+1,j+1)=round(sum(sum(ERR(i*blocksize+1:i*blocksize+blocksize,j*blocksize+1:j*blocksize+blocksize)/(blocksize*blocksize);endendnumberarray=0:1:255;form=1:255numberarray(m+1)=0;end;zeronumber=0;forn=1:16form=1:16dif=abs(ERR1(m,n);if(dif=0)temp=zeronumber;zeronumber=temp+1;

12、elsenumberarray(dif)=numberarray(dif)+1;end;end;end;figure;plot(0,zeronumber,k*);holdon;plot(numberarray,r*),title(预测误差分布2);holdoff;figure;fori=1:16forj=1:16quiver(i,j,xrecord(i,j)/16,yrecord(i,j)/16);holdon;endendgridon;figure;quiver(1:16,1:16,yrecord,xrecord);gridon;TSS算法%读第%读第I1=imread(C:UsersAdm

13、inistratorDesktop运动估计算法11.bmp);一帧图像I1=rgb2gray(I1);l2=imread(C:UsersAdministratorDesktop运动估计算法22.bmp);二帧图像I2=rgb2gray(I2);dm=7;I1=double(I1);I2=double(I2);rownumcolnum=size(I1);II=zeros(rownum+2*dm,colnum+2*dm);II(dm+1:dm+rownum,dm+1:dm+colnum)=I1;fori=1:dmII(i,dm+1:dm+colnum)=II(dm+1,dm+1:dm+colnum

14、);II(rownum+dm+i,dm+1:dm+colnum)=II(dm+rownum,dm+1:dm+colnum);endforj=1:dmII(1:rownum+2*dm,j)=II(1:rownum+2*dm,dm+1);II(1:rownum+2*dm,colnum+dm+j)=II(1:rownum+2*dm,dm+colnum);endtic%开始计时blocksize=16;rowblocks=rownum/blocksize;colblocks=colnum/blocksize;A=99999999999999999999;%Eij=0;xrecord=ones(16,1

15、6);%yrecord=ones(16,16);diff=zeros(256,256);forx=0:(rowblocks-1)row=x*blocksize;fory=0:(colblocks-1)col=y*blocksize;forp1=-4:4:4forq1=-4:4:4Eij=0;Eij=sum(sum(I2(row+1:row+blocksize,col+1:col+blocksize)-II(row+dm+p1+1:row+dm+p1+blocksize,col+dm+q1+1:col+dm+q1+blocksize).A2)/(blocksizeA2);ifEijAA=Eij;

16、xrecord(x+1,y+1)=p1;yrecord(x+1,y+1)=q1;endendendp1=xrecord(x+1,y+1);q1=yrecord(x+1,y+1);forp2=p1-2:2:p1+2forq2=q1-2:2:q1+2ifp2=p1|q2=q1Eij=0;Eij=sum(sum(I2(row+1:row+blocksize,col+1:col+blocksize)-II(row+dm+p2+1:row+dm+p2+blocksize,col+dm+q2+1:col+dm+q2+blocksize).A2)/(blocksizeA2);ifEijAA=Eij;xrec

17、ord(x+1,y+1)=p2;yrecord(x+1,y+1)=q2;endendendendp2=xrecord(x+1,y+1);q2=yrecord(x+1,y+1);forp3=p2-1:1:p2+1forq3=q2-1:1:q2+1ifp3=p2|q3=q2Eij=0;Eij=sum(sum(I2(row+1:row+blocksize,col+1:col+blocksize)-II(row+dm+p3+1:row+dm+p3+blocksize,col+dm+q3+1:col+dm+q3+blocksize).A2)/(blocksizeA2);ifEijAA=Eij;xreco

18、rd(x+1,y+1)=p3;record(x+1,y+1)=q3;endendendendA=999999999999999999;formx=1:blocksizeforny=1:blocksizediff(row+mx,col+ny)=I2(row+mx,col+ny)-II(row+mx+dm+xrecord(x+1,y+1),col+ny+dm+yrecord(x+1,y+1);endendendendtoc%结束计时figure,imshow(I1,);title(第一帧图像);figure,imshow(I2,);title(第二帧图像);IIII=I2-I1;figure,im

19、show(IIII,);title(帧间误差);figure,imshow(diff,);title(预测误差);forx=0:(rowblocks-1)row=x*blocksize;fory=0:(colblocks-1)col=y*blocksize;III(row+1:row+blocksize,col+1:col+blocksize)=II(row+dm+xrecord(x+1,y+1)+1:row+dm+xrecord(x+1,y+1)+blocksize,col+dm+yrecord(x+1,y+1)+1:col+dm+yrecord(x+1,y+1)+blocksize)+di

20、ff(row+1:row+blocksize,col+1:col+blocksize);endendfigure,imshow(III,);title(恢复后的第二帧图像)ERR=diff;numberarray=0:1:255;form=1:255numberarray(m+1)=0;end;zeronumber=0;forn=1:rownumform=1:colnumdif=abs(ERR(m,n);if(dif=0)temp=zeronumber;zeronumber=temp+1;elsenumberarray(dif)=numberarray(dif)+1;end;end;end;f

21、igure;plot(0,zeronumber,k*);holdon;plot(numberarray,r*),title(预测误差分布);holdoff;ERR1=zeros(16,16);fori=0:15forj=0:15ERR1(i+1,j+1)=round(sum(sum(ERR(i*blocksize+1:i*blocksize+blocksize,j*blocksize+1:j*blocksize+blocksize)/(blocksize*blocksize);endendnumberarray=0:1:255;form=1:255numberarray(m+1)=0;end;

22、zeronumber=0;forn=1:16form=1:16dif=abs(ERR1(m,n);if(dif=0)temp=zeronumber;zeronumber=temp+1;elsenumberarray(dif)=numberarray(dif)+1;end;end;end;figure;plot(0,zeronumber,k*);holdon;plot(numberarray,r*),title(预测误差分布2);holdoff;figure;fori=1:16forj=1:16quiver(i,j,xrecord(i,j)/16,yrecord(i,j)/16);holdon;endendgridon;figure;quiver(1:16,1:16,yrecord,xrecord);gridon;四、仿真结果参考图像:全搜索算法仿真结果：根据全搜索算法得到的第二帧图像第二帧运动位移矢量图三步搜索算法仿真结果：根据三步算法恢复的第二帧图像第二帧图像运动位移矢量图仿真结果分析:通过实验我们得到各种匹配算法的Matalab执行时间、重构图像。Matalab执行时间反映了算法的执行效