摘 要

运动估计是常用的序列图像压缩编码方法之一，由于图像序列两帧之间存在相当程度的关联性，通常情况下两者之间的数据变化量一般很小，表现为移动物体所在的空间位置稍有差异， 运动估计针对于此类图像序列能够消除时间上的数据冗余，从而提高传送效率。块匹配作为运动估计方法中较常用的算法，通过某一路径搜索得到目标图像块的匹配图像块。对于不同种类的块匹配方法而言，搜索匹配块方法的不同决定了块匹配方法的搜索速度和搜索准确性上的差异。常用的快速块匹配方法都是在基本块匹配方法全搜索的基础上对搜索路径进行了修改得到的，在搜索速度和搜索精度上有一定的提升。然而如何寻找到最为合适的快速块匹配算法仍是当前图像压缩领域的热门研究方向之一。

本文主要研究工作包含以下几个方面:

1. 对运动估计的概念进行简单的介绍，了解运动估计的基本步骤。对块匹配的原理、匹配准则进行了解释，对于几种较经典的块匹配运算方法的原理和步骤进行了说明。
2. 针对经典的块匹配算法全搜索算法进行图像估计的实现，重点对全搜索算法对图像序列的预测效果进行了分析，并针对宏块尺寸对于图像预测效果的影响进行了研究。实验结果证明宏块尺寸越小预测效果越好，但搜索时间越长。
3. 针对经典的快速块匹配算法三步搜索法进行图像估计的实现，重点研究三步搜索法对图像序列的预测效果，同时对比三步搜索法和全搜索法对同一图像序列的搜索效果，研究结果表明三步搜索法搜索效率更高，但全搜索法预测效果略好。

关键词：图像编码, 运动估计, 块匹配, 全搜索, 三步法

Abstract

Motion estimation is one of the most common methods of image sequence compression coding, because there is a certain correlation between two consecutive frames in the image sequence, the data variation between the two is generally very small, which shows that the space position of moving object is slightly different, and the motion estimation can eliminate the data redundancy in this kind of image sequence. Block matching is a more commonly used algorithm in motion estimation, and the matching image block of target image block is obtained by a path search. for different block matching methods, the search speed and search accuracy of block matching method are determined by different search methods. Common fast block matching methods are all based on the basic block matching method to search the search path on the basis of the modified, in search speed and search accuracy of a certain upgrade. However, how to find the most suitable fast block matching algorithm is still one of the hot research directions in the field of image compression. The main research work in this paper includes the following aspects:

1. The concept of motion estimation is briefly introduced to understand the basic steps of motion estimation. This paper explains the principle and matching criterion of block matching, and explains the principles and steps of several classical block matching algorithms.
2. According to the classical block matching algorithm, the whole search algorithm is used to realize the image estimation, and the effect of the whole search algorithm on the image sequence is analyzed, and the effect of the macro block size on the image prediction is studied. Experimental results show that the smaller the macro-block size, the better the prediction effect, but the longer the search time.
3. The classical fast block matching algorithm for the three-step search method for the realization of image estimation, this paper focuses on the three-step search method to predict the image sequence, at the same time comparing the search effect of the three-step search method and the full search method to the same image sequence, the results show that the three-step search method is more efficient, but the whole search method has a little better prediction effect.

Keywords: image coding, motion estimation, block matching, full search method, three-step search method

目 录

摘 要 I

Abstract II

第一章 绪论 1

1.1研究背景及意义 1

1.2块匹配研究现状及发展方向 2

1.3本文主要研究内容及结构安排 3

第二章 基于块匹配的运动估计算法原理综述 4

2.1 运动估计 4

2.1.1 块匹配运动估计原理概述 4

2.1.2 块匹配搜索准则 4

2.2 典型块匹配搜索策略原理及分析 5

2.2.1 全搜索法 6

2.2.2 二维对数法 7

2.2.3 三步搜索法 8

2.2.4 菱形搜索法 8

2.2.5 四步搜索法 10

2.3 块匹配运动估计评价 12

2.4 本章小结 12

第三章 全搜索法算法实现与分析 13

3.1 全搜索算法实施具体描述 13

3.1.1 初始化与帧提取 13

3.1.2 全搜索计算运动矢量 14

3.1.3 重构预测图像和误差图像 15

3.1.4 计算PSNR值并绘制运动矢量图 15

3.2 实验结果及分析 16

3.2.1 全搜索法实现图像压缩效果及分析 16

3.2.1宏块尺寸对图像压缩影响分析 18

3.3 本章小结 20

第四章 三步搜索法算法实现与分析 21

4.1 三步搜索算法实施具体描述 21

4.1.1 三步搜索法计算运动矢量 22

4.2 三步搜索法实现图像压缩效果及分析 23

4.3 三步法与全搜索法预测效果比较与分析 25

4.4 本章小结 26

第五章 总结与展望 27

5.1 本文工作总结 27

5.2 展望 27

中外文参考文献 28

致谢 30

第一章 绪论

1.1研究背景及意义

随着信息技术的发展和社会的不断进步，多媒体技术开始兴起，视频和图像等信息以广泛性，确切性，直观性等一系列深受人们欢迎的优点而得到广泛的使用。而当人们发现数字信号具有方便计算机、系统可靠性高、处理易于传输的优势，便开始以数字化的形式储存和传输视频和图像。然而随着影像中所携带的信息量的爆发式增长，具有庞大数据量的数字图像通信对现有的有限带宽带来严峻的考验，从1948年提出电视信号数字化开始，无数研究者希望通过不同的方式来使得图像在尽可能不失真的情况下产生更高的压缩率。^[2]。这既是对过去对于图像压缩编码领域的融合和总结，也是对以后的图像编码压缩领域研究的约束和指导。

针对动态图像的编码压缩，由于图像连续两帧之间存在一定的关联性，两者之间的数据变化量一般很小，背景并没有非常明显的变化，只是表现为移动物体所在的空间位置略微不同， 便存在着时间上的数据冗余。^[3]为了消除冗余，常用采用运动补偿帧间预测技术。而好的的运动补偿的关键是运动估计，运动估计和运动补偿技术是紧密结合的。运动估计是检测两幅图像中同一物体的位置，而运动补偿便是找到该物体是从另一幅图像中那个位置移动过来的，计算该物体的运动预测矢量。常用的运动估计和运动补偿方法有块匹配法，像素递归法与相位相关法。然而因为块匹配的复杂度相对较低，因此在大多数运动图像压缩中采用块匹配方法。块匹配就是将当前帧划分为多个小的图像块,对于当前帧中的每一个图像块,在参考帧的对应搜索窗口内搜索一个同样大小的最佳匹配块,继而确定这个图像块的运动向量。针对块匹配算法的特点，通常通过选择初始搜索点，匹配准则和搜索策略三个方面来提高块匹配算法的效率。^[4]

块匹配算法已经在运动估计领域得到了非常广泛的运用，经过多年的研究已经在最基本的全搜索方法上发展出了多种搜索方法来提高块匹配方法的搜索效率，然而仍存在着搜索匹配块速度较低，易陷入局部最佳匹配块等缺点，为了得到搜索效率更高的全域最佳匹配块，人们正在不断努力着。^[5]

1.2块匹配研究现状及发展方向

块匹配算法最初起源于上世纪七十年代美国在飞行器辅助导航系统等军事应用研究中，此后在军事，医学等领域运用广泛。正因为块匹配能够有效的减少帧间相关性，因此在各类国际图像编码标准中都有运用，例如MPEG-1，MPEG-2，MPEG-4，H.261，H.263以及H.264等编码标准中。相较于像素递归法和光流法，块匹配计算复杂度最低。^[6]

针对图像序列的每一帧，将其分成大小相同的M×N个宏块（通常情况下M=N），然后根据一定的匹配原则对于某一当前帧中的每一宏块参考帧中限定的搜索区域内寻找到和当前块最为相似的宏块，成为匹配块。通过计算匹配块和当前计算宏块的相对位置计算得到相对位移，相对位移便是当前计算宏块的运动矢量。块匹配更准确，得到的补偿残差更小，编码效率更高。

评价块匹配算法是否性能较高，主要通过搜索速度和搜索精度两方面来评价。^[7]从刚开始提出块匹配算法开始，人们为了追求得到最优的运动矢量，不断的提出新的算法，希望能够在降低算法复杂度的同时，找到最合适的匹配块。在所有块匹配运动估计算法中，搜索精度最高的是最初提出的全搜索法，全搜索会对参考帧内限定搜索范围每一个像素点进行块匹配运算得到最优的运动矢量。但对于图像像素点较多或搜索限定区域较小时运算时间较长。人们针对全搜索法搜索点数过多的问题又在此基础上提出了三步法，交叉法和二维对数法，这些方法搜索点数大大减少，但是存在可能陷入局部最优匹配块的问题。^[8]由此，新三步法，基于块的梯度下降法和新四步法产生了，这些方法利用运动矢量具有中心偏移的分布特性，减小了陷入局部最佳匹配点的可能性，提高了运算速度。根据当前计算结果浮动调整下一步搜索步长的动态搜索窗调整法提高了一定的算法性能。后来又出现了一些利用相邻块运动相关性的算法，例如预测搜索法，自适应运动跟踪法，这些方法把反映当前块的运动趋势的预测点作为初始搜索点，在一定程度上提高了搜索速度和预测的准确性。正由于块匹配算法在运动估计领域的广泛运用，菱形法在1991年被收入MPEG-4 国际标准收入验证模型。

尽管块匹配方法已经相对成熟，但是这些方法都是基于传统块匹配方法上做出一些改进，因为传统块匹配认为，宏块之间运动距离较小，目标运动物体移动距离变化不大。所以并不太适用于运动物体移动距离变化较大的序列图像。^[9]但是当参考帧与当前帧相对应的宏块存在运动距离剧烈变化时，不连续或者形状变化时，以上方法无法适应。研究学者针对这一类型的序列图像的运动估计，提出了可变块匹配的运动估计算法。这正是目前块匹配发展方向之一。在可变块匹配算法中，当前帧被不留缝隙的分为三角形，四边形等宏块，在一定的匹配规则下，在参考帧中寻找对应的匹配块。可变块匹配很好的解决了两帧图像间运动物体发生剧烈变化的情况，提高了匹配的准确性。

半像素块匹配也是块匹配当今研究方向之一。因为传统块匹配方法计算最小都是以单个像素为计算单位来计算预测宏块的运动位移从而比较确定最佳匹配块，然而在实际的图像序列中有很多情况下物体运动或者变化并不是以单个像素为最小单位变化的，这就导致在计算匹配块运动矢量时存在一定误差，影响了图像的压缩效率。运用半像素或是四分之一像素技术，可以提高计算运动矢量的精度。^[10]

1.3本文主要研究内容及结构安排

本文的主要工作侧重于在熟悉认识图像序列块匹配运动估计方法的，分析并总结常用的经典块匹配搜索算法。选择其中一种较为常用的算法针对不同的图像序列进行运动估计压缩编码，得到复原后的预测图像和重构误差，并通过压缩信噪比来分析压缩效果。本文共分为五章，各章主要内容如下：

第一章绪论部分，主要介绍了课题的背景及研究意义，通过查阅相关国内外文献资料，较系统的介绍块匹配算法的研究现状及发展方向。

第二章常见块匹配方法算法分析，从原理的角度系统性分析多种常见的块匹配算法，主要介绍各种算法的理论模型，搜索方法和搜索步骤，分析各种经典算法的适用范围和主要优缺点。

第三章全搜索法算法实现与分析，根据全搜索算法原理实现对实验图像序列的运动估计，并将预测重构帧和参考帧对比分析，研究搜索半径对于压缩信噪比与重构图像效果的影响，分析并得出相关结论。

第四章三步搜索法算法实现与分析，根据全搜索算法原理实现对实验图像序列的运动估计，并将预测重构帧和参考帧对比分析，研究搜索半径对于压缩信噪比与重构图像效果的影响，对比全搜索法与三步法对于同一图像序列相同条件下的压缩效果，分析并得出相关结论。

第五章总结与展望，总结了全文的研究成果,分析存在的问题，并对运动估计块匹配算法研究的最新方向进行展望,提出了进一步的研究工作。

第二章 基于块匹配的运动估计算法原理综述

2.1 运动估计

2.1.1 块匹配运动估计原理概述

运动估计有基于图像块和基于像素两种估计方法，其方法类似，一般采用基于图像块估计，故在此介绍基于图像块的方法。首先会将一副图像分为大小相等的若干块，再将每一块对应在参考帧（与此帧图像相邻的上一帧图像）的对应位置，整个过程叫做运动估计。运动估计常出现在帧间预测编码中，用于压缩图像，提高传输效率。而在计算中得到的位移差通常被称为运动矢量，运动矢量用来描述图像块在水平和垂直两个方向上位置的变化。

图2.1 运动估计过程图

决定运动估计效果的整体效率的因素有三个，一是初始搜索点的选取，初始搜索点的选取一般有两种，直接选择参考帧中目标块的中心位置，或者选择预测起点。参考帧目标块中心位置方法简单，无需计算，但初始步长较大，并且易陷入局部最优点；通过预测来确定初始搜索点能够让搜索次数变少。^[11]关于搜索点的选取在此不过多论述。另外两个因素是搜索准则和搜索方法，下面将详细介绍。

2.1.2 块匹配搜索准则

搜索准则是图像块和目标匹配块的相似程度的重要依据，搜索准则的选取对于算法的简易程度及运行结果的速度都和匹配 的原则性有很大关系。常见的匹配准则有四种， 最小均方误差（MSE），最小绝对值差（MAD），归一化互相关函数（NCCF）和求和绝对误差（SAD）。下面对四种函数一一介绍:

1. 最小均方误差（MSE）

（2.1）

计算当前宏块与目标宏块之间的均方误差，比较搜索范围内所有的MSE值，取MSE值最小点为最佳匹配块。

1. 最小绝对值差（MAD）

（2.2）

相较于MSE不需要使用平方运算，计算更加简单。计算当前宏块与目标宏块之间的最小绝对值之差，比较搜索范围内所有的MAD值，取MAD值最小点为最佳匹配块。

1. 归一化互相关函数（NCCF）

（2.3）

归一化互相关函数得到搜索范围内最大值时取得最佳匹配块，算法有开方与平方运算，计算较为繁琐。

1. 求和绝对误差（SAD）

（2.4）

求和绝对误差与最小绝对值差类似，只是缺少做平均步骤，实现较MSE更简单，同样在搜索范围内取得最小值时得到最佳匹配块。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：