基于群智能优化快速运动估计方法研究【文献综述】.doc

1、 1 毕业论文文献综述 电子信息工程 基于群智能优化快速运动估计方法研究 摘要： 本文主要针对群智能优化快速运动估计，介绍运动估计的几种分类、算法以及它们之间的优缺点，并作相应的比较。由于群智能化是一个新兴的研究领域，对于一个新兴的领域而言，有各种不同的方法对其进行着研究。而在对快速运动估计的应用方面，许多领域都运用到了这一手段，当然所运用的方法却各不相同，它们之间有着各自的优缺点，要选择性地加以利用。 关键词： 运动估计；块匹配；快速搜索；自适应搜索；快捷高精度法；总结 1. 引言 近些年来，随着各项科学技术的 全面发展，群智能优化方法作为一个新兴的研究领域，为复杂优化的问题求解提供了一个有

2、效手段，现今已经为许多学者所关注，并在许多领域得到应用。运动估计是视频压缩编码中的核心技术之一，在现代图像以及视频处理中应用十分广泛。而群智能优化的快速运动估计方法已然成为一种新的技术而被运用于各种领域。各种运动估计方法有着其各自的特点，它们既相互联系，又相互区别。只有弄清楚各自的优缺点，才能更有效地运用到实际生活中去。 2. 运动估计 运动估计，简单地说，就是对每一个运动物体进行位移估计。它是将图像序列的每一帧分为许多互不重叠的宏块 ，并假设宏块中所有的象素位移量相同，然后根据一定的匹配准则找出与当前块最相似的块（匹配块），匹配块与当前块的相对位移称为运动矢量，得到运动矢量的这个过程就叫做运

3、动估计。 通过运动估计可以有效地减少视频图像帧间时间的相关性 ,并 可以去除帧间冗余度，使视频传输的比特数大为减少 。有效的运动估计还可以减少运动补偿残差帧中的能量 ,能够明显提高视频的压缩性能。 运动估计有很多种不同的算法，不同情况下将使用不同的算法。各算法有其自己的优缺点，在选择算法时应该对各种方法进行比较，选择合适的算法来进行运算。下面将论述几种常用的 算法以及它们的优缺点，并做适当的总结。 3. 运动估计算法及优缺点 运动矢量估计方法有很多种，主要有块匹配算法、 递归估计法、贝叶斯估计法和光流法。 其他2 分法还可以分为快速运动估计法、混合运动估计法，分层运动估计法，时空相关性运动估计

4、法和自适应运动估计法。 3.1 块匹配算法（ BMA） 块匹配运动估计算法是目前使用最多的运动估计算法，它凭借简单的算法以及方便的硬件实现而广受人们的青睐。目前块匹配运动估计算法有很多，如全搜索法、三步法、共轭方向搜索法、二维对数搜索法、交叉搜索法、菱形搜索法以及四步搜索法 等。 3.1.1 全搜索算法 块匹配算法估计一个像素移动时，取以该像素为中心的一个子块，然后在前一帧图像中所有可能的位置寻找一个与之最匹配的子块，该子块中心与当前像素的位移即为估计的位移矢量。我们将这种搜索方法称为全搜索算法，也称为穷尽法或遍历法 1。 从数学角度方面考虑，这是一个求子块匹配的过程，可采用上面提及的均方误差

5、（ MSE）或平均绝对误差（ MAD）作为判决准则。采用全搜索算法进行运动估计时要求选择合适的子块尺寸。子块尺寸较小时，块内像素运动的一致性较好，运动估计的准确度较高，而相应 的编码传输的运动矢量码率会增大，计算量也会随之增大。当子块尺寸较大时，编码传输的运动矢量码率会变小，计算量将会随之减小，但是运动估计准确度较低，不能进行有效的运动补偿预测，主要原因是块内像素运动一致性变差 2。 在全搜索条件下，块匹配算法达到全局最优，精度也达到最高，但其缺点是运算量很大，计算复杂，实时性不高。 传统的全搜索块匹配算法 由于其 性能容易受到各种噪声的影响 ， 针对这个不足 ， 朱长征 、 沈振康提出了一种

6、改进的全搜索块匹配算法 。 在新的 全搜索块 匹配 算法 中 ， 搜索区域 内 图像序列的当前帧 与 参考帧 所 对应的像 素对 ，与 匹配结果是否有 影响完全 取决于它们灰度值之差的绝对值与预先设定的门限值大小 之间 比较的结果 ，而与外界的各种因素无关 3。 3.1.2 三步搜索算法（ TSS） 三步搜索算法（ TSS）是仅次于全搜索算法的次最优运动估计搜索算法，目前应用也十分广泛。三步法就是在上一帧以当前子块为原点，将当前子块在周围 8 个点按照一定的规则进行移动，并且每移动到一个位置时，取出同样大小的子块与当前子块进行匹配计算。步骤如下： （ 1） 从原点开始 ， 选取最大搜索长度的一

7、半为步长 ， 在周围距离步长的 8个点处进行块匹配计算并比较 ， 找 到 最小误差（ MBD） 点 。 （ 2） 将步长减半 ， 中心点移到上一步的 （ MBD） 点 ， 重新在周围距离步长的 8个点处进行块匹配计算并 做 比较。 3 （ 3） 在中心及周围 8个点处找出 MBD点 ， 若步长为 1， 该点所在位置即对应最佳运动矢量 ， 算法结束 ； 否则 ， 重复 步骤（ 2） 。 三步搜索法较全搜索方法，计算量减少了很多，步骤也只需三步，但它对于小运动检测效果不好，当搜索范围大于 7 时，搜索步骤就会增多，不会只有三步。 现在 吴炳昊 、 阮秋琦 、 吴向君 提出了新三步搜索方法（ NTS

8、S），就解决了三步法对于小运动估计效果较差的缺点。它在 第一步搜索时采用了并行思想，有效地弥补了三步搜索法的这种缺陷。 NTSS改进之处在于对外围大模板进行搜索时 ， 同时 也 对内侧的小模板进行 了 搜索 。 外围大模板由最大搜索长度一半为步长的原点周围的 8个点组成 ， 内侧小模板由原点以及原点周围步长为 1个像素的 9个点组成。使用新三步搜索法得到的平均绝对偏差和峰值信噪比均优于三步搜索法得到的结 果， 得到的图像也优于三步搜索法得到的图像 4。 3.1.3 菱形搜索算法 菱形搜索法类似于三步搜索算法，它首先在大菱形中搜索，当最优点位于菱形的中心时，再使用小菱形进行搜索。其中找到一个最

9、佳匹配点的最少搜索次数为 13点，也就是当最佳匹配点位于第一个菱形中心时的这种情况。这种情况由于运动矢量中心偏移的存在占据运动矢量分布的大部分，所以减少最佳匹配点的搜索次数，可以大大降低运动估计运算的复杂度 5。 当前又出现了一种准菱形搜索方法，该方法在图像处于运动复杂的情况下，不仅能根据方向选择来扩大搜索范围，而且能够有效地降低搜索点数与搜索次数。该算法是利用 C语言编程，并结合MATLAB软件来处理典型的图像序列。运算结果表明，与菱形搜索与六角形搜索相比，准菱形搜索法不仅能有效地保持原图像的质量，而且其计 算方便，为人们所欢迎 6。 3.2 快速搜索算法 运动估计快速算法可分为：多分辨率或

10、多层的快速块匹配方法、降低匹配准则复杂度的快速块匹配方法、固定搜索模式的快速块匹配方法、基于时空相关性和视觉特性的快速块匹配方法。 用低分辨率块的运动矢量预测较高分辨率块的运动矢量，或者用同一分辨率大尺寸块运动矢量预测其内部子块的运动矢量，并且在后续搜索中做进一步的修正，我们称这种方法为多分辨率或分层的运动估计快速算法。 其缺点是在构造多层 /多分辨率图像时，会有较大的计算复杂度，且内存需求较大。小波域运动估计是其中的一种典 型。 自从小波引入图像压缩领域以来 ， 小波编码在图像处理中越来越显示出了空间域的许多无法企及的优点 ， 人们纷纷致力于基于小波的视频编码技术的研究之中。基于小波分解域的

11、可变块多分辨率运动估计算法 ，它 是利用小波金字塔结构每层间的相关性 ， 来降低运动估计过程的运算复杂性。4 该 算法是基于小波变换的视频编码中降低时间冗余的重要算法之一 7。 降低匹配准则复杂度的快速块匹配方法的主要两种方式是连续消除法和像素子采样法。 固定搜索模式的快速块匹配方法中主要的算法有三步法、梯度下降法、四步法、菱形法和六边形法。它的缺点是 由于搜索法本身的搜索范围是固定的，没有能够利用图像本身的相关信息，不能够自适应改变搜索起点与搜索半径。针对固定搜索模式的不足之处，人们提出了许多该进的算法，主要可分为：预测搜索起点、终止条件、改进搜索模板与宏块运动类型的判别。 消元算法是一种新

12、的快速运动估计算法，此算法的优点是可以显著降低 H.264 编码器中可变块大小运动估计的复杂度。该算法把传统的分层消元方式应用于 7 块模式中，也就是说，该算法可以消除不必要的搜索过程，从而达到更快速的搜索 8。 3.3 自适应搜索方法 自适应搜索方法是一种新的群智能优 化算法，它已经成功地应用于函数优化问题。由于该算法存在对参数敏感等问题，因此提出了自适应搜索算法。 通过自适应 算法 调整搜索半径 、 搜索步 、 灵敏度等参数 ，可以 提高算法对环境的适应性 、 鲁棒性和在 “ 探索”和“开发”之间的平衡能力 9。结果证明 ，自适应搜索算法 不仅降低了对参数的依赖性 ， 而且成功率高 、 收

13、敛速度快 。 该算法中，个体在其搜索半径内会随机产生一些坐标，找出其中的最佳适应度坐标并计算其信息素。通过对信息素和灵敏度的比较，确定个体的新坐标 10。 该算法充分利用视频序列中当前块的运动状态，根据不同块的运动情况合理 选择运动搜索模板。实验表明，该算法在保证重构图像质量的前提下，编码速度有了显著提高，保证了实时应用的要求 11。 3.4 快捷高精度方法 由于高清数字电视对图像质量有严格的要求，因而它的编码采用了计算十分复杂的高精度运动估计方法，这在视频编码中既占很多资源，又增加了计算的复杂性。现在提出了一种新的快捷高精度方法，该方法结合了不同宏块运动特性的方法，可以自适应选择高精度运动估

14、计方法或简单运动估计方法。它通过改变宏块编码顺序与运动向量预测顺序的关系，可以在减少 70%运算时间的情况下，仍保持与高精度方法 相同的搜索精度 12。 4. 总结 运动估计有着广阔的应用前景，如军事领域，工业过程，商业领域，医学领域以及虚拟现实方面的应用等。运动估计算法是视频压缩编码的核心算法之一 ,然而如何更好地选择运动估计算法以保证计算的精确性与速度，已经成为一个亟需解决的问题。 块运动估计算法是目前所使用的最普遍的一种运动估计算法，它可以分为 全搜索法、三步法、共轭方向搜索法、二维对数搜索法、交叉搜索法、菱形搜索法以及四步搜索法等。全搜索法虽然达5 到全局最优，精度也达到最高，但其缺点

15、是运算量很大，计算复杂度高，实时性不高。而 在 所有的快速搜索算法中， 三步法 因为简单有效而 受欢迎 ，特别适合低码率视频应用，如视频会议和视频电话。该算法适合查找大运动的全局最小 ， 对于小的运动容易陷入局部最小 。四步法相比于三步法所需的搜索点更少。菱形搜索法 适合于小运动和静态场景，它 可以 减少最佳匹配点的搜索次数，并可以大大降低运动估计运算的复杂度。改进的菱形搜索法不仅能根据方向选择来扩大搜索范围，而且能够有效地降低搜索点数与搜索次数。 除了块匹配运动估计算法外，主要的运动估计方法还有 递归估计法、贝叶斯估计法和光流法。象素递归法是预测校正型的位移估算器，它的预测 值可以作为前一个

16、象素位置的运动估算值，或作为当前象素邻域内的运动估算线性组合。贝叶斯法零用随机平滑约束条件，通常采用 Gibbs（随即场）方法来估算位移场，它的主要缺点是计算量大。光流法依据时空图像的亮度梯度得到一个光流场的估计，对于灰度图像和彩色图像，光流法所使用的方法不同。 综上所述，运动估计具有很多种方法，而且每一种方法都有各自的优点与缺点。在图像处理或者其他领域应用到运动估计算法时，需要根据物体本身的需要来选择相对应的运动估计算法来运算。比如需要高精度的运算结果时，就需要运用到全搜索算法，如果需要简便 快捷，则选择三步法、四步法或菱形法。目前已经出现许多改善的运动估计算法，它们在原来的基础上进行了相应

17、的修改，这样既能保持原有的功能，还能改善它们的缺点，适合于更多不同场合的运用，这样就降低了运动估计算法本身的缺点，增加了它们的使用范围。今后一段时间内，仍将有许多科学家致力于研究更好的运动估计算法，群智能优化方法就是有一个典型的例子。 参考文献： 1 朱秀昌，刘峰 .数字图像处理与图像通信 M.北京：北京邮电大学出版社， 2002， 5. 2 王 喆 ，刘贵忠，钱学明 .基于 H.264/AVC 压缩域信息的全 局运动估计方法 J.第 18 届 全国多媒体学术会议（ NCMT2009)， 2009:167 173. 3 朱长征，沈振康 .一种改进的完全搜索块匹配算法 J.红外与激光工程， 20

18、04， 8， 33 （ 4）： 388 391. 4 吴炳昊 ， 阮秋琦 ， 吴向君 .基于新三步搜索法的超分辨率图像处理研究 J.北京电子科 技学院学 报， 2005， 12， 13（ 4）： 40 44. 5 洪波， 余松煜 .基于对象的菱形搜索运动估计方法 J.数据采集与处理， 2001， 3， 16 （ 1）： 110 114. 6 龚涛 ， 丁润涛 .一种改进的有效运动估计方法 准菱形搜索法 J.中国图象图形学 报， 2002， 11， 7（ 11）： 1181 1186. 6 7 魏玉芬 ， 周凯 ， 柳培林 .序列图像的小波域运动估计和补偿技术研究 J.黑龙江八一农 垦大学学报

19、， 2008， 2， 20（ 1）： 78 81. 8 Chan Lim， Hyun-Soo Kang， Tae-Yong Kim， Kook-Yeol Yoo.A Fast Full Search Algorithm for Variable Block-Based Motion Estimation of H.264J.Lecture Notes in Computer Science， 2005， 3804： 710 717. 9 周晖，徐晨，邵世煌，李丹美 .自适应搜索优化算法 J.计算机科学， 2008， 11， 35 （ 10）： 188 191. 10 李秋山，李伟，费宝顶，张珍 .快速自适应运动估计算法 J.计算机工程与应用， 2009， 4， 45（ 8） ： 187 189. 11 Yu-Ming, LeeWen-Chuan Hsu, and Yinyi Lin.An Adaptive Multiple Reference Frame Motion Estimation for H.264 Video CodingJ. Lecture Notes in Computer Science， 2009， 5879： 1244 1250. 12 陆寄远，朝红阳 .一种快捷的高精度运动估计方法 J.计算机科学， 2010， 2， 37（ 2）： 282 285.