硕士学位论文h运动估计算法的研究与FPGA验证

1、H.264运动估计算法的研究与FPGA验证 分类号UDC密 级学 号硕士学位论文 H.264运动估计算法的研究与FPGA验证学 科 名 称： 电路与系统 学 科 门 类： 工 学 指 导 教 师： 申 请 日 期： 论文题目：H.264运动估计算法的研究与FPGA验证学科专业：电路与系统研 究 生：摘 要随着互联网的飞速发展，人们的生活中充满了各种多媒体技术。2003年3月份，ITU-T（国际电信联盟）颁布了H.264视频编码标准。H.264是一个新的数字视频编码标准，这个标准下，可获得比以往标准都高的编码效率，满足低带宽、高质量网络视频应用的需要。为了达到实时性，对视频编码技术提出了更高的挑

2、战。作为视频压缩编码中运算量最大也最重要的一部分运动估计，它能有效去除视频信号中存在的大量的时间冗余和空间冗余，使视频数据得到高效压缩，这是能够解决实时性的关键，也是视频压缩编码标准中的一个重要研究方向。在分析了运动估计几种典型的算法，结合前人已有的硬件结构的基础上，结合高性能 VLSI 设计实现的特点，提出了一种改进的脉动阵列及流水线相结合的全搜索块匹配的整像素运动估计结构，并完成了其 VLSI 设计。先简要描述了H.264标准及其性能，对块匹配运动估计原理和相关参数对运动估计效果的影响进行了详细的介绍。接下来对全搜索算法和几种快速搜索算法作了一一介绍。然后重点介绍了两种脉动结构 ：1-D

3、和2-D ，阐述了各自的优点和不足。由于搜索区域中的相邻参考块之间有一定的数据重叠，为了重用这些重叠数据，提出了本文的数据流，根据数据流的特点给出了相应的硬件结构，采用串入并出的流水线，提高了计算速度的同时也大大减小了 I/O 带宽。最后利用FPGA 的分块设计思想，先详细的划分了全搜索运动估计算法的各个功能子模块，编写了各个子模块的 Verilog 代码，并分块进行了功能仿真，子模块仿真通过后，把所有模块综合起来，进行了仿真。通过分析仿真数据，证明了本文设计的全搜索运动估计模块能够正常工作，并且能够实现全搜索算法的功能，输出正确的运动矢量。关键词：H.264；视频编码；运动估计；VLSI；脉

4、动结构Title: THE RESEARCH OF H.264 MOTION ESTIMATION ALGORITHMAND FPGA VERIFICATIONMajor: Circuits and SystemsName: Yang LiuSignature: Supervisor: Associate Prof. Shijie QiaoSignature: AbstractWith the rapid development of the internet, multimedia technology in people's daily lives has been more wi

5、dely used, multimedia communications is one indispensable part of daily life. In March of 2003, ITU-T ( International Telecommunication Union ) issued H.264 video coding standard. H.264 is a new digital video coding standard, this standard has a high coding efficiency, it is suitable for high qualit

6、y network video and low-bandwidth applications. In order to achieve real-time，video coding technology faced a higher challenge. As video compression coding in computing the largest and most important part - motion estimation, it can effectively remove the use of the video signal in the presence of a

7、 large number of temporal redundancy and spatial redundancy and compressed video data efficiently, real-time requirements is a solution bottlenecks, which is an important research direction of the video compression.Based on the analysis of integer motion estimation algorithm and architecture, combin

8、ed characteristics of high-performance VLSI design and implementation, suggested an improved pipelined systolic array and a combination of full-search block-matching motion estimation structure of integers, and completed its VLSI design. Firstly，described the H.264 standard and its performance brief

9、ly. Detailedly introduced the block-matching motion estimation principle and some relevant parameterss effect on the result of motion estimation. Secondly, introduced the full search algorithm and several fast search algorithms.Thirdly, presented two kinds of pulse structure :1-D and 2-D and their r

10、espective advantages and weaknesses . In order to reuse the overlapping data among the adjacent reference block data in search area, put forward the data stream，gave the structure according to the characteristics of the data stream, used the pipeline operation to improve the computing speed and redu

11、ce the I/O bandwidth greatly.Finally, through the FPGA block design thinking, devided the full search motion estimation algorithm into many functional sub-modules，Write the Verilog code for each sub-module, after function simulation of sub-modules，synthesized all the sub-modules and simulated.Analys

12、ysed the simulation data and proved the design of full search motion estimation module can work properly, be able to realize the full search function and output correct motion vectors.Key words：H.264; Video Coding; Motion Estimation; VLSI; Pulsating Structure目 录1 前言11.1 研究背景与意义11.2 国内外研究现状21.3 论文的主要

13、研究内容和章节安排31.3.1 主要研究内容31.3.2 论文的章节安排32 运动估计算法的介绍52.1 H.264标准概述52.2 运功估计技术的概述62.2.1 运动估计的基本概念6运动估计的基本过程62.3 块匹配技术概述62.4 块匹配运动估计的参数和准则72.4.1 分块大小72.4.2 匹配准则82.4.3 搜索策略92.4.4 搜索范围的确定92.4.5 算法评定指标92.4.6 估计精度102.5经典块匹配运动估计算法介绍和性能分析112.5.1 全搜索算法（FS）112.5.2 三步搜索法 （TSS）12新三步搜索法 (New Three Step Search)13菱形搜索

14、法 (Diamond Search)142.5.5 四步搜索法(Four Step Search)152.5.6 混合非对称十字多六边形格点搜索（UMHexagonS）162.6 本章小结173 运动估计的经典硬件结构193.1 流水线技术概述193.2 脉动阵列概述203.3 全搜索运动估计算法的硬件结构203.3.1 经典的 1-D 脉动结构213.3.2 AB1 类型的 1-D 脉动结构233.3.3 AS2 类型的 2-D 脉动结构243.3.4 AB2 类型的 2-D 脉动结构25树形结构263.4 本章小结274运动估计硬件结构的设计284.1设计流程284.2设计方法294.3

15、运动估计算法和相关参数的确定294.3.1 运动估计算法的选择29相关参数的确定304.4 数据复用304.5 脉动阵列结构的设计和实现流程304.6本章小节335运动估计模块的设计和仿真355.1运动估计模块的总体结构355.2 存储单元功能模块365.3 数据选择功能模块375.4 PE 运算模块395.5 比较运算模块415.6 整体控制模块435.7整体结构功能测试和分析435.8 FPGA验证435.9 本章小结456 总结和展望47致谢49参考文献511 前言1.1 研究背景与意义在当今这个信息化的社会，信息技术影响着我们日常生活的方方面面。在我们的生活中有近70%的信息，通过我们

16、的视觉系统获得，即图像，而视频是由运动的图像构成的，这里面就包含了更为丰富的信息。从普通电话到可视电话，普通手机到智能手机，有线电视到数字电视的飞速发展。人们更希望无论何时，无论何地，都能实时、方便的通过图像和视频等方式进行通信，但受到客观条件的的限制，比如处理器的处理能力，要想达到实时性，就需要有视频压缩编码方面高性能的处理器，同时也可以提出更好的视频压缩编码方法。人们的生活因为视觉而丰富多彩。为了更好的生活和娱乐，数字视频的质量需要不断的提高，因此加大了对数字视频编码技术的研究。2003年3月，H.264标准经过多次修改后，最终确定。H.264较以往标准，同等质量下，压缩比方面有了明显的提

17、高，明显增进了网络的可靠性和视频传输安全，大大改善了网络传输时易阻塞、易误码、QoS没有保证的情况【1】。H.264标准中，为了提高其性能和编码效率，增加了很多相当复杂的算法，提高了编码效率的同时使得编解码更难。H.264/AVC标准仍然是基于块的混合编码，但采用了大量以往标准中没有的技术，大大提高了编码性能。视频编码层VCL和网络提取层NAL构成了H.264/AVC视频编码标准。H.264/AVC标准显著提高了压缩比，同等图像质量下，H.264/AVC要比H.263和MPEG-4节省大约50%的码率【2】，因此也被广泛的应用，像可视电话、实况转播、视频会议和监控等。实时视频效果的好坏不仅与网

18、络性能有关，而且还与所采用的视频压缩标准以及所利用的实现平台有关。H.264视频编码标准计算杂度高，运算量也庞大，要想在实时方面得到很好的应用，就必须要考虑用硬件来实现。 运动估计，一种帧间编码方法。由于两帧图像间相隔的时间很短，因此存在很大的相似性，运动估计就是利用了这个相似性，减少时间的冗余度，这个时间的多少取决于运动估计算法的好坏，所以它是视频编码中的一个关键技术，视频的压缩比完全体现在这里。FPGA，一种大规模的可编程器件【8】，有着逻辑单元灵活、集成度高，开发周期短、开发工具先进、制造成本低等特点，因此被广泛的应用于各种设计之中。它对执行运算量庞大，但原理简单，运算工整的算法，有着自

19、己独特的优势，因为它的内部有大量的触发器和I/O引脚，拥有强大的并行计算能力。H.264中的加法和位移，原理简单，运算工整，使得它能在FPGA中能够高效并行进行，大大缩短了处理时间，提高了系统的实时性。因此，深入研究H.264视频编码核心算法中的运动估计硬件实现结构是一件值得做的工作。1.2 国内外研究现状随着各种视频编码技术的快速发展，与之相对应的硬件视频编码器也陆续出现，各自有一定的优缺点。为了促进H.264/AVC在硬件方面的发展，国内外在优化H.264/AVC编码算法各个模块的同时，提出了很多像三步搜索法、钻石搜索法、混合非对称十字多六边形格点搜索等算法，这些算法降低了计算复杂度，减小

20、了运算量，效果也不错，也提出了现在最常用的匹配准则：SAD准则，大大降低了计算复杂度。ASIC是早期视频编码方案采取的主要芯片，众所周知，ASIC是固化了特定功能的芯片，不可编程，从设计到使用需要很长时间，产品一旦做出来就不允许再更改，导致它跟不上视频编码技术的发展，因此出现了其他方案，并替代了该方案。大多数的视视频编码设计方案，伴随着DSP技术的飞速发展，都相继转向了DSP平台。新一代高性能DSP芯片的陆续推出，并成为了现今视频编码设计方案的主流。主要有EQUATOR的BSP16、 Sigma Design公司的EM86XX【9】和Davinci平台、ADI Blackfin【10】处理器和

21、Philip公司的TriMedia系列及新品PNX1500 【11】以及 TI的 DM642 DSP 等。这些产品的设计都利用了DSP高性能的数字信号处理能力，同时DSP成本低，功耗也低，因此广受欢迎。加拿大UB Video公司制作的一套基于TMS320C64x系列DSP芯片的H.26L实时视频通信系统，可以在H.263+的1/20倍的码率情况下，获得相同的图像质量【12】。随着人们需求的提高，编码技术在飞速的发展，视频编码的算法越来越复杂，控制也越来越难，需要更高性能的硬件结构。仅仅靠DSP芯片来完成运算量庞大的H.264视频编码算法已没有一点优势可言，虽然DSP芯片拥有强大的数字信号处理能

22、力，但无法完成复杂的控制操作。在市场的压力下，大多数视频编码公司逐步转向DSP+FPGA或者DSP+ARM【13】的设计方案。在DSP+ARM的方案中，控制部分由ARM完成，DSP处理算法，软硬协同处理。在DSP+FPGA的方案中，控制部分交给FPGA完成，也是由DSP来完成算法的处理。Nios II软核技术【14】的发展使得SOPC的应用逐渐成熟，用FPGA来实现软硬协同工作也不再是难事。上述的两种方案有一个共同点，就是算法部分都由DSP芯片来完成，不同的是一个控制部分由ARM完成，一个控制部分由FPGA来完成。随着流水线技术在DSP芯片中的应用，使得其性能有了进一步的提升，但对实时性要求很

23、高的应用，计算速度有限的中低端DSP芯片已无用武之地。高端的DSP，虽然能够满足要求很高的实时应用的需求，但这样做又显得成本太高，使得整个设计投入过大，投入市场收益甚微。FPGA作为一种新型的逻辑器件，拥有强大的并行运行能力和很高的计算速度。H.264视频编码的算法简单，运算工整，很适合利用FPGA来完成它的设计。大规模FPGA的出现，使得在FPGA上实现H.264视频编码的全部算法和控制成为了可能。已经有很多公司和研究所在从事基于PFGA的H.264视频编码器的设计。由Altera和 Xilinx Altera公司开发的基于大规模FPGA的视频处理套件很早就已经在市场上出售。经过近3年的努力

24、，JointWave公司在2007年3月完成了H.264 Main Profile Encoder的纯verilog语言的设计，并且FPGA验证顺利通过，通过封装和处理已在全球发行。它是第一款，也是现在业内水平遥遥领先的H.264 Main Profile Level 3.0级别的纯硬件编码器。H.264视频编码技术虽然在迅速发展，但是采用FPGA设计的编码器却发展缓慢，我国还处在起步阶段。为了满足人们在日常生活和工作中对实时通信和娱乐的需求，大力发展H.264基于FPGA的视频编码器的设计与实现，将会赢得很大的市场。这将极大的改善实时通信，满足人们的需求。1.3 论文的主要研究内容和章节安排

25、1.3.1 主要研究内容运动估计是视频编码中运算量最大，但同时也是最关键的部分，它对视频压缩的性能起着决定性的作用。采用FPGA强大的并行能力来完成强大的运算量，改善H.264视频编码的实时性，是一个很有意义的设计。本文主要研究了运动估计算法，在已有的运动估计硬件实现的基础上，通过扬长避短，提出了本文的数据流，根据数据流的特点给出了相应的硬件结构，通过数据流的串行输入、最终结果的并行输出，大大减小了I/O带宽，PE的利用率也一直保持在100%，充分利用了硬件资源。最后利用FPGA 的分块设计思想，先详细的划分了全搜索运动估计算法的各个功能子模块，使用硬件描述语言 Verilog HDL完成了各

26、个模块的代码编写并进行了功能仿真，然后把各个模块综合在一起进行了功能仿真。最后在Altera公司的FPGA开发板上进行了验证。1.3.2 论文的章节安排全文共六章，各章节内容如下：第一章 首先介绍了研究的目的和意义，国内外的研究和发展现状，最后介绍了本文的主要研究内容及章节安排。第二章 介绍了运动估计的概念和块匹配运动估计的原理，详细介绍了块匹配运动估计中的几项重要技术指标以及它们对运动估计效果的影响，对全搜索算法（FS）和几种常用的效果不错的快速搜索算法在匹配速度、运算量、匹配效果、硬件实现起来的难易程度等方面进行了对比分析。第三章 对全搜索算法已有的两种脉动处理结构： 1-D 和 2-D，

27、进行了详细的分析，通过比较它们各自的优点和存在的弊端，取长补短，为后面的设计奠定一定的基础。最后简要的介绍了一下树形结构，分析了它的工作原理，并指出了其存在的严重不足。第四章 介绍了VLSI 的设计流程和方法，确定了本文设计中的运动估计算法和参数指标。通过对前一章两种脉动结构的扬长补短，同时充分利用参考帧中相邻当前块匹配区域数据的交叠，给出了一种本文的数据流，根据数据流的特点映射出相应的 2-D 脉动结构，大大减小了 I/O 带宽。第五章 将整个运动估计模块划分为一个个功能子模块，然后使用硬件描述语言 Verilog HDL完成了各个子模块的代码编写并进行了功能仿真。子模块仿真通过后，把所有模

28、块综合起来，进行了仿真。通过分析仿真数据，证明了本文设计的全搜索运动估计模块能够正常工作，并且能够实现全搜索算法的功能，输出正确的运动矢量。第六章 总结与展望，总结了本文完成的主要工作，指出了其中存在的不足之处，为以后的研究指明了方向。2 运动估计算法的介绍运动估计是视频压缩编码技术中一个相当重要的组成部分。它能够降低相邻帧间存在的大量时间冗余，提高了视频压缩比。运动估计的效果好坏决定了视频编码器的性能。运动估计占用了整个编码时间的70%左右，所以运动估计算法的复杂度直接决定了视频编码器的性能和效率。H.264中运动估计算法采用块匹配算法，该算法最简单，效果也相当不错，促进了实时实现的可行性，

29、因此它成为目前最常用的方法，国际视频编码标准也采用块匹配算法。2.1 H.264标准概述H.264，一个视频压缩编解码的标准，虽然它的编码技术简单，却达到了增强压缩性能，提高了网络传输（network-friendly）的能力，以满足日益增长的“对话型”（视频电话，会议等）和“非对话型”（视频存储、广播以及流媒体等）视频应用的需求。H.264是在H.26L基础上提出来的，保留了MPEG-4等以往标准的优点，并沿用了MC-DCT，同时增加了CAVLC等新技术的应用，使得压缩效率更高，同时也提高了视频质量。其主要优点【15】有以下几点:(l)更高的编码效率。在大多数的码率下，与以前的标准相比，当获

30、得等同的视频质量时，H.264的码率只有它们的40%左右；(2)更高的视频质量。在任何码率下，经过H.264处理的视频，通过解码后，视频的质量比其它标准偏高；(3)自适应的延时特性。可用于延时小的视频会议等，也能够用于无延时的视频监控等；(4)错误恢复功能。H.264能够很好的解决网络传输时丢包的问题，适用于高误码率下，无线网络中的数据传输；(5)良好的网络传输功能。如图2-1所示，H.264标准分为两个层次。视频编码层（VCL: Video Coding Layer）负责对视频的压缩，网络适配层（NAL: Network Adaptation Layer）负责对特定网络信息包的传输，因此，H

31、.264能够优先控制信息，更好的完成对网络数据的封装。图2-1 H.264标准结构图Fig. 2-1 H.264 standard structure2.2 运功估计技术的概述2.2.1 运动估计的基本概念在帧间编码中，相邻帧间的时间间隔很小，人眼分辨不出来，其中的运动量很小，两帧的相似度很高，可以将图像帧分成互不重叠等大小的宏块，找到每个宏块在相邻帧中的最佳相似位置，计算出相对偏移量，这个偏移量就是运动矢量，这个过程就是运动估计。 运动估计能够大大减小帧间存在的大量时间冗余，增大了视频压缩比，也就减少了视频需要传输的比特数，减小了传输带宽，因此它在视频压缩处理中起着很大的作用。运动估计的基本

32、过程运动估计分以下几步完成:第一步，把当前视频帧分为若干个等大小的互不重叠的宏块，设法找到当前块每个宏块在前一帧给定的搜索区域中最佳相似位置，计算出运动矢量；第二步，将在搜索区域中得到的最相似宏块和当前帧对应宏块的对应像素作减法，求的绝对值和，也就是残差块像素；第三步，把得到的每个当前块的运动矢量和残差块的像素传递给下一个模块，经过下一个模块的处理后进行传输。2.3 块匹配技术概述实际上，两帧图像之间的物体运动一般是刚体的平移运动，位移量不大，彼此间存在着很强的相关性。块匹配法就是将图像分成若干个子块，并有以下的假设：（1）当前块中的所有像素有着相同的运动；（2）运动物体不会随着时间的变化而改

33、变了像素值。块匹配算法就是将当前帧图像分为等大小且互不重叠的宏块，满足以上的两点假设，这时候就可以根据预定的搜索范围16，按照匹配准则，在搜索区域中找到和当前块最相似的宏块，计算出两个块之间的相对位移量，并记录，这个便为当前块相对于前一帧的运动矢量，然后将在搜索区域中得到的最相似宏块和当前帧对应宏块的对应像素作减法，求的绝对值和，也就是残差块像素，这样每个当前块就可由一个运动矢量和残差块像素进行表示。运动估计越准确，得到的匹配块就越相似，对应的残差块像素越小，经过处理后变为很小的比特数，传输的过程中占用的带宽将大大减小。运动补偿过程：依据每个当前块的运动矢量，找到在前一帧的对应的最佳匹配块，加

34、上残差块的像素，便可以得到一个和原当前块基本一样的宏块。运动估计越准确，得到的运动矢量也就越精确。运动补偿的效果取决于运动矢量的精确程度，运动矢量的精确程度又取决于运动估计的准确度，因此，选择一个好的运动估计算法很重要。实际上，两帧之间的物体运动一般是刚体的平移运动，位移量不大，因此往往把一帧图像分成若干M×N块，以块为单位分配运动矢量，大大降低码率。如图2-2所示。图2-2 块匹配算法Fig2-2 Block matching algorithm设前一帧搜索区为（M+2Wx, N+2Wy），当前帧块与前一帧块的位移为d(i, j)，在搜索区中，如能找到与当前帧块匹配的前一帧块，则该

35、块运动矢量为(i, j)。2.4 块匹配运动估计的参数和准则块匹配算法中，涉及到分块大小、搜索范围、匹配准则等几个参数的选取，这些参数的选取需要综合考虑，它们的好坏严重影响着运动估计的准确度及实现难易程度。2.4.1 分块大小块匹配算法的使用是有前提的，这个前提就是假设每个分块内所有点做着位移相同的运动，而且运动过程中，物体各个点的像素不会发生变化。运动的剧烈程度不同，需要采用的分块大小最好也不要相同。块太大时，块内各像素位移相同的假设，与实际情况不相符，会对运动估计的准确度造成很大的影响；分块太小时，很容易受到噪声等因素的影响，也使运动估计的准确度不高，同时还会得到大量的运动矢量，大大增加了

36、计算量，降低了编码效率。因此有必要选择合适的块大小，满足既定的前提。H.26x 和 MPEG一般采用 16×16 宏块，这种分法已被证明很平衡，为了进一步提高预测的精度，H.263 和 MPEG-4增加了对8×8宏块的处理，而H.264 将最小宏块分到了 4×4，更进一步的提高了运动估计的结果精确度。采用4x4的分块，虽然在一定程度上能够提高运动估计的精度，但这样每一帧图像就需要更过的运动矢量和残差块来表示，编码效率降低，传输时也将占用更多的带宽。故在选择分块大小时要综合考虑上述因素，提高编码效率。2.4.2 匹配准则任何事物的执行都需要一定的标准。在H.264中

37、，衡量当前块和匹配块之间的相似程度的准则是块匹配准则，同时匹配准则直接决定了运算复杂度和匹配精度，因此匹配准则的选取很重要。常见的匹配准则有：(1)MAD是最小绝对差。公式如下: （2.1）式中(i，j)为位移矢量，和分别为当前块和参考帧中相对当前块的位移为（i，j）的亮度像素值，MxN为分块的大小，经过匹配比较，MAD的值最小的点，就是最优匹配点。（2）最小均方误差函数 (MSE)。公式如下： （2.2） MSE 值最小的点即为最优匹配点。（3）归一化互相关函数 (NCCF)。公式如下： （2.3） 结果最大时即为最优的匹配点。（4）绝对差值和（SAD）。公式如下： （2.4）SAD最小是即

38、为最优的匹配点。由于 MSE 准则和 NCCF 准则中有乘方运算，实现时相比之下就要占用更多的资源，计算复杂度也较其它的高。而 MAD 准则相比之下就有一定的优势。确定了需要采用的运动估计算法和搜索范围的大小，匹配准则对运动估计精度的影响可以忽略不计，但采用SAD能够明显的降低计算复杂度，它和MAD相比只是少了一个除法因子，其它一样，虽然如此，但它却和MAD准则有着相同的匹配效果。因为分块大小一旦确定，MxN的大小也就固定，在进行除法操作显得有点多余，所以MAD准则逐渐被SAD准则取代。 2.4.3 搜索策略搜索策略选择恰当与否，严重影响着运动估计的准确性和速度。搜索策略体现在搜索方向和搜索路

39、线两个方面，二者结合不同的搜索步长就能成为不同的搜索模式。但不能让搜索过程无限制的进行下去，有时候没有必要，比方对静止的图像，那么多搜索步骤都是在做无用功，因此需要一个提前终止准则，保证搜索过程能够及时终止，减少时间的浪费。搜索算法的效率取决于搜索模式，提前终止准则也可以在一定程度上提高搜索算法的效率。2.4.4 搜索范围的确定搜索范围的大小严重影响着运动估计的精度，它的确定需要综合、慎重的考虑。搜索范围的确定需要注意以下两点：1 要根据视频的清晰度来确定搜索范围的大小，清晰度越高，相对搜索范围就越大；清晰度较低，就可以选取较小的搜索范围；2 要根据视频图像运动的剧烈程度来确定搜索范围的大小，

40、运动相对剧烈，需要的搜索范围就相对较大；运动相对平缓，只需要一个较小的搜索范围就能达到预期目的；以上两点是确定搜索范围时需要考虑的重要因素，可见，搜索区域的大小的确定需要从实际情况出发，不能采用一个相同的标准。当搜索区域增大时，虽然能在一定程度上提高运动估计的准确度，但是增大了计算量，这就意味着将要占用更多的硬件资源。因此搜索区域的大小的选择就要视具体情况而定，具体情况具体分析。2.4.5 算法评定指标 运动估计就是为了在前一帧搜索区域中找到与当前块最为相似的块，运动估计越准确，得到的相似块的相似度就越高，压缩性能就越好，需要传输的残差块像素就越少。如何判断一个算法的好坏，就要通过观察匹配的效

41、果和花费搜索时间的多少，时间多少可以用客观条件衡量，匹配效果的好差最直接的办法就是人眼观察。但人眼看到的图像是诸多因素相互作用的过程。这些因素具有不确定性，其中都加入了人的主观意识，用人眼的观察来衡量匹配效果的好差显得不科学。客观的标准不受任何因素的影响，因此采取客观的标准来衡量匹配效果的好差，其中最常用的是峰值信噪比 PSNR(Peak Signal to Noise Ratio)： (2.5)PSNR 值越大，图像的质量就越高，PSNR 值越小，图像的质量相对较低。PSNR的计算简单，也能够很好的反映图像的质量，不受主观因素的影响，因此被广泛的使用2.4.6 估计精度实际中的物体并不是都在

42、做着整像素的位移，所以整像素运动估计的精度在这个时候就不能真实反映物体的位移。物体运动具有连续性，相邻两帧之间不可能都是是以整像素为基本单位的运动的，可能是以1/2像素或者1/4像素等亚像素作为运动单位的。图2-3给出了一个视频序列分别用1/2像素、1/4像素和1/8像素精度时编码的效率，从图中可看到采用1/4像素精度时的编码效率相对于1/2像素精度有了显著的提高，但1/8像素精度和1/4像素精度的编码效率相比并没有明显的提高，1/8像素的内插公式也更为复杂，所以1/8像素精度的运动矢量模型渐渐被1/4像素精度的运动矢量模型所取代。图2-3 不同亚像素的编码效率Fig2-4 Coding ef

43、ficiency of the different sub-pixel为了进一步提高运动估计的准确度，后来的标准采用了亚像素的运动估计，虽然在一定程度上提升了性能，但却大大增加了运算量。亚像素并不存在于参考图像中，它的像素值需要通过邻近已编码点的像素按一定的准则内插而得到。亚像素运动估计通常在整像素搜索得到的最佳匹配点的附近插值形成一个虚拟的亚像素块，将步长变为分数进行下一步的搜索。亚像素运动估计的实现很复杂，考虑到本人的能力和时间问题，只研究了整像素运动估计。2.5经典块匹配运动估计算法介绍和性能分析运动估计的算法决定了视频压缩的性能和速度，是视频压缩编码系统中至关重要的一环。运动估计的准确

44、度和匹配的速度反映了一个算法的优劣。准确度越高，残差值越小，编码后需要传输的比特数就越少，降低了传输带宽。匹配速度客观的表现在得到一个运动矢量所搜索的点数。下面介绍几种常用的运动估计算法。2.5.1 全搜索算法（FS）全搜索算法是一种穷尽的搜索算法，将当前块和参考帧搜索区域中的每一个可能的块都进行一次匹配比较，按照匹配准则找到最佳匹配块。全搜索法有光栅式和螺旋式两种搜索方式，如图 2-4 所示。光栅式搜索如图(a)，从左上角的开始，按行搜索，直到将整个搜索范围内的可能块匹配完毕；螺旋式搜索如图(b)，从中心开始，螺旋搜索到最后一个边缘块，各个块的运动矢量规律性比较差，实现起来困难，相对于光栅式

45、搜索略显复杂。（a）光栅式搜索（b）螺旋式搜索图2-4 全搜索的两种搜索方式Fig2-4 Two search methods of full search全搜索法（FS）拥有最高的运动估计准确度，也不容易陷入局部最优，也是其它快速搜索算法的判断准则，将匹配结果和全搜索法进行对比，来评判该算法的好坏。全搜索法高的准确度是建立在庞大的运算量之上的。全搜索算法(FS)的规则最简单的，但运算量却占到了视频压缩编码过程的 70%左右，当搜索范围为(-f,+f)时，需要进行(2f+1)2次的运算，因此加大了实时性实现的难度，要想实时实现，就需要很高的硬件水平。后来，为了减小全搜索算法庞大的运算量，出现了

46、很多快速运动估计算法，运动估计的准确度也挺高，运算量却大大减小。全搜索法的算法简单，性能也最好，易于VLSI实现，考虑到现有的硬件条件，要实现它已成为一种可能，某些要求高的应用场合非的采用全搜索算法不可，因此对它的研究还是很有意义的。2.5.2 三步搜索法 （TSS）目前，在全搜索算法的基础上，已发展出了一些快速搜索算法。快速搜索法只是将当前块与对应搜索区域中的部分宏块进行匹配计算，从这几个宏块中找到最佳的匹配块，这样做就减小了全搜索算法需要的匹配次数。在减小了匹配次数的同时，另一个问题也相继而生，就是快速搜索算法所找到的最优匹配块，到底是真正的最优，还是局部的最优。为了保证速度，快速搜索算法

47、并没有像全搜索算法那样进行穷尽的搜索，只搜索了特定的宏块，虽然保证了速度，却容易陷入局部最优，而全搜索算法能够保证找到全局最优的匹配块，保证最匹配的宏块运动矢量信息。由于快速搜索算法得到的不是最优匹配块，因此得到的残差块像素也就越大，传输的时候就要占用更多的带宽。三步搜索法（TSS），顾名思义，得到最终的运动矢量需要三个步骤。它从搜索区域的中心开始，搜索周围的8个点，该步得到的最小SAD值点，作为下一步搜索的中心，步长减半，搜索周围的8个点，第三步也是如此，最终找到的SAD值最小点就是最优点，该点相对原点的位移就是运动矢量。三步法思想简单，性能良好，被许多软件采用。如果选定搜索范围为（-7，+

48、7），三步搜索过程如图2-5所示：第一步，从搜索区域的中心开始，步长为 4，匹配运算周围8个带1的圆圈点；第二步，以第一步中SAD值最小的点为新的中心，步长为2，匹配运算周围8个带2的圆圈点；第三步，以第二步中SAD值最小的点为新的中心，步长为1，匹配运算周围 8 个带3的圆圈点，这时候得到的便是最佳匹配块，计算出该块相对搜索中心的位移，就是当前块的运动矢量。图2-5 三步搜索法Fig2-5 Three-step search method图 2-5 示意了最大搜索距离为 7 时的搜索过程。各步操作如圆圈中的数字和对应位置所示。三步搜索法，最多需要计算 25 个点的SAD值，而全搜索算法采用相

49、同的搜索范围，却需要计算225个点的SAD值，相比可见，三步法大大降低了运算量。但是，虽然三步搜索法大大降低了运算量，但第一步过于简单，在搜索范围较大时，第一步就有很大的可能偏离了最佳的搜索区域，像那种静止的运动，运动估计得到的就不是真正的最佳匹配点，只是局部最优，最终影响压缩编码的性能，导致图像失真。新三步搜索法 (New Three Step Search)NTSS算法16弥补了TSS算法在估计运动不剧烈的的运动上的不足。新三步法在三步法第一步搜索的基础上增加了对中心点的8个邻域的测试，并采用了提前终止的策略，倘若最小的BDM (Block Distortion Measure)出现在8邻

50、域的中心就停止搜索，这样对于估计静止块是非常有效的。具体步骤如下:(l)在三步法的第一步的基础上，增加对中心点的8个邻域的测试。(2)提前终止策略对估估计静止块和亚静止块(运动范围在2个像素内)的运动矢量有很大的优势。如果第一步最小的BDM在搜索窗口的中心，就停止搜索;如果出现在中心点的8邻域中，则以最小BDM为中心计算其8个邻域，重复该步骤，直至最小BDM出现在中心。如果最小的BDM出现在w/2上，接下来就按三步搜索法的第二步和第三步执行，找到最佳的运动矢量。NTSS算法执行完所有的步骤需要测试33个点，但NTSS算法有时会在第一步或第二步的时候就提前终止，对于静止的块只需测试17个点，对于

51、亚静止的块需要测试20或者22个点，所以NTSS相对于TSS有了一定的改善，加速了约18%。图2-6 新三步搜索法Fig2-6 New three step search菱形搜索法 (Diamond Search)菱形搜索法因其搜索模板像钻石又被称为 “钻石”搜索算法17，它采用LDSP（Large Diamond Search Pattern，大钻石搜索模板）和SDSP（Small Diamond Search Pattern，小钻石搜索模板）两种搜索模板，如图2-7所示。“钻石”搜索算法，先采用步长大、范围广LDSP模板搜索，进行一个粗略的定位，这也符合视频图像运动的基本规律，陷于局部最优

52、的可能性降低；当完成了粗略定位后，再采用SDSP模板搜索LDSP中得到的最小SAD值点的周围4个点，这时得到的SAD值最小点便是最优匹配点，这样做避免了陷入局部最优，提升了运动估计的准确度。 （a）大菱形 （b）小菱形图2-7 “钻石”搜索模板Fig2-7 "Diamond" search templateDS算法流程如下:第一步:以搜索窗口的原点(O，0)为中心，采用LDSP模板，检测这九个点。如果MBD(Minimum Block Distortion)点位于中心，就转至第三步;否则，转至第二步继续搜索。第二步:以第一步搜索得到的MBD点为中心，构造另一个LDSP。如果

53、得到的新MBD点位于中心，转至第三步，否则，重复此步操作，直至匹配点到达搜索窗的边缘，停止搜索。第三步:采用SDSP模板，这一步搜索得到的MBD点便是最优匹配点，其相对位移便是运动矢量。2.5.5 四步搜索法(Four Step Search)四步搜索法也利用了运动矢量靠近中心分布的理论，将TSS的9x9搜索窗改为5x5，每一步都以上一步最小的BDM的位置为中心，继续下一步的搜索，步长取决于最小BDM的位置。四步搜索法的四步操作如下:(l)在搜索区域的中心用一个5x5的窗口，如果最小BDM出现在窗口中心，转到第四步，否则继续;(2)搜索窗口仍用5x5，但搜索模式要依赖上一步最小BDM的位置，若

54、在窗口的四个角，就增加五个测试点，若在窗口四条边的中心，就增加三个测试点，若出现在窗口的中心，转至第四步继续，否则继续;(3)搜索模式和第二步一样，但该步下来不管怎样都转至第四步;(4)搜索窗口换为3x3，这时得到的最小BDM点便是最优匹配点，其相对位移便是运动矢量。图2-8 四步搜索法Fig2-8 Four-step search methodFSS又一次改进了快速搜索算法，搜索速度不一定比TSS快，但是FSS的计算复杂度相比TSS有所降低，而且整个搜索过程比较平缓，减小了出现局部最优的可能，并对静止的块缩短了搜索时间，所以获得了较好的搜索效果。2.5.6 混合非对称十字多六边形格点搜索（U

55、MHexagonS）混合非对称十字多六边形格点搜索算法【18】(UMHexagonS)是已有的快速搜索算法中估计效果最好的，已被 H.264 官方采用。UMHexagonS 算法分四步完成搜索，搜索步骤如下：第一步：进行矢量预测，确定搜索的起始点。第二步：非对称的十字搜索，在一般的运动中，水平方向的运动幅度大于垂直方向的运动幅度，故可以通过非对称的十字形搜索先做一个初步的搜索。所谓非对称十字，如图 2-9 中 step2 的点所示，水平方向的搜索长度为垂直方向搜索高度的2倍，搜索点间距2个步长。这一步得到最佳匹配点便是下一步搜索的中心。第三步：多层次六边形搜索，分两步完成。首先以上一步的最佳匹

56、配点的位置作为搜索中心，做一个5×5 范围的全搜索，如图 2-9 中 step3-1 的圆圈所示；第二步进行多层次六边形搜索，采用了16 点的六边形，即图 2-9 中 step3-2 的小方形所示，如图 2-9 所示，六边形覆盖的区域比较大，而且六边形左右两侧的点数比上下两侧的搜索点数多，这也符合运动的规律。六边形由里到外层层搜索，等搜索结束后，比较每层中相对较小的SAD值，其中最小的SAD值所对应的位置便是下一步继续搜索位置的中心。第四步：扩展的六边形搜索，第三步的多层次六边形搜索可以得到不同精度的运动矢量，当最佳匹配块在外部六边形时，得到的运动矢量精度就偏低，故需要进一步细化搜索

57、，通常用六边形继续下一步的搜索，如图 2-9 Step4 所示。先采用半径为 2 的六边形反复搜索，直到最佳点出现在六边形中心，接下来用半径为 1 的小菱形继续搜索，直至最佳匹配块位于小菱形的中心。图2-9 非对称十字型多层次六边形格点运动搜索算法Fig2-9 Asymmetric cross-shaped multi-layered hexagonal movement grid search algorithm通过对以上几种搜索算法的实现过程对比，发现全搜索算法虽然计算量最庞大，但是匹配效果却是最好的，而UMHexagonS 算法虽然能达到和全搜索算法差不多的效果，但是搜索模板多样化，不利与硬件实现，通过权衡，最终选择了全搜索法进行研究。2.6 本章小结本章介绍了运动估计的概念和块匹配的原理，分析了分块大小、匹配准则、搜索策略、搜索范围、估计精度对视频压缩编码性能的影响，以及它们选取和确定中需要注意的问题，介绍了几种运动