基于块匹配运动估计算法的设计

目 录中文摘要IAbstractII引言1第一章 运动估计的研究背景和现状21.1 课题的背景与意义21.2 运动估计的研究现状31.3 本文的主要工作及内容安排4第二章 块匹配运动估计原理以及技术指标42.1 运动估计62.2 二维运动场模型72.3 块匹配运动估计的基本原理82.4 块匹配运动估计运动的技术指标102.4.1块的模式选择102.4.2常见的块匹配准则102.4.3 算法评定指标11第三章 典型块匹配运动估计算法分析123.1 全搜索法123.2 三步搜索法133.3 新三步搜索算法153.4 四步搜索法163.5 菱形搜索法173.6 六边形搜索法20第四章 基于块匹配运动估计算法的改进与设计224.1 经典的菱形算法固有的缺陷224.2 准十字菱形搜索算法原理224.2.1 运动向量的分布224.2.2 搜索模块的改进244.3 准十字菱形算法描述254.4 算法流程图26第五章 仿真结果及分析285.1 实验平台285.2 仿真实验结果285.3 实验结果分析29结论31致谢32参考文献33附录35III基于块匹配运动估计算法的设计摘要 运动估计技术是视频压缩编码中的核心技术之一，采用运动估计和运动补偿技术可以消除视频信号的时间冗余，从而提高编码效率。研究设计高效、快速、鲁棒的运动估计算法成为目前视频压缩技术中研究的重要课题。在各种运动估计方法中，块匹配法由于其原理简单、便于实现等优点得到了普遍应用，其相关快速算法也得到了广泛的研究和发展。但是，传统的快速块匹配算法如三步法、菱形法等虽然极大地提高了搜索速度却具有易陷入局部最优的固有缺陷，这对于运动估计的质量有很大的影响，是迫切需要解决的问题。该设计是在分析和研究几种经典的运动估计算法的基础上，改进并实现一种更优的算法。首先阐述了基于块匹配的运动估计的基本原理，并详细介绍了全搜索法和几种典型的块匹配运动估计快速算法，分析了各算法的优缺点。然后重点介绍了一种改进的自适应运动估计算法准十字菱形搜索算法。此算法根据序列图像中运动矢量的十字中心偏置分布特性和运动矢量间的时空相关性，设计了一种准十字菱形搜索模板。以上技术保证搜索准确性的同时，很大的提高了运动估计的速度。最后，采用两个指标对该算法设计进行衡量:平均每块的搜索点数和平均峰值信噪比PSNR。综合实验数据，可以得出该设计对具有小运动、中等运动和大运动的视频序列图像均能在搜索速度和搜索精度两方面保持比较优异的性能，特别是对大运动视频序列，表现的尤为明显。所以该算法无论在搜索准确性还是搜索速度方面，与以往的快速搜索算法相比，均具有一定的优势，并且由于本算法充分利用了向量的时间和空间上的相关性来预测起始搜索点，从而使算法不容易陷入局部最优，极大的避免了出现搜索错误的可能，提高了搜索效率。关键词： 运动估计 ；块匹配 ；十字菱形搜索模板 ；平均峰值信噪比 The Design of Algorithm for Motion Estimation Based on Block-matching Abstract Motion estimation is one of the core techniques of video coding. Motion estimation and motion compensation can reduce the large amount of temporal redundancy that exists between frames of video sequences, which leads to high compression. Therefore, research on efficient video compression coding technology has already been a hot topic for technicians and researchers all over the world. Motion estimation and motion compensation techniques, which can effectively eliminate temporal redundancy between video sequences, have been widely applied to popular video compression coding standards to improve compression efficiency. Nowadays, it is an important issue in video coding area to develop a speedy, robust and efficient motion estimation algorithm. Among current motion estimation methods, block-matching algorithm(BMA)is the most popular one owing to its simple principle and suitability for implementation. Many fast block-matching algorithms such as Three-step Search-(TSS),Diamond Search(DS)have been proposed to reduce computational amount of Full Search(FS)which is not fit for real-time applications because of its unacceptable computational cost. Although these traditional fast algorithms can improve search speed significantly, they have an inherent shortcoming of being liable to get trapped in local optima, which can degrade the quality of motion estimation to some extent, it is a problem that needs resolute urgently .In this design, the main task is to analyze and study several classic motion estimation algorithms, and on the basis of these algorithms, an attempt is made to implement and improve the performance of motion estimation algorithms. Firstly, this design elaborates the essential principle of the motion estimation based on block matching, introduces Full Search method and several typical motion estimation fast algorithms based on block matching, analyzes each characteristic. Secondly, an improved motion estimation fast algorithm is proposed. An adaptive Quasi-Cross-Diamond Search(QCDS) algorithm based on predictive initial point is presented. Based on the cross-center-bias property and spatial-temporal correlation of the motion vector field, a quasi-cross-diamond search pattern was designed. The algorithm in this desige substantially improves the motion estimations speed, while ensures the search accuracy. Finally, two indicators used to measure the algorithm design: the average search points per block and the average peak signal to noise ratio PSNR.According to the experiments data， the following conclusions can be drawn, for whatever small, middle and large motion of video sequences, the algorithm in this paper keeps the two relatively high-performance in the search speed and accuracy, especially for the sequences with large motion. Therefore, compared with the fast search algorithms in the past, the algorithm in this paper have certain advantages both in search accuracy and search speed. And because the algorithm takes full advantage of spatial-temporal correlation of the motion vector field to predict the initial search point, it is not easy to get a local optimum, but can avoid mistakes and improve the search efficiency.Key words Motion Estimation ; Block Matching ; Quasi-cross- Diamond Search Pattern;Peak Signal to Noise Ratio引 言随着计算机技术与通信技术的发展，图像处理与传输，特别是视频图像传输成为人们获取信息的主要途径。然而表达视频图像所需要的巨大数据量与有限的传输通道成为视频信息交换的主要障碍，因此视频压缩是视频传输之前的重要任务。运动估计是视频压缩技术中非常重要的组成部分，其估计方法直接决定了视频图像压缩编码的运行速度。运动估计的方法很多，其中基于块匹配的运动估计算法（BMA）由于实现较简单且容易而受到广泛关注。全搜索（FS）作为 BMA 的一种原始算法虽然搜索精度极高，但所需计算量相当大，很难适应实际应用，特别是实时应用的要求。为了改善搜索速度，在过去的二十年中出现了大量快速 BMA。比较有代表性的算法有三步搜索法（TSS）和二维对数法（2LOGS）等。这些算法主要利用运动矢量的均匀分布模式进行搜索，其搜索步长较大，因此可能导致搜索方向的不确定性和搜索的局部性。为了解决上述问题，人们提出了利用现实图像序列运动矢量空间分布中心偏置特性的算法，如四步搜索法（FSS）、新三步搜索法（NTSS）。由于这些算法充分考虑了运动矢量概率（MVP）分布，因此在保持与 FS 相当的图像质量的同时，很大程度地提高了搜索速度。在此基础上，出现了大量的非矩形搜索模型的算法，如菱形搜索算法（DS）和六边形搜索算法（HEXBS）等。其中：DS算法被 MPEG标准所采用。除了搜索模型的形状对搜索的影响之外，搜索模型的大小以及搜索策略对搜索速度和图像质量同样有影响。为此，本文根据序列图像中运动矢量的十字中心偏置分布特性和运动矢量间的时空相关性，设计了一种改进型的十字菱形搜索（QCDS）算法。第一章 运动估计的研究背景和现状1.1 课题的背景与意义随着信息技术的发展和社会的不断进步，人类对信息的需求越来越丰富，人们希望无论何时何地都能够方便、快捷、灵活的通过语音、数据、图像与视频等多种方式进行通信。视觉信息给人们直观、生动的形象，图像/视频的传输更受到广泛的关注。数字信号处理技术、物理媒体与网络技术、超大规模集成电路技术突飞猛进的发展，使得多媒体通信成为研究和应用的热点。其中，最为关键的技术是数字视频的处理和传输技术，它将电视技术、计算机技术和通信技术结合在一起，在电视系统、计算机网络和通信产业中得到了广泛的应用，己经进入千家万户的日常生活中。数字视频硬件方面的进步和有关数字视频压缩国际标准的推出，使得数字视频技术领域趋于成熟。自20世纪90年代以来，国际电联ITU和国际标准化组织ISO先后颁布了一系列视频编码和多媒体视频通信的建议和国际标准。如ISO/IEC成立了JPEG(Joint Photographic Expert Group)和MPEG(Moving Picture Experts Group)并先后完成了JPEG、JPEG2000、MPEG-1、MPEG-2和MPEG-4标准的制定；ITU-T也先后制定了H.261、H.262 (与MPEG组织合作)、H.263 / H.263+和H.264(与MPEG组织合作)等一系列国际数字视频压缩编码标准。它们为视频编码技术的发展起到了巨大的推动作用。研究发现，图像数据表示中存在大量的冗余。通过去除那些冗余数据可以使原始图像数据极大的减少，从而解决图像数据量巨大的问题。对于静态图像，最主要的数据冗余是空间冗余。图像帧记录了可见景物的颜色，而同一景物各采样点的颜色之间存在着空间连贯性，但基于离散像素采样来表示物体颜色的方法通常没有利用景物表示颜色的这种空间连贯性，因此产生了空间冗余。序列图像帧内存在空间冗余，而帧间则存在着很大的时间冗余。这是由于序列图像一般是位于同一时间轴区间内的一组连续画面，其相邻帧间变化量一般很小，只是表现为移动物体所在的空间位置略微不同。运动估计和运动补偿技术就是解决图像帧间时间冗余的很好的方法。运动估计与运动补偿是现阶段视频压缩编码的关键技术。它是一种实现帧间编码的方法，利用前后两帧或若干帧之间的时间相关性，去除时间冗余度。帧间编码之所以能减少冗余度，是因为在一般视频序列的两帧之间有很大的空间结构相似性，前后两帧的差帧可以用比帧内编码所需少很多的比特数来进行编码。而帧间预测的方法基本上是以基于块匹配的运动估计(补偿)算法为主。运动估计目前面临的主要问题就是如何比较快速的得到比较准确的运动矢量，因为在整个视频编码的过程中，即使采用快速算法，运动估计仍然是耗时最长、资源占用最高的环节，如在H.261的编码过程中，在采用著名的三步快速搜索法的情况下，运动估计仍要占用整个编码过程的63%的计算量; 而在H.263编码器中，运动估计也还占用了42%的计算量。因此，运动估计成了视频压缩编码的瓶颈，特别是对于帧幅较大、帧频较高的视频对象，在编码实时性和硬件实现方面，运动估计还有很多潜力可挖。基于上述原因，高效快速的运动估计算法一直是视频压缩编码领域的研究热点，由于上述原因，高效快速的运动估计算法一直是视频压缩编码领域的研究热点，尤其是从 1997 年 10 月召开的 MPEG 会议上开始征集运动估计快速算法以来，这个领域的竞争异常激烈。运动估计与补偿可分为块匹配法、像素递归法与相位相关法。由于块匹配法能够在精度与复杂度方面得到较好的折衷，故目前制定的运动图像压缩标准（H.261, MPEG-4）都采用了块匹配法。块匹配法的性能主要由三个因素决定，即匹配标准、搜索算法与搜索区，其复杂度亦由上述三个因素决定。与其它算法相比，虽然块匹配法的复杂度是最低的，但仍然难以接受。在决定复杂度的三个因素中，匹配标准与搜索区相对固定，搜索算法较灵活，所以人们往往通过一些非最优搜索算法来降低复杂度，如三步搜索算法（TSS）、新三步算法（NTSS）、四步搜索算法（FSS）、钻石搜索算法（DS）等等本课题的意义在于，在己有算法的基础上提供了一种新的思路，通过研究已经成熟的各种模板匹配算法的优缺点，从而提出了一种优化和改进的块匹配运动估计算法，该算法经过仿真试验，使其能够在保证图像质量的同时，搜索速度得到较大的提高。1.2运动估计的研究现状运动估计算法通常分为两大类:一类是象素递归算法PRA(Pixel Recursive Algorithm);另一类是块匹配算法BMA(Block Matching Algorithm)。PRA是基于递归思想，如果连续帧中象素数据的变化是因为物体的移位引起的，算法就会沿着梯度方向对某个象素周围的若干象素做迭代运算，使连续的运算最后收敛于一个固定的运动估计矢量，从而预测该象素的位移;而BMA则是基于当前帧中一定大小的块，在当前帧的前后帧的一定区域内搜索该象素块的最佳匹配块，作为它的预测块。尽管PRA对比较复杂的运动形式来说，其预测精度要高于BMA，但是由于其计算量比BMA大的多，同时BMA本身也拥有较好的性能，因此目前的视频压缩编码国际标准普遍都采用BMA。在基于块匹配的运动估计中，最直接的是全搜索算法(Full Search，FS)，它能够得到全局最优的运动矢量，但该算法的运算量也相当巨大，成为了编码器实时应用的瓶颈。为了提高运动估计的运算速度，人们不断提出针对块匹配运动估计的改进快速算法，该算法的经典代表有三步法【1】(Three Step Search，TSS)、2维对数法【2】(2-Dimension Logarithm，2D-LOG)、交叉搜索法【3】(Cross Search Algorithm，CSA)、新三步法【4】(New Three Step Search，NTSS)、四步法【5】(Four Step Search，FSS)、菱形法【6】(Diamond search，DS)、十字菱形搜索【7】(Cross Diamond search，CDS)、六边形搜索法【8】(Hexagon-Based search，HEXBS)等。1.3 本文的主要工作及内容安排本论文的主要工作就是在基于块匹配的视频图像运动估计技术研究的基础上，深入分析、全面总结现有的经典块匹配运动估计算法。在此基础上，提出一种优化和改进后的块匹配运动估计算法，同时对新算法的性能与经典算法作对比实验以证明其效果。本论文章节安排如下：第一章 运动估计的研究背景和现状。通过查阅大量的相关文献，介绍了课题的背景与研究的重要意义。简要介绍了现今运动估计的研究现状，并叙述了本课题在整个大的项目中的作用和意义。第二章 块匹配运动估计原理及技术指标。介绍了运动估计的概念以及块匹配运动估计的原理，并叙述了块匹配运动估计的几项技术指标。第三章 典型块匹配运动估计算法分析。详细阐述了各经典块匹配运动估计算法的基本思想、流程，并都举例说明了各算法的搜索过程，分析了各算法的优缺点。第四章 改进的块匹配快速运动估计算法。介绍了本文提出的一种改进的自适应运动估计算法准十字菱形搜索算法。第五章 进行系统仿真实验，来论证论文中改进的算法，通过对实验结果中的数据列表分析、比较，发现改进后的算法均优于经典的块匹配运动估计算法，实现了预期的研究目标。 第二章 块匹配运动估计原理及其技术指标由于视频序列图像在时间上具有较强的相关性，运动估计(ME)及运动补偿(MC)技术可以有效的减少时间相关性，因此该技术被广泛应用于各种视频压缩编码方案中。运动估计用来估计物体的位移，得到运动矢量;运动补偿根据得到的运动矢量，对前一帧中由于运动而产生的位移进行调整，从而得到尽可能接近本帧的预测帧。由此可见，运动估计算法越完善，估计出的运动矢量越准确，运动补偿的性能就越好，从而使预测误差越小，编码后需要传输的信息量也将随之大大减少，整个系统的码率压缩比就会得到很大的提高，因此运动估计和补偿技术己经成为视频序列图像编码系统中减少时间冗余、提高压缩比的重要技术。H.26x和MPEG-1，MPEG-2，MPEG-4等标准采用的都是基于块匹配运动估计与运动补偿的帧间压缩方案，其压缩比和基于帧内压缩的标准(如JPEG)相比有较大的提高。典型的视频压缩编解码系统如图2-1所示，运动估计算法实现帧间编解码的基本过程是这样的:在编码端，如图2-1(a)所示当前帧与帧存器里的参考帧先进行运动估计，得到当前帧的运动矢量，运动矢量与参考帧又补偿出当前帧的预测帧，预测帧与当前帧相减得到预测误差，然后对预测误差进行DCT变换和量化，最后，把运动矢量和量化后的DCT信息一起进行变长编码，同时，量化后的DCT信息又经过反量化、IDCT变换得到预测误差，预测误差与先前的预测帧相加得到当前帧，存入帧存器作为下一帧的参考帧。在解码端，如图2-1（b）所示，压缩码流经过变长解码分成两部分:运动矢量和预测误差的逆信息，然后将预测误差的逆信息经过反量化、IDCT变换得到预测误差，将运动矢量与帧存器里的前一帧进行运动补偿得到预测帧，再将预测帧与预测误差相加就得到了当前帧的重构图像，同时保存到帧存器里作为下一帧的参考帧。在视频压缩编码中，即使采用快速算法，运动估计仍是最费时的环节，如在H.261的编码过程中，在采用著名的三步快速搜索法的情况下，运动估计仍要占用整个编码过程的63%的计算量;而在H.263编码器中，运动估计占用了42%的计算量。因此，运动估计是视频压缩的瓶颈。基于上述原因，高效快速的运动估计算法一直是视频压缩领域的研究热点。尤其是从1997年10月召开的MPEG会议上开始征集运动估计快速算法以来，在视频编码中的运动估计算法的研究领域中竞争日益激烈。 （a）编码器 （b）解码器 图2-1 典型的视频压缩编解码框图2.1运动估计运动估计使用于帧间编码方式时，通过参考帧图像产生对被压缩图像的估计运动估计是以宏块为单位进行，计算被压缩图像与参考图像的对应位置上的宏块间的位置偏移。这种位置偏移是以运动矢量来描述的，一个运动矢量代表水平和垂直两个方向上的位移。运动估计的主要过程如图2-2所示。运动估计及补偿的基本原理就是利用帧间运动估计得到待编码块的一个参考块，然后用这个参考块进行运动补偿，将补偿后的残差进行行DCT变换和可变长编码。这样运动补偿方法是基于局部运动估计的，它对图像中的宏块进行操作，在参考帧图像的搜索范围内，搜索与当前帧最接近的宏块，从而得到这个宏块的运动矢量 。运动矢量是一个包括水平和垂直分量的二维矢量，编码过程只对这个运动矢量和当前宏块与在参考帧中搜索到的宏块的插值进行编码。运动估计越准确，那么所要编码的残差图像就越小运动补偿编码所需的位数就越少。另外，由于运动估计的搜索过程通常采用全搜索方法，它占用了编码过程中程序运行的大部分时间，所以为了提高搜索速度和效率，搜索策略也很重要。目前研究最多的快速搜索算法，有三步法、四步法、新三步法、菱形法等。 图2-2 宏块、搜索区域与运动矢量的关系2.2 二维运动场模式活动图像(视频)编码主要研究由物体和摄像机的相对运动而形成的二维运动。假定运动物体在帧间做平移运动，相对应的运动模型可以表示为:， (2-1) 当运动物体在帧间有旋转、形状和大小等变化时，采用上式所表示的运动模型来做运动估计，会产生很大的估计误差。为了解决这个问题，有人提出了如下12个参数的运动模型: （2-2） （2-3）这种运动模型虽然能有效地估计运动物体的平移、旋转和缩放等不同的运动变化，但需要进行很复杂的参数估计，因此并不实用。上述模型都是基于运动物体的，然而在视频编码过程中把图像分割成有不同运动的物体非常困难。通常采用两种比较简单的方法，一种方法是把图像分成若干矩形块，假定块做平移运动，对块的运动进行匹配估计;另一种方法是对每个像素的位移进行递归估计。通常像素递归估计的精度高，对多运动画面的适应性强，但它的计算量大，跟踪范围小，实现复杂。块匹配运动估计虽然精度低，但它的位移跟踪能力强，容易实现，因而得到了广泛的应用，并被H.26X和MPEG标准采用。因此，本文主要研究基于块匹配的运动估计技术。2.3块匹配运动估计的基本原理运动估计可以看作是对相邻图像帧时域相关性的检测，通过对相邻图像帧之间相似部分的搜寻来获得图像中景物对象的运动信息。运动估计和补偿的基本过程是通过一定的方法在参考帧图像中搜索当前帧图像的运动信息，再根据这些运动信息在参考图像上进行相应的运动补偿操作，得到一个当前帧的重构图像。由于运动估计时得到了当前图像与参考图像的相关信息，这个重构图像与当前图像的差值往往比直接用参考图像和当前图像作差而得到的比特数要少得多，因此，运动估计与补偿技术能有效减少相邻帧之间的数据冗余，从而获得更高的压缩比，降低视频压缩编码后的码率。运动估计的一个基本问题是如何选择运动信息的表示方式，这又与运动估计的算法模型密切相关。最直接的方法是对于每一个当前帧的像素都采用一个二维矢量(由于我们这里讨论的都是针对二维图像的运动估计，因此每个被估计的图像单元的运动信息都可以表示为一个由水平方向分量和垂直方向分量构成的二维矢量)来表示其运动信息，即我们通常所称的运动矢量。这种方法具有普遍的适用性，但是由于视频图像通常具有非常多的像素，这样对每一个像素都进行运动估计是不现实的，同时这样得到的运动矢量场的数据量太大而使得总的编码比特反而不能减少。因此，在实际中，我们一般将图像帧分割为许多互不重叠的宏块，并假定宏块中的所有像素做相同的平动，这样就可以分别对每个宏块独立地估计其运动信息参数即运动矢量，这就是目前在各种主流的视频压缩标准(如MPEG-4、H.264等)中被广泛应用的基于块匹配的运动估计方法。这种方法在运动估计精度与计算复杂度之间提供了一个较好的折衷，其基本原理如图 3所示。在对某一帧图像进行运动估计时，首先将其按照一定的方式划分成互不重叠的若干个宏块，设宏块的大小为MN(H.263、MPEG-2和MPEG-4建议采用M=N=16，而H.264则可采用几种不同大小的宏块模式进行估计)，然后再对每帧中的宏块依次进行运动估计，获得各自的运动矢量。在基于块匹配运动估计和补偿的视频压缩编码系统中，宏块是进行DCT变换、量化、运动估计、运动补偿及图像重建等操作的基本单元，即在运动预测编解码过程中均以宏块作为操作的单位。 图2-3 块匹配运动估计原理示意图为了便于说明块匹配算法的基本原理，设当前帧中的某目标宏块左上角像素点的坐标为:s=(x，y)。需要说明的是，由于假设宏块中的所有像素都作相同的平移运动，因此宏块中的任意一点都可以标明其位置。然后，在参考帧中，以待估计宏块的位置坐标S为中心，在水平方向分别向左和向右扩展一定长度的搜索距离dx，而在垂直方向分别向上和向下扩展dy，则可得到一个大小为(2dx+l)(2dy+l)的搜索窗W。搜索窗中的每一个点都对应着一个候选匹配宏块，设某个候选宏块的左上角像素点的坐标为S,=(x，y,)，则该候选宏块相对于目标宏块的偏移量mv就是该搜索点对应的运动矢量，即:(2-4)块匹配运动估计的目的是在搜索窗中搜寻与目标宏块最为匹配的候选宏块，并获得相应的运动矢量。其中，搜索窗的大小由视频中景物对象的运动速度决定。对象的运动速度越块，搜索窗也应越大，即dx和dy的取值需加大，以覆盖更大的运动范围，从而获得更高的预测精度。不过，较大的搜索窗通常会使得搜索点增多，从而加大计算量，因此，搜索距离的设定需综合考虑具体视频的运动特性、运动估计的质量以及算法的计算量等因素，以获得最佳的估计性能。2.4块匹配运动估计的技术指标块匹配运动估计可以从以下三个方面进行研究:块的模式选择、块匹配准则、算法评定指标以及搜索起点预测。2.4.1块的模式选择块匹配方法隐含着如下假设:同一块内的像素的运动是一致的。显然这个假设具有一定的片面性，但选择合适的块形状与大小可在一定的程度上消除这种片面性。一般来说，块形状选用正方形是比较自然的选择，这样既便于图像的划分，又有利于块匹配准则函数的计算。但这并不是最佳选择，因此有的算法采用了其他形状，如文献【14】采用了三角形块，文献【15】针对视频对象的边缘形状特征，将宏块按照不同形状的模块进行分割。关于块的大小，显然块越小，得到的残差块越小，但这会导致块内进入较多的运动矢量，可能降低编码的效率。作为折衷，通常选择1616的宏块作为单位，但它由于块尺寸相对较大，可能包含图像中的不同的运动部分，造成预测精度的下降:在H.263和MPEG-4标准中则在宏块运动矢量的基础上加入88块的运动矢量，预测精度得到了一定的提高。2.4.2常见的块匹配准则块匹配准则是判断块相似程度的依据，因此匹配准则的好坏直接影响了运动估计的精度;另一方面，匹配运算复杂度、数据读取复杂度在很大程度上取决于搜索采用的块匹配准则。因此，提高运动估计算法的速度可以有两种途径:一种是减少搜索匹配的点数，另外一种是降低块匹配准则来减少复杂度。视频压缩的一些国际标准，如H.261，H.263，MPEG-l，MPEG-2，MPEG-4中，并没有对视频编码器中的匹配函数给出统一的规定，估计精度高、运算复杂度低的匹配准则函数仍然是视频编码中的研究热点。目前常用的匹配准则有绝对平均误差(MAD)、求和绝对误差(SAD)、归一化互相关函数(NCFF)、最小均方误差函数(MSE)、最大误差最小函数(MME)、最大匹配像素数(MPC)等。（1）求和绝对误差(Sum of Absolute Difference.SAD)的表达式： -wi,jw （2-5）（2）最小均方误差MSE的表达式：-wi,jw （2-6）MSE值最小的点位最佳匹配点。实验表明【24】，MSE 匹配函数运动估计的精度最高，但其众多的乘方运算在VLSI 实现中比较困难；MAD 匹配函数略差，但其相对简单的运算易于在 VLSI中实现；MME 匹配函数则过于简单，没有充分利用匹配块所包含的特征信息，使运动估计的精度大大降低。相对而言，MAD 准则函数比较实用，一度得到广泛运用。而 SAD 准则出现以后，迅速取代 MAD 被各种运动估计算法采用，因为它与MAD 的匹配效果等价，而计算量却大大降低。这是因为，对采用相同形状大小的块来说，MN 都是相同的，除以它已没有必要；另一方面，在计算 SAD 的过程中，当发现块的部分 SAD 己经大于当前最小 SAD 时，可以中途退出，从而使计算量大大减少。2.4.3算法评定指标通过观察匹配的效果和搜索的时间复杂度可以评判一个运动估计算法的好坏，具体说来，匹配效果可通过人眼主观和一些客观的指标来评价重构图像的质量。人眼对图像质量的评价是许多因素的一个交互过程，包括人类视觉系统(HVS)，眼睛和大脑系统等。人类视觉感知受空间保真度和时间保真度的影响，同时还受到其它因素的影响，如观察环境、观察者的精神状态等。这些都具有较大的随意性，不易进行准确的和定量的比较【17】【18】鉴于以上视频效果主观判断的局限性，视频压缩和视频处理的开发者越来越倾向于客观的判断，应用最广泛的就是峰值信噪比PSNR(Peak Signal to Noise Ratio)和平均MSE,MSE在前面已经有介绍，PSNR的计算公式如下: （2-7）PSNR的计算非常简单和快捷，因此成为一种应用广泛的客观图像质量评定方法。通常地，PSNR值高表示图像具有比较高的质量，PSNR值低则表示图像具有比较低的质量。因此从PSNR值可以很好的反应图像的质量。时间复杂度可通过搜索点数和搜索时间进行比较。由于搜索时间受到运行平台及其它诸多因素的影响，目前最常见的还是比较搜索点数，即搜索过程中进行匹配比较的次数。第三章 典型块匹配运动估计算法分析目前最简单的块匹配运动估计算法是全搜索法(FS)，它穷尽参考帧搜索窗内所有可能的点进行搜索，确实能找到BDM最小的匹配块。因此，一般来说，FS的预测精度最高。但是FS的运算占到整个编码运算量的70%-90%，巨大的时间开销使得其在实时编码的情况下难以使用，因此如何快速有效的进行运动估计就成了视频编码的主要问题，于是出现了各种类型的快速算法。本章我们将对一些典型的运动估计算法进行介绍，分析各自的优缺点，并进行仿真实验，分析它们的性能。3.1全搜索法(1) 算法思想：全搜索算法(Full search Method，FS)，也称为穷尽搜索法，是一种搜索策略最简单的搜索算法。它对MN搜索范围内所有可能的候选位置计算SAD(i，j)值，从中找出最小SAD，其对应偏移量即为所求运动矢量。此算法虽计算量大，但最简单、可靠，找到的必为全局最优点。（2）算法描述：FS算法的描述如下：从原点出发，按顺时针方向由近及远，在逐个像素处计算SAD值，直到遍历搜索范围内所有的点。在所有的SAD中找到最小块误差MBD(Minimum Block Distortion)点(SAD值最小的点)，该点所在位置即对应最佳运动矢量。图3-1为全搜索法的示意图。它在整个搜索窗范围内按螺旋搜索方式逐点搜索计算各位置的SAD值，从中找出具有最小匹配差值的块即为最佳匹配块。 图 3-1 全搜索法搜索过程（3）FS 算法分析FS 算法是最简单、最原始的块匹配算法，由于可靠，且能够得到全局最优的结果，通常是其它算法性能比较的标准，但它的计算量的确很大，这就限制了在需要实时压缩场合的应用，所以有必要进一步研究其它的快速算法。3.2 三步搜索法三步搜索算法(TSS, Three Step Search)是由TKOGA等人提出的，它是一种由粗到精的搜索算法，快速而且高效。它通过三步搜索，逐步减小搜索步长。每次搜索都是以上一步的搜索结果为中心，进行周围步长为33像素搜索。由于简单、健壮，性能良好等特点，为人们所重视。若最大搜索长度为7，搜索精度取一个象素，则步长为4、2、1，共需三步即可满足要求，因此而得名三步法。(1)基本思想：TSS算法的基本思想是采用一种由粗到细的搜索模式，从原点开始，按一定步长取周围8个点构成每次搜索的点群，然后进行匹配计算，跟踪最小块误差 MBD点。(2)算法描述：TSS算法描述如下:第一步:从原点开始，选取最大搜索长度的一半为步长，在周围距离步长的 8个点处进行块匹配计算并比较。第二步:将步长减半，中心点移到上一步的MBD点，重新在周围距离步长的8个点处进行块匹配计算并比较。第三步:在中心及周围8个点处找到MBD点，若步长为1，该点所在位置即对应最佳运动矢量，算法结束;否则重复第二步。（3）TSS算法的搜索过程如图3-2所示 图 3-2 TSS算法搜索过程(4)算法分析。TSS算法搜索时，整个过程采用了统一的搜索模板 (Search Pattern)，使得第一步的步长过大，容易引起误导，从而对小运动效率较低。最大搜索点数为1+8W2当搜索范围大于7时，仅用3步是不够的，搜索步数的一般表达式为2(1+dmax)。总体说来，三步法是一种较典型的快速搜索算法，后来又相继有许多改进的新三步法出现，改进了它对小运动的估计性能。3.3新三步搜索算法Renxiang Li和Bing Zeng等在三步算法的基础上做了一些改进得到了新三步搜索(New Three-Step search，NTSS)算法。NTSS算法在视频序列的中心偏置特性上做了改进，从而获得比三步算法更好的性能。(1)算法的基本思想：NTSS利用运动矢量的中心偏置分布，采用具有中心倾向的搜索点模式，并应用中止判别技术，减少搜索次数。(2)算法描述第一步:对搜索窗口中心99的矩形框和33的矩形框的17个点进行匹配运算。如果MBD点为搜索窗中心，算法结束;如果MBD点在中心点的8个相邻点，则进行第二步，否则进行第三步。第二步: 以上一步MBD点为中心，使用33搜索窗进行搜索，若MBD点在搜索窗中心，则算法结束;否则重复第二步。第三步: 执行TSS算法的第二步和第三步，算法结束。(3)模板及搜索过程图示 图 3-3 NTSS算法搜索过程4)NTSS算法分析由于运动矢量通常总是高度集中分布在搜索窗的中心位置附近，因此NTSS采用基于中心偏置的搜索模式不仅提高了匹配速度，也减少了陷入局部最优的可能性;而采用中止判别技术则大大降低了搜索复杂度，提高了搜索效率。3.4四步搜索法四步搜索算法(Four Step Search，FSS)是1996年由Lai-Main Po和Wing-Chung Ma提出的，该算法类似于三步法，但它基于现实中序列图像的一个特征，即运动矢量都是中心分布的，从而在55大小的搜索窗口上构造了有 9个检查点的搜索模板。(l)算法的基本思想TSS算法第一步用了99的搜索窗，这很容易造成搜索方向的偏离，FSS算法首先用55的搜索窗口，每一步将搜索窗的中心移向MBD点处，且后两步搜索窗的大小依赖于MBD点的位置。(2)算法描述FSS算法流程如下:第一步: :以搜索区域原点为中心选定55的搜索窗，然后在9个检测点处进行匹配计算，若MBD点位于中心点，则跳到第四步；否则进行第二步。第二步: 窗口保持为55，但搜索模式取决于上一步的MBD点位置:上一步MBD点位于窗的四个角上，则另外再搜索5个检测点;上一步MBD点位于窗的四边中心处，则只需再搜索3个检测点。若这一次MBD点再窗口中心，则跳到第四步；否则进行第三步。第三步:与第二步的搜索过程相同，只是做完搜索后直接转到第四步。第四步:对33搜索矩形框的九个点做匹配运算，得出的最佳匹配位置就是最终的匹配位置。(3)模板及搜索过程图示图3-4 FSS算法搜索过程图3-4 给出FSS算法一种可能的搜索过程。3.5菱形搜索法菱形搜索法(DS，Diamond Search)是目前快速算法中性能最优异的算法之一，该算法最早由Shan Zhu和Kai-Kuang Ma 两人提出，后又经过多次改进，已成为目前快速块匹配算法中性能最优异的算法之一。1999年10 月，菱形法 (DS )被MPEG-4国际标准采纳并收入验证模型 (VM)。 图3-5 菱形法中运动矢量的中心偏置分布规律(l)算法的基本思想在块匹配算法中，搜索模板的形状和大小不但影响整个算法的运行速度，而且也影响算法的搜索质量。由于实际视频中的误差函数曲面通常不是单调的，所以搜索窗口太小，就容易陷入局部最优，例如BBGDS22，其搜索窗口仅为33;而搜索窗口太大，又容易产生错误的搜索路径，例如TSS的第一步。另外，根据运动矢量的中心偏置分布特性，在进行运动估计时，最佳运动矢量通常在零矢量周围，如图3-5所示。DS算法使用两种搜索模式，如图3-6 所示，第一个称为大菱形搜索模式(LDSP)，由九个检测点组成，围绕中心点的八个点形成一个大菱形形状。第二个称为小菱形搜索模式(SDSP)，由五个检测点形成小菱形的形状。 (a)LDSP (b)SDSP 图3-6 菱形法的两种搜索模版菱形法先使用大模板进行搜索，当其MBD点出现在中心点处时，认为找到了最优匹配点所在的区域，然后再用小模板进行更为精细的定位，最后这个小模板5个点中的MBD点即为最终获得的运动矢量。(2)算法描述第一步:初始化大菱形LDSP以搜索窗口的原点(O，0)为中心，测试LDSP的九个检测点。如果计算得到的MBD点位于中心位置，则转到第三步;否则，转到第二步。第二步:以上一次找到的MBD点作为中心建构新的LDSP并计算其8个搜索点的匹配误差，找到新模板的MBD点。若它位于模板中心，则转到第三步;否则重复第二步。第三步:以上一次得到的MBD点作为中心建构小模板SDSP，在其5个搜索点处进行匹配计算和比较，找出MBD点，该点所在位置即对应最终得到的运动矢量。(3)模板及搜索过程图示图12给出DS算法一种可能的搜索过程。图中（-2，O)、(-3，l)、(-4，2)、（-4，2)分别是第一、二、三、四次LDSP搜索的MBD点，然后按SDSP模式搜索（-4，2)周围的四个点，即可得到最后一步的MBD点，从而得到运动矢量。图中黑色的点代表已搜索点，白色的点代表待搜索点。 图 12 DS算法搜索过程(4)DS算法分析DS算法的特点在于它分析了视频图像中运动矢量的基本规律，选用了大小两种形状的搜索模板 LDSP和SDSP。先用 LDSP搜索，由于步长大，搜索范围广，可以进行粗定位，似搜索过程不会陷于局部最小;当粗定位结束后，可以认为最优点就在LDSP周围8个点所围的菱形区域中，这时再用SDSP来确定定位，使搜索不至于有大的起伏，所以它的性能优于其他算法。另外，DS搜索时各步骤之间有很强的相关性，模板移动时只需在几个新的检测点处进行匹配计算，所以也提高了搜索速度。3.6 六边形搜索法