《通信工程应用技术-多媒体信息处理-运动估计算法.docx》由会员分享，可在线阅读，更多相关《通信工程应用技术-多媒体信息处理-运动估计算法.docx（37页珍藏版）》请在三一办公上搜索。
1、武汉理工大学通信工程应用技术课程设计说明书学 号： *课 程 设 计题 目通信工程应用技术学 院信息工程学院专 业通信工程班 级姓 名指导教师2014年1月16日课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位： 信息工程学院 题 目: 多媒体信息处理 初始条件：MATLAB 及数字图像视频处理基础要求完成的主要任务: 任务：设计视频压缩系统中的运动估计算法：全搜索法（FS: Full Search）和三步法(TSS: Three Step Search)，比较二种方法的搜索点和每帧的峰值信噪比（PSNR： peak signal to noise ratio）要求：1、编制算法代码
2、；2、对视频进行运动估计；3、计算PSNR。时间安排：序号设 计 内 容所用时间1根据设计任务确定实验方案2天2根据实验条件进行测试，并对结果进行分析7天3撰写课程设计报告1天合 计2周指导教师签名: 2014 年 月 日系主任签名: 2014年 月 日目录摘 要IAbstractII1 设计任务11.1 设计目的11.2 设计要求12 视频压缩介绍22.1 视频压缩技术发展概况及国际标准22.2视频压缩中的主要研究内容22.3 视频压缩技术面临的挑战32.4 运动估计在视频压缩中的重要性43 视频压缩系统中的运动估计技术53.1 视频压缩系统的基本框架53.2 运动估计63.2.1 运动估计
3、的基本原理73.2.2 运动估计技术73.2.3搜索范围83.2.4 搜索策略84 运动估计算法分析104.1 基于块匹配的运动估计技术104.1.1 块匹配运动估计的基本原理104.1.2块匹配法114.1.3块匹配运动估计算法的研究现状124.2全搜索法134.2.1全搜索法原理134.2.2 全搜索法特点134.3 三步搜索法144.3.1 三步搜索法原理144.3.2 三步法特点144.4 峰值信噪比145 仿真结果165.1 全搜索算法仿真结果165.2 三步搜索法仿真结果175.3仿真结果分析186 心得体会207 参考文献21附录223武汉理工大学通信工程应用技术课程设计说明书摘
4、 要运动估计算法是视频压缩编码的核心算法之一，通常也是编码器中计算量最大的环节。在视频编码和处理系统中，运动估计和运动补偿技术对降低视频序列时间冗余度、提高编码效率起着非常关键的作用。运动估计的准确程度将直接决定视频编码器的编码效率。它极大地消除了视频序列的帧间相关性。高质量的运动估计算法是高效视频编码的前提和基础，因此分析和研究快速运动估计算法，提高编码器速度是非常必要的，运动估计算法采用某一匹配准则在搜索区域内搜索最佳匹配点获得运动矢量。不同的搜索方法在搜索最佳匹配点上采用了不同的搜索策略，通常的搜索算法主要有全搜索法、三步搜索法、新三步搜索法、菱形搜索法等搜索方法。目前的各种搜索算法都试
5、图在搜索速度和精度之间取得最好的折衷。本次课程设计设计视频压缩系统中的运动估计算法用全搜索法和三步法，并比较二种方法的搜索点和每帧的峰值信噪比。关键字：视频压缩；运功估计；全搜索；三步法AbstractMotion estimation algorithmis one of the corealgorithm of videocompression coding,computationis oftenthe largestpart ofthe encoder.In the video coding and processing system,motion estimation and moti
6、on compensation technology toreduce the redundancy of video sequence time,improve the coding efficiencyplays a very important role.The accuracy of motion estimation directlyaffects the efficiency of the video coder.It greatlyeliminates the inter framecorrelation.High qualitymotion estimation algorit
7、hmis the basis and prerequisite forefficient video coding,so theanalysis and research offast motion estimationalgorithm,it is necessary toimprove the encoder speed,motion estimation usingamatching criterionin the search area inthe best matching pointto obtain the motion vectoralgorithm.The different
8、 search methodsin thesearch for the bestmatchingpoint withdifferent search strategies,global search,three step search,three step search,diamond searchmethodand searchmethod isthe mainsearch algorithmusually. Varioussearch algorithmsare currentlytrying to getthe best compromisebetweenspeed and precis
9、ion of search. The course design of design in the video compression system with full search motion estimation algorithm method and three-step method, and compare the two methods of search points and peak signal to noise ratio of each frame.Keywords: Video compression; Motion estimation;FS; TSS32武汉理工
10、大学通信工程应用技术课程设计说明书1 设计任务1.1 设计目的通信工程应用技术课程设计是通信工程等专业的重要专业实践环节，目的是培养学生科学理论结合实际工程的能力。通过该课程设计，要求学生应用多门专业基础课知识：如线性电子线路、非线性电子线路、EDA技术、DSP技术、MATLAB、C语言程序设计、信号与系统、电子测量、通信原理等，结合实验中心的实验设备，设计现代数字通信系统中的组成部分方案及实验验证。1.2 设计要求本课程设计要求学生理解一般电子系统的基本工作原理，掌握系统的性能指标的含义和计算方法，得到仿真和实测结果。本组题目为多媒体信息处理，要求设计视频压缩系统中的运动估计算法：全搜索法（
11、FS: Full Search）和三步法(TSS: Three Step Search)，比较二种方法的搜索点和每帧的峰值信噪比（PSNR： peak signal to noise ratio）。要求完成以下任务：1）编制算法代码；2）对视频进行运动估计；3）计算PSNR。2 视频压缩介绍2.1 视频压缩技术发展概况及国际标准视频压缩编码开始于1970年美国贝尔实验室中第一部电话的出现。传统的压缩编码是建立在香农信息论基础上的：1948 年香农的经典论文通信的数学原理首次提出并建立了信息率失真函数概念，1959 年，香农进一步确立了码率失真理论，奠定了信息编码的理论基础。主要的编码方法有预测
12、编码、变换编码和统计编码，称为三大经典编码方法。这类方法以经典的集合论为基础，用统计概率模型来描述信源，但它未考虑信息接受者的主观特性、主观意义及事件本身的具体含义、重要程度和可能导致的后果。为了更好地促进互操作性，视频压缩编解码开始进入标准化阶段。目前，制定标准的组织包括国际电信联盟（ITU）、美国 AMSI 委员会电信委员会、电信工业联合会（TIA）、欧洲电信标准机构（ETSI）、日本电信技术委员会（TIC）、美国电器电子工程师学会（IEEE）和国际标准化组织（ISO）等。随着产业化活动的进一步开展，国际标准化组织于 1998 年成立了运动图像压缩编码组织 MPEG。MPEG 专家组主要致
13、力于运动图像压缩编码标准的制定。经过专家组不懈的努力，一系列主要针对视频数据的存储、广播电视和视频流的网络传输等应用场合的视频压缩编码国际标准产生了：MPEG-1、MPEG-2、MPEG-4、MPEG-7。而由另一个国际标准化组织 ITU 制定的标准主要是针对实时视频通讯的应用，如视频会议和可视电话等，它们以 H.26x 命名，主要有：H.261、H.263、H.264。2003 年 3 月，由 ITU-T 和 MPEG 两个专家组组成的联合视频专家组（JVT）开发并公布的被称为ITU-T的H.264协议或ISO/IEC的MPEG-4的高级视频编码部分是目前最新的视频编码标准。为了降低码率，获
14、得尽可能更好的图像质量，H.264 标准吸取了 MPEG-4 的长处，克服了以前标准的弱点，具有更高的压缩比、更好的信道适应性。这些视频压缩编码国际标准的制定很好地促进了视频压缩编码技术和相关的多媒体通信技术的发展。2.2视频压缩中的主要研究内容视频图像中存在冗余信息，即相关性。主要的冗余信息有空间冗余信息和时间冗余信息。空间冗余信息是指在一帧图像中像素之间的相关性。一帧图像中，相邻或相近的像素，其灰度值或色度分量的值总是很相近，相邻像素之间存在很强的相关性。而相邻帧之间的时间间隔是由帧率决定的。帧率越大，相邻帧之间的时间间隔就越小，一般是几十毫秒。在这样短的时间内，大部分被拍摄的对象都是静止
15、不动或只有很小的移动，因此视频序列中存在时间上的冗余信息。视频压缩主要就是从时域、空域两方面去除冗余信息。(1) 去时域冗余视频图像是沿时间轴方向的一个帧序列，其帧间图像相关性很强。具体表现为两帧有很多静止图像其数据是不变的。实现帧间编码的方法是运动估计和运动补偿。其原理是利用帧间的时间相关性，减小时间冗余度。帧间编码可以减小冗余度，这是因为两帧之间有很大的相似性。将前后两帧相减(移动物体作相应位移)得到的误差作编码所需比特要比直接进行帧内编码所需的比特少，帧间差值集中在零附近,可以用短的码字传送。(2)去空间冗余视频图像的帧内数据和预测的帧间误差数据，都有很高的空域冗余信息。可用于减少空域冗
16、余信息的技术很多，主要都是基于块的技术。在基于块的空间冗余技术领域中，变换编码技术是最常用的方法，归纳起来，可分为三个阶段：正交变换、对变换系数进行量化、及编码三个阶段。正交变换：正交变换是将空域图像信号映射变换到另一个正交矢量空间如频域，产生一批变换系数，然后对这些变换系教进行编码处理。最常用的为DCT变换，它与K-L最佳变换压缩性能和误差非常接近，而且计算量适中，又具有可分离特性，还有快速算法等特点，所以在图像数据压缩中，采用DCT变换编码的方案很多。量化：变换后系数的量化是关键的操作，量化使变换后的系数用较少的位数来表示，量化器结合编码才使大部分数据得以压缩。它是不可逆的，是有损的压缩方
17、法。编码：量化后数据在编码后输出。将数据有效统计，消除编码冗余，有效地压缩数据量。2.3 视频压缩技术面临的挑战近年来，新的视频业务的兴起，如视频会议、视频点播、远程监控、远程医疗等，对视频数据的实时性传输和视频质量提出了较之以前更高的要求，但互联网和无线网固有的局限性给视频应用业务带来很大的问题，也给视频数据压缩技术提出了更高的要求。视频数据压缩技术主要面临以下几个急需解决的问题：（1）视频数据的高效压缩问题。虽然网络的发展可使有效带宽变的越来越宽，但事实上网络用户数量的增长速度比有效带宽的增长速度快得多，而且在网络上传输的视频信息也日益增多，因此视频数据的有效压缩是目前视频数据压缩技术面临
18、的一个必须解决的问题。（2）能够适应网络带宽变化和具备一定的容错能力。由于通信子网的异构特性，使得网络带宽波动和传输错误不可避免，因此，对视频数据压缩技术的要求不再是单纯的追求某一固定码率下的压缩效率，而是在保证高压缩效率的前提下，要求压缩后的视频码流能够在一定的带宽范围内提供较好的视频质量。同时，还要求在保证高压缩效率的前提下，生成的码流具有一定的容错特性来抵抗传输错误的影响。2.4 运动估计在视频压缩中的重要性视频数据压缩主要通过三种技术手段来实现：利用 DCT 变换和矢量量化来消除视频帧内空间冗余；利用熵编码来消除编码冗余；利用运动估计来消除帧间时间冗余。而帧间时间冗余度远大于帧内空间冗
19、余度和编码冗余度，因此，运动估计是视频压缩编码系统中非常重要的模块，它直接影响到视频数据压缩编码的效率和编码质量。运动估计的越准确，编码的效率就越高，解码出来的视频质量就越好。同时，运动估计的计算复杂度在整个视频数据压缩编码系统中最大，占整个系统计算量的 50%以上。因此，运动估计性能的好坏不仅很大程度上决定了视频图像压缩编码的质量，还根本性地决定了整个视频压缩编码系统的实时性能。研究高效的运动估计算法对提高视频数据压缩编码的效率有着非常重要的实际意义，是解决目前视频数据的高效压缩问题的有效途径。3 视频压缩系统中的运动估计技术3.1 视频压缩系统的基本框架本小节将对H.26x和MPEG-x系
20、列视频压缩国际标准制定的视频压缩系统的框架进行提炼，说明视频压缩系统的一般性结构。一般地，人们把H.26x系列和MPEG-1、MPEG-2称为基于第一代压缩编码结构的视频压缩编码标准。基于“第一代压缩编码结构”是指这些编码标准采用的视频压缩编码框架都是由预测编码、变换编码、熵编码及运动补偿这四个模块组成的。对视频图像的压缩编码一般有两个部分：一部分是帧内编码，也就是 I 帧编码，这部分的编码方式与一般的静止图像的编码方式一样，编码过程是先将图像帧进行分块离散余弦变换（DCT），然后将 DCT 系数量化重排经可变长编码（VLC）形成码流输出；另一部分是帧间编码，即P 帧和B帧编码，这部分的编码结
21、构比较复杂，图 3-1 说明了帧间编码的基本过程。图 3-1 帧间预测编码模块的一般结构当图像帧采用帧间编码模式时，输入的待编码原始图像数据先与经运动估计后的预测图像相减，产生残差图像，接着对残差图像进行 DCT 变换和量化后经熵编码后形成编码比特流输出；同时对由运动估计得到的运动矢量也要进行编码形成码流；这两部分的码流组合产生当前待压缩图像帧的最后的编码比特流。其中，P 帧是参考过去的 I 帧图像或者过去预测得到的图像用运动补偿预测技术进行编码，这些预测图像通常作为进一步预测的参考图像，预测图像的编码效率较高；而 B 帧在预测时，既可使用前一帧图像作参考，也可使用下一帧图像作参考或同时使用前
22、后两帧图像作参考图像，即所谓的双向预测，因此 B 帧的压缩率最高，但双向预测图像不再作为预测的参考图像，这主要是为了保证比较好的预测精度。解码则是编码的逆过程。对采用帧内编码的 I 帧图像，解码时码流经反量化、离散余弦反变换后直接输出；对于采用帧间编码的 P 帧图像和 B 帧图像的解码，则需根据帧存储器中的参考帧图像和当前帧的运动矢量数据，进行运动补偿，得到当前帧的预测图像，然后与当前帧的重建残差图像相加后输出。综上所述，目前的视频压缩编码国际标准基本上都是采用基于DCT变换和运动补偿的混合编码框架，利用DCT变换去除图像空间冗余，以运动估计与运动补偿来去除运动图像时间冗余，从而达到压缩图像数
23、据的目的。I 帧图像利用图像本身的空间相关性进行压缩，采用基于 DCT 的编码技术，编码不需要其他帧作参考图像，反而是要作为 P 帧和 B 帧图像的参考图像，其压缩率并不高，同时为提供足够高的预测精度，其压缩比也不能太高；视频压缩中更多的是 P 帧和 B 帧图像编码类型，运动估计与补偿技术正是于消除 P 帧和 B 帧图像在时间上的冗余，具有比较高的压缩比弹性，这部分是决定视频编码系统的压缩效率的关键环节。不同的视频压缩编码国际标准针对不同的应用，采取不同的运动估计与补偿策略来提高帧间编码效率，从而提高视频压缩系统的整体性能。3.2 运动估计视频序列在时间域的冗余度很大，因此在视频压缩和视频通信
24、中，不需要将每一帧的所有像素信息传输到解码器端，而只需要传输对象运动信息，解码器即可根据前一帧图像和运动信息更新当前帧，从而达到压缩的目的，这种方法的关键是确定运动信息，即进行运动估计。视频数据压缩主要通过三种技术手段来实现:利用DCT变换和矢量量化来消除视频帧内的空间冗余;利用熵编码来消除编码冗余;利用运动估计来消除帧间的时间冗余。运动估计是指在参考帧中搜索一个与当前帧图像块最相似的图像块，即最佳匹配块，搜索结果用运动向量来表示。由于运动估计在整个系统中的计算复杂度最大，因此，如何提高运动估计的效率，是运动估计算法的搜索过程更健壮、更快速、更高效成为了视频编码技术研究的重点。运动矢量和经过运
25、动匹配后得到的预测误差共同发送到解码端，在解码端按照运动矢量指明的位置，从已经解码的邻近参考帧图像中找到相应的块或宏块，和预测误差相加后就得到了块或宏块在当前帧中的位置。通过运动估计可以去除帧间冗余度，使得视频传输的比特数大为减少，因此，运动估计是视频压缩处理系统中的一个重要组成部分。3.2.1 运动估计的基本原理运动图像多数情况下只是其中的很少一部分图像在运动，同一场景相邻的两帧图像之间在内容上的差异不会太大，也就是说相邻两帧，甚至是相邻数帧的内容有很多是重复的。这说明相邻的图像帧是相关的，用香农的信息论观点解释就是运动图像存在数据冗余，即时间冗余。一般的视频图像中都存在大量的时间冗余。采用
26、帧间预测编码可以显著去除时间域上的冗余度，提高压缩比。如果将上一帧相同空间位置处的像素值作为待编码的当前帧的预测值，这种预测对图像中的静止背景部分将是很有效的。但是对于运动部分，这种不考虑物体运动的简单的帧间预测效果并不好。运动估计可以确定出当前帧的某像素（或某像素块）是从上一帧的哪一个位置移动过来的，获得表示它们相对位移的运动矢量。有了运动矢量后，再通过运动补偿得到它们的差值块。运动估计的精度越高，差值块中的各像素灰度值也越小，甚至大部分都为零，那么用来表示差值块经 DCT 变换、量化和熵编码后形成的压缩码流的比特位数就越少，这就达到了压缩图像数据的目的，而且压缩的空间很大。3.2.2 运动
27、估计技术运动估计算法的效率主要体现在图像质量、压缩码率和搜索速度三方面。运动估计越准确，得到的图像质量就越高，视频序列的比特率就越低，运动估计中搜索速度越快,就越有利于视频编码系统的实时应用。提高图像质量和估计速度、降低比特率是运动估计算法研究的目标。一般通过研究初始匹配点选择、匹配准则、搜索策略来提高运动估计算法的效率。（1）初始匹配点选择a) 直接选取参考帧对应的（0，0）位置这种方法简单，但易陷入局部最佳。如果采用的算法初始步长太大，而原点又不是最优点，有可能使快速搜索跳出原点周围可能性比较大的区域而去搜索远距离的点，导致搜索方向的不确定性，故有可能陷入局部最优。b) 选择预测的起点由于
28、同一帧内相邻块之间的空间相关性和相邻帧之间很强的时间相关性，许多算法都利用这种相关性先对初始搜索点进行预测，以预测点作为搜索起点。实验证明，预测点越靠近最佳匹配点，运动矢量的搜索次数就越少。常用的几种预测初始搜索点的方法有中值预测法、相邻参考帧预测及基于ASD值的初始搜索点预测。（2）匹配准则选取运动估计算法中常用的匹配准则有三种：最小绝对差(MAD)，最小均方差(MSE)和归一化互相关函数(NCCF)。3.2.3搜索范围搜索区域最合适的大小取决于三个方面：（1）每一帧的清晰度：更高的清晰度要求更大的搜索区域； （2）画面的类型：高速运动的画面要比低速运动的画面更适合采用大的搜索区域；（3）可
29、用的处理资源：由于大的搜索区域带来更多的运算比较操作，因此需要更多的处理。因此，并不一定搜索区域越大就越合适。当搜索区域加大时，运动估计的性能得到了提高，但是，需要处理的运算量也加大了。因此选择搜索区域的大小要根据实际处理的图像来确定。3.2.4 搜索策略搜索策略是否恰当对运动估计的准确性、运动估计的速度都有很大影响。有关搜索策略的研究主要是解决运动估计中存在的运算复杂度和搜索精度这一矛盾。目前运动估计的搜索方法很多，有全搜索法（FS）、二维对数法（TDL）、三步法（TSS）、交叉法（CS）、新三步法（NTSS）、四步法（FSS）、菱形法（DS）和运动场自适应搜索算法（MVFAST）等。搜索策
30、略的改进是指以减少搜索窗内的参与匹配计算的匹配块数目来达到加快搜索速度的，但是这在一定程度上会降低搜索精度。搜索窗在运动估计开始后一般是固定的，搜索窗内匹配块的总数目也就固定下来了，如果搜索策略是对搜索窗内的所有匹配块都逐一计算匹配差值，那么此时的计算量将达到最大。一般参与匹配计算的匹配块数目越少，运算量越少，搜索速度当然也越快，但是搜索精度却会降低，这正是这种运动估计改进方法的缺点，搜索速度和搜索精度此时是相互矛盾的。因此如何设计搜索策略，使得在最大限度地减少参与匹配计算的匹配块数目同时又能够保证足够的搜索精度，这是设计此类方法的关键所在。设计好的搜索策略，要利用运动矢量分布的一般特性。通常
31、，运动矢量总是高度集15中在搜索窗口的中心附近，即中心偏置特性，这是因为在图像序列中，静止块和缓慢运动块占主导地位。具体来说，运动矢量一般分布在以搜索窗口中心为圆心，两个像素间距为半径的范围内，如图3-4 所示。运动矢量的另一个特性是时空相关性，即在视频序列图像中，物体的运动在时间和空间上具有很强的相关性。在基于块的运动估计中，由于物体运动是连续的，即相邻帧对应位置块的运动矢量具有时间上的相关性，同时由于图像中对象和背景都覆盖相当多的块，且属于同一对象或背景的块的运动场也具有很大的相似性，因此可以利用时间、空间上的相邻块来预测当前块的运动矢量的动态范围，由此自适应的选择、设计较理想的搜索策略。
32、图 3-4 运动矢量中心偏移分布特性示意图4 运动估计算法分析在各种视频编码标准中，广泛采用基于块匹配的运动估计与补偿技术来减少时间冗余。下面对已有的一些常用的基于块匹配法的快速运动估计算法进行简要讨论和分析。4.1 基于块匹配的运动估计技术作为帧间压缩模块的核心和关键环节，运动估计技术受到人们的广泛关注，出现了多种研究方案，主要有光流方程法、贝叶斯估计法、像素递归法和块匹配法四种。综合考虑计算复杂度和编码效率等因素，块匹配法由于简单、便于 VLSI 实现，已经成为运动估计算法的主流，各个视频压缩国际标准也都采用块匹配法作为运动估计的解决方案。4.1.1 块匹配运动估计的基本原理基于块匹配法的
33、运动估计的基本思想就是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏块内所有像素的位移量都相同，然后对于当前帧中的每一块到前一帧或后一帧某一给定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块，由匹配块与当前块的相对位置计算出运动位移，所得运动位移即为当前块的运动矢量。利用搜索得到的运动矢量在参考帧上进行运动补偿，残差值经 DCT 变换、量化、行程编码后与运动矢量共同经熵编码，然后以比特流形式传出去。图 4-1 为块匹配运动估计基本思想的示意图。图 4-1 块匹配运动估计基本思想的示意图4.1.2块匹配法视频编码技术在数字电视、高清晰度电视、可视电话、会议电视和多媒体视频通信服
34、务中起着至关重要的作用。在H.26x和MPEG这些视频压缩国际标准中视频系统编码器的复杂性最主要取决于运动估计。在视频编码过程中把图像分割成有不同运动的物体是比较困难的。通常采用两种比较简单的方法，一是把图像分成若干个矩形块，假定块做平移运动，对块进行匹配运动估计。另一种方法是对每个象素的位移进行递归估计。通常象素的递归估计的精度高，对多运动画面的适应性强，但它的跟踪范围小，实现复杂。块匹配运动估计虽然精度较低，但它的位移跟踪能力强，且容易实现。由于受带宽的限制及实时视频回放的迫切需要，视频编码成为许多图像通信应用中不可缺少的过程，并且总是要求很高的压缩比。为此，首先必须很好地辨识视频序列中相
35、邻帧间的相关性，并消除所谓的时间冗余。在各种视频编码标准，如H.261，H.263，MPEG-1，MPEG-2及MPEG-4中，广泛采用块匹配运动估计(Bloek Matching Algorithm，BMA)与补偿技术来减少时间冗余。因此,发展快速且精确的块匹配运动估计算法具有非常重要的意义。块匹配法实现效果主要取决于三个因素：匹配准则、搜索范围和搜索方法。实用匹配准则有很多种，两种常用的块匹配准则为绝对差值和SAD以及绝对方差和SSE，和 这里分别表示当前块和参考块图像。(i,j)代表参考块相对当前块的位移。SAD对每个象素的算术平均即为平均差值和MAD，SSE对每个象素的算术平均即为平均
36、方差MSE。选用SAD和MAD准则可以避免乘法运算，而SAD运算量最小，便于硬件实现，所以用得最多。搜索范围一般以宏块和块为单位，而搜索方式是影响块匹配法性能的主要因素，也是运动估计算法中的关键技术。块匹配原理如图4-2所示，其基本思想是将当前帧分成若干个M*N大小相同的块(各类视频压缩标准中块大小均为（16*16），对每一个块(当前块)分别在参考帧中的一定区域(称为搜索窗口)内，假设当前块相对参考块最大位移为d个象素，那么，参考帧内与当前块相对应的坐标附近N+2d范围为搜索范围。当前块按照一定的匹配准则在参考帧中搜索与之最接近的块(称为预测块)，预测块与当前块间的位移称为运动矢量，它们的像素
37、间的差值称为残差块，预测块与当前块之间通过匹配准则函数得到的值称为块失真度(BDM)。这样在已知参考帧视频数据时，当前帧中的每一块数据都可用一个残差块和一运动矢量来表示，显然，残差块和运动矢量的值越小，越有利于压缩。因此运动估计的主要目标就是使预测块与当前块之间的BDM和运动矢量的值尽量小，匹配误差最小的参考块所对应的位移就是所求的运动矢量。图4-2块匹配方法4.1.3块匹配运动估计算法的研究现状目前，块匹配运动估计算法中搜索精度最高的是全搜索法（FS），它对搜索范围内的每一个像素点进行匹配运算以得到一个最优的运动矢量。但它的计算复杂度很高，不适合实时应用。为此很多学者提出了许多快速算法。早期
38、的三步法（TSS）、二维对数法（TDL）、交叉法（CS）等，主要是通过限制搜索点的数目来减少计算量。但它们在第一步搜索步长较大，不利于估计较小的运动。动态搜索窗调整法（DSWA）根据当前结果动态调整下一步搜索步长的大小，算法性能在一定程度上有了改进。新三步法（NTSS）、四步法（FSS）和基于块的梯度下降法（BBGDS）等利用运动矢量中心偏移的分布特性，有效提高了块匹配速度，减少了陷入局部极小的可能性，但它们都是以原点作为初始搜索中心，没有根据块之间的相关性提供运动矢量预测值。预测搜索法（PSA）、自适应运动跟踪法（AMTS）等利用相邻块的运动相关性选择一个反映当前运动趋势的预测点作为初始搜索
39、点，以提高搜索速度和预测的准确性。1999年 10 月，菱形搜索法（DS）被 MPEG-4 国际标准采纳并收入验证模型（VM）。虽然DS 算法的综合性能较其他算法优越，但它不能根据图像的内容做出灵活处理。快速运动估计算法的较新成果Ma 等提出的 MVFAST 算法和 Tourapis 等提出的PMVFAST 算法在 DS 算法的基础上利用了视频图像运动间的相关性确定菱形搜索的起始点，并根据运动的剧烈程度自适应选择大小菱形搜索模式，因此在搜索速度和搜索精度方面都有进一步的提高。4.2全搜索法4.2.1全搜索法原理要得到最佳匹配的运动矢量，最简单的方法是让i和j在（-d，d)范围内逐加点取值，在每
40、一点计算块匹配误差，然后求出相应的运动矢量，这就是全搜索法。用FS计算一个运动矢量需做次块匹配。基于FS的算法性能很好，且硬件实现简单、规则，但是计算量很庞大，需要很多处理单元，在要求实时编码的情况下难以适用。FS算法描述如下：从原点出发，按顺时针螺旋方向由近及远，在逐个像素处计算MAD值，直到遍历搜索范围内听有的点，然后在计算的所有点的MAD中找到最小值，该点所在位置即对应最佳运动矢量。FS算法程序流程图如图4-3所示。获取图像分成N*N大小的块进行块匹配计算MSE计算MAD比较结束 图4-3 全搜索算法程序流程图4.2.2 全搜索法特点全搜索具有以下一些特点：1）对搜索区域的所有位置进行穷
41、尽搜索；2）精度最高计算复杂，难以实时处理；3）必须研究相应的运动估计快速算法。4.3 三步搜索法4.3.1 三步搜索法原理由于FS的运算量十分庞大,为减小运算量,先后提出了许多快速算法,这些算法均试图构造快速逼近最佳匹配位置的搜索路径,以尽量减少冗余的块匹配。典型的算法为TSS,其搜索过程如图4-4所示,这里d=7,它是通过三步搜索,逐步减小搜索步长。每次搜索都是以上一步的搜索结果为中心,进行周围一定步长的3*3像素的搜索。第一步,以窗口中心为中心,步长为4,进行周围8个点搜索,根据匹配准则得到一个最佳匹配点,共搜索了9个点;第二步,以上步最佳匹配点为中心,步长为2,继续搜索周围8个点得到匹
42、配点,共搜索了8个点;第三步,同上一步,只是步长为1,最后得到的最佳匹配点就是要得到的运动估计的点,从而得到运动矢量。进行图像的预测共进行了25次块匹配,同样情况下,采用FS则需做225次块匹配。一般地,TSS的运算量为次块匹配。TSS运算时间明显减少,性能比FS有所下降,但它在硬件上容易实现,是一种很常用的快速搜索算法。4-4 三步搜索法4.3.2 三步法特点1）搜索范围为 ；2）搜索模板半径依次减半；3）确定方向早，容易陷入局部。4.4 峰值信噪比峰值信噪比（PSNR）是一个表示信号最大可能功率和影响它的表示精度的破坏性噪声功率的比值的工程术语。由于许多信号都有非常宽的动态范围，峰值信噪比
43、常用对数分贝单位来表示。PSNR是“Peak Signal to Noise Ratio”的缩写。PSNR是一般是用于最大值信号和背景噪音之间的一个工程项目。通常在经过影像压缩之后，输出的影像通常都会有某种程度与原始影像不一样。为了衡量经过处理后的影像品质，我们通常会参考PSNR 值来认定某个处理程序够不够令人满意。PSNR计算公式如（4-4）、（4-5）： （4-4） （4-5）Peak 就是指8 bits 表示法的最大值255。I(角标n)指原始影像第n个pixel 值，P(角标n)指经处理后的影像第n个pixel 值。PSNR 的单位为dB。所以PSNR值越大，就代表失真越少。PSNR
44、是最普遍，最广泛使用的评鉴画质的客观量测法，不过许多实验结果都显示，PSNR 的分数无法和人眼看到的视觉品质完全一致，有可能 PSNR 较高者看起来反而比 PSNR 较低者差。这是因为人眼的视觉对于误差的敏感度并不是绝对的，其感知结果会受到许多因素的影响而产生变化（例如：人眼对空间频率较低的对比差异敏感度较高，人眼对亮度对比差异的敏感度较色度高，人眼对一个区域的感知结果会受到其周围邻近区域的影响）。5 仿真结果文中的仿真实验在配置为Intel(R) core i5 CPU 24302.4GHz 2.4GHz，8GB内存，Windows8专业版的PC平台下，使用Matlab 2011b作为仿真平
45、台，参考图像如5-1和5-2所示。 图5-1 第一帧参考图像 图5-2 第二帧参考图像5.1 全搜索算法仿真结果全搜索算法得到的仿真结果如图5-3、5-4、5-5和5-6所示。 图5-3 帧间差值 图5-4 预测误差图像 图5-5 全搜索法估计得到的第二帧图像图5.6 运动位移矢量图5.2 三步搜索法仿真结果三步搜索算法得到的仿真结果如图5-7、5-8、5-9和5-10所示。 图5-7 帧间差值 图5-8 预测误差图像图5-9 三步搜索法估计得到的第二帧图像图5-10 运动位移矢量图5.3仿真结果分析通过实验我们得到各种各种匹配算法的Matlab执行时间、重构图像和重构图像的PSNR值。Matlab执行时间反映了算法的执行效率；图像重构PSNR反映了图像恢复的质量，反映了算法的估算精度。各种匹配算法的Matlab执行时间、重构图像的PSNR值如表5-1.表5-1 全搜索法与三步搜索法比较分析匹配算法Matlab运行时间峰值信噪比PSNR值全搜索法（FS）0.719951 seconds31.8851三步搜索法（TSS）0.345247 seconds31.6533从表中分析和恢复出来的图像看，全搜索匹配恢复效果好，这与
