块匹配的运动估计算法比较
摘 要本文介绍了各种在视频压缩中使用的块匹配算法，文中比较了7种不同种的块匹配运动估计算法，从最基础的全搜索算法到最近的快速匹配算法例如自适应十字搜索算法。这里介绍的这些算法被多种视频图像压缩系统中所广泛采用，被设定成该种压缩技术的标准，包括MPEG1，H.261，MPEG4，H.264。文中介绍了运动估计中会使用到的多中技术和准则。并且在matlab平台上将不同的算法进行比较，通过对处理前后参考帧与预测帧的psnr值和运行时间进行比较，得出了不同要求条件下，各种算法的优劣。
目 录
摘 要 VII
ABSTRACT VIII
第 1 章 绪论 1
1.1背景和研究意义 2
1.2国内外研究现状 2
1.3本文主要研究内容及章节安排 3
第 2 章 块匹配运动估计原理 4
2.1 运动估计的原理和方法 4
2.1.1 运动估计的原理 4
2.1.2 块匹配运动估计过程 4
2.2 几种匹配准则 5
2.3 运动矢量的特性 6
第 3 章 多种块匹配算法 8
3.1 完全搜索法（FS：full search method） 8
3.2 三步搜索法（Three Step Search，TSS） 8
3.3 新三步法（NTSS） 9
3.4 四步搜索法（FSS） 11
3.5 菱形搜索法（DS） 12
3.6 自适应十字搜索法 13
3.6.1 目标运动矢量的预测 14
3.6.2 选择合适的搜索模型 15
3.6.3 臂长的选取 15
3.6.4 初始点的确定 16
第 4 章 Matlab实验 18
4.1 实验过程简介 18
4.1.1 Matlab软件简介 18
4.1.2 实验步骤及部分程序代码 19
4.2 实验结果与分析 23
4.2.1 结果评价标准 23
4.2.2 实验数据 23
4.2.3 数据分析 27
*好棒文|www.hbsrm.com +Q: *351916072*
第 5 章 总结与展望 29
5.1 本文工作总结 29
致 谢 30
附录：英文文献及其中文翻译 31
绪论
1.1背景和研究意义
视频压缩的系统中运动估计算法占据着重要的作用，一个好的运动估计算可以明显的提高视频压缩编码的效率。在各种的运动估计匹配算法中，块匹配算法有着结构简单容易硬件电路实现，在各种视频压缩系统中被大量采用。算法估计运动矢量的速度和精度，关系到重构图像的质量，压缩系统的压缩比率，还决定了系统的实时性。因为在视频图像中邻近帧间的图像内容有着很强的相关性，所以在进行预测时，可以采用这样的方式，将视频图像的进行分块，这样可以利用相邻帧间的宏块匹配来求得运动矢量。从参考帧中某一块可以在相应的预测帧中找到与之相同的宏块，他们之间的相对位移量就是运动矢量，得到的运动矢量表现为x方向和Y方向的位移量，研究如何得到运动向量的过程就是运动估计算法，就得运动向量的过程称为运动估计。研究如何使得运动矢量更加准确，求解过程更加高效，简便，重构图像更加接近原图像的运动估计算法至关重要。
运动估计是基于以下的基本思想，因为视频图像相邻帧间具有很大的相关性，将每一帧分割成许多互相不重叠的块，并且假设在块内所有的像素点具有相同的运动方向，当块的选取比较小时，只要求得该帧和后面的邻近帧中该块的运动矢量，即在预测帧中找到与该块最相似的匹配块。两个匹配块之间的位移就是运动矢量。那么得到所有块的运动矢量，就可以通过当前帧与运动矢量重构预测帧。当然，在实际中还存在着一定的误差，那么在视频压缩时，需要保留运动矢量，当前帧以及补偿误差函数，就可以在解压时完全恢复视频序列。大大减少了数据量。这样的一个得到相邻帧间的运动矢量的过程被称为运动估计。
在解压缩端，数据包括当前帧和他与邻近帧的运动矢量，以及每个宏块的误差值，解码时每个宏块加上相应的运动矢量再加上每块的预测误差，就可以得到预测帧，重复这样的步骤，完整的视频序列就可以得到重构。
经过运动估计处理视频序列，可以有效的减少视频序列的帧间信息冗余，使得视频传输的数据比特数减少，而又不会影响视频的品质。所以说在视频压缩处理系统中运动估计过程占据着重要的地位。本文从运动估计的一般问题入手，重点讨论各种块匹配运动估计算法的原理，以及运动估计过程的各种技术，比较各种块匹配算法优劣。
可以想象在原始的视频图像序列中，由于视频图像的相关性很强，它们帧间存在着大量的信息冗余，包括时间冗余，信息熵冗余，空间冗余，谱间冗余，几何结构冗余等等。如何消除这些信息冗余，减少视频传输的比特数，但又不能影响视频的质量。于是提出了运动估计技术，运动估计可以有效地降低视频序列的信息冗余，使得它成为了视频编码系统中的核心技术。有效，高速的运动估计算法成为影响视频压缩质量的关键。如何设计出计算量少，运动估计准确性高，消除冗余能力强的运动估计算法成为了研究的热点。
研究这些算法的目的就在于，尽可能准确的得到视频帧间的运动矢量。只要所求的运动矢量越接近实际物体的运动方向，预测帧得到的图像就越接近实际图像，需要的补差误差就越小，补偿误差编码所需的位数也就越小，视频经过压缩传输的比特数也就越少。得到的运动矢量在帧间进行补偿。压缩编码时补偿残差经过编码后和编码后的运动矢量以及消除了大量帧的视频序列一起编码，通过比特流的形式发送出去。
求得运动矢量的方法有很多种，我们根据策略不同可以把它们分成四类：光流法，块匹配算法，递归估计算法和贝叶斯估计法。块匹配算法的算法由于原理简单，容易设计实现等特点，得到了最广泛的应用。本文将重点介绍以下几种块匹配算法，以及它们的演进发展过程，包括全搜索算法、三步搜索法、新三步搜索法、四步搜索法、菱形搜索法和自适应十字搜索算法，通过TATLAB对各种算法的执行速度和计算精度进行了比较。
1.2国内外研究现状
我们所研究的块匹配算法，是在这样一个假设下进行的，这一假设是符合实际视频序列的内在规律的，认为误差函数在搜索区域有着最小者，且误差值与最小最之间的距离成正比。基于这着特征的算法经历了以下3个发展阶段。第一个阶段是通过逐步减少搜索步长的方式来找到最佳匹配点，使用这一思想的算法有，二维对数搜索法，交叉搜索法，三步搜索法等算法。这种算法有着很大的缺点。首先，由于算法开始时采用的搜索步长通常比较大，所以不能加快对细小运动序列的搜索速度；其次，由于帧间的亮度变化、孔径问题、局部纹理等的问题，导致在整个平面内，误差函数的取值单调的假设不成立，如果算法开始发生错误，容易陷入局部最优点的误区。
第二个阶段时，通过对之前算法的改进产生了多种的快速改进型算法，其中包括，新三步搜索法，四步搜索法，六边形搜索算法和菱形搜索算法。这些算法都会在第三章进行详细的介绍。对大量的视频序列的研究发现最佳匹配块，即运动矢量集中在搜索窗口的中心位置上，运动矢量具有中心偏置特性。第二阶段的算法利用这一特性，极大的改进了搜索的效率和鲁棒性，这也使得在1999年被MPEG4国际视频标准所采用。
目 录
摘 要 VII
ABSTRACT VIII
第 1 章 绪论 1
1.1背景和研究意义 2
1.2国内外研究现状 2
1.3本文主要研究内容及章节安排 3
第 2 章 块匹配运动估计原理 4
2.1 运动估计的原理和方法 4
2.1.1 运动估计的原理 4
2.1.2 块匹配运动估计过程 4
2.2 几种匹配准则 5
2.3 运动矢量的特性 6
第 3 章 多种块匹配算法 8
3.1 完全搜索法（FS：full search method） 8
3.2 三步搜索法（Three Step Search，TSS） 8
3.3 新三步法（NTSS） 9
3.4 四步搜索法（FSS） 11
3.5 菱形搜索法（DS） 12
3.6 自适应十字搜索法 13
3.6.1 目标运动矢量的预测 14
3.6.2 选择合适的搜索模型 15
3.6.3 臂长的选取 15
3.6.4 初始点的确定 16
第 4 章 Matlab实验 18
4.1 实验过程简介 18
4.1.1 Matlab软件简介 18
4.1.2 实验步骤及部分程序代码 19
4.2 实验结果与分析 23
4.2.1 结果评价标准 23
4.2.2 实验数据 23
4.2.3 数据分析 27
*好棒文|www.hbsrm.com +Q: *351916072*
第 5 章 总结与展望 29
5.1 本文工作总结 29
致 谢 30
附录：英文文献及其中文翻译 31
绪论
1.1背景和研究意义
视频压缩的系统中运动估计算法占据着重要的作用，一个好的运动估计算可以明显的提高视频压缩编码的效率。在各种的运动估计匹配算法中，块匹配算法有着结构简单容易硬件电路实现，在各种视频压缩系统中被大量采用。算法估计运动矢量的速度和精度，关系到重构图像的质量，压缩系统的压缩比率，还决定了系统的实时性。因为在视频图像中邻近帧间的图像内容有着很强的相关性，所以在进行预测时，可以采用这样的方式，将视频图像的进行分块，这样可以利用相邻帧间的宏块匹配来求得运动矢量。从参考帧中某一块可以在相应的预测帧中找到与之相同的宏块，他们之间的相对位移量就是运动矢量，得到的运动矢量表现为x方向和Y方向的位移量，研究如何得到运动向量的过程就是运动估计算法，就得运动向量的过程称为运动估计。研究如何使得运动矢量更加准确，求解过程更加高效，简便，重构图像更加接近原图像的运动估计算法至关重要。
运动估计是基于以下的基本思想，因为视频图像相邻帧间具有很大的相关性，将每一帧分割成许多互相不重叠的块，并且假设在块内所有的像素点具有相同的运动方向，当块的选取比较小时，只要求得该帧和后面的邻近帧中该块的运动矢量，即在预测帧中找到与该块最相似的匹配块。两个匹配块之间的位移就是运动矢量。那么得到所有块的运动矢量，就可以通过当前帧与运动矢量重构预测帧。当然，在实际中还存在着一定的误差，那么在视频压缩时，需要保留运动矢量，当前帧以及补偿误差函数，就可以在解压时完全恢复视频序列。大大减少了数据量。这样的一个得到相邻帧间的运动矢量的过程被称为运动估计。
在解压缩端，数据包括当前帧和他与邻近帧的运动矢量，以及每个宏块的误差值，解码时每个宏块加上相应的运动矢量再加上每块的预测误差，就可以得到预测帧，重复这样的步骤，完整的视频序列就可以得到重构。
经过运动估计处理视频序列，可以有效的减少视频序列的帧间信息冗余，使得视频传输的数据比特数减少，而又不会影响视频的品质。所以说在视频压缩处理系统中运动估计过程占据着重要的地位。本文从运动估计的一般问题入手，重点讨论各种块匹配运动估计算法的原理，以及运动估计过程的各种技术，比较各种块匹配算法优劣。
可以想象在原始的视频图像序列中，由于视频图像的相关性很强，它们帧间存在着大量的信息冗余，包括时间冗余，信息熵冗余，空间冗余，谱间冗余，几何结构冗余等等。如何消除这些信息冗余，减少视频传输的比特数，但又不能影响视频的质量。于是提出了运动估计技术，运动估计可以有效地降低视频序列的信息冗余，使得它成为了视频编码系统中的核心技术。有效，高速的运动估计算法成为影响视频压缩质量的关键。如何设计出计算量少，运动估计准确性高，消除冗余能力强的运动估计算法成为了研究的热点。
研究这些算法的目的就在于，尽可能准确的得到视频帧间的运动矢量。只要所求的运动矢量越接近实际物体的运动方向，预测帧得到的图像就越接近实际图像，需要的补差误差就越小，补偿误差编码所需的位数也就越小，视频经过压缩传输的比特数也就越少。得到的运动矢量在帧间进行补偿。压缩编码时补偿残差经过编码后和编码后的运动矢量以及消除了大量帧的视频序列一起编码，通过比特流的形式发送出去。
求得运动矢量的方法有很多种，我们根据策略不同可以把它们分成四类：光流法，块匹配算法，递归估计算法和贝叶斯估计法。块匹配算法的算法由于原理简单，容易设计实现等特点，得到了最广泛的应用。本文将重点介绍以下几种块匹配算法，以及它们的演进发展过程，包括全搜索算法、三步搜索法、新三步搜索法、四步搜索法、菱形搜索法和自适应十字搜索算法，通过TATLAB对各种算法的执行速度和计算精度进行了比较。
1.2国内外研究现状
我们所研究的块匹配算法，是在这样一个假设下进行的，这一假设是符合实际视频序列的内在规律的，认为误差函数在搜索区域有着最小者，且误差值与最小最之间的距离成正比。基于这着特征的算法经历了以下3个发展阶段。第一个阶段是通过逐步减少搜索步长的方式来找到最佳匹配点，使用这一思想的算法有，二维对数搜索法，交叉搜索法，三步搜索法等算法。这种算法有着很大的缺点。首先，由于算法开始时采用的搜索步长通常比较大，所以不能加快对细小运动序列的搜索速度；其次，由于帧间的亮度变化、孔径问题、局部纹理等的问题，导致在整个平面内，误差函数的取值单调的假设不成立，如果算法开始发生错误，容易陷入局部最优点的误区。
第二个阶段时，通过对之前算法的改进产生了多种的快速改进型算法，其中包括，新三步搜索法，四步搜索法，六边形搜索算法和菱形搜索算法。这些算法都会在第三章进行详细的介绍。对大量的视频序列的研究发现最佳匹配块，即运动矢量集中在搜索窗口的中心位置上，运动矢量具有中心偏置特性。第二阶段的算法利用这一特性，极大的改进了搜索的效率和鲁棒性，这也使得在1999年被MPEG4国际视频标准所采用。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/dzxx/txgc/1151.html
