多媒体信息处理-视频运动估计算法

1、武汉理工大学通信工程应用技术综合训练与实习报告课程设计任务书课程设计任务书学生姓名：学生姓名： 专业班级：专业班级： 指导教师：指导教师： 苏杭苏杭 工作单位：工作单位： 信息工程学院信息工程学院 题题 目目: 多媒体信息处理多媒体信息处理 初始条件：初始条件：MATLAB 软件平台；视频运动估计相关知识要求完成的主要任务要求完成的主要任务: : 设计视频压缩系统中的运动估计算法：全搜索法（FS: Full Search）和三步法(TSS: Three Step Search)，比较二种方法的搜索点和每帧的峰值信噪比（PSNR： peak signal to noise ratio）要求：编制

2、算法代码；对视频进行运动估计；计算 PSNR时间安排：时间安排：序序号号设设 计计 内内 容容所用时所用时间间1根据设计任务，分析算法原理，确定实现方案2 天2根据实验条件进行算法的测试，并对结果进行分析7 天3撰写课程设计报告4 天合 计2 周武汉理工大学通信工程应用技术综合训练与实习报告指导教师签名：指导教师签名： 20152015 年年 1 1 月月 1818 日日系主任（或责任教师）签名：系主任（或责任教师）签名： 20152015 年年 1 1 月月 1818 日日武汉理工大学通信工程应用技术综合训练与实习报告I摘要随着计算机视觉、数字视频信号处理和通信技术的发展，多媒体技术得到了广

3、泛的应用。其中，数字视频信号处理是关键技术。为了克服视频信号数据量大的问题，必须提高视频信号的压缩编码效率。运动估计是视频压缩编码中的核心技术之一。为了使多媒体产品能得到更加广泛的应用，国际上提出了一些视频压缩标准。但这些标准并没有规定具体采用哪种运动估计算法。因此，具有高压缩性的快速运动估计算法的开发成为近年来和今后的研究热点。本文通过 MATLAB 仿真平台，实现了经典的全搜索算法（FS）和二维三步搜索算法(TSS)，并对更加高效的 ETSS 算法进行编程仿真，性能比较也显示ETSS 比 TSS、FS 更加具有实时性。关键词关键词：运动估计；视频压缩；全搜索算法 ；三步搜索算法武汉理工大学

4、通信工程应用技术综合训练与实习报告IIAbstractWith the development of computer vision, digital video signal processing and communication technology, multimedia technology has been widely used. Among them, the digital video signal processing is the key technology. In order to overcome the problem of large amount of vid

5、eo data signal, video signal compression coding efficiency must be raised. Motion estimation is one of the core technology of video compression coding. In order to make the multimedia products can be used more widely, people put forward some international video compression standard. But these standa

6、rds are not provided specific use what kind of motion estimation algorithms. Therefore, the development of the fast motion estimation algorithm with high compressibility is becoming a hot spot in recent years and the future research.In this article, through the MATLAB simulation platform, has realiz

7、ed the full search algorithm (FS) and the classic 2d three-step search algorithm (TSS),and simulated the more efficient algorithm-ETSS, performance comparisons also show ETSS is more real-time than TSS and FS .Keywords: motion estimation，video compression，FS, TSS武汉理工大学通信工程应用技术综合训练与实习报告I目目 录录摘要.IABST

8、RACT .II1 视频运动估计概述 .11.1 运动估计技术的地位与作用.11.2 运动估计技术的发展趋势.11.3 视频压缩系统的组成.12 运动估计原理.32.1 基于块的运动估计.32.2 基于光流方程的运动估计 .42.3 基于像素的运动估计.42.4 全局运动估计.42.5 基于区域的运动估计.52.6 多分辨率的运动估计.63 全搜索算法和三步搜索算法.73.1 全搜索算法.73.2 三步搜索算法.74 运动估计算法的设计 .94.1 全搜索算法设计.94.2 三步搜索算法设计.95 仿真结果.115.1 全搜索法结果.115.2 三步法结果.125.3 性能比较.145.3.1

9、 计算复杂度.145.3.2 峰值信噪比.156 结论.177 参考文献.18附录.19武汉理工大学通信工程应用技术综合训练与实习报告11 视频运动估计概述1.1 运动估计技术的地位与作用视频信号通常每秒包括十几帧以上的静态图像。视频信号的处理通常需要存储、传输并操作大量数据。如果不采用数据压缩，视频信号频带宽度达6MHZ，甚至更宽的频带。为在只有 64Kbps 的公众服务电话网上传输这个视频图像序列，需要用压缩比倍数大于 100 的方法来压缩此视频信号。即使对于现在带宽较高的网络来说，视频压缩后能使该网络提供更多的服务，也可以使网络为更多的用户服务。为使多媒体产品能更广泛地应用，视频压缩就显

10、得尤为重要。为满足在多媒体通信中视频压缩的需要，人们提出了一些视频压缩方面的国际标准。视频数据压缩主要通过三种技术手段来实现:利用离散余弦变换（DCT）和离散小波变换（DWT）来消除视频帧内的空间冗余，利用熵编码来消除编码冗余，利用运动估计来消除帧间的时间冗余。运动估计是视频压缩编码中的核心技术之一，采用运动估计和运动补偿技术可以消除视频信号的时间冗余以提高编码效率。1.2 运动估计技术的发展趋势在人们提出的各种视频压缩标准中，运动估计都是其中重要的一部分。然而，压缩标准的提出并没有规定采用具体的哪种运动估计算法。所以这部分的工作就留给了标准的具体开发者。因此，提高运动估计的效率，使运动估计算

11、法的搜索过程更健壮、更快速、更高效成为近些年研究的热点。1.3 视频压缩系统的组成图 1.1 给出了一个典型的视频编码器的结构。现今视频压缩标准 MPEG-1，MPEG-2，MPEG-3，MPEG-4，H.261，H.262，H.263+和 H.264 采用了这个结构。在压缩重建后的视频序列的失真度小于我们规定值的前提下，此编码武汉理工大学通信工程应用技术综合训练与实习报告2器的目的就是用最少的输出比特来表示初始的视频信息。如前文所述，运动估计用来去除帧间的时间冗余。在帧间预测编码中，由于活动图像邻近帧中的景物存在着一定的相关性。我们通常利用各帧之间的相关性来压缩视频信号。例如，可将当前帧分成

12、若干块或宏块，并设法搜索出每个块或宏块在前一帧图像中的位置，并得出两者之间的空间位置的相对偏移量，得到的相对偏移量就是通常所指的运动矢量，得到运动矢量的过程被称为运动估计。图 1.1 视频编码器结构运动矢量的信息被编码并发送到解码端，这样，在解码端按照运动矢量指明的位置，从已经解码的前一参考帧图像中找到相应的块或宏块，和预测误差相加后就得到了块或宏块在当前帧中的位置。由于用来表示运动矢量的比特数在通常情况下都远远小于直接表示当前帧的比特数，因此，利用运动估计技术可以大大减少表示当前帧的比特数。由此可以看出，运动估计是视频压缩处理系统中的一个重要组成部分。在大多情况下，当前块和参考块之间的误差（

13、帧间误差）比较大，同时存在空间冗余。因此，编码器中对帧间误差进行 DCT 或 DWT 变换，以消除帧间误差在空间的相关性。DCT 或 DWT 的系数经过量化后被编码和传输到接收端，解码器可以利用编码和表示帧间误差的比特来提高重建帧的质量。武汉理工大学通信工程应用技术综合训练与实习报告32 运动估计原理运动估计是数字视频处理的基本问题之一，它涉及到图像平面二维运动或物体三位运动的估算，其中二维运动估计除了是迈向三维运动分析的第一步，还作为运动补偿滤波和压缩的重要部分，本章只介绍二维运动估计，并着重介绍块运动估计方法。2.1 基于块的运动估计块运动模型是假设图像由运动的块构成。块运动估计算法的目的

14、是从参考帧（先前重建的帧）的搜索窗中寻找和当前块相匹配的块（参考块） 。 图 2.1 块匹配法原理图假设图像中每块的大小为 MN，dxmax 为参考块水平方向可搜索最大位移而 dymax 为参考块垂直方向可搜索最大位移，那么基于块匹配的运动估计就是在参考帧（或者其它上一帧）的(M+2dxmax)(N+2dymax)候选区搜索窗口中找到和目标帧的当前大小为 MN 的块的最匹配的块，参考块的运动矢量可用如下的数学公式描述： (2-1)R 表示相关性评价函数，f(m,n)表示目标或当前帧图像的亮度值。满足 R为最大时的 X、Y 为运动矢量，用 MV 表示。武汉理工大学通信工程应用技术综合训练与实习报

15、告4 (2-2)参考块和当前块的相似度通常用平均绝对差值（Mean Of Absolute Difference, MAD）表示。有些文献中 MAD 演变为绝对差和： （2-3）2.2 基于光流方程的运动估计基于光流方程的方法是试图依据时空图像亮度梯度来得到一个光流场的估算。对于单色图像需要与合适的时空平滑约束条件联合使用，这个条件要求位移矢量在附近区域缓慢变化。对于彩色图像，可分别施加于每个颜色带，它能够约束三个不同方向的位移矢量。然而，在绝大多数的情况下，一个适当的平滑度约束条件对于获得满意结果也是需要的。整体平滑度约束条件引起遮挡边界上的不准确的运动估算，更先进的有向平滑约束条件允许运动

16、场中有突变的间断点。2.3 基于像素的运动估计在基于像素的运动估计中，必须估计每一个像素的运动矢量。显然，这个问题是难于处理的。如果使用恒定亮度假设，对于锚定帧的每一个像素，在目标帧里将会有许多完全相同亮度的像素。如果使用光流方程，这个问题仍然是不确定的，因为未知数只有一个方程。为了防止这个问题发生，一般有四种方法：第一，可以使用正则化技术在运动场上施加平滑约束，使得新像素的运动矢量受周围像素的已找到的那些运动矢量的约束。第二，可以假定每一个像素周围领域中的运动矢量是相同的，并且把恒定亮度假设或光流方程应用到整个领域。第三，可以利用另外一些不变量约束；除导致光流方程的亮度不变量外，还可以假设运

17、动中的亮度梯度是不变的。最后，可以利用运动场前后帧的相位武汉理工大学通信工程应用技术综合训练与实习报告5函数之间的关系。2.4 全局运动估计对于基于网格的运动表示，锚定帧中的图像被分成互不重叠的多边元素，每一个元素用几个节点和节点的连线表示，这样的元素称为网格。基于网格的运动估计一般要解决两类问题：在锚定帧中给定一个网格，如何确定目标帧中的节点位置，这实质上是一个运动估计问题。在锚定帧中如何建立网格，使得网格与物体的边界一致。注意，每一个元素对应于单个物体的一小块光滑表面的网格比任意配置的网格（例如，正规网格）能得到更精确的估计。一个物体自适应的网格也将更适应于帧序列的运动跟踪。关于网格生成，

18、主要方法有健壮估计器、直接估计和间接估计。这里就不详细讲述了。2.5 基于区域的运动估计在基于区域的的运动估计中，把图像帧（锚定帧）分割成多个区域，并估计每一个区域的运动参数。这种分割应该使一个单一的参数运动模型可以很好地表示每个区域进行单独的平移运动。然而这个要求会造成太多小的区域，因为在对应于一个物理物体的区域中的二维运动，极少能够用一个简单的平移来模型化。这样一个区域必须分割成许多小的子区域，使每一个区域具有单一的平移运动。对于更高效的运动表示，应该使用正交和透视运动模型。一般实现基于区域的运动估计有 3 中方法：（1）第一种方法，首先把图像帧分割成不同的区域，即基于纹理同质性、边缘信息

19、以及有时通过对两帧间不同图像的分析得到的运动边界，然后估计每一个区域中的运动，称这种方法为区域优先。（2）第二种方法，首先估计整个图像的运动场，然后分割得到的运动场，使得每一个区域的运动可以用单一的参数模型描述，称这种方法为运动优先。得到的区域可以在一些空间的连通性约束下进一步优化。这个方法中的第一步武汉理工大学通信工程应用技术综合训练与实习报告6可以利用前面描述的各种运动估计方法实现，包括基于像素、块、和网格的方法。第二步涉及基于运动的分割，这里不再详细讲述。（3）第三种方法是对区域分割和每一个区域的运动进行联合估计。一般这时用一个迭代过程实现的，交替地进行区域分割和运动估计。2.6 多分辨

20、率的运动估计前面介绍的运动估计方法存在的问题有：最小化误差函数可能收敛到局部最小值和最小化误差函数过程的计算量很大。多分辨率运动估计可有效解决这两个问题。首先在最小分辨率层（由空间低通滤波和欠取样获得）进行运动估计，并把结果作为下一层的初始解。然后每层依次进行运动估计，每层的运动估计结果都将作为下一层的初始解每层的运动估计可使用前面介绍的方法，如基于光流、像素、块、网格等运动估计方法。图 2.2 多分辨率运动估计分层多分辨率运动估计优点：（1）运动场接近最优解的概率更大（2）较小分辨率层上，误差函数可以接近全局最小值，通过插值，获得高分辨率上的初始解，最后到达最大分辨率时，误差函数接近全局最小

21、值的可能性更大。武汉理工大学通信工程应用技术综合训练与实习报告7（3）计算量比直接在最大分辨率上进行运动估计时要小（4）较小分辨率层上，搜索范围限制在较小的范围。武汉理工大学通信工程应用技术综合训练与实习报告83 全搜索算法和三步搜索算法上述介绍的几种运动估计算法中，基于块的运动估计硬件复杂度较少，易在超大规模集成电路中实现，被认为是最通用的方法3.1 全搜索算法全搜索法（Full Search, FS）也称为穷尽搜索法，是对（M2dx）（N2dy）搜索范围内所有可能的候选位置计算 MAD 值，从中找出最小MAD，其对应偏移量即为所求运动矢量。此算法虽计算量大，但最简单、可靠，找到的必为全局最

22、优点。FS 算法描述如下：从原点出发，按顺时针螺旋方向由近及远，在逐个像素处计算 MAD 值，直到遍历搜索范围内所有的点，然后在计算的所有点的MAD 中找到最小值，该点所在位置即对应最佳运动矢量。FS 算法是最简单、最原始的块匹配算法，由于可靠，且能够得到全局最优的结果，通常是其它算法性能比较的标准，但因为对于搜索窗中的每一的候选运动矢量都需要计算一次它的平均绝对差值，所以它的计算量的确很大，这就限制了在需要实时压缩场合的应用，所以有必要进一步研究其它的快速算法。由于块运动估计的全搜索算法具有很高的计算复杂度，因此在已有的文献中，人们提出了许多快速运动估计算法。这些算法可大致归为多步搜索算法和

23、穷尽搜索算法这两类。对于多步搜索算法，只选择搜索窗中所有运动矢量的一个子集，这样就可以减少对 MAD 的计算次数。对于穷尽搜索算法，先计算MAD 的一个下界，然后尽可能地利用此下界来避免计算 MAD。3.2 三步搜索算法三步搜索算法、新三步搜索算法、四步搜素算法、基于块的梯度下降搜索算法、二维对数搜索算法、菱形搜索算法、交叉搜索算法、共轭方向搜索算法、武汉理工大学通信工程应用技术综合训练与实习报告9正交搜索算法、分层块匹配算法、简易搜索算法是属于此类的快速算法。在这些搜索算法中，运动估计的过程都将包括几个步骤。每一个步骤都将选择一些搜索点，并计算这些搜索点的 MAD/SAD 值。本文着重介绍三

24、步搜索算法(TSS)。图 3.1 三步搜服哦算法三步法是应用得相当广泛的一种次优的运动估计搜索算法。此搜索算法如图 2-2 所示，可分为下面三步：第一步搜索 9 个位置点，如图中方块所标示的 9 个点。对每一个位置点计算 MAD，找出最小 MAD 值的点。将搜索中心移动到第一步中具有最小 MAD 值的点上。搜索步长减少为第一步搜索步长的一半，进行第二步的搜索匹配，如图中圆形标示的点。对每个位置点计算 MAD 值，找出最小 MAD 值的点。然后继续将搜索中心移动到第二步中具有最小 MAD 值的点上。搜索步长减少为第二步搜索步长的一半，来进行第三步的搜索匹配，如图中三角块标示的点。对每个位置点计算

25、 MAD 值，找出最小 MAD 值的点。得到最佳的运动矢量 MV（） 。由于第二步和第三步的 9 个搜索点中均有一个点是在上一步中已经计算过MAD 值，所以第二步与第三步均只要计算 8 个点而已，所以 TSS 算法的计算次数是 98825 次，同直接匹配需要 225 次比较，计算量大大减少。武汉理工大学通信工程应用技术综合训练与实习报告104 运动估计算法的设计对于全搜索法和三步法的仿真，本文将采用 MATLAB （R2009a）软件进行仿真。4.1 全搜索算法设计将图像的 k+1 帧分为不重叠，紧靠的 N*N 大小的块，然后依次对每一块进行处理。在处理某一块时，以该块的中心点为中心点，在源帧

26、 k 中的窗口内的每个像素进行一次匹配，计算所有的 MAD（公式 2.2） ，然后找出最小的 MAD的点，就是与之相匹配的点。图 4.1 全搜索算法程序流程图 4.2 三步搜索算法设计武汉理工大学通信工程应用技术综合训练与实习报告11三步法是一种较好的搜索算法，快速而且高效，它是在对数法的基础上对其进行了改进，提出在每一步搜索后搜索步长均减半的算法。它基本保持了FS（全搜索算法）的性能，但比 FS 少了大量的计算量。TSS 在会议电视和可视电话中应用较多， 它通过三步搜索，逐步较小搜索步长。对于搜索步长 m0,我们定义T（m）=M(m) (-m,-m)， （-m,m）,(m,m),(m,-m)

27、这里 M（m）定义为：M（m）=(0,0)， （m,0）,(-m,0),(0,-m)这种搜索样式将会被重复利用直到搜索步长为 1。三步搜索法采用 T(M)这个搜索样式。三步搜索法的初始搜索步长为搜索窗的 1/4。接着，在三步搜索法中的每一步的搜索步长均减半，直到搜索步长为1。初始的搜索中心是在搜索窗的中心。除初始步骤外，在每一步所选择的搜索中心为前一步中具有最小 MAD 值的位置。(1)初始化对每一个（i,j）N(W),MAD(i,j)=,这里 N(W)=(i,j)|-m=i,j 图像% | | | |% | | | |% | | | |% |-|-|-|% | G | H | I |% |-

28、|-|-|%武汉理工大学通信工程应用技术综合训练与实习报告23rownum 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);endfor j=1:dm II(1:rownum+2*dm,j)=II(1:rownum+2*dm,dm+1)

29、; II(1:rownum+2*dm,colnum+dm+j)=II(1:rownum+2*dm,dm+colnum);endblocksize=16; rowblocks =rownum/blocksize; colblocks =colnum/blocksize; A=99999999999999999999; %为了找到最小的均方误差，A 用于设定一个很大的初值 Eij=0; xrecord=ones(16,16); %xrecord，yrecord 用于存放匹配块的块号，即运动矢量 yrecord=ones(16,16); diff=zeros(256,256); %这幅图像的大小为

30、256*256，diff 用于存放像素差值 tic for x=0:(rowblocks-1) %x 表示行中第几个子块 row=x*blocksize; for y=0:(colblocks-1) %y 表示列中第几个子武汉理工大学通信工程应用技术综合训练与实习报告24块 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(

31、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)/(blocksize2); if EijA A=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

32、+mx+dm+xrecord(x+1,y+1),col+ny+dm+yrecord(x+1,y+1);武汉理工大学通信工程应用技术综合训练与实习报告25 end end end end for x=0:(rowblocks-1) %x 表示行中第几个子块 row=x*blocksize; for y=0:(colblocks-1) %y 表示列中第几个子块 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)+block

33、size,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 toc FS_time=toc;mse=sum(sum(diff.2);mse=mse/(rownum*colnum);FS_PSNR=10*log10(255*255/mse);三三步搜索法子程序%三步搜索法武汉理工大学通信工程应用技术综合训练与实习报告26function TSS_PSNR,TSS_time,diff,III,xrecord,yreco

34、rd=TSS(I1,I2)dm=7;%给图像扩边，每个边都扩 dm 大小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);endfor j=1:dm II(1:rownum+2*dm,j)=II(1:rownum+2*dm,

35、dm+1); II(1:rownum+2*dm,colnum+dm+j)=II(1:rownum+2*dm,dm+colnum);endblocksize=16; rowblocks =rownum/blocksize; colblocks =colnum/blocksize; A=99999999999999999999; %为了找到最小的均方误差，A 用于设定一个很大的初值 Eij=0; xrecord=ones(16,16); %xrecord，yrecord 用于存放匹配块的块号，即运动矢量 yrecord=ones(16,16); diff=zeros(256,256); %这幅图像

36、的大小为 256*256，diff 用于存放像素差值 tic for x=0:(rowblocks-1) %x 表示行中第几个子块武汉理工大学通信工程应用技术综合训练与实习报告27 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 p1=-4:4:4 %第一步 for q1=-4:4:4 %（p，q）表示在 x，y 对应子块在前一帧中所的搜索位置 Eij

37、=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).2)/(blocksize2); if EijA A=Eij; xrecord(x+1,y+1)=p1; yrecord(x+1,y+1)=q1; end end end p1=xrecord(x+1,y+1);武汉理工大学通信工程应用技术综合训练与实习报告28 q1=yrecord(x+1,y+1); for p2=p1-2:2:p1+2

38、%第二步 for q2=q1-2:2:q1+2 if p2=p1 | q2=q1 Eij=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).2)/(blocksize2); if EijA A=Eij; xrecord(x+1,y+1)=p2; yrecord(x+1,y+1)=q2; end end end end p2=xrecord(x+1,y+1); q2=yrecord(x+1,y+1); for p3=p2-1:1:p2+1 %第三步 for q3=q2-1:1:q2+1 if p3=p2 | q3=q2 Eij=0; 武汉理工大学通信工程应用技术综合训练与实习报告29Eij=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).2)/(blocksize2); if EijA A=Eij; xrecord(x+1,y+1)=p