1、 本科毕业设计 （ 20 届） 基于群智能优化快速运动估计方法研究 所在学院 专业班级 电子信息工程 学生姓名 学号 指导教师 职称 完成日期 年 月 - 1 - 摘 要 近些年来，伴随着人类社会的进步，科学技术的发展，信息技术已全面服务于社会生产和生活的方方面面，人们对信息处理和信 息交流的要求也越来越高。运动估计作为视频压缩编码的核心技术之一，在现代图像以及视频处理中处于十分重要的地位。 快速运动估计作为运动估计的一部分，虽然在生产生活中已经得到广泛应用，但其自身还存在着许多不足之处。群智能优化方法作为一个新兴的研究领域，为复杂优化的问题求解提供了一个有效手段，现已为许多学者所关注，并在许
2、多领域得到广泛地应用。这类算法虽然能够寻找到全局最优解，提高搜索的速度，但是模式的选择比较复杂，搜索的精度也有待提高。 针对群智能优化算法的不足之处，文章提出了一种基于生物种群优化的快速运动估计算法 ，该算法可以提高视频编码中运动估计的性能。它以运动矢量的特性为基础，通过生物种群优化算法的迁徙与变异操作来寻找全局最优解，并且采用迭代终止策略，这样就进一步简化了运算的复杂度。实验结果表明，该算法的整体性能高于其它的群智能优化搜索算法，他能够有效地兼顾起搜索的精度与搜索的速度。由于该算法的这些性能，且实现简单，适用广泛，因此能够很好地实现实时编码的需求。 关键词： 运动估计；快速运动估计；群智能优
3、化；优化问题；生物种群优化 - 1 - Abstract In recent years, with the progress of human society, the development of science and technology, information technology has been service in all aspects of social production and life. People on the information processing and information exchange requirements are getting hi
4、gher and higher. Motion estimation as one of the core technology in video coding, it is very important in the modern image and video processing. Fast motion estimation is a part of motion estimation, although it has been widely used in production and life, there are still many itself inadequacies. S
5、warm intelligence optimization methods as an emerging area of research, providing an effective means for complex optimized problem, now it has been concerned by many scholars, and it is applied in many fields. Although the algorithm can search for global optimal solution, improving the search speed,
6、 but the selection of modal is complex, the search accuracy also needs improved. For the shortcomings of swarm intelligence optimization methods, this paper presents a new fast motion estimation algorithm based on biological populations optimization, the algorithm can improve the motion estimation p
7、erformance in video coding. It is based on the characteristics of motion vector, and according to the migration and mutation operation of biological populations optimization algorithm search for global optimal solution, and then adopt the iterative termination strategy, further simplify the computat
8、ional complexity. The results show that the overall performance of the algorithm is higher than other swarm intelligence optimization algorithms, and can effectively take into account the searching accuracy and searching speed. For the performance of this algorithm, the implement is simple and the u
9、se is wide, so it can meet the needs of real-time video encoding. Key Words: Motion estimation; Fast motion estimation; Swarm intelligence optimization; The problem of optimization; Optimization of biological populations - 2 - 目 录 1 引言 . 1 2 运动估计（ ME） . 2 2.1 运动估计的发展阶段 . 2 2.1.1 全搜索算法 . 2 2.1.2 规定最大
10、搜索步数的快速搜索算法 . 3 2.1.3 不限搜索步数的快速搜索算法 . 3 2.1.4 混合模型搜索法 . 3 2.2 块匹配算法（ BMA） . 3 2.2.1 全搜索算法（ FS） . 4 2.2.2 改进的全搜索算法 . 5 2.3 快速运动估计 . 6 2.3.1 多分辨率的快速块匹配方法 . 6 2.3.2 固定搜索模式的快速块匹配 方法 . 6 2.3.3 自适应的快速运动估计算法 . 6 3 群智能优化 . 7 3.1 优化问题的分类 . 7 3.2 动态优化 . 8 3.3 群智能优化算法 . 8 3.3.1 群智能优化算法的基本原理 . 9 3.3.2 群智能优化算法的不
11、足之处 . 9 3.3.3 群智能优化算法 的分析与展望 . 9 4 群智能优化快速运动估计算法 . 10 4.1 生物种群优化快速运动估计算法 (MBO)简介 . 10 4.2 生物种群优化快速运动估计算法 (MBO)流程 . 11 4.3 基于生物种群优化的快速运动估计算法 (MBO). 12 4.3.1 种群的选择与适应度 (HSI)的计算 . 12 4.3.2 迁徙操作与变异操作 . 13 4.3.3 迭代终止 策略 . 16 5 仿真结果与分析 . 17 6 结论与展望 . 20 致 谢 .错误 !未定义书签。 参考文献 . 21 附录 1 MBO 算法主要程序 . 23 附录 2
12、科研论文 . 25 - 1 - 1 引言 进入 21 世纪以来，全世界的信息化程度越来越高，人类开始进入高速发展的阶段。今天的社会，由于信息化技术已全面服务于社会生产和生活的方方面面，而常被人们称之为信息化社会。因此可以说，在信息化社会中，人们所做的相当一部分工作就是对信息的处理与传输 1。 近些年来，由于信息技术的发展，图像处理的技术也得到了快速的发展，在理论和应用上都取得了重大的进展。运动估计作为视频压缩编码的核心技术之一，在现代图像以及视频处理中应用十分广泛。 运动估计作为一种视频压缩编码技术，它有许多种不同的算法，并且应用于许多不同的领域，有着各自的功用。运动估计算法虽运用十分广泛，但
13、也存在着许多不足之处。快速运动估计作为其中的一部分，与普通的运动估计方法不同，其在效率应用以及速度方面能够满足人类更高的要求。 群智能优化算法是一个新兴的研究领域，为复杂优化问题的求解提供了一种有 效的研究手段，目前已引起相关领域学者的广泛关注。 并在许多领域得到了成功地应用。目前，已有的群智能理论和研究证明群智能方法是一种能够有效解决大多数优化问题的新方法，更为重要的是，群智能的分布式和并行性特点为处理大量的数据提供了可靠的技术保证。无论是从理论研究还是从应用研究的角度分析，群智能理论及应用研究都具有重要的学术意义和现实价值。 群智能优化快速运动估计方法作为群智能优化算法的一种，已然成为一种
14、新的技术算法而应用于更广阔的领域。 生物种群优化是关于生物物种地理分布的研究，主要研究生物种群分布的数学模型，包 括物种的迁徙过程，变异过程以及相邻栖息地之间物种的分布情况。为了提高视频编码中运动估计的各种性能，文章提出了一种新的基于生物种群优化的快速运动估计算法（ MBO） 2。该算法研究的基本思想是根据栖息地之间物种的迁徙来完成信息的流通，通过调整迁徙过程中的迁入率与迁出率、迁徙时间间隔与迁徙策略来实现信息的共享，以提高栖息地的适应度，并通过相关物种的变异操作来达到物种新的迁徙，这样就能得到较高的适应度值（ HSI），也就进一步接近了最佳匹配点的准确值。 - 2 - 2 运动估计（ ME）
15、 运动估计，简单地说，就是对每一个运动着 的物体进行位移估计。它的思想主要是将图像序列的每一帧分为许多互不重叠的宏块，并假设宏块中像素的位移量相同，然后根据相关的匹配准则寻找与当前宏块最相似的块，匹配块与当前块的相对位移就称之为运动矢量，而得到运动矢量的这一过程就叫做运动估计。 通过运动估计可以有效地减少视频图像帧间时间的相关性，去除帧间的冗余度，这样可以使视频传输的比特数大为减少。有效的运动估计还可以减少运动补偿残差帧中的能量，并且能够明显提高视频编码时的压缩性能。 运动估计是任何一个视频压缩系统中的重要组成部分，因为它可以通过利用存在于视频序列 中的时间冗余度达到有效的压缩。运动估计的目的
16、 ,就是为了搜索出当前块的运动矢量 ,并进行相应地编码。 运动估计是视频压缩中耗时最多的模块，它在视频压缩技术中扮演着一个至关重要的角色，其搜索速度不仅直接影响到整个编码器的编码速度，还影响编码之后图像的质量 2。在通常的视频压缩编码过程中，运动估计占用了总计算量的60 80%3。近几年，新的视频编码标准陆续推出，大都采用了更为复杂并且高效的新技术比如层间预测、视点间预测等，这使得计算量更加复杂化。因此，寻找简单高效的运动估计算法一直是视频编码领域研究的重点与热 点。 运动估计方法主要有像素递归法，块匹配算法，贝叶斯估计算法与光流法。其它分法还可以分为快速运动估计法，混合运动估计法，分层运动估
17、计法，时空相关性运动估计法和自适应运动估计法。 2.1 运动估计的发展阶段 2.1.1 全搜索算法 全搜索算法主要是在一个预先定义的搜索区域内，把当前块与参考帧中所有的块进行比较，并从中寻找具有最小匹配误差匹配块的这一过程 4。 全搜索算法思想虽然简单，它主要是对搜索区域内的所有点进行搜索，是最优的运动估计算法，但也是计算量最大的运动估计算法。它并不适合进行实时的- 3 - 编码，因此减 少搜索的点数，加快搜索的速度已成为当前研究的主要发展方向。 2.1.2 规定最大搜索步数的快速搜索算法 规定最大搜索步数的快速搜索算法的优缺点主要有： 1）最大的搜索步数是一定的； 2）采用特定模板进行搜索，
18、可以减少搜索点数，并加快搜索的速度； 3）由于规定最大的搜索步数，可计算出最坏情况下的运算量与存储量； 4）容易陷入局部最优的局面。 其主要代表方法有：三步搜索法，新三步搜索法，四步搜索法等 4。 2.1.3 不限搜索步数的快速搜索算法 当视频序列运动较为剧烈时，步数固定的模板匹配算法因为容易陷入局部 最优，这样就使得视频序列编码的质量大大下降，于是提出了步数不限的快速模板匹配方法，该算法的主要特点是：搜索步数没有限制，搜索模板种类的多样性 4。 代表性的算法主要有：基于块的梯度下降法、钻石形搜索法、六边形搜索法。 2.1.4 混合模型搜索法 由于物体运动的千变万化，很难用一种简单的模型进行相
19、应地描述，也很难用一种单一的算法来搜索最佳运动的匹配矢量，而实际上大多采用多种搜索算法相互结合的方法，这样可以在很大程度上提高预测的有效性和准确性 4。 混合模型搜索法常用的算法主要有：交叉钻石形搜索法、交叉钻石 六边形搜索法、非对称十字形多层次六边形格点运动搜索算法。 2.2 块匹配算法（ BMA） 在已出现的运动估计算法中，基于块匹配的运动估计算法因其搜索简单易于实现，目前被大多数国际视频编码标准所采用。它是目前使用最广泛的运动估计算法，它凭借简单的算法以及简便的硬件实现广受人们的欢迎。它具有简单、实用等优点，在 MPEG-1， MPEG-4， H.263等许多视频编码标准中都采用了这种技
20、术。 - 4 - 块匹配算法（ BMA）的基本思想是：把当前图像帧均匀地划分为 N N像素的宏块，并且假定位于同一宏块内的所有像素具有相同的位移，在参 考帧中对预先确定的一个搜索区域进行位移匹配运算，得出每个宏块的运动矢量。在传输时，仅仅传输宏块信息、运动矢量与预测误差，而无需传送每个像素的数据，这就大大降低了实际传输的比特数 5。目前，块匹配算法 (BMA)已经在精确度和复杂性之间提供了一个很好的折中，并且在实际的视频编码系统中取得了巨大的成功。人们也在这种思想的基础上提出了许多相关性的算法，如基于搜索模式的快速块匹配算法和多分辨率下的块匹配算法等。 虽然现在的块匹配算法应用十分广泛，然而基
21、于块匹配的运动估计技术尚存在一些不足： 首先，尽管三步搜索法、四 步搜索法、六边形搜索法、基于块的梯度下降搜索法、菱形搜索法等多种快速运动估计算法能够减小搜索的点数，提高搜索的速度，但是这些算法均在一定程度上以牺牲运动补偿后的质量为代价，也就是它会影响编码后的图像质量。 其次，以宏块为单位进行的运动估计，假如同一个宏块中包含两个或两个以上具有不同运动形式的物体，或在一个边界宏块中，对象被较强的背景所影响，那么经过运动补偿后，就有可能产生不连续的物体边界，从而影响运动补偿后的视觉效果以及编码的效率。 再次，虽然 H.264/AVC标准提出了较为先进的运动估计技术，提高了编码的效率，但是在运动估计
22、过程中，它的匹配准则仍是基于灰度图像信息的，也没有将物体边界的连续性作为考察的主要因素 6。 目前常用的块匹配运动估计算法有很多种，如全搜索法、三步法、共轭方向搜索法、二维对数搜索法、交叉搜索法、菱形搜索法以及四步搜索法等。 2.2.1 全搜索算法（ FS） 目前最常用的运动估计方法中，全搜索算法（ FS）是对给定搜索区域内的所有点进行匹配，它的搜索精度很高，因此能够得到最佳的运动估计效果。 该算法为了得到最优的运动矢量，对搜索范围内的每一个像素点都进行相应的匹配。块匹配算法估计一个像素移 动时，取以该像素为中心的其中一个子块，- 5 - 然后在前一帧图像中所有可能的位置处寻找一个与之最匹配的
23、子块，该子块的中心与当前像素的位移差即为估计的位移矢量，我们将这种搜索方法称之为全搜索算法（ FS） 1。 从数学角度考虑，运动估计算法实际上是一个求子块匹配的过程，可采用均方误差或平均绝对误差作为判决准则。采用全搜索算法进行运动估计时要求选择合适的子块尺寸，子块尺寸较小时，块内像素运动的一致性较好，运动估计的准确性较高，而相应的编码传输时的运动矢量码率就会增大，计算量也会随之增大；当子块尺寸较大时，编码传输时的运动 矢量码率会变小，计算量将会随之减小，但运动估计的准确性则较低，不能进行有效的运动补偿预测，其主要原因是块内像素运动的一致性相应地变差 7。 在全搜索条件下，块匹配算法达到全局最优
24、，精度也达到最高，但其缺点是运算量很大，计算较为复杂，实时性不高，且采用全局最优的全搜索法时，运动估计要占到整个编码运算量的近 80%，随着搜索半径的不断增大，其运算量也成倍地增长，从而导致整个编码过程时间消耗过多，不适合实时的应用。 2.2.2 改进的全搜索算法 传统的全搜索块匹配算法中由于其性能容易受到待稳定图像序列中各种噪声的 影响，针对这个不足，朱长征、沈振康提出了一种改进的全搜索块匹配算法。在新的匹配准则中，搜索区域中图像序列的当前帧与参考帧所对应的像素对与匹配结果是否有影响，完全取决于它们间的灰度值之差与预先设定的门限值进行比较的结果，而与外界的因素无关 8。当对应的灰度值之差不超
25、过该门限值的像素对时，则对匹配结果有贡献，而且贡献的大小受到与像素对位置相关的影响，否则该像素对对匹配结果无贡献 8。 改进的全搜索块匹配算法延续了传统的全搜索块匹配算法的基本思想，且它对匹配准则也进行了相应地改进。结果分析表明，改进的全搜索算 法的估计值更接近真实值。因此，改进的全搜索算法具有很强的抗噪性能。 该算法虽具有良好的性能，但是还存在着一些不足：（ 1）算法所需的运算时间较长；（ 2）门限值的选择问题有待解决；（ 3）算法需要构造一个加权模块，如何构造与为什么如此构造这个恰当的加权模板也是一个待解决的问题。 - 6 - 2.3 快速运动估计 为了减少运动估计消耗的时间，提高编码效率
26、，近年来国内外学者提出了各种快速运动估计算法。其中，新三步法、钻石法、六边形搜索法等，都是利用运动矢量的中心偏置分布特性来进行搜索模板与搜索方法设计的，这样既加快搜索的速度，而 且在视频序列运动较为平缓的情况下表现出良好的运动估计效果 9。 快速运动估计算法可分为：多分辨率或多层次的快速块匹配方法、降低匹配准则复杂度的快速块匹配方法、固定搜索模式的快速块匹配方法、基于时空相关性和视觉特性的快速块匹配方法。 2.3.1 多分辨率的快速块匹配方法 用低分辨率块的运动矢量预测较高分辨率块的运动矢量，或用同一分辨率的大尺寸块运动矢量预测其内部子块的运动矢量，并在其后续搜索中做进一步的修正，这种方法称之
27、为多分辨率或多层次的运动估计快速算法。 其缺点是在构造多层 /多分辨率图像时，会有较大的计算 复杂度，且内存需求也很大。 2.3.2 固定搜索模式的快速块匹配方法 固定搜索模式的快速块匹配方法中主要的算法有三步法、四步法、梯度下降法、菱形法、十字法和六边形法。这类算法搜索模式固定，搜索点数少，实现简单，计算复杂度较低。它的缺点是，没有能够利用图像本身的相关信息，不能够自适应地改变搜索的起点与搜索半径。针对固定搜索模式的不足，人们又提出了许多改进的算法，主要是针对预测搜索起点、终止条件、改进搜索模板与宏块运动类型的判别 9。 2.3.3 自适应的快速运动估计算法 自适应快速运动估计算法结合了变块尺寸 运动估计的特点，利用运动矢量的时空域相关性，预测初始搜索中心。它采用多种搜索模式，提出了搜索模式自适应的选择机制，以节省不必要的搜索点数，加快搜索速度，并避免陷入局部最优。该算法使整个运动估计的耗时降低了近三成，同时保持编码效率的基本不变 10。
