多媒体信息处理.docx

课程设计任务书

学生姓名： 专业班级：
指导教师： 学 院： 信息学院
题 目: 多媒体信息处理
初始条件：
MATLAB软件平台
要求完成的主要任务:
1. 设计任务
设计视频压缩系统中的运动估计算法：全搜索法（FS: Full Search）和三步法(TSS: Three Step Search)，比较二种方法的搜索点和每帧的峰值信噪比（PSNR： peak signal to noise ratio）
2. 设计要求
编制出有全搜索法和三步搜索法分别实现的算法代码对给定的视频中的两幅相邻图像进行运动块估计算法，对视频进行运动估计，并根据估计结果与原来的第二幅图进行比较，计算PSNR，分析全搜索法和三步搜索法的优劣。
时间安排：
2013年12月15日-12月25日： 研究原理，进行理论学习
2013年12月26日-12月31日： 编写程序源代码
2014年1月1日-1月5日 ： 调试程序
2014年1月6日-1月10日 ： 撰写报告
答辩时间2014年1月12日。

指导教师签名： 年 月 日

系主任签名： 年 月 日

摘要 2
Abstract 3
1 运动估计算法概念 4
1.1 运动估计算法基本思想 4
1.2 运动估计算法实验原理 4
2 实验原理和方法 5
2.1 块匹配运动估计中的准则函数 5
2.1.1 SSE(和方差) 5
2.1.2 MSE(均方差) 5
2.1.3 RMSE(均方根) 6
2.1.4 比较结果 6
2.2 全搜索法（FS） 6
2.3 三步法(TSS) 7
2.4 峰值信噪比 8
3运动估计算法的MATLAB编程 8
3.1 MATLAB介绍 8
3.2 全搜索法 9
3.2.1 算法的描述 9
3.2.2 算法的流程图 9
3.3 三步法 10
3.3.1 算法的描述 10
3.3.2 算法的流程图 11
3.4 主要的函数说明 11
4 仿真结果及分析 12
4.1 全搜索法结果 12
4.2 三步法结果 15
4.3分析与比较 18
4.4 实验中出现的问题 18
5 小结与体会 19
参考文件 20
附录 21

摘要
近几十年来，我们正在经历着一场数字革命，数字数据和数字通讯异常普遍。现在，在台式机上的多媒体信息处理技术已经日趋成熟。 数字信号不仅更加健壮，而且数字表示和数字传输最主要的好处是它们使得在同样的网络上提供不同范围的服务变得更加简单。基于计算机的多媒体信息处理技术中的视频处理技术使计算机和通讯以一种全新的方式结合在一起。
运动估计是多媒体视频信息处理中一个很基本的、也很重要的问题。运动估计，通常是指二维的平面图像运动估计或者是三维的实体运动的估计。 事实上，它一直是人们研究很多的主题。块运动估计和块运动补偿是最常用的方法。块运动估计和补偿已经被使用在如 H.261，MPEG1-2 等国际数字视频压缩标准中[1]。块运动估计同样也被广泛地使用在很多其它的数字视频应用中，比如标准压缩中的运动补偿滤波。
当前的块运动估计算法包括：全搜索法；三步法；共轭方向搜索法；两维对数下降法；交叉搜索法；动态窗口搜索法；两步搜索法等。它们在计算速度和计算精度上各有特点。其中全搜索方法的精度一般是最高的，但是由于是逐点搜索，所以在速度上是最慢的；而三步快速搜索仅在事先确定的侯选的运动矢量的范围内计算准则函数的值，因此精度比较低，但是由于处理的点较少，它的处理速度很快。运动估计与超分辨率等技术相结合，将可以很大程度地提高图像的质量，运用到视频恢复等技术中，因而运动估计的研究会有较大的应用前景。

关键词：多媒体信息处理 运动估计 全搜索法 三步法

Abstract
In recent decades, we are experiencing a digital revolution . digital data and digital communications are abnormaly common. Now, on the desktop, multimedia information processing technology has matured . Not only digital signal is more robust , but also the main benefit of digital representation and digital transmission is that they make it easier to provide a diverse range of services on the same network . Computer-based multimedia information processing technology in the video processing technology enables computers and communications together in a new way .
    Motion estimation is a very basic and very important issue in multimedia video information processing . Motion estimation usually refers to the estimated two-dimensional planar image motion estimation or three-dimensional movement of the entity . In fact, it has been the study subject of a lot of people . Block motion estimation and motion compensation block are the most commonly used methods. Block motion estimation and compensation have been used in such as H.261, MPEG1-2 digital video compression and other international standards [ 1 ] . Block motion estimation is widely used also in many other digital video applications , such as the standard compression motion compensation filtering.
The current block motion estimation algorithms include full search method ,three-step method , conjugate direction search method , two-dimensional logarithmic descent , cross- search method , dynamic window search method , two-step search method. They have their own characteristics in calculation speed and accuracy . The accuracy of the full search method is generally the highes.But because it is the search -by-point , it is the speed of the slowest .And three-step quick search calculated only criterion function value in the range of pre-determined candidate motion vectors ,therefore it has relatively low accuracy and fewer point processing . It’s processing speed is very fast. Motion estimation combining super-resolution technology will be able to greatly increase the quality of the image, using the video restoration technology , and thus the motion estimation studies have greater prospects.

Keywords multimedium information processing motion estimation Full search Method of three-step method

1 运动估计算法概念
视频原始图像中存在着大量的信息冗余，如时间冗余、空间冗余信息熵冗余、谱间冗余、几何结构冗余、视觉冗余和知识冗余等等。运动估计是视频压缩编码中的核心技术之一，采用运动估计和运动补偿技术可以消除视频信号的时间冗余以提高编码效率。如何提高运动估计的效率，使运动估计算法的搜索过程更健壮、更快速、更高效成为目前研究的热点。
运动估计的基本思想是尽可能准确地获得序列图像帧间的运动位移，即运动矢量。因为运动估计越准确，预测补偿的图像质量越高，补偿的残差就越小，补偿编码所需位数越少，需要传输的比特率就越小。利用得到的运动矢量在帧间进行运动补偿。补偿残差经过变换、量化、编码后与运动矢量一起经过熵编码，然后以比特流形式发送出去。
运动估计算法多种多样，大体上可以把它们分成四类：块匹配法、递归估计法、贝叶斯估计法和光流法。其中块匹配运动估计算法因其具有算法简单、便于VLSI实现等优点得到广泛应用。所以本文将重点介绍块匹配运动估计算法。

1.1 运动估计算法基本思想
运动估计的基本思想是尽可能准确地获得序列图像帧间的运动位移，即运动矢量。运动估计算法的目标是效率和准确性。由于在成象的场景中一般有多个物体作不同的运动，如果直接按照不同类型的运动将图像分割成复杂的区域是比较困难的。最直接和不受约束的方法是在每个像素都指定运动矢量，这就是所谓基于像素表示法。这种表示法是对任何类型图像都是适用的，但是它需要估计大量的未知量，并且它的解时常在物理上是不正确，除非在估计过程中施加适当的物理约束。这在具体实现时是不可能的，通常采用基于块的物体运动表示法。因为运动估计越准确，预测补偿的图像质量越高，补偿的残差就越小，补偿编码所需位数越少，需要传输的比特率就越小。

1.2 运动估计算法实验原理
在帧间预测编码中，由于活动图像邻近帧中的景物存在着一定的相关性。因此，可将活动图像分成若干块或宏块，并设法搜索出每个块或宏块在邻近帧图像中的位置，并得出两者之间的空间位置的相对偏移量，得到的相对偏移量就是通常所指的运动矢量，得到运动矢量的过程被称为运动估计。
　　运动矢量和经过运动匹配后得到的预测误差共同发送到解码端，在解码端按照运动矢量指明的位置，从已经解码的邻近参考帧图像中找到相应的块或宏块，和预测误差相加后就得到了块或宏块在当前帧中的位置。
运动估计的准确程度往往用补偿图像与原图像比较的PSNR来衡量表示。

2 实验原理和方法
2.1 块匹配运动估计中的准则函数
块之间是否匹配是通过各种不同的准则函数来判断。常用的块匹配准则函数包括均方误差函数（MSE），最小绝对差误差函数（MAD），最大匹配像素个数函数（MPC），绝对平均误差函数（MAE），互相关函数（CCF），最大误差最小函数（MME）。还有一些比较新的准则函数，比如，块特征匹配函数（BFM）等等。下面介绍其中几种。

2.1.1 SSE(和方差)

该统计参数计算的是拟合数据和原始数据对应点的误差的平方和，计算公式如下

SSE越接近于0，说明模型选择和拟合更好，数据预测也越成功。接下来的MSE和RMSE因为和SSE是同出一宗，所以效果一样。

2.1.2 MSE(均方差)

该统计参数是预测数据和原始数据对应点误差的平方和的均值，也就是SSE/n，和SSE没有太大的区别，计算公式如下

2.1.3 RMSE(均方根)

该统计参数，也叫回归系统的拟合标准差，是MSE的平方根，就算公式如下
（2-1）
在这之前，我们所有的误差参数都是基于预测值和原始值之间的误差。从下面开始是所有的误差都是相对原始数据平均值而展开的。

2.1.4 比较结果
根据块匹配的特性和实现的方便性，我们选择MSE(均方差)算法。即
（2-2）

2.2 全搜索法（FS）
所有的运动估计算法中FS是性能最好的，因为它是对整个搜索窗口的每一个点进行块匹配计算，根据均方差（比如MSE准则函数）或绝对差（比如MAD准则函数）最小的原则最后得出最佳匹配点。由于FS逐点搜索，其计算量也是最大的，如果系统处理速度不够，那么用这种方法是很难实现多媒体系统的实时化的。其它任何一种算法的性能都不如FS，但是其它的算法都是通过减少在搜索窗中搜索的点数，以减少计算量，其性能必然都有所下降，是以牺牲性能来换取处理速度的提高。X下图为FS的搜索过程，黑色箭头矢量表示了搜索点的顺序，直到搜索完整个窗口的点[2]。

图2-3 全搜索法
2.3 三步法(TSS)
三步法是运动估计的一种很好的算法，快速而且高效，它基本上保持了FS的性能，但其计算量只有FS的10%左右。TSS在会议电视和可视电话中是应用最多的，它是通过三步搜索，逐步减小搜索步长。每次搜索都是以上一步的搜索结果为中心，进行周围一定步长的3*3像素的搜索，搜索精度为1个像素。如图，显示TSS的全过程：第一步，以窗口中心为中心，步长为4，进行周围8个点搜索，根据最小绝对差原则得到一个最佳匹配点，共搜索了9个点；第二步，以上步最佳匹配点为中心，步长为2，继续搜索周围8个点得到匹配点，共搜索了8个点；第三步，同上一步，只是步长为1，最后得到的最佳匹配点就是要得到的运动估计的点，从而得到运动矢量进行图像的预测。TSS共搜索了25个点，而FS要进行15*15=225点搜索，运算时间明显减少，性能稍有下降。因此，它是一种很好的运动估计算法。

图2-4 三步搜索法

2.4 峰值信噪比
峰值信噪比（经常缩写为PSNR）是一个表示信号最大可能功率和影响它的表示精度的破坏性噪声功率的比值的工程术语。由于许多信号都有非常宽的动态范围，峰值信噪比常用对数分贝单位来表示。PSNR是“Peak Signal to Noise Ratio”的缩写。peak的中文意思是顶点。而ratio的意思是比率或比列的。整个意思就是到达噪音比率的顶点信号，psnr是一般是用于最大值信号和背景噪音之间的一个工程项目。通常在经过影像压缩之后，输出的影像通常都会有某种程度与原始影像不一样。为了衡量经过处理后的影像品质，我们通常会参考PSNR 值来认定某个处理程序够不够令人满意。
Peak 就是指8 bits 表示法的最大值255。MSE 指 Mean Square Error（均方误差，各值相差的n次方和的平均值的n次平方根这几个字应该没有)），I(角标n)指原始影像第n个pixel 值，P(角标n)指经处理后的影像第n个pixel 值。PSNR 的单位为dB。所以PSNR值越大，就代表失真越少。
PSNR 是最普遍，最广泛使用的评鉴画质的客观量测法，不过许多实验结果都显示，PSNR 的分数无法和人眼看到的视觉品质完全一致，有可能 PSNR 较高者看起来反而比 PSNR 较低者差。这是因为人眼的视觉对于误差的敏感度并不是绝对的，其感知结果会受到许多因素的影响而产生变化（例如：人眼对空间频率较低的对比差异敏感度较高，人眼对亮度对比差异的敏感度较色度高，人眼对一个区域的感知结果会受到其周围邻近区域的影响）
计算公式如下所示：
（2-3）

3运动估计算法的MATLAB编程
3.1 MATLAB介绍
MATLAB是一个高级的矩阵/阵列语言，它包含控制语句、函数、数据结构、输入和输出和面向对象编程特点。用户可以在命令窗口中将输入语句与执行命令同步，也可以先编写好一个较大的复杂的应用程序（M文件）后再一起运行，可移植性好、可拓展性极强。
MATLAB是一个包含大量计算算法的集合。其拥有600多个工程中要用到的数学运算函数，可以方便的实现用户所需的各种计算功能。MATLAB的这些函数所能解决的问题大致包括矩阵运算和线性方程组的求解、微分方程及偏微分方程的组的求解、符号运算、傅立叶变换和数据的统计分析、工程中的优化问题、稀疏矩阵运算、复数的各种运算、三角函数和其他初等数学运算、多维数组操作以及建模动态仿真等。
MATLAB有两种工作方式：一种是交互式的命令行工作方式；另一种是M文件的程序工作方式。在前一种工作方式下，MATLAB被当做一种高级数学演算纸和图形表现器来使用，MATLAB提供了一套完整的而易于使用的编程语言，为用户提供了二次开发的工具，下面主要介绍MATLAB控制语句和程序设计的基本方法。
用MATLAB语言编写的程序，称为M文件。M文件有两类：命令文件和函数文件。两者区别在于：命令文件没有输入参数，也不返回输出参数；而函数文件可以输入参数，也可以返回输出参数。命令文件对MATLAB工作空间的变量进行操作，而且函数文件中定义的变量为局部变量，当函数文件执行完毕时，这些变量被清除。M文件可以使用任何编辑程序建立和编辑，而一般常用的是使用MATLAB提供的M文件窗口。
本次课程设计中我全部采用M文件，把每个需要自己编程实现的模块都分别放在一个人函数文件中最后建立一个命令文件中放主干程序并在其中调用之前写好的函数实现整个过程。

3.2 全搜索法
3.2.1 算法的描述
全搜索算法是先将视频流中的第 K+1 帧划分为许多个不重叠的，相互紧靠着的 N*N 大小的块。然后依次对每一块进行处理。在处理某一块时，以该块的中心点为中心点，在第 K 帧中的窗口内的每个点都进行一次匹配的运算。从中选择准则函数值最理想的那个点，就是与之相匹配的点。

3.2.2 算法的流程图
块运动估计算法的核心是准则函数的选择。其总体思想是首先将图像划分成若干个块，对每一个块进行估计。也即计算出窗口中的像素点的个数后，再选择合适的准则函数进行计算，求出其最小值。该算法的流程图[3]如图

图3-1 全搜索法流程
3.3 三步法
3.3.1 算法的描述
三步法是运动估计的一种很好的算法，快速而且高效。它是通过三步搜索，逐渐减小搜索步长。每次搜索都是以上一步的搜索结果为中心，进行周围一定步长的 3*3 像素的搜索，搜索精度为 1 个像素。

3.3.2 算法的流程图

图3-2 三步搜索法流程
3.4 主要的函数说明
1 A=imread(filename)
读取一个名为filename的灰度或者真彩图像到A中如果文件包含一个灰度图像，A为一个二维数组；如果文件包含一个真彩色（RGB）图像，则A是一个三维数组。
2 A=rgb2gray(B)
将真彩色图像B转换成灰度图像格式A
3imshow(A,[])
用处理图形图的格式将图形显示出来。[]表示将A中的最高值显示为黑，最低值显示为白。
4 quiver(x,y，u，v)
在点（x,y）处显示对应于分量（u,v）的速度向量。
5 tic;toc
用于计算程序所花的时间

4 仿真结果及分析
4.1 全搜索法结果

图4-1 第一幅图

图4-2 第一幅图像

图4-3 帧间差值

图4-4 利用全搜索法匹配后的帧间差

图4-5 利用全搜索法恢复的图像

图4-6 全搜索法得出的位移矢量图
Elapsed time is 9.579308 seconds.
PSNR =37.6302

4.2 三步法结果

图4-7 第一幅图

图4-8 第二幅图

图4-9 帧间差值

图4-10 三步搜索法匹配后的帧间差值

图4-11 用三步法恢复后的第二帧图像

图4-12 三步搜索法的位移矢量图
Elapsed time is 7.989397 seconds.
PSNR =336.9460
4.3分析与比较
全搜索法中的PSNR =37.6302 time=9.579308 seconds
三步搜索法中的PSNR =36.9460 time=7.989397 seconds
也就是说两种搜索法的性能相近，全搜索法更精确一些。但是全搜索法所用的时间稍长些。

4.4 实验中出现的问题
1当使用其他自己截取的较大视频图片进行试验时，会出现如下警告：
Warning: Image is too big to fit on screen; displaying at 67%
通过查询网上的帮助发现了问题的原因：480P的视频要显示的像素太多，但figure显示图片位置的大小是固定的，这两者发生了冲突。于是我在暴风视频中选择240P的视频截图进行的实验，顺利得出结果。
2 每次试验显示的所需时间略有不同
通过查阅网上的资料发现是因为系统在运行程序时还运行了其他的应用程序，所以每次试验得出的时间都略有不同。

5 小结与体会
通过本次对多媒体信息处理课程设计，让我更深刻的理解了多媒体信息的获取、搜索和保存的基本方法。基于块的运动估计，是先将视频图像分成一个个规则的图像块，然后对每个图像块估计运动矢量。基于块的运动估计和运动补偿已经广泛应用于各种视频压缩编码标准。因此，本次课程设计是非常有作用的，它让我了解了多媒体处理的基本原理。
课程设计中会遇到很多的困难，但在自己思考下最终解决了问题。所以，本次课程设计我个人的收获很大，但是让我知道自己还在图像编程方面有很多欠缺的地方。不仅对均方误差(MSE)、绝对值误差(MAD)更深的理解，并且采用全搜索块匹配方法得到所有宏块的运动矢量，把MATLAB语言的知识又重新的过了一遍。

参考文件
[1] 戴 酉, 李小红, 钱源诚.MPEG 运动估计的改进.淮南工业学院学报，2001 年，第 21 卷第 2 期，30~33.
[2] 唐泽鹏，秦雷，朱昌秀.运动估计算法分析.南京邮电学院，2001年，第12期，10~13.
[3] 赵美枝.运动估计算法的实现、分析与改进，2006年

附录
1 全搜索法
%?给图像扩边，每个边都扩大dm大小
%%%%%

I1=double(I1);
I2=double(I2);
[rownum colnum] = size(I1);

II=zeros(rownum+2*dm,colnum+2*dm);
II(dm+1:dm+rownum,dm+1:dm+colnum)=I1;%error
for i=1:dm
II(i,dm+1:dm+colnum)=II(dm+1,dm+1:dm+colnum);%left
II(rownum+dm+i,dm+1:dm+colnum)=II(dm+rownum,dm+1:dm+colnum);%down
end
for j=1:dm
II(1:rownum+2*dm,j)=II(1:rownum+2*dm,dm+1);%up
II(1:rownum+2*dm,colnum+dm+j)=II(1:rownum+2*dm,dm+colnum);%right
end
tic;
%下面进行全搜索算法
blocksize=16;
rowblocks =rownum/blocksize;
colblocks =colnum/blocksize;
A=99999999999999999999; %为了找到最小的均方误差，A用于设定一个很大的初值
Eij=0;
xrecord=ones(16,16); %xrecord，yrecord用于存放匹配块的块号，即运动矢量
yrecord=ones(16,16);
diff=zeros(rownum,colnum); %这幅图的大小为rownum*colnum

for x=0:(rowblocks-1) %x表示行中第几个子块
row=x*blocksize;
for y=0:(colblocks-1) %y表示列中第几个子块
col=y*blocksize;
% tempx=x*blocksize+1:(x+1)*blocksize;
% tempy=y*blocksize+1:(y+1)*blocksize;

for p=-dm:dm
for q=-dm:dm %（p,q）表示x,y对应子块在前一帧所的搜索位置
% 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)).^2))/(blocksize^2); %后一张图片与前一张图片对应位置的值作比较，得mse
if Eij xrecord(x+1,y+1)=p;
yrecord(x+1,y+1)=q;
end
end
end
A=999999999999999999;
for mx=1:blocksize
for ny=1:blocksize
diff(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));%后一张图片与对应位置的帧间差值
end
end
end
end

toc
z=sum(sum(diff.^2));
z=z/(rownum*colnum);
PSNR=10*log10(rownum*colnum/z)%PSNR=10*log10((2^n-1)^2/MSE)

figure,imshow(I1,[]);
title('the first frame');
figure,imshow(I2,[]);
title('the second frame');
IIII=I2-I1;
figure,imshow(IIII,[]);
title('帧间差值');
figureimshow(diff,[]);
title('利用全搜索算法匹配后的帧间差');

for x=0:(rowblocks-1) %
row=x*blocksize;
for y=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);%前一张图片根据帧间差值还原得到新图像
end
end
%III=I1+abs(diff);
figure,imshow(III,[]);
title('恢复的图像');

ERR=diff;
% figure,imshow(ERR,[]);
% title('DFD');

figure;quiver(xrecord,yrecord);
title('运动位移矢量');
grid on;

2 三步搜索法
clear all;

I1=imread('111.bmp'); %read the first frame
I2=imread('222.bmp'); %read the second frame
I1=rgb2gray(I1);
I2=rgb2gray(I2);

dm=7;
I1=double(I1);
I2=double(I2);
[rownum colnum] = size(I1);
II=zeros(rownum+2*dm,colnum+2*dm);
II(dm+1:dm+rownum,dm+1:dm+colnum)=I1;
for i=1:dm
II(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);
end
for j=1:dm
II(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;
%下面进行3步搜索法
blocksize=16;
rowblocks =rownum/blocksize;
colblocks =colnum/blocksize;
A=99999999999999999999; % Eij=0;
xrecord=ones(16,16);
yrecord=ones(16,16);
diff=zeros(rownum,colnum); % tic
for x=0:(rowblocks-1) %
row=x*blocksize;
for y=0:(colblocks-1) %
col=y*blocksize;
%