《本科毕业设计(论文) 视频压缩中基于快匹配算法的运动补偿预测1.doc》由会员分享，可在线阅读，更多相关《本科毕业设计(论文) 视频压缩中基于快匹配算法的运动补偿预测1.doc（50页珍藏版）》请在三一办公上搜索。
1、西 南 交 通 大 学本科毕业设计（论文）视频压缩中基于快匹配算法的运动补偿预测BLOCK MATCHING ALGORITHM BASED ON THE FORECASTING MOTION COMPENSATION VIDEO COMPRESSION 2011年06月承 诺本人郑重承诺：所呈交的设计（论文）是本人在导师的指导下独立进行设计（研究）所取得的成果，除文中特别加以标注引用的内容外，本文不包含任何其他个人或集体已经发表或撰写的设计（研究）成果。对本设计（研究）做出贡献的个人和集体，均已在文中以明确方式标明。如被发现设计（论文）中存在抄袭、造假等学术不端行为，本人愿承担一切后果。 学
2、生签名： 年 月 日院 系 计算机与通信工程系 专 业 通信工程 年 级 2007级1班 姓 名 李 波 题 目 视频压缩中基于块匹配算法的运动补偿预测 指导教师评 语 指导教师 (签章)评 阅 人评 语 评 阅 人 (签章)成 绩 答辩委员会主任 (签章) 年 月 日 毕业设计（论文）任务书班 级 07计通本一班 学生姓名 李波 学 号 20078191 发题日期：2011 年 2 月 28 日 完成日期：2011 年 6 月 24 日题 目 视频压缩中基于块匹配算法的运动补偿预测 1、本论文的目的、意义 运动补偿的基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏块内所有象素的位
3、移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的相对位移即为运动矢量。视频压缩的时候，只需保存运动矢量和残差数据就可以完全恢复出当前块 。高精度的运动补偿预测可以大大提高视频编码的效率，是视频编码中的重要环节。 2、学生应完成的任务 （1）了解运动补偿的目的意义和发展史； （2）掌握MATLAB仿真工具； （3）对基于块匹配算法的运动补偿预测方法进行仿真； （4）要求所编制的软件在答辩时演示； （5）严格按照格式要求完成设计论文的排版打印，字数不少于1.8万字； （6）应完成不少于一万英文字符的翻译及将毕业设计(论文)
4、的中文摘要翻译成英文。 3、论文各部分内容及时间分配：（共 17 周）第一部分熟悉设计题目功能要求 ( 3周) 第二部分掌握MATLAB仿真工具 ( 3周) 第三部分对运动补偿的三步搜索方法进行仿真 ( 5周) 第四部分完成外文摘要翻译外文资料 ( 2周) 第五部分毕业设计文本打印装订善后 ( 2周) 评阅及答辩 ( 1周) 论文整理 ( 1周)备 注 答辩前应向指导老师交毕业设计（论文）说明书（书面文档应不少于1万8千个汉字）和电子文档（含毕业设计（论文）说明书及应用软件）。 指导教师： 年 月 日审 批 人： 年 月 日摘要多媒体技术在人们的生活中应用得越来越广泛，随着互联网的快速发展，多
5、媒体通信更是成为人们必不可少的需求。多媒体技术的飞速发展，使得许多应用领域对视频图像的实时压缩提出了更高的要求，快速、高效的压缩算法是解决这一问题的关键。影响视频压缩编码质量和效率的因素很多，运动估计是其中最有影响力的因素之一。运动估计得越准确，视频压缩编码的效率就越高，解码出来的视频图像质量越好;而且，运动估计在整个视频压缩编码系统中的计算复杂度最大。因此，快速、高效的运动估计算法是视频压缩编码技术的研究重点。采用运动估计和运动补偿技术可以消除视频信号的时间冗余，从而提高编码效率。研究设计高效、快速、鲁棒的运动估计算法成为目前视频压缩技术中研究的重要课题。在各种运动估计方法中，块匹配法由于其
6、原理简单、便于实现等优点得到了普遍应用，被许多视频编码标准（如MPEG以及TH.26X）所采用，在理论研究和实践应用中，得到了不断的发展和完善，成为数字视频技术的一个研究热点。其相关快速算法也得到了广泛的研究和发展。本论文中，主要的任务是分析和研究几种经典的运动估计算法，并对它们进行相关比较。本文首先介绍了课题的研究背景与意义以及视频压缩技术，然后阐述了基于块匹配的运动估计的基本原理，最后详细介绍了全搜索法和几种典型的块匹配运动估计快速算法，分析了它们各自的技术特点，通过实验数据定量地评价了各算法的优缺点。文章最后对本文工作进行了总结，并对未来的研究方向进行了展望。关键词: 运动估计;块匹配;
7、三步搜索法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 , which puts forward higher request to real-time compression of vide
8、o 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 the most influential factors. The more precise of motion estimati
9、on 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, rapid and high efficient motion estimation algorithm is the point
10、 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 efficient, fast and robust motion estimation algorithm has been the impo
11、rtant 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 video coding standard, such as the MPEG and TH. 26 X. And in the
12、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 development.In this paper, the main task is to analyze and study se
13、veral 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 motion estimation based on block matching . Finally, introduces the
14、 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 experimental data .At the end of this paper, we summarize the w
15、hole 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 块匹配运动估计的基本原理122.3 块匹配的运动估计的参数和指标142.3.1 分块大小142.3.2 匹配准则142.3.3
16、 搜索范围的确定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 实验结果分析353.4 本章小结35结束语374.1 本文工作总结374.2 研究展望37致谢39参考文献40第1章 绪论1.1 引言
17、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.263/H.263+和H.264(与MPEG组织合作)等一系列国际数字视频压缩编码标准。它们为视频编码技术的发展起到了巨大的推动作
19、用。在传统的图像通信领域，例如基于ISDN、PSTN以及DDN的会议电视和可视电话等视频通信业务取得巨大成功的同时，新的多媒体通信方式也不断出现，尤其是Internet和数字移动通信的迅速普及，利用IP网络以及宽带无线网络进行图像和视频信息的传输成为倍受人们重视的新方式。但是大量频繁的图像、视频信息的交流与存贮活动也带来了许多新要求和新问题，例如视频图像巨大的信息量与当前有限的信道带宽和传输效率已成为制约多媒体技术发展的一个重要瓶颈，因此人们在努力增加信道带宽和提高信道传输效率的同时，对视频图像采取高效的压缩编码己成为目前的研究热点。例如，1幅640x450分辨率的彩色图像(24比特/像素)，
20、其数据量约为0.92MB，如果以每秒30帧的速度播放，则视频信号的传输速率高达27.6Mbps，如果存放在容量为650MB的光盘中，在不考虑音频信号的情况下，每张光盘也只能播放24秒。由此可见，数字视频信息的数据量是非常巨大的，若不经过压缩，数字图像传输所需要的高传输速率和数字图像存储所需要的巨大容量将成为推广应用数字视频技术的最大障碍。要解决多媒体信息存储容量大、数据传输率高的难题，就需要采用压缩技术。研究发现，图像数据表示中存在大量的冗余。通过去除那些冗余数据可以使原始图像数据极大的减少，从而解决图像数据量巨大的问题。对于静态图像，最主要的数据冗余是空间冗余。图像帧记录了可见景物的颜色，而
21、同一景物各采样点的颜色之间存在着空间连贯性，但基于离散像素采样来表示物体颜色的方法通常没有利用景物表示颜色的这种空间连贯性，因此产生了空间冗余。序列图像帧内存在空间冗余，而帧间则存在着很大的时间冗余。这是由于序列图像一般是位于同一时间轴区间内的一组连续画面，其相邻帧间变化量一般很小，只是表现为移动物体所在的空间位置略微不同。运动估计和运动补偿技术就是解决图像帧间时间冗余的很好的方法。运动估计与运动补偿是现阶段视频压缩编码的关键技术。它是一种实现帧间编码的方法，利用前后两帧或若干帧之间的时间相关性，去除时间冗余度。帧间编码之所以能减少冗余度，是因为在一般视频序列的两帧之间有很大的空间结构相似性，
22、前后两帧的差帧可以用比帧内编码所需少很多的比特数来进行编码。而帧间预测的方法基本上是以基于块匹配的运动估计(补偿)算法为主。运动估计目前面临的主要问题就是如何比较快速的得到比较准确的运动矢量，因为在整个视频编码的过程中，即使采用快速算法，运动估计仍然是耗时最长、资源占用最高的环节，如在H.261的编码过程中，在采用著名的三步快速搜索法的情况下，运动估计仍要占用整个编码过程的63%的计算量;而在H.263编码器中，运动估计也还占用了42%的计算量。因此，运动估计成了视频压缩编码的瓶颈，特别是对于帧幅较大、帧频较高的视频对象，在编码实时性和硬件实现方面，运动估计还有很多潜力可挖。基于上述原因，高效
23、快速的运动估计算法一直是视频压缩编码领域的研究热点。从全搜索到三步搜索法、菱形搜索、以及六边形搜索法等，提高了基于块匹配的运动估计算法的性能，使实时应用成为了可能，但是由于实际需求越来越高，所以也要求我们不断的改进运动估计算法以满足现实的需求。基于块匹配的运动估计作为视频编码的关键技术，需要解决的问题是如何提高它的估算速度和精度。而鱼和熊掌不能兼得，这两个指标在实际计算过程中往往无法同时达到最优，如何解决这个折衷问题具有很高的理论和实际意义，是一个图像处理领域和图像通信领域极其重要的研究课题。它的研究和应用必将促进计算机通信、图像通信和多媒体技术的发展。本课题的意义在于，通过实验和仿真，比较了
24、各种算法的优缺点，找出了最优的算法，确保视频压缩的质量。力求在己有算法的基础上寻找一种新的思路，找出了一种优化和改进的块匹配运动估计算法，使其能够在保证图像质量的同时，搜索速度得到较大的提高。1.1.2 视频压缩技术介绍对视频进行压缩，就要了解视频的构成。普通的未压缩视频都是由一帧帧图像序列组成的，一般1秒中包含24帧图像。一般图像的变化都很小，而且变化都是局部的，甚至是静止的，这样就可以从中找到突破。数字视频中的这些情况都可以称为信息的冗余，因此可以通过除去这些冗余数据来减少大量的原始视频的数据量，从而达到数据压缩以解决视频传输中数据不便传输的问题。通常的视频信息中存在以下三种冗余：1空间冗
25、余：这是静态图像存在的最主要的一种数据冗余。研究数据表明，图像帧内的行、列相邻点之间的相关性可以达到90%以上。时间冗余：这是视频里图像序列中最经常包含的冗余。视频序列前后帧之间存在着较大的相关性。同样有研究证明活动图像相邻帧同一位置上前后样值的相关性也达到90%以上。视觉冗余：人类的视觉系统对图像的敏感性是非均匀的和非线性的。人的视觉系统(HVS)对于某些失真并不敏感。然而，在记录的原始图像数据时，通常假设这个系统是均匀的和线性的，对视觉敏感和不敏感的部分同等对待，从而产生了比理想编码更多的数据，这就是视觉冗余。视频信号都是由一系列单独的图像帧组成。每一帧都可以利用图像编解码器(JPEG)进
26、行帧内编码(Intra-frame Coding),每一帧在内部先进行编码而没有考虑到其它的帧。消除视频序列中的时间冗余（连续视频帧中的相似性），可以达到更好的压缩效果。具体可以通过给图像编解码器增加一个“前后帧”来实现，主要有以下的两个功能：(1)预测：从一个或多个先前传输的帧来建立对当前帧的预测；(2)补偿：从当前帧中减去预测帧来产生“残差帧”。接着用图像编解码器来处理这个残差帧。经过这个处理，残差帧将包含很少的数据，因而可以用图像解码器对它进行有效的压缩。为了解码帧，解码器必须进行逆反补偿过程，把预测加到解码的残差帧中，这就是帧间编码(Inter-frame Coding)。视频编码标准
27、的最重要的发展都是源于两大标准组织：ITU(前身是CCITT)和ISO。1986年，ISO和CCITT联合成立了“联合图片专家组（JPEG Joint Photographic Experts Group）”，于1991年3月提交了用于灰度等级和颜色两方面连续变化静止图像编码的JPEG建议草案，于1992年7月通过证实标准。1988年，MPEG(Moving Picture Expert Group)运动图像专家组成立，它致力于运动图像及其伴音编码标准化的工作，包括MPEG系统，即MPEG视频和MPEG音频。原先共有三个版本MPEG-1，MPEG-2，MPEG-3，后来又增加了MPEG-4，M
28、PEG-7等，不同的版本对应了不同的应用场合及相关的视频质量，对多媒体通信的发展起到了巨大的影响。2(1)MPEG-1MPEG-1制定于1993年，是针对1.5Mbps以下数据传输率的数字存储媒质运动图像及其伴音编码的国际标准。MPEG-1用于在CD-ROM上存储同步和彩色运动视频信号，可优化为中等分辨率，并在这个优化模式下，采用标准交换格式(SIF)。它可针对SIF标准分辨率(对于NTSC制为352240；对于PAL制为352288)的图像进行压缩，传输速率为1.5Mbits/sec，每秒播放30帧。MPEG-1对色差分量采用4:1:1的二次采样率。MPEG-1旨在达到VRC质量，其视频压缩
29、率为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-2还可用于为广播、有线电视网、电缆网络以及卫星直播提供广播级的数字视频。还可提供一个较广的范围改变压缩比，以适应不同画面质量、
30、存储容量以及带宽的要求。对于最终用户来说，由于现存电视机分辨率的限制，MPEG-2所带来的高清晰度画面质量(如DVD画面)在电视上效果并不明显，反而其音频特性(如加重低音，多伴音声道等)更引人注目。(3)MPEG-3MPEG-3是ISO/IEC最初为HDTV开发的编码压缩标准。但由于MPEG-2的高速发展，MPEG-3的功能已被淘汰，其原来的工作由MPEG-2小组承担。(4)MPEG-4MPEG-4于1998年11月公布，该标准提出了基于对象编码的概念，不仅针对一定比特率下的视频编码、音频编码，更加注重于多媒体系统的交互性和灵活性。MPEG-4标准主要应用于视像电话(Video Phone)，
31、视像电子邮件(Video Email)和电子新闻(Electronic News)等，其传输速率要求较低，在4800-64000bits/sec之间，分辨率为176144。MPEG-4利用很窄的带宽，通过帧重建技术，压缩和传输数据，以最少的数据能取得最佳的图像质量。MPEG-4是第一个让用户由被动变为主动的动态图像标准，从根源上说，MPEG-4将自然物体与人造物体相溶合(视觉效果意义上的)，其试图达到两个目标：低比特率下的多媒体通信及多工业的多媒体通信的综合。据此目标，MPEG-4引入了AV对象(Audio/Visual Objects)，从而使得更多的交互操作成为可能。MPEG-4的应用前景
32、可以说非常广阔。它的出现能推动以下的几个方面：数字电视、动态图像、万维网(WWW)、实时多媒体监控、低比特率下的移动多媒体通信、Internet/Intranet上的视频流与可视游戏、基于面部表情模拟的虚拟会议、DVD上的交互多媒体应用、基于计算机网络的可视化合作实验室场景应用等。MPEG-4技术还在不断的完善和发展当中，新的MPEG-4标准的应用正在促进多媒体压缩技术经历另一次重大变化。这一变化会与1990年MPEG-2压缩标准的推出一样巨大，而且随着视频通信应用的快速发展，MPEG-4标准势会影响到范围广泛的多种应用领域。(5)MPEG-7继MPEG-4之后，要解决的矛盾就是对日渐庞大的图
33、像、声音信息的管理和迅速搜索。针对这个矛盾，MPEG提出了这个解决方案MPEG-7。MPEG-7力求能够快速并且有效地搜索出用户所需的不同类型的多媒体信息。该标准没有规定利用描述进行搜索的工具或任何程序。目前MPEG系列国际标准已经成为影响最大的多媒体技术标准，对数字电视、视听消费电子产品、多媒体通信等产业产生了深远影响。ITU主要精力则集中在支持实时、双向视频通信上。而负责发展这些标准的组织就是众所周知的VCEG(视频编码专家组)，其主要标准有：(1) H.261视频编码标准H.261是ITU-T为在综合业务数字网(ISDN)上开展双向声像业务而制定的，速率为64kb/s的整数倍。H.261
34、只对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.263与H.261相比采用了半象素的运动补偿，且增加了4种有效的压缩编码模式。先进的预测模式允许一个宏块中4个88亮度块各对应一个
35、运动矢量，提高了预测精度；两个色度块的运动矢量取这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的整数变换；时间相关性则通过帧间预测来去除。这里所说的变换去除空间相关性，仅仅局限在所变换的块内，如88或者44，并没有块与块之间的处理。H.263+与MPEG-4则引入了帧内预测技术，在变换域中根据相邻块对当
37、前块的某些系数做预测。H.264则是在空域中，利用当前块的相邻象素直接对每个系数做预测，有效地去除相邻之间的相关性，极大地提高了帧内编码的效率。1.2 运动估计的研究现状运动估计算法通常分为两大类:一类是象素递归算法PRA(Pixel Recursive Algorithm);另一类是块匹配算法BMA(Block Matching Algorithm)。PRA是基于递归思想，如果连续帧中象素数据的变化是因为物体的移位引起的，算法就会沿着梯度方向对某个象素周围的若干象素做迭代运算，使连续的运算最后收敛于一个固定的运动估计矢量，从而预测该象素的位移;而BMA则是基于当前帧中一定大小的块，在当前帧的
38、前后帧的一定区域内搜索该象素块的最佳匹配块，作为它的预测块。尽管PRA对比较复杂的运动形式来说，其预测精度要高于BMA，但是由于其计算量比BMA大的多，同时BMA本身也拥有较好的性能，因此目前的视频压缩编码国际标准普遍都采用BMA。本文的研究都是针对块匹配的运动估计算法，在后文中，如无特别说明，所提到的运动估计也都是指基于块匹配的运动估计。在基于块匹配的运动估计中，最直接的是全搜索算法(Full Search，FS)，它能够得到全局最优的运动矢量，但该算法的运算量也相当巨大，成为了编码器实时应用的瓶颈。为了提高运动估计的运算速度，人们不断提出针对块匹配运动估计的改进快速算法，其目标是在保证编码质量的同时，尽可能的降低运算复杂度。快速搜索模板这类算法的主要想法是通过在搜索窗口内按照固定的搜索模板和步骤，对较少的几个点进行匹配运算来降低运算复杂度，这类快速模板算法都是基于一个共同的假设，即在搜索窗内有且仅有一个全局匹配误差最小点，而且匹配误差随着当前点与全局最优点之间距离的增大而增大。模板搜索快速算法是提出最早，发展最为成熟，也是应用最为广泛的一类快速算法。它的优点是算法简单，计算量小，加速比较大，缺点是容易陷入局部最优值，尤
