本科毕业设计(论文) 视频压缩中基于快匹配算法的运动补偿预测1

《本科毕业设计(论文) 视频压缩中基于快匹配算法的运动补偿预测1》由会员分享，可在线阅读，更多相关《本科毕业设计(论文) 视频压缩中基于快匹配算法的运动补偿预测1（50页珍藏版）》请在装配图网上搜索。

1、西 南 交 通 大 学本科毕业设计（论文）视频压缩中基于快匹配算法的运动补偿预测BLOCK MATCHING ALGORITHM BASED ON THE FORECASTING MOTION COMPENSATION VIDEO COMPRESSION 2011年06月承 诺本人郑重承诺：所呈交的设计（论文）是本人在导师的指导下独立进行设计（研究）所取得的成果，除文中特别加以标注引用的内容外，本文不包含任何其他个人或集体已经发表或撰写的设计（研究）成果。对本设计（研究）做出贡献的个人和集体，均已在文中以明确方式标明。如被发现设计（论文）中存在抄袭、造假等学术不端行为，本人愿承担一切后果。 学

2、生签名： 年 月 日 西南交通大学本科毕业设计(论文) 第I页院 系 计算机与通信工程系 专 业 通信工程 年 级 2007级1班 姓 名 李 波 题 目 视频压缩中基于块匹配算法的运动补偿预测 指导教师评 语 指导教师 (签章)评 阅 人评 语 评 阅 人 (签章)成 绩 答辩委员会主任 (签章) 年 月 日 西南交通大学本科毕业设计(论文) 第IV页毕业设计（论文）任务书班 级 07计通本一班 学生姓名 李波 学 号 20078191 发题日期：2011 年 2 月 28 日 完成日期：2011 年 6 月 24 日题 目 视频压缩中基于块匹配算法的运动补偿预测 1、本论文的目的、意义 运

3、动补偿的基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏块内所有象素的位移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的相对位移即为运动矢量。视频压缩的时候，只需保存运动矢量和残差数据就可以完全恢复出当前块 。高精度的运动补偿预测可以大大提高视频编码的效率，是视频编码中的重要环节。 2、学生应完成的任务 （1）了解运动补偿的目的意义和发展史； （2）掌握MATLAB仿真工具； （3）对基于块匹配算法的运动补偿预测方法进行仿真； （4）要求所编制的软件在答辩时演示； （5）严格按照格式要求完成设计论文的排版打

4、印，字数不少于1.8万字； （6）应完成不少于一万英文字符的翻译及将毕业设计(论文)的中文摘要翻译成英文。 3、论文各部分内容及时间分配：（共 17 周）第一部分熟悉设计题目功能要求 ( 3周) 第二部分掌握MATLAB仿真工具 ( 3周) 第三部分对运动补偿的三步搜索方法进行仿真 ( 5周) 第四部分完成外文摘要翻译外文资料 ( 2周) 第五部分毕业设计文本打印装订善后 ( 2周) 评阅及答辩 ( 1周) 论文整理 ( 1周)备 注 答辩前应向指导老师交毕业设计（论文）说明书（书面文档应不少于1万8千个汉字）和电子文档（含毕业设计（论文）说明书及应用软件）。 指导教师： 年 月 日审 批 人

5、： 年 月 日摘要多媒体技术在人们的生活中应用得越来越广泛，随着互联网的快速发展，多媒体通信更是成为人们必不可少的需求。多媒体技术的飞速发展，使得许多应用领域对视频图像的实时压缩提出了更高的要求，快速、高效的压缩算法是解决这一问题的关键。影响视频压缩编码质量和效率的因素很多，运动估计是其中最有影响力的因素之一。运动估计得越准确，视频压缩编码的效率就越高，解码出来的视频图像质量越好;而且，运动估计在整个视频压缩编码系统中的计算复杂度最大。因此，快速、高效的运动估计算法是视频压缩编码技术的研究重点。采用运动估计和运动补偿技术可以消除视频信号的时间冗余，从而提高编码效率。研究设计高效、快速、鲁棒的运

6、动估计算法成为目前视频压缩技术中研究的重要课题。在各种运动估计方法中，块匹配法由于其原理简单、便于实现等优点得到了普遍应用，被许多视频编码标准（如MPEG以及TH.26X）所采用，在理论研究和实践应用中，得到了不断的发展和完善，成为数字视频技术的一个研究热点。其相关快速算法也得到了广泛的研究和发展。本论文中，主要的任务是分析和研究几种经典的运动估计算法，并对它们进行相关比较。本文首先介绍了课题的研究背景与意义以及视频压缩技术，然后阐述了基于块匹配的运动估计的基本原理，最后详细介绍了全搜索法和几种典型的块匹配运动估计快速算法，分析了它们各自的技术特点，通过实验数据定量地评价了各算法的优缺点。文章

7、最后对本文工作进行了总结，并对未来的研究方向进行了展望。关键词: 运动估计;块匹配;三步搜索法 西南交通大学本科毕业设计(论文) 第40页AbstractWith the rapid development of the Internet, multimedia technology is used more and more widely in our daily life, and multimedia communication has become a necessity. With the rapid development of multimedia technology , wh

8、ich puts forward higher request to real-time compression of video image in application fields, rapid and high efficient compression algorithm is the key to solve this problem.There are many factors which affect the quality and efficiency of video compression coding, and motion estimation is one of t

9、he most influential factors. The more precise of motion estimation and the higher efficiency of video compression coding, the better quality of the decoding video image; Furthermore，in the whole video compression coding system, calculative complexity of motion estimation is the largest. Therefore, r

10、apid and high efficient motion estimation algorithm is the point of research of video compression coding technology. The motion estimation and motion compensation technology can eliminate time redundancy of the video signal, so as to improve the coding efficiency. Studying and designing the efficien

11、t, fast and robust motion estimation algorithm has been the important issue of study for the present video compression techniques. In all kinds of motion estimation methods, motion estimation is used widely because of its advantages such as simple principle, easy to realize ,and is adopted by many v

12、ideo coding standard, such as the MPEG and TH. 26 X. And in the theoretical research and practical application, it has become a hot research topic in the field of digital video technology getting continuous development and improvement. The fast relevant algorithm also gets extensive research and dev

13、elopment.In this paper, the main task is to analyze and study several classical motion estimation algorithms and make a comparison among them. This paper introduces the research background and significance of the topic and video compression technology at first, then expounds the principle of the mot

14、ion estimation based on block matching . Finally, introduces the full search method and several typical kinds of fast algorithm of block matching motion estimation, analyses their technical characteristics, and evaluates their advantages and disadvantages of the algorithm quantitatively according to

15、 experimental data .At the end of this paper, we summarize the whole work and prospect the research direction in the future.Keywords: motion estimation; Block matching; Three-step search method目 录第1章 绪论11.1 引言11.1.1 课题的背景与意义11.1.2 视频压缩技术介绍31.2 运动估计的研究现状71.3 本文主要内容和工作安排7第2章 运动估计概述及其技术指标92.1 运动估计102.2

16、 块匹配运动估计的基本原理122.3 块匹配的运动估计的参数和指标142.3.1 分块大小142.3.2 匹配准则142.3.3 搜索范围的确定152.3.4 估计精度162.4 算法评定指标16第3章 典型块匹配运动估计算法分析183.1全搜索法（FS）183.2 快速匹配算法193.2.1 三步搜索法（FSS）193.2.2 新三步搜索法（NTSS）213.2.3 四步搜索法（FSS）243.2.4 钻石搜索法（DS）253.2.5 六边形搜索法（HEXBS）273.3 运动估计算法仿真303.3.1 实验平台303.3.2 三步搜索法仿真示例313.3.3 实验结果333.3.4 实验结

17、果分析353.4 本章小结35结束语374.1 本文工作总结374.2 研究展望37致谢39参考文献40第1章 绪论1.1 引言1.1.1 课题的背景与意义随着信息技术的发展和社会的不断进步，人类对信息的需求越来越丰富，人们希望无论何时何地都能够方便、快捷、灵活的通过语音、数据、图像与视频等多种方式进行通信。视觉信息给人们直观、生动的形象，图像/视频的传输更受到广泛的关注。数字信号处理技术、物理媒体与网络技术、超大规模集成电路技术突飞猛进的发展，使得多媒体通信成为研究和应用的热点。其中，最为关键的技术是数字视频的处理和传输技术，它将电视技术、计算机技术和通信技术结合在一起，在电视系统、计算机网

18、络和通信产业中得到了广泛的应用，己经进入千家万户的日常生活中。数字视频硬件方面的进步和有关数字视频压缩国际标准的推出，使得数字视频技术领域趋于成熟。自20世纪90年代以来，国际电联ITU和国际标准化组织ISO先后颁布了一系列视频编码和多媒体视频通信的建议和国际标准。如ISO/IEC成立了JPEG (Joint Photographic Expert Group)和MPEG(Moving Pieture Experts Group)并先后完成了JPEG、JPEG2000、MPEG-l、MPEG-2和MPEG-4标准的制定;ITU-T也先后制定了H.261、H.262(与MPEG组织合作)、H.2

19、63/H.263+和H.264(与MPEG组织合作)等一系列国际数字视频压缩编码标准。它们为视频编码技术的发展起到了巨大的推动作用。在传统的图像通信领域，例如基于ISDN、PSTN以及DDN的会议电视和可视电话等视频通信业务取得巨大成功的同时，新的多媒体通信方式也不断出现，尤其是Internet和数字移动通信的迅速普及，利用IP网络以及宽带无线网络进行图像和视频信息的传输成为倍受人们重视的新方式。但是大量频繁的图像、视频信息的交流与存贮活动也带来了许多新要求和新问题，例如视频图像巨大的信息量与当前有限的信道带宽和传输效率已成为制约多媒体技术发展的一个重要瓶颈，因此人们在努力增加信道带宽和提高信

20、道传输效率的同时，对视频图像采取高效的压缩编码己成为目前的研究热点。例如，1幅640x450分辨率的彩色图像(24比特/像素)，其数据量约为0.92MB，如果以每秒30帧的速度播放，则视频信号的传输速率高达27.6Mbps，如果存放在容量为650MB的光盘中，在不考虑音频信号的情况下，每张光盘也只能播放24秒。由此可见，数字视频信息的数据量是非常巨大的，若不经过压缩，数字图像传输所需要的高传输速率和数字图像存储所需要的巨大容量将成为推广应用数字视频技术的最大障碍。要解决多媒体信息存储容量大、数据传输率高的难题，就需要采用压缩技术。研究发现，图像数据表示中存在大量的冗余。通过去除那些冗余数据可以

21、使原始图像数据极大的减少，从而解决图像数据量巨大的问题。对于静态图像，最主要的数据冗余是空间冗余。图像帧记录了可见景物的颜色，而同一景物各采样点的颜色之间存在着空间连贯性，但基于离散像素采样来表示物体颜色的方法通常没有利用景物表示颜色的这种空间连贯性，因此产生了空间冗余。序列图像帧内存在空间冗余，而帧间则存在着很大的时间冗余。这是由于序列图像一般是位于同一时间轴区间内的一组连续画面，其相邻帧间变化量一般很小，只是表现为移动物体所在的空间位置略微不同。运动估计和运动补偿技术就是解决图像帧间时间冗余的很好的方法。运动估计与运动补偿是现阶段视频压缩编码的关键技术。它是一种实现帧间编码的方法，利用前后

22、两帧或若干帧之间的时间相关性，去除时间冗余度。帧间编码之所以能减少冗余度，是因为在一般视频序列的两帧之间有很大的空间结构相似性，前后两帧的差帧可以用比帧内编码所需少很多的比特数来进行编码。而帧间预测的方法基本上是以基于块匹配的运动估计(补偿)算法为主。运动估计目前面临的主要问题就是如何比较快速的得到比较准确的运动矢量，因为在整个视频编码的过程中，即使采用快速算法，运动估计仍然是耗时最长、资源占用最高的环节，如在H.261的编码过程中，在采用著名的三步快速搜索法的情况下，运动估计仍要占用整个编码过程的63%的计算量;而在H.263编码器中，运动估计也还占用了42%的计算量。因此，运动估计成了视频

23、压缩编码的瓶颈，特别是对于帧幅较大、帧频较高的视频对象，在编码实时性和硬件实现方面，运动估计还有很多潜力可挖。基于上述原因，高效快速的运动估计算法一直是视频压缩编码领域的研究热点。从全搜索到三步搜索法、菱形搜索、以及六边形搜索法等，提高了基于块匹配的运动估计算法的性能，使实时应用成为了可能，但是由于实际需求越来越高，所以也要求我们不断的改进运动估计算法以满足现实的需求。基于块匹配的运动估计作为视频编码的关键技术，需要解决的问题是如何提高它的估算速度和精度。而鱼和熊掌不能兼得，这两个指标在实际计算过程中往往无法同时达到最优，如何解决这个折衷问题具有很高的理论和实际意义，是一个图像处理领域和图像通

24、信领域极其重要的研究课题。它的研究和应用必将促进计算机通信、图像通信和多媒体技术的发展。本课题的意义在于，通过实验和仿真，比较了各种算法的优缺点，找出了最优的算法，确保视频压缩的质量。力求在己有算法的基础上寻找一种新的思路，找出了一种优化和改进的块匹配运动估计算法，使其能够在保证图像质量的同时，搜索速度得到较大的提高。1.1.2 视频压缩技术介绍对视频进行压缩，就要了解视频的构成。普通的未压缩视频都是由一帧帧图像序列组成的，一般1秒中包含24帧图像。一般图像的变化都很小，而且变化都是局部的，甚至是静止的，这样就可以从中找到突破。数字视频中的这些情况都可以称为信息的冗余，因此可以通过除去这些冗余

25、数据来减少大量的原始视频的数据量，从而达到数据压缩以解决视频传输中数据不便传输的问题。通常的视频信息中存在以下三种冗余：1空间冗余：这是静态图像存在的最主要的一种数据冗余。研究数据表明，图像帧内的行、列相邻点之间的相关性可以达到90%以上。时间冗余：这是视频里图像序列中最经常包含的冗余。视频序列前后帧之间存在着较大的相关性。同样有研究证明活动图像相邻帧同一位置上前后样值的相关性也达到90%以上。视觉冗余：人类的视觉系统对图像的敏感性是非均匀的和非线性的。人的视觉系统(HVS)对于某些失真并不敏感。然而，在记录的原始图像数据时，通常假设这个系统是均匀的和线性的，对视觉敏感和不敏感的部分同等对待，

26、从而产生了比理想编码更多的数据，这就是视觉冗余。视频信号都是由一系列单独的图像帧组成。每一帧都可以利用图像编解码器(JPEG)进行帧内编码(Intra-frame Coding),每一帧在内部先进行编码而没有考虑到其它的帧。消除视频序列中的时间冗余（连续视频帧中的相似性），可以达到更好的压缩效果。具体可以通过给图像编解码器增加一个“前后帧”来实现，主要有以下的两个功能：(1)预测：从一个或多个先前传输的帧来建立对当前帧的预测；(2)补偿：从当前帧中减去预测帧来产生“残差帧”。接着用图像编解码器来处理这个残差帧。经过这个处理，残差帧将包含很少的数据，因而可以用图像解码器对它进行有效的压缩。为了解

27、码帧，解码器必须进行逆反补偿过程，把预测加到解码的残差帧中，这就是帧间编码(Inter-frame Coding)。视频编码标准的最重要的发展都是源于两大标准组织：ITU(前身是CCITT)和ISO。1986年，ISO和CCITT联合成立了“联合图片专家组（JPEG Joint Photographic Experts Group）”，于1991年3月提交了用于灰度等级和颜色两方面连续变化静止图像编码的JPEG建议草案，于1992年7月通过证实标准。1988年，MPEG(Moving Picture Expert Group)运动图像专家组成立，它致力于运动图像及其伴音编码标准化的工作，包括M

28、PEG系统，即MPEG视频和MPEG音频。原先共有三个版本MPEG-1，MPEG-2，MPEG-3，后来又增加了MPEG-4，MPEG-7等，不同的版本对应了不同的应用场合及相关的视频质量，对多媒体通信的发展起到了巨大的影响。2(1)MPEG-1MPEG-1制定于1993年，是针对1.5Mbps以下数据传输率的数字存储媒质运动图像及其伴音编码的国际标准。MPEG-1用于在CD-ROM上存储同步和彩色运动视频信号，可优化为中等分辨率，并在这个优化模式下，采用标准交换格式(SIF)。它可针对SIF标准分辨率(对于NTSC制为352240；对于PAL制为352288)的图像进行压缩，传输速率为1.5

29、Mbits/sec，每秒播放30帧。MPEG-1对色差分量采用4:1:1的二次采样率。MPEG-1旨在达到VRC质量，其视频压缩率为26:1。(2)MPEG-2MPEG-2制定于1995年，它追求的是CCIR 601建议的图像质量DVB,HDTV和DVD等制定的3Mbps10Mbps的运动图像及其伴音的编码标准。MPEG-2在NTSC制式下的分辨率可达720486,MPEG-2能够提供广播级的视像和CD级的音质。由于MPEG-2在设计时的巧妙处理，使得大多数MPEG-2解码器可播放MPEG-1格式的数据。正因为MPEG-2的出色性能表现，已能适用于HDTV。除了做为DVD的指定标准外，MPEG

30、-2还可用于为广播、有线电视网、电缆网络以及卫星直播提供广播级的数字视频。还可提供一个较广的范围改变压缩比，以适应不同画面质量、存储容量以及带宽的要求。对于最终用户来说，由于现存电视机分辨率的限制，MPEG-2所带来的高清晰度画面质量(如DVD画面)在电视上效果并不明显，反而其音频特性(如加重低音，多伴音声道等)更引人注目。(3)MPEG-3MPEG-3是ISO/IEC最初为HDTV开发的编码压缩标准。但由于MPEG-2的高速发展，MPEG-3的功能已被淘汰，其原来的工作由MPEG-2小组承担。(4)MPEG-4MPEG-4于1998年11月公布，该标准提出了基于对象编码的概念，不仅针对一定比

31、特率下的视频编码、音频编码，更加注重于多媒体系统的交互性和灵活性。MPEG-4标准主要应用于视像电话(Video Phone)，视像电子邮件(Video Email)和电子新闻(Electronic News)等，其传输速率要求较低，在4800-64000bits/sec之间，分辨率为176144。MPEG-4利用很窄的带宽，通过帧重建技术，压缩和传输数据，以最少的数据能取得最佳的图像质量。MPEG-4是第一个让用户由被动变为主动的动态图像标准，从根源上说，MPEG-4将自然物体与人造物体相溶合(视觉效果意义上的)，其试图达到两个目标：低比特率下的多媒体通信及多工业的多媒体通信的综合。据此目标

32、，MPEG-4引入了AV对象(Audio/Visual Objects)，从而使得更多的交互操作成为可能。MPEG-4的应用前景可以说非常广阔。它的出现能推动以下的几个方面：数字电视、动态图像、万维网(WWW)、实时多媒体监控、低比特率下的移动多媒体通信、Internet/Intranet上的视频流与可视游戏、基于面部表情模拟的虚拟会议、DVD上的交互多媒体应用、基于计算机网络的可视化合作实验室场景应用等。MPEG-4技术还在不断的完善和发展当中，新的MPEG-4标准的应用正在促进多媒体压缩技术经历另一次重大变化。这一变化会与1990年MPEG-2压缩标准的推出一样巨大，而且随着视频通信应用的

33、快速发展，MPEG-4标准势会影响到范围广泛的多种应用领域。(5)MPEG-7继MPEG-4之后，要解决的矛盾就是对日渐庞大的图像、声音信息的管理和迅速搜索。针对这个矛盾，MPEG提出了这个解决方案MPEG-7。MPEG-7力求能够快速并且有效地搜索出用户所需的不同类型的多媒体信息。该标准没有规定利用描述进行搜索的工具或任何程序。目前MPEG系列国际标准已经成为影响最大的多媒体技术标准，对数字电视、视听消费电子产品、多媒体通信等产业产生了深远影响。ITU主要精力则集中在支持实时、双向视频通信上。而负责发展这些标准的组织就是众所周知的VCEG(视频编码专家组)，其主要标准有：(1) H.261视

34、频编码标准H.261是ITU-T为在综合业务数字网(ISDN)上开展双向声像业务而制定的，速率为64kb/s的整数倍。H.261只对CIF和QCIF两种图像格式进行处理，每帧图像被分成图像层、宏块组(GOB)层、宏块(MB)层、块(Block)层来处理。H.261是最早的运动图像压缩标准，包括运动补偿的帧间预测、DCT变换、量化、熵编码，以及与固定速率的信道相适配的速率控制等部分。(2) H.263视频压缩标准H.263是ITU-T为低于64kb/s的窄带通信信道而制定的视频编码标准。它的标准输入图像格式可以是S-QCIF、QCIF、CIF、4CIF或者16CIF的彩色420亚取样图像。H.2

35、63与H.261相比采用了半象素的运动补偿，且增加了4种有效的压缩编码模式。先进的预测模式允许一个宏块中4个88亮度块各对应一个运动矢量，提高了预测精度；两个色度块的运动矢量取这4个亮度块运动矢量的平均值。补偿时，88亮度块每个象素的补偿值由3个预测值加权平均而得到。使用这个模式可以产生显著的编码增益，特别是采用重叠的块运动补偿后，能减少块效应，提高主观质量。(3) H.264视频压缩标准H.264是由ISO/IEC与ITU-T组成的联合视频组(JVT)制定的新一代视频压缩编码标准。它的主要优点列出如下：在相同重建图像质量下，H.264比H.263+和MPEG-4(SP)减小50%的码率。既可

36、工作于低时延的模式以满足实时业务，如会议电视；又可工作于无时延限制的场合，如视频存储。在编/解码器中采用复杂度可分级设计，在图像质量和编码处理之间可分级，以适应不同复杂度的场合。相对于早期的视频压缩标准，H.264引入了许多相对先进的技术，包括44的整数变换、空域内的帧内预测、1/4象素精度的运动估计、多参考帧与多种大小块的帧间预测技术等。新技术带来了较高的压缩比，同时大大的提高了算法的复杂度。视频编码通过去除图像的空间与时间相关性来达到数据压缩的目的。空间相关性可以通过有效的变换来去除，如DCT变换、H.264的整数变换；时间相关性则通过帧间预测来去除。这里所说的变换去除空间相关性，仅仅局限

37、在所变换的块内，如88或者44，并没有块与块之间的处理。H.263+与MPEG-4则引入了帧内预测技术，在变换域中根据相邻块对当前块的某些系数做预测。H.264则是在空域中，利用当前块的相邻象素直接对每个系数做预测，有效地去除相邻之间的相关性，极大地提高了帧内编码的效率。1.2 运动估计的研究现状运动估计算法通常分为两大类:一类是象素递归算法PRA(Pixel Recursive Algorithm);另一类是块匹配算法BMA(Block Matching Algorithm)。PRA是基于递归思想，如果连续帧中象素数据的变化是因为物体的移位引起的，算法就会沿着梯度方向对某个象素周围的若干象素

38、做迭代运算，使连续的运算最后收敛于一个固定的运动估计矢量，从而预测该象素的位移;而BMA则是基于当前帧中一定大小的块，在当前帧的前后帧的一定区域内搜索该象素块的最佳匹配块，作为它的预测块。尽管PRA对比较复杂的运动形式来说，其预测精度要高于BMA，但是由于其计算量比BMA大的多，同时BMA本身也拥有较好的性能，因此目前的视频压缩编码国际标准普遍都采用BMA。本文的研究都是针对块匹配的运动估计算法，在后文中，如无特别说明，所提到的运动估计也都是指基于块匹配的运动估计。在基于块匹配的运动估计中，最直接的是全搜索算法(Full Search，FS)，它能够得到全局最优的运动矢量，但该算法的运算量也相

39、当巨大，成为了编码器实时应用的瓶颈。为了提高运动估计的运算速度，人们不断提出针对块匹配运动估计的改进快速算法，其目标是在保证编码质量的同时，尽可能的降低运算复杂度。快速搜索模板这类算法的主要想法是通过在搜索窗口内按照固定的搜索模板和步骤，对较少的几个点进行匹配运算来降低运算复杂度，这类快速模板算法都是基于一个共同的假设，即在搜索窗内有且仅有一个全局匹配误差最小点，而且匹配误差随着当前点与全局最优点之间距离的增大而增大。模板搜索快速算法是提出最早，发展最为成熟，也是应用最为广泛的一类快速算法。它的优点是算法简单，计算量小，加速比较大，缺点是容易陷入局部最优值，尤其在大运动情况下，搜索的准确度难以

40、保证。该类算法的经典代表有三步法3(Three step seareh，TSS)、2维对数法4 (2-Dime nsion Logarithm，2D-LOG)、新三步法5(New Three step seareh，NTSS)、四步法6(Four Step Seareh，FSS)、菱形法7(Diamond Seareh，DS)、六边形搜索法8(Hexagon- Based seareh，HEXBS)等。1.3 本文主要内容和工作安排本论文的主要工作就是在基于块匹配的视频图像运动估计技术研究的基础上，深入分析、全面总结现有的经典块匹配运动估计算法，并通过仿真实验比较他们的性能。在此基础上，力争提

41、出一种优化和改进后的块匹配运动估计算法，使其能够在保证图像质量的同时，搜索速度得到较大的提高。本论文章节安排如下:第1章 绪论。通过查阅大量的相关文献，介绍了课题的背景与研究的重要意义，然后对视频压缩技术也进行了简要介绍，最后介绍了运动估计的研究现状。第2章 运动估计概述及其技术指标。介绍了运动估计的思想，着重分析了块匹配运动估计的原理，对块匹配运动估计的几项重要的技术指标(分块的大小，匹配准则，搜索范围，估计精度)的确定进行了重点讨论。第3章 典型块匹配运动估计算法分析。详细阐述了各种经典块匹配运动估计算法，并从搜索算法在搜索速度、计算量、匹配质量、等方面的性能进行了分析比较。最后通过仿真、

42、实验数据定量地评价了各算法的优缺点。总结与展望。总结了全文的研究成果，并对运动估计算法研究进行了展望，提出了进一步的研究工作。第2章 运动估计概述及其技术指标由于视频序列图像在时间上具有较强的相关性，运动估计(ME)及运动补偿(MC)技术可以有效的减少时间相关性，因此该技术被广泛应用于各种视频压缩编码方案中。运动估计用来估计物体的位移，得到运动矢量;运动补偿根据得到的运动矢量，对前一帧中由于运动而产生的位移进行调整，从而得到尽可能接近本帧的预测帧。由此可见，运动估计算法越完善，估计出的运动矢量越准确，运动补偿的性能就越好，从而使预测误差越小，编码后需要传输的信息量也将随之大大减少，整个系统的码

43、率压缩比就会得到很大的提高，因此运动估计和补偿技术己经成为视频序列图像编码系统中减少时间冗余、提高压缩比的重要技术。H.26x和MPEG-1，MPEG-2，MPEG-4等标准采用的都是基于块匹配运动估计与运动补偿的帧间压缩方案，其压缩比和基于帧内压缩的标准(如JPEG)相比有较大的提高。典型的视频压缩编解码系统如图2-1所示，运动估计算法实现帧间编解码的基本过程是这样的:在编码端，如图2-1(a)所示当前帧与帧存器里的参考帧先进行运动估计，得到当前帧的运动矢量，运动矢量与参考帧又补偿出当前帧的预测帧，预测帧与当前帧相减得到预测误差，然后对预测误差进行DCT变换和量化，最后，把运动矢量和量化后的

44、DCT信息一起进行变长编码，同时，量化后的DCT信息又经过反量化、IDCT变换得到预测误差，预测误差与先前的预测帧相加得到当前帧，存入帧存器作为下一帧的参考帧。(a)编码器（b）解码器图2-1 典型的视频压缩编解码系统在解码端，如图2-1(b)所示，压缩码流经过变长解码分成两部分:运动矢量和预测误差的逆信息，然后将预测误差的逆信息经过反量化、IDCT变换得到预测误差，将运动矢量与帧存器里的前一帧进行运动补偿得到预测帧，再将预测帧与预测误差相加就得到了当前帧的重构图像，同时保存到帧存器里作为下一帧的参考帧。在视频压缩编码中，即使采用快速算法，运动估计仍是最费时的环节，如在H.261的编码过程中，

45、在采用著名的三步快速搜索法的情况下，运动估计仍要占用整个编码过程的63%的计算量;而在H.263编码器中，运动估计占用了42%的计算量。因此，运动估计是视频压缩的瓶颈。基于上述原因，高效快速的运动估计算法一直是视频压缩领域的研究热点。尤其是从1997年10月召开的MPEG会议上开始征集运动估计快速算法以来，在视频编码中的运动估计算法的研究领域中竞争日益激烈。2.1 运动估计对于视频序列图像，由于相邻帧间存在很大的时间相关性，即时间兀余(Temp- oral Redundancy)。所以减少时间冗余，可以大幅度提高视频压缩编码的效率。这方面一种有效的方法就是基于块匹配的运动估计(Motion E

46、stimation，ME)，因为算法简单，便于实现等优点而得到广泛的应用。其基本思想是将图像序列的每一帧分成M*N的宏块，然后对于当前帧中的每一块根据一定的匹配准则在前一帧或后一帧中在给定的搜索范围内找出与当前块最相似的块，即匹配块，根据匹配块与当前块的相对位置计算出运动位移，所得运动位移既为当前块的运动矢量。运动估计的越准确，补偿的残差就越小，编码效率就越高，解码出来的图像质量就越好。运动估计用于帧间编码方式时，通过参考帧图像产生对被压缩图像的估计。运动估计是以宏块为单位进行，计算被压缩图像与参考图像的对应位置上的宏块间的位置偏移。这种位置偏移是以运动矢量来描述的，一个运动矢量代表水平和垂直

47、两个方向上的位移。图2-2 宏块、搜索区域与运动矢量的关系运动估计及补偿的基本原理就是利用帧间运动估计得到待编码块的一个参考块，然后用这个参考块进行运动补偿，将补偿后的残差进行DCT变换和可变长编码。运动估计的主要过程如图2-2所示。这样运动补偿方法是基于局部运动估计的，它对图像中的宏块进行操作，在参考帧图像的搜索范围内，搜索与当前帧最接近的宏块，从而得到这个宏块的运动矢量。运动矢量是一个包括水平和垂直分量的二维矢量，编码过程只对这个运动矢量和当前宏块与在参考帧中搜索到的宏块的差值就行编码。运动估计越准确，那么所要编码的残差图像就越小，运动补偿编码所需要的位数就越少。另外，如果运动估计的搜索采

48、用全搜索法，它占用了编码过程中程序运行的大部分时间，所以为了提高搜索速度和效率，搜索策略也很重要。目前研究最多的快速搜索算法，有三步法、四步法、新三步法、菱形法等，这些算法将在第三章详细介绍。2.2 块匹配运动估计的基本原理运动估计可以看作是对相邻图像帧时域相关性的检测，通过对相邻图像帧之间相似部分的搜寻来获得图像中景物对象的运动信息。运动估计和补偿的基本过程是通过一定的方法在参考帧图像中搜索当前帧图像的运动信息，再根据这些运动信息在参考图像上进行相应的运动补偿操作，得到一个当前帧的重构图像。由于运动估计时得到了当前图像与参考图像的相关信息，这个重构图像与当前图像的差值往往比直接用参考图像和当

49、前图像作差而得到的比特数要少得多，因此，运动估计与补偿技术能有效减少相邻帧之间的数据冗余，从而获得更高的压缩比，降低视频压缩编码后的码率。运动估计的一个基本问题是如何选择运动信息的表示方式，这又与运动估计的算法模型密切相关。最直接的方法是对于每一个当前帧的像素都采用一个二维矢量(由于我们这里讨论的都是针对二维图像的运动估计，因此每个被估计的图像单元的运动信息都可以表示为一个由水平方向分量和垂直方向分量构成的二维矢量)来表示其运动信息，即我们通常所称的运动矢量。这种方法具有普遍的适用性，但是由于视频图像通常具有非常多的像素，这样对每一个像素都进行运动估计是不现实的，同时这样得到的运动矢量场的数据

50、量太大而使得总的编码比特反而不能减少。因此，在实际中，我们一般将图像帧分割为许多互不重叠的宏块，并假定宏块中的所有像素做相同的平动，这样就可以分别对每个宏块独立地估计其运动信息参数即运动矢量，这就是目前在各种主流的视频压缩标准(如MPEG-4、H.264等)中被广泛应用的基于块匹配的运动估计方法。这种方法在运动估计精度与计算复杂度之间提供了一个较好的折衷，其基本原理如图2-3所示。在对某一帧图像进行运动估计时，首先将其按照一定的方式划分成互不重叠的若干个宏块，设宏块的大小为M*N(H.263、MPEG-2和MPEG-4建议采用M=N=16，而H.264则可采用几种不同大小的宏块模式进行估计)，

51、然后再对每帧中的宏块依次进行运动估计，获得各自的运动矢量。在基于块匹配运动估计和补偿的视频压缩编码系统中，宏块是进行DCT变换、量化、运动估计、运动补偿及图像重建等操作的基本单元，即在运动预测编解码过程中均以宏块作为操作的单位。图2-3 块匹配运动估计原理示意图为了便于说明块匹配算法的基本原理，设当前帧中的某目标宏块左上角像素点的坐标为:s=(x，y)。需要说明的是，由于假设宏块中的所有像素都作相同的平移运动，因此宏块中的任意一点都可以标明其位置。然后，在参考帧中，以待估计宏块的位置坐标s为中心，在水平方向分别向左和向右扩展一定长度的搜索距离，而在垂直方向分别向上和向下扩展，则可得到一个大小为

52、的搜索窗砰。搜索窗中的每一个点都对应着一个候选匹配宏块，设某个候选宏块的左上角像素点的坐标为，则该候选宏块相对于目标宏块的偏移量mv就是该搜索点对应的运动矢量，即: (2-1)块匹配运动估计的目的是在搜索窗中搜寻与目标宏块最为匹配的候选宏块，并获得相应的运动矢量。其中，搜索窗的大小由视频中景物对象的运动速度决定。对象的运动速度越块，搜索窗也应越大，即和的取值需加大，以覆盖更大的运动范围，从而获得更高的预测精度。不过，较大的搜索窗通常会使得搜索点增多，从而加大计算量，因此，搜索距离的设定需综合考虑具体视频的运动特性、运动估计的质量以及算法的计算量等因素，以获得最佳的估计性能。2.3 块匹配的运动

53、估计的参数和指标基于块匹配的运动估计算法，在具体实现的时候，需要考虑其中的几个参数：分块大小（M,N取值），匹配准则，搜索范围和估计精度。其中每一个都对匹配的效率产生重要影响，有些则是最关键的。2.3.1 分块大小上面已经提到过一点，块匹配法有个前提，就是同一个块内的像素运动方向是一致的。因此需要选择合适的块大小。块大小大时，块内各像素作平移运动的可能性比较小，不满足我们的前提条件，会影响估计的精度；块大小小时，会受噪声影响，结果不准确，而且还会导致产生许多运动矢量，使得运算量增加，降低了编码的效率。所以块的大小必须选择合适，满足上面的要求。当前的视频压缩标准，如H.26x和MPEG一般以1616大小的块作为一个宏块，这是一个已经证明的较好的平衡结果。而且H.263和MPEG-4在进行1616的宏块运动估计的基础上，还加入了88块的处理，使得预测的精度有了提高。H.264更是最小分块达到了44，进一步使得运动估计的结果精确。2.3.2 匹配准则块匹配准则是判断块相似程度的算法和标准，准则的好坏直接影响了运动估计的结果。而且匹配运算、数据读取复杂度很大程度上决定于所采用的块匹配准则。在块匹配法中，有三种最优匹配准则：(1)最小绝对差MAD(Mean Absolute Difference)、 （2-2）MAD值最小时为最优的匹配点。(2)最小均方误差