块匹配方法的运动估计研究.docx

《块匹配方法的运动估计研究.docx》由会员分享，可在线阅读，更多相关《块匹配方法的运动估计研究.docx（29页珍藏版）》请在第一文库网上搜索。

1、块匹配方法的运动估计研究摘要：在视频图像压缩编码中，运动估计技术作为一项核心技术，能够很好的解决视频图像中存在的时间冗余问题。运动估计效率的提高，运动估计算法的优化完善已成为目前研究的热点。运动估计(ME)技术主要分为两大类：块匹配法和像素递归法。考虑到计算复杂度与实时性的要求，目前常用的是块匹配方法。本论文研究了块匹配的算法中的全搜索算法、三步搜索算法、四步搜索算法、以及菱形搜索算法。通过学习掌握这几种经典块匹配运动估计算法的原理，熟悉各种算法的搜索过程、计算流程,编写实现算法的MAT1AB程序。针对相应的视频图像序列，分别采用以上算法测试运动估计的运行结果。通过分析实验结果，从不同角度比较

2、了算法的优缺点，选出最优算法。关键词：运动估计块匹配全搜索算法三步搜索算法四步搜索算法菱形搜索算法1引言1.1课题的背景及意义随着计算机网络的普及和发展，很多信息可以通过网络实现共享，尤其是网络传输的各种各样的视频信息，占据的比例越来越高。但视频信息容量大，导致在网络中的传播速度慢，因此视频信息的压缩成为视频传输的关键。而视频信息压缩中使用的核心技术是运动估计技术，它与运动补偿技术一起，能够解决视频图像中时间冗余的问题，在视频压缩编码方案里广泛应用。运动估计用来估算视频序列图像中运动物体的位移，获得运动矢量；运动补偿利用估计得到的运动矢量，将上i帧中运动物体产生的位移进行调整，使其尽可能接近当

3、前帧，故运动估计技术的优劣直接关系到运动补偿效果的好坏。由此可见运动估计技术在视频处理中的重要性。运动估计作为数字视频处理过程中不可或缺的一部分，受到人们的广泛关注，目前运动估计的方法多种多样，例如各种快速块匹配法、像素递归法。对视频信号进行处理时，要求具有很高的实时性，而运动估计算法的搜索过程又较为复杂，运动量也很大，因此寻找适合实时应用的先进算法是科研学者急于实现的共同目标。实践表明，基于块的运动估计算法已经成为视频压缩中最先进、最实用的运动估计方法,易于实现。虽然块匹配算法多种多样，但是每种算法都有各自的优缺点，因此研究运动估计效率高、搜索速度较快的算法来解决问题具有重要意义。1.2运动

4、估计的研究现状随着现代科技的飞速发展，人们对数字信息的需求日益增多。如何利用语音、图像、视频等实现人类之间方便快捷的通信已经成为全球内外科技研究的目标。数字信息的发展，带给人类的不仅仅是视觉上的冲击，更多的是对我们生活产生的巨大影响。在众多媒体技术得到关注的同时，数字视频技术在通信产业中被广泛应用，从而视频的压缩也就成为数字视频处理和传输过程中的重中之重。在视频压缩编码中，运动估计的计算量占据的比例很大，一直被视为编码压缩的瓶颈。运动估计技术主要分为像素递归法和块匹配法，而块匹配法是最为常用的一种。时至今日，学者们研究出的块运动估计算法已经有多种，而且仍在不断发展。目前，全搜索（FS）算法在块

5、匹配运动估计算法中搜索精度属于最高的，它对搜索范围内的像素点逐一都进行匹配运算，从而得到一个最优的运动矢量。如此进行，不仅计算复杂，耗时多，而且不适于实时应用。为解决这一问题，优化块匹配算法,学者们开始研究快速算法，并且提出了许多以减少搜索窗尺寸或搜索点数目网的块匹配方法，如三步搜索（TSS）算法、四步搜索（4SS）算法、菱形搜索（DS）算法等等。这些快速的搜索算法不仅降低计算复杂度，减少耗时，适合实时应用，而且己经被作为基准用于发展其他新算法。虽然越来越多块匹配运动估计的算法被提出，但是实际操作中存在各种各样的问题，使得提高算法的实时性和精确度“M22）成为运动估计的难题。一直以来，研究者们

6、都在不断寻找解决问题的方法，不断反复实验，并且提出更多适于实时应用的快速算法，但遗憾的是，仍没有找到令人满意的最优方案。随着科技的迅猛发展，运动估计领域已经出现了许多新的研究方向，相信它们会为克服这些困难、为实现算法的优化提供一个契机。1. 3本文主要工作及组织安排本文的主要工作就是在基于块匹配方法运动估计研究的基础上，研究并分析几种经典的块匹配算法，并通过运行MAT1AB程序，分析结果，从而比较几种算法的优缺点，选出最优算法。论文的章节安排如下：第一章引言。本章通过查阅相关的文献资料，介绍课题的背景意义以及运动估计技术目前的发展现状等。第二章块匹配方法的运动估计原理及技术指标。本章介绍了块匹

7、配运动估计的基本原理以及几种重要的技术指标。第三章块匹配算法。本章介绍了全搜索算法、三步搜索算法、四步搜索算法等几种经典的块匹配算法，包括算法的基本原理、所搜过程及主要流程。第四章不同块匹配算法的比较及分析。本章主要是从主客观两个方面来分析比较各块匹配算法的性能，选出最优算法。2块匹配方法的运动估计原理及技术指标1.1 块匹配运动估计的原理运动估计可以被理解为求同一对象在两帧图像中的位置差U1在块匹配运动估计中，将视频序列的每一帧图像分成许多互不重叠的宏块U2W叫并假设图像块中的各像素只做相等的位移对于当前帧中的每一个图像块，利用块匹配算法(b1ockmatchinga1gorithm,BMA

8、)在参考帧中的某个区域内搜索到最佳匹配块1(预测块)，参考帧中搜索到的预测块与相对于当前帧图像块的位移差被称为当前帧图像块的运动矢量(motionvector121,MV)o预测块和当前图像块逐像素的差值组成残差块，二者之间利用匹配准则函数计算出的值称为块匹配误差(BDM)。最佳匹配块的搜索是固定在某个范围内，起点一般在当前帧块起点位置的7像素区域内口叫称这个区域就是搜索窗口(SearChwindow)0块运动估计原理可以用如图2-1所示的思想表达，将当前帧划分为不同的图像块，设(p,q)为当前帧中一个图像块起始位置的坐标，在参考帧中确定搜索窗口，然后在此搜索窗口内搜索一个与当前帧确定的图像块

9、有同样大小的预测块，进而就得出该图像块的运动矢量(u,v)。图2-1块运动估计原理图2. 2块匹配运动估计的技术指标块运动估计的效率可以从多方面体现，如估计图像的质量、算法搜索的速度以及视频压缩码率。本文将从块匹配准则、块大小等四个方面对块运动估计的技术指标进行介绍。2.1.1 块的形状与大小块匹配方法隐含着如下假设：同一块内的像素的运动是一致的。不难发现，这个假设是片面的，怎样尽可能消除这种片面性？通过试验，正确选择块形状与大小可以在一定程度上改善这种情况。对于块的形状，为了便于图像的划分，大多考虑选用正方形，这样也简化了块匹配准则的计算。但这种选择达不到最佳效果，故有的算法考虑了其他形状，

10、例如三角形块。受两个矛盾的约束)，块大小的选择不同，估计的效果也不同。选择的块大时，假设块内各像素点做相等位移是不合理的“叫选择的块小时,运动估计结果不够准确,且会增加运算量，影响编码的效率(。多次实验表明，块大小一般选16x16或8x8最为合适网2曳2.1.2 块匹配准则根据块匹配准则可以有效判断块相似程度，使用不同的匹配准则，估计的运动矢量也不同，好的匹配准则估计出的运动矢量准确性相对较高；同时，块匹配准则对块匹配运算的复杂度、数据读取的复杂度也有很大影响。因此，正确选择的块匹配准则也是提高估计效率的有效渠道。运动估计算法中用到的块匹配准则主要有以下三种123：均方误差(MeanSquar

11、eError,MSE)和平均绝对误差(MeanAbso1uteDifference,MAD)以及归一化的互相关函数(NCCF)闽24),其定义如下：平均绝对误差：IMNMADi,J)=-IAn)-(m+i,+j(2.1)MN/M=|n=式(2.1)中，。,力是位移矢量，人是当前帧的灰度值，j是参考帧的灰度值，MN为宏块的大小。如果在某一点(io。)处MAD。)达到最小”叫那么该点即为要寻找的最优点。均方误差I网:IMNMSE(i,)=ZZfk(m,)一-(利+)(2.2)最小MSE值对应的点即为最优点网。归一化的互相关函数：（加,MfkT（加+，,+7）NCCF（i,j）=以上irMNHomN

12、2m=/1=16（加,）-（根z+7）最大NCCF值对应的点即为最佳优点。在运动估计过程中，块匹配准则对匹配的精度没有很大的影响，其中平均绝对误差准则是不需要作乘法运算的，实现起来简单方便，所以使用次数也就最多。2.1.3 初始搜索点的选择124一般情况下，我们可以把初始搜索点的选择分为两种方式：一种是选择参考帧对应的原点，该操作很简单，但不足之处就是使得搜索到的最佳匹配点带有局部性；在原点非最佳匹配点的情况下，若调用算法采用较大的初始步长，那么搜索过程中会丢失那些相似性比较大的点，搜索距离变大，搜索到的点准确性降低，使得搜索方向变得混乱，如此获得的点可能不是全局最优点。另外一种就是选择预测的

13、起点。这种方法是基于视频序列的相关性提出来的，利用这一点预测初始搜索点，由此得到初始点。通过多次试验证明，预测点位置的选择对搜索次数有很大影响，他的位置离最佳匹配点越近，搜索次数越少。2.1.4 搜索策略整个搜索算法的好坏关键体现在搜索策略。搜索策略复杂多样，千变万化，对它正确运用，能够有效减少搜索次数、降低搜索复杂度。搜索策略有多种，从不同的角度出发，得到的策略也就不同。从搜索方向出发，可以有梯度式、螺旋式；从搜索路线出发，有菱形、交叉线性及圆形等等。若将不同的搜索步长与这些搜索策略相结合,就会产生不同的搜索模式，从而构成不同的搜索算法。3块匹配算法在视频编码过程中，运动估计是计算最耗时的步

14、骤。块匹配算法发展至今，学者们已经提出多种性能各异的搜索算法。在全搜索算法的基础上，出现了多种快速算法,有三步搜索算法、四步搜索算法和菱形搜索算法等等。总结前面的内容可知，采用不同的块匹配运动估计的技术指标，就会构成不同的搜索算法。块匹配算法在实现时，分块的大小、最佳匹配准则不是必需的，因此寻找最佳匹配块的搜索路径是区分不同块匹配算法的主要依据。3. 1全搜索算法基本原理全搜索算法也称为穷尽搜索算法（网（ES）,它是对搜索窗口内的像素点逐一进行计算MAD的值，选出平均绝对误差最小值对应的点，即为最小块匹配误差（MBD）点12叫其相对应原始帧的偏移量为运动矢量。全搜索算法通常只作为一种基准或者在

15、一些快速搜索算法中，用它的结果表示真的运动矢量以衡量其他运动估计块匹配算法的优劣。算法描述：FS算法的搜索过程示意图如图3-1,步骤描述如下：第一步：全搜索算法在搜索窗口内，按照从左至右，从上到下的顺序，对每个像素都进行搜索，同时分别计算各个像素的MADft,直到将搜索范围中所有的点搜索完全,记录所有的MAD值。第二步：在所有记录下来的MAD值中找到MAD值最小的点，即MBD点，该点对应的位置即为所求的运动矢量12%算法流程图图3-2FS算法流程图3. 2快速算法3.1.1 三步搜索算法基本原理：在小运动视频序列中，三步搜索算法1（TSS）已作为经典算法被广泛应用。TSS算法的搜索步骤简单，搜索过程由简到精，选取一定的步长后，从（0,0）开始，按照正方形，每次选取周围的8个点进行匹配运算，找到MBD点。算法描述：第一步：从（0,0）开始，以4为步长，计算各点中心点及其周围8个邻点的MAD值，记录下MBD点；第二步：以第一步搜索到的MBD点为中心，步长缩小为2,同第一步一样计算像素点的MAD值，找到并记录MBD点；第三步：以第二步搜索到的MBD点为中心，步长减为1,此时该点为最终的MBD占其搜索过程示例如图3-3所示：第一步第二步