（光学工程专业论文）基于遗传算法的运动估计.pdf

摘要 摘要 运动估计作为图像( 或视频) 序列的超分辨率复原和视频压缩的关键技术之一 被越来越多人们所关注。运动估计的好坏决定着图像超分辨率复原和视频压缩的 结果，所以本文主要考虑了运动估计的运算结果和运算时间。 本文首先介绍了块匹配算法的基本原理；其次介绍了全搜索算法，它的结果 精确，运算时间量大，同时实现了快速算法如：二位对数、三步搜索、新三步搜 索、四步搜索、钻石搜索、六边形搜索等；最后，基于遗传算法具有数学简单性和 隐含并行性等特点将遗传算法应用到运动估计中，并模拟生物状态下的变异性， 从而避免了其他算法易于陷入局部最优的情况，最终使用半像素插值，本算法以 较小的搜索运算得到了与全搜索相当的结果，通过试验证明本文算法的可行性和 实用性。 关键词：运动估计遗传算法块匹配插值 a b s t r a c t a b s t r a c t t h e r ei sag r o w i n gi n t e r e s ti nt h ek e yt e c h n i q u eo fs u p e r - r e s u l u t i o no fo b t a i n i n g t h ei m a g ef r o ms t i l li m a g eo rv i d e os e q u e n c e s t h es u p e r - r e s o l u t i o no ft h eo b t a i n e d i m a g e si sd e t e r m i n e db yt h ev a l u eo fm o t i o ne s t i m a t i o n i nt h i sp a p e r , t h ec o m p u t a t i o n t i m ea n dt h ea c c u r a c yo f m o t i o nv e c t o r sa r es t u d i e d f i r s t l y , t h ep a p e ri n t r o d u c e st h et h e o r yo f b l o c km a t c h i n g s e c o n d l y , t h ef u l ls e a r c h a l g o r i t h mf f s a l c a l lf i n dt h eo p t i m a ls o l u t i o nb yt h er e q u i r e dt r e m e n d o u sc o m p u t a t i o n m e a n w h i l e ，s o m eo t h e rf a s tb l o c k - m a t c h i n ga l g o r i t h m s ，s u c ha st h r e e s t e ps e a r c hf r s s ) ， n e wt h r e e - s t e ps e a r c h ( n t s s ) ，f o u r - s t e ps e a r c h ( f s s ) ，d i a m o n ds e a r c h ( d s ) a n dg e n e t i c a l g o r i t h m ( o a ) a r ep r o p o s e d f i n a l l y , b a s e do nt h ep r o p e r t yo fg e n e t i ca l g o r i t h m , t h e m e t h o dg a l lo v e r c o m et h es h o r t c o m i n go fb e i n gl i a b l et ol o c a lo p t i m u m , b yt r e a t i n g m o t i o nv e c t o r sa sc h r o m o s o m ea n dp u t t i n gg e n e t i co p c l a t i o no ni t , t h e nt h e i n t e r p o l a t i o ni so p c r a t c d t h ee x p e r i m e n t a lr e s u l t , t h ep r o p o s e da l g o r i t h mp r e d u c e s b e t t e rp e r f o r m a n c e 脚o r d ：g e n e t i cj d g o r i t h m b l o c km a t c h i n gm o t i o ne s t i m a t i o n 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别标注和致谢中所罗列的内容以外，论文中不包含 其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：萼a 0 砷日期3 吨 r r 一 一 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文成果时署名单位仍然为西安电子科技大学。学校 有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或 部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解 密后遵守此规定) 。 本人签名：刎 导师签名：等庆支军 日期，嘲1 1 日期2 呐j t 第一章绪论 第一章绪论 1 1 运动估计的简单介绍及应用领域 图像序列运动估计的基本任务是从图像序列中检测出运动信息和结构参数。 它是数字视频处理与计算机视觉领域中一个非常活跃的分支，在国民经济和军事 领域的许多方面，如视频压缩编码、目标跟踪、自主导航、机器人视觉和视频监 视等都有着广泛的应用，所以对它的研究受到广泛关注。 研究目的的不同，运动估计的作用也不尽相同。在视频压缩编码中，运动估 计的作用是尽量减小运动矢量和预测误差占用的码率之和，并使重建图像尽量逼 近于原始图像。在计算机视觉中，运动估计的作用是从图像序列中提取运动物体 的运动参数或物体的三维结构用于描述三维世界，这往往要求运动矢量反映场景 中的真实运动。在超分辨率的图像复原中【”，由于许多成像系统，如红外成像仪和 c c d 相机等，在采集图像的过程中，受其固有传感器阵列排列密度的限制，图像 的分辨率不是很高，同时欠采样效应又会造成图像的频谱交叠，使获取的图像发 生降质。这就需要超分辨率复原技术来解决，这个技术的目的就是由序列低分辨 率变形图像来估计一幅( 或一序列) 较高分辨率的图像，同时消除加性噪声以及由有 限检测器尺寸和光学元件产生的模糊。其中运动估计是超分辨率复原的关键技术 之一，运动估计结果的精确度直接决定着图像复原后的效果。 国外对于图像序列得研究主要用于测量云层的运动。到了8 0 年代，许多的运 动估计算法被提出【2 l ：有基于点的像素递归法、光流法、相位相关法、叶贝斯法0 4 1 和基于宏块的块匹配方法等。 块运动模型：假设图像是由运动的块构成，逐帧进行块匹配并确定块位移的 算法。有如：全搜索法( f s s ) 、三步法( t s s ) 、菱形法( d s ) 、交叉搜索法和分级搜索 法。 光流方程的方法：整个帧的运动矢量集合我们称之为运动矢量场。 像素递归法：以像素为单位，在前一帧中寻找它的最佳匹配，即查找正在编 码的像素在前一帧中的坐标，这个坐标和当前像素的坐标差，即为该像素的运动 矢量。 常用的运动估计的算法很多，但它们或有运算量大或有结果不够精确的缺点。 现在运动估计算法的主要焦点在于在减少运算量提高搜索时间的同时得到精确的 结果，所以有两个方法可以解决这个问题：( 1 ) 改进或是提出新的搜索模式，以更 基于遗传算法的运动估计 少的搜索的点和更小的搜索范围，得到更为精确的搜索结果。( 2 ) 引入新的数学方 法来辅助已有的搜索方法。 随着近些年视频方面的迅速发展，有将遗传算法1 6 7 】和小波方法引入运动估计 中。遗传算法的基本思想来源于达尔文的进化论和门德尔的遗传学说。遗传算法 就是借助于计算机编程将待求问题表示成串( 或染色体) ，即为二进制码或数码串。 从而构成一群串，并置于问题的求解环境中，更具一定适应度的原则选择出适应 环境的串进行复制，且通过交换和变异两种基因操作产生新的更适应环境的一代 串群，经这样一代代不断变化，最后收敛到一个最适应环境的串上，而求得问题 的最优解。 基于遗传算法的运动估计，即在运动估计算法中块匹配不再只局限于传统的 矩形，可以自适应的改变形状和大小，且搜索路径也趋于多样化。传统的遗传算 法 g l 需要在最初时选用大量的个体，这使得计算量并没有显著的减少，而且由于遗 传算法中变异的引用使得运算结果有一定的随机性。近几年的文献 9 - 】中对许多基 于传统遗传算法上的改进有：( 1 ) 初始种群的选取：在传统随机选取初始群体的基 础上提出运动矢量具有中心偏置特性和空间一致性的假设；( 2 ) 进化机制的改进： 基于传统遗传算法中随机的对染色体进行变异改进为先变异低位染色体。 遗传算法和其他的搜索算法相比，其优点在于： 1 ) 遗传算法在搜索过程中不易于陷于局部最优，即使在所定义地适应度函数 非连续不规则和伴有噪声地情况下也能以极大地概率找到全局最优解。 由于遗传算法固有的并行性，使得它非常适合于大规模并行处理。 运动估计可用于以下几个方面： 视频压缩1 1 2 1 ：视频序列信息存在空域冗余和时域冗余。空域冗余的消除方法 是对d c t 变换后的系数量化，去掉人眼不敏感的高频信息。时域冗余的消除方法 就是运动估计。因此，研究运动估计算法，尽可能的去掉冗余信息并减少视频质 量的损失，对视频编解码系统具有重要的意义。 超分率图像的复原技术。对低分辨率图像的运动估计是超分率图像复原的关 键技术，所以研究运动估计的意义深远。 1 2 本文的研究内容和章节安排 本文主要介绍了运动估计的基本概念、基本理论、及其不同运动估计算法的 实现与改进。具体章节安排如下： 第一章绪论简单介绍了运动估计的概念和发展，并分析了运动估计的应用领 域。 第二章介绍了运动估计的基本理论，包括运动估计模型和块匹配运动估计的 第一章绪论 要素，其中详细的介绍了块匹配运动估计的要素，如：块的大小如何选取、块匹 配准则、块的搜索策略、块的搜索起点的预测、象素搜索精度和算法的评定标准。 第三章详细讲述了运动估计中已有的经典算法，如：全搜索法( f s ) 、二维对 数法( t d l ) 、三步搜索算法( t s s ) 、新三步搜索算法( n t s s ) 、四步搜索算法( f s s ) 、 菱形搜索算法( d s ) 和六角形法o t e x b s ) 。 第四章基于遗传算法的运动估计，首先介绍了遗传算法的基本原理和适用性， 接着进一步将遗传算法与图像的运动估计相结合，并将其算法实现，用此方法得 出的结果和前面提到的经典算法实现的结果作对比并得到结论。 第五章回顾了在对本论文所做的工作，并对今后工作迸行了展望。 第二章运动估计的基本理论 第二章运动估计的基本理论 2 1 运动估计模型 运动估计作为数字视频处理的重要部分之一，越来越多的受到人们的关注。 其中已提出很多运动估计方法，如：块匹配法、像素递归法、光流场估计的方法 和贝叶斯方法等等。 常见的运动估计方法 2 1 有以下几种： ( 1 ) 块运动模型：假设图像是由运动的块构成的，逐帧确定块位移的算法有： 相位相关法和块匹配法。在相位相关法中，两个相邻帧之间的傅立叶相位差的 线性项决定了运动估算。块匹配法是用一些块匹配准则搜索下一帧( 和或上一 帧) 固定大小的最佳匹配块的位置。这两种方法的基本形式仅适用于平移运动。 ( 2 ) 像素递归法：像素递归法是预测校正型的位移估算器。预测值可以作为前 一个像素位置的运动估算值，或作为当前像素邻场内的运动估算线性组合依 据该像素上位移帧差( d f d ) 的梯度最小值，对预测作进一步修正。预测过程看 作一种隐含的平滑度估算条件，把这个算法推广到基于块的估算，就推导出所 谓的“w i e n e r 型”估算方案。 ( 3 ) 基于光流方程( o f e ，o p t i c a lf l o we q u a t i o n ) 的方法：依据空间图像亮度梯 度来得到一个光流场的估算。需要与合适的时空平滑度约束条件联合使用，要 求运动矢量在附加区域缓慢变化，基于光流方程的运动估计算法对每一个象素 点都要求出其独立的运动矢量。计算复杂，不易用于硬件实现。 ( 4 ) 贝叶斯法；贝叶斯法利用随机平滑度约束条件，通常采取吉布斯( g i b b s ) 随 机场方法来估算位移场。它的主要不足之处是需要大量的计算。 在已有的算法中，考虑到计算复杂度和实时实现的要求，我们最常用的是基 于块运动模型的块匹配法。基于块匹配法的运动估计易于大型集成电路的逻辑实 现，在实际中几乎所有的视频编码标准中的运动估计都采用了这种方法。 2 2 块匹配原理 本章介绍两种类型的块运动【2 】：块的简单二维平移和块的各种二维变形。 6 基于遗传算法的运动估计 2 2 1 平移的块运动 块匹配方法【1 3 1 的思想是将图像序列中的每一帧划分成很多互不重叠的固定大 小的宏块，并假定其宏块内所有像素的位移量都相同，然后对于当前帧中的每一 块根据一定的匹配准则在前一帧或后一帧某一给定搜索范围内找出与当前块最相 似的块，即匹配块，所得匹配块与当前块的相对位置计算出来的运动位移，即为 当前块的运动矢量( m o t i o nv e c t o r ) 。 第k 帧 图2 1 块匹配原理图 第k z 帧 如图2 1 示，假设在图像序列中，t 时刻对应于第k 帧图像，将此图像的当前 帧( 第k 帧) 划分为固定大d 、( m x n ) 像素，为了方便算法的实现，一般m 。取值 相等，即( n x n ) 的图像子块，为了简化运算假设位于同一图像子块内的所有像素 具有相同的位移，且只作平移运动，对于每一个子块只需计算一个运动矢量。虽 然实际中，块内各像素运动不一定相同，也不一定只有平移运动，但当宏块的取 值较小时，上述假设可近似成立。块匹配法对第k 帧图像中的每一块，在其t f 时 刻对应于第k ，帧图像中的一定范围( 搜索窗) 内搜索最优匹配，并认为该块就是 从第| i ，帧图像最优匹配块位置处平移过来的。设图像子块可能的最大位移矢量为 ( x ，) ，) ，则搜索范围为( m + 2 x ) x ( n + 2 y ) ，工和y 分别是最大搜索距离，为了简化 运算经常使x 和y 相等( x = y = w ) ，即( + 2 们2 。 2 2 2 一般的变形的块运动 平移块模型能表示为如下形式： = 五+ d l 呓= x 2 + d 2 ( 2 1 ) 第二章运动估计的基本理论 7 其中( 爿，蔓) 代表帧( 七+ ，) 中像素的坐标 空问平移可被推广到仿射坐标变换，由下式给出 x 一：= a l x ! - t - a 2 x 2 ：之 ( 2 2 ) = a 3 而+ 口4 屯+ 以 仿射燹抉既司处理正方形( 长方形) 二维燹形剑半行四边形，又司处理块旋转， 如图2 2 所示。其它的空间变换包括透视的和双线性的坐标变换。透视变换由下式 给出： xj = 筹皋糟 x ；= 鼍杀特 g 3 同时双线形变换可表示为： 爿= c x t + 呸恐+ 吗五恐+ a 4 = 略五+ 恐+ 吗五恐+ ( 2 4 ) 仿射 透视 双线形 双线形 图2 2 空间平移 8 基于遗传算法的运动估计 2 3 匹配运动估计的要素 块匹配算法包括五个要素：( 1 ) 搜索范围、( 2 ) 匹配块大小、( 3 ) 匹配准则、( 4 ) 搜索精度和( 5 ) 搜索方式。 2 3 1 搜索范围 通常认为搜索范围越大，运动估计的效果就会越好，但是大的搜索范围会带 来大的计算量。在视频编码中，图像的运动矢量总是高度集中在搜索窗i = l 的中心 附近，所以一般的搜索窗的选取希望运动矢量集中在其中心，并且搜索窗不大， 一般为搜索窗为( + 2 x x + 2 y ) ，即x 、y 分别是水平或垂直方向的最大运动， n x n 是宏块大小。 2 3 2 匹配块大小 块匹配法中块大小的选取：选取的块大时，减少运算量并加快了运算时间，但 是影响运动估计结果的精度；选取的块小时，可以假设块内各像素的平移运动接 近，但是易受噪声影响，而且运算量增加。因此必须恰到好处地选择块的大小， 以做到两者兼顾。目前的视频压缩标准，如h 2 6 x 和m p e g 系列等，块匹配中的 子模块多选用1 6 x 1 6 大小的块。 2 3 3 块匹配准则 在运动估计算法中，运动估计的准确性依赖于在块匹配过程中所用的匹配准 则，其中常见的匹配准则【1 q 有：均方误差( 旌e ) 、平均绝对误差( 膨4 d ) 和归一化 相关函数( n c c f ) ，具体公式如下： 1 ) 均方误差m s e ： 一l - 1 m s e ( x , 力= 嘉( e o ，) 一e 。( f + x ，+ ) ，) ) 2 ( 2 5 ) 1 i = 0 i = 0 在运动估计的计算中坯e 的最小值对应的点为最佳匹配点。 此式中e 一。和e 分别为上一帧和当前帧的灰度值，( x ，y ) 为位移矢量，n x n 是 计算块匹配误差的像素块的尺寸( 分别对应匹配块的宽度和高度) 。 2 ) 平均绝对误差m a e ： n - i - i m a e ( x , 力= 吉i e ( f ，_ ，) 一曩。o + x ，_ ，+ j ，) i ( 2 6 ) o j = 0 j - 0 在运动估计的计算中m a e 的最小值对应的点为最佳匹配点。 第二章运动估计的基本理论 9 此式中e 一，和e 分别为上一帧和当前帧的灰度值，( x ，y ) 为位移矢量，n 是 计算块匹配误差的像素块的尺寸( 分别对应匹配块的宽度和高度) 。 3 1 归一化相关函数n c c f ： m f k ( m ，n ) f k _ l ( m + i ，厅+ d n c c f ( i ，力= _ 要生! = l 1 ( 2 7 ) l a 2 ( m ，n ) ii 丘( m “栉+ ，) i z l m - 1n s ljl m t in = lj 在运动估计的计算中朋z f 的最大值的点为最佳匹配点。 此式中e 一。和e 分别为上一帧和当前帧的灰度值，( x ，y ) 为位移矢量， 是计算块匹配误差的像素块的尺寸( 分别对应匹配块的宽度和高度) 。 从范匹配函数在匹配过程中有众多的乘方运算，朋? c f 匹配函数的运算比 坯西更为复杂，所以在纥舰实现中比较困难；m a e 是这三个公式中运算最简单 的，在v l s l 中容易实现，所以被较多使用。 2 3 4 估计精度 在实际中，图像中的物体在帧间的真实位移不一定是整像素的，所以整个像 素运动估计的精度就显得不够精确了，在新的压缩标准中h 2 6 3 + 、m p e g - 2 中， 已要求运动估计精确到亚像素级。为了得到亚像素级或是更精确的1 4 像素级等， 一般都采用插值法来获得，经典的线性插值法有；最邻近插值、双线性插值和双 三次插值等。 2 3 5 搜索方式 搜索方式是指在寻找最优块匹配时的搜索方法，即初始点的选取和搜索策略 选择。 初始点的选取 起始点的选取是搜索匹配前的第一步，所以它的选取显得尤为重要。起始点”叫 的选取关系到运算量的大小和运算结果的准确性。搜索起始点的选取具体分析如 下： 运动的相关性也就是运动物体的整体性和视频运动的连续性。由于运动的相 关性，因此视频的运动必然具有时间和空间上的相关性。一方面由于摄像机的运 动造成了整个画面的运动，这种全局的运动( g l o b a lm o t i o n ) 造成了该帧图像不同部 分运动具有相似性；此外由于块划分的小型化，使得同一帧图像的同一物体可能覆 盖多个块，这也使得这些块的运动具有相似性。像这样的同一帧图像的不同部分 运动的相似性，就称为运动的空间相关性。另一方面由于运动在时间上的连续性， 1 0 基于遗传算法的运动估计 因此前后相邻帧图像运动具有相关性，这称为运动的时间相关性。 既然运动矢量具有空间和时间上的相关性，就产生了利用这个特性对搜索起 点进行预测的想法。利用运动的相关性对搜索起点预测的基本思想是：利用运动 的相关性，以空间位置上的相邻块( 左边和上边己编码的块，如图2 3 的所示) 的运 动预测当前块的初始运动矢量，然后以此为起点作进一步的搜索。 宏块4 的运动矢量= ( 宏块l 的运动矢量+ 宏块2 的运动矢量 + 宏块3 的运动矢量) 3 宏块1 宏块2 宏块3宏块4 图2 3 空间位置的运动矢量预测 搜索策略的选择 在已有的算法中，有一种匹配结果最为精确的全搜索算法，此搜索算法没有 采用任何优化措施，所以，即使结果被认为是最优的，但由于对每一个可能的运 动向量都计算匹配误差，以至于运算量非常的大，因此在实际中应用较少。 为了减少搜索运算量，人们又提出了快速搜索算法0 6 , 1 7 l ，这种算法假定匹配 误差在搜索区域内的分布是单调的，即以匹配误差最小的搜索位置为中心，其它 位置对应的匹配误差是单调递增的，整个匹配误差分布曲面只有一个极小点。在 这个假定的基础上，采用一些启发式的方法，使搜索方向朝匹配误差下降的方向 前进，从而减小计算量。快速搜索的假设在现实中有些情况下是不能成立的，因 此常常陷入局部最优，找出的是运动向量次优解。 运动估计的评判标准主要有两个方面，如结果的准确度和运算效率。结果的准 确度来自两个方面，第一个方面是运算结果是否和真实运动相近，第二个方面是 人眼的主观评定。另外运动估计算法的评判标准有一项很重要的就是运算效率， 也就是说好的运动估计算法在保证一定精确度的情况下，希望有尽量少的运算量 即运算时间。 第三章典型的块匹配运动估计算法 第三章典型的块匹配运动估计算法 本章主要介绍了运动估计的经典算法，首先是全搜索算法，但由于此方法的 搜索是在搜索窗内的每一个参考位置遍历的寻找最佳匹配块，运算量非常大，为 了降低运算量，提出了许多快速算法，二维对数法( t d l ) 、三步搜索算法( t s s ) 、 新三步搜索算法( n t s s ) 、四步搜索算法( f s s ) 、菱形搜索算法( d s ) 、六角形法 ( i - m x b s ) 。 3 1 全搜索算法 s ) 全搜索算法 1 s ( f u ls e a r c hm e 蝴，f s ) 也称为穷尽搜索法，是块匹配法中最简 单、最可靠的方法。对搜索窗为( 2 x b + r ) 2 范围内所有可能的候选位置进行块匹 配，计算m a e 值，并从中找出最小值，其对应偏移量即为所求运动矢量。 全搜索算法( f s ) 具体步骤如下： 从原点开始逐个像素处计算m a e 值，直到遍历搜索范围内所有的点。在所有 的m a e 中找到最小块误差点( m a e 值最小的点) ，该点即为最佳匹配点。 全搜索算法由于可靠，且能够得到全局最优的结果，通常是其他算法性能比 较的标准，但它的计算量很大，尤其是在大幅图像的处理时运算量非常大，非常 耗时，不适合于v l s l 的设计，所以有了下面快速算法的提出。 二维对数( t w o - d i m e n s i o n a ll o g a r i t h m i c ，t d l ) 搜索法由j r j a i n 和a k j a i n 提 出【1 9 l ，它开创了快速算法的先例，分多个阶段搜索，逐次减小搜索范围直到不能 再小为止。 二维对数法的算法思想：通过快速搜索跟踪最小m a e 点，首先把初始运动矢 量的指向位置设为点( o ，o ) ，以十字型分布的五个点构成每次搜索的点群，求出m a e 最小点，并作为下一次运动搜索的中心；如果新的搜索中心点位子十字型的边缘， 则继续进行十字型搜索、步长不变，如果搜索中心不变，步长减半，继续进行十 字型搜索；如此循环，直到步长减为1 。( 如图3 1 所示) 基于遗传算法的运动估计 上 - 。1 r 3 1 二维对数法f 儿) 搜索图 3 3 三步搜索算法和新三步搜索算法 3 3 1 三步搜索算法( t s s ) 三步搜索法是利用运动矢量的中心偏置分布，采用具有中心倾向的搜索点模 式，并利用终止判别技术，减少搜索次数。 算法的基本思想是：每次搜索都是以上一步搜索得到的最佳匹配位置作为当前 搜索的中心位置，每做一步，步长减半。一般选取搜索窗的最大搜索长度为7 ，而 每次搜索都是前一次步长的一半，共需三步即可完成，因此这种算法称为三步搜 索法。 三步搜索算法( t s s ) 具体步骤如下： 步骤一：从搜索窗原点为中心，选取最大搜索长度的一半为步长，在其周围 的8 个点( 如图3 - 2 中的圆点所示) 处进行块匹配m a e 计算并比较大小，找到最 小的m a e 值，接着进行步骤二。 步骤二：以上一步得到的点为中心，将步长减半，进行块匹配计算并比较这8 个点( 如图3 2 中的三角形所示) 的m a e 值，并找出最小值，接着进行步骤三。 步骤三：以上一步得到的点为中心，步长为1 ，在其周围的8 个点( 如图3 2 中的方形所示) 处进行块匹配m a e 计算并比较大小，找到最小m i l e 值，则该点所 在位置即为要求的解。 三步搜索算法在搜索过程中搜索步长由大到小依次变化，即先进行粗定位， 再逐步聚焦到精确的位置。对于小运动的情况，第一步的步长过大，影响最终的 第三章典型的块匹配运动估计算法 1 3 搜索结果的精确度，而且第一步步长较大时会误导搜索方向，为了改进三步搜法 在小运动估计方面的效果，于是提出了新三步搜索法。 7 6 5 4 - 2 1012 3 4 561 弋 、 。 3 2 三步搜索算法( t s s ) 的搜索图 3 3 2 新三步搜索法( n t s s ) 新三步搜索法的基本思想是：在按照三步搜索法的第一步大模版搜索的同时， 也对内部的小模板进行搜索。以后每步的步长与三步搜索是一样的。 新三步法搜索法的具体步骤如下： 步骤一；以搜索窗的原点为中心，对其周围的外围大模板和内侧小模板进行 块匹配m a e 计算并比较值的大小，即以原点为中心，步长为最大搜索长度一半的 8 个点所组成的外围大模块( 如图3 3 所示，以大圆形表示) ，再以原点为中心，步 长为l 的8 个点所组成内侧小模块( 以小圆形表示) ，一共1 7 个点来进行m a e 计 算并比较，找到m a e 值最小的点。( 1 ) 如果这个点是原点，则终止搜索；( 2 ) 如果这 个点为内侧模块的8 个点中的一个，则跳到步骤三；( 3 ) 如果这个点是属于大模板 中的点，则进行步骤二 步骤二：以上一步所得的点为中心，步长减半，并对其周围的8 个点( 如图 3 3 所示，以三角形表示) 进行m a e 计算并比较，找到m a e 值最小的点，并进行 步骤三。 步骤三：以上一步所得的点为中心，步长减半，并对其周围的8 个点( 如图3 3 所示，以方形表示) 进行m a e 计算并比较，找到m a e 值最小的点( 五角形所示为 m a e 值最小的点) 。则此点即为搜索结果，搜索终止。 0 0 d o l 2 3 4 5 6 7 1 4 基于遗传算法的运动估计 【 - 1 i l上： 一。 o jo 1- _1 3 3 新三步搜索算法的搜索图 3 4 四步搜索法、菱形搜索法和六角形搜索 3 4 1 四步搜索法( f s s l 虽然新三步搜索法在三步搜索法的基础上做了许多改进，并且在物体做小范围 运动时改进很明显，然而，在物体做大范围运动时，这种改进却带来了额外的运 算量。因此随后又提出了四步搜索法，这种算法考虑到了块的中心偏置特性，同 时兼顾了物体的大范围运动。这种改进在物体既有小范围运动又有大范围运动时 可以得到较好的性能。 四步搜索法的具体步骤如下： 步骤一：以搜索窗的原点为中心，步长为2 ，并对其周围的8 个点( 如图3 4 中圆点所示) 做块匹配运算，如果得到的最小m a e 值在窗口的中心位置，则跳到 的步骤四；否则进行步骤二。 步骤二：以上一步所得点为中心，( 1 ) 如果第一步得出的最小m a e 位置在四个 边上，则额外的三个位置需要做匹配运算( 如图3 4 的右方的方形所示) ；( 2 ) 如果 第一步得出的最t j 、m a e 值在四个顶点上，则对其余的五个位置( 如图3 4 的左下 方，方形所示) 需要做匹配运算；( 3 ) 如果这一步得出的最小m a e 匹配位置在窗口 的中心位置，则直接跳到步骤四，否则进行步骤三。 步骤三：以上一步所得点为中心，步长与第二步的步长相同，搜索过程也相 同，但是做完搜索后直接进行步骤四。 步骤四：以上一步所得点为中心，步长减半，对其周围的九个点做匹配运算， 第三章典型的块匹配运动估计算法 得出的最佳匹配位置，就是最终的匹配位置。 3 4 2 菱形搜索法( d s ) 3 4 四步搜索算法的搜索图 菱形算法是目前使用广泛的一种快速搜索算法，它是一种基于中心偏移的多 级搜索方法。与之前的搜索不同，即应该选用圆形搜索模式。它采用了两种搜索匹 配模版。第一种是大菱形搜索模板l d s p ( l a r g ed i a m o n ds e a r c hp a t t e r n ) ，由9 个搜 索点( 中心点和周围按菱形分布的8 个点) 构成的一个大菱形。第二种是小菱形 搜索模板s d s p ( s m a l ld i a m o n ds e a r c hp a t t e r n ) ，由5 个点( 中心点和垂直、水平方 向相邻的4 个点) 构成一个小菱形。如图3 5 所示。 ( a ) 大菱形小菱形 3 5 菱形搜索法中的大菱形和小菱形 1 6 基于遗传算法的运动估计 3 6 菱形搜索法的搜索图 菱形搜索法【2 1 2 2 1 的具体步骤如下： 步骤一：以搜索窗的原点为中心，在搜索窗内先按大菱形法对包括中心点在 内的9 个点进行匹配运算( 如图3 6 ，大圆形标示) ，计算得的最小 m a e 值的点为最优匹配点，如果这点在搜索窗的中心位置，则跳转 到步骤三；否则进行步骤二。 步骤二：以上一步得到的最小失真点为中心进行大菱形法的匹配运算，如果 得到m a e 的最小值的点在中心点处，刚转到步骤三；否则重复步骤 一 步骤三：以上一步得到的点为中心，进行小菱形法匹配( 如图3 6 中的小圆形 所示) ，计算并比较m a e 值，褥到的最优匹配即为所求解。 钻石算法的特点在于先用l d s p 搜索，由于步长大，搜索范围广，可以进行 粗定位，使搜索过程不会陷入局部最小；当粗定位结束后，可以认为最优点在l d s p 周围8 个点所围的菱形区域中，这时再用s d s p 来准确定位，使搜索不致于有大的 起伏，所以它的性能优于其它算法。另外。d s 搜索时各步骤之间有很强的相关性， 模板移动时只需在几个新的检测点进行匹配计算，所以也提高了搜索速度。 3 4 3 六角形搜索0 - m x b s ) 一个典型的六角形斟1 搜索的模板如图3 - 7 所示，六角形模板( h s p ) ( 图a ) 和小菱形模板( s d s p x b ) ，六角形搜索的搜索模式是：先用六角形模板进行计算， 当最优匹配点出现在中心处时，以最优点为中心将六角形模板换成小菱形模板， 然后在这五个点中找寻最优匹配点。 六角形搜索的步骤如下： 第三章典型的块匹配运动估计算法 1 7 步骤一：用大六角形进行搜索，当其中的最优点位于六角形中心时( 如图3 8 中大圆形所示) ，进行步骤二；否则转入步骤三。 步骤- - ：以上一步的最优点为中心，用大六角形来计算m a e 值并比较大小， 如果最优点在大六角形的中心，如图3 8 中三角形和方形所示，则跳转到步骤三； 否则继续步骤二。 步骤三：以上一步的最优点为中心，用小菱形搜索该点周围的4 个点，如图 3 8 种小圆点所示，计算m a e 值并比较大小，得到的解即为所求解。 ， 3 7 、 ( a ) 大六角形 r 3 7 六角形搜索模块 ( b ) 小菱形 声 3 8 六角形法的搜索图 小结： 本章首先介绍了运动估计的二维运动模型，在此基础上，详细回顾了其它几 种典型的运动估计算法，重点描述了这些典型的块匹配法的理论模型、搜索方法 以及各自的优缺点。 第四章基于遗传算法的运动估计 第四章基于遗传算法的运动估计 4 1 遗传算法 遗传算法是模拟生物在自然界中的遗传和进化过程而形成的一种自适应全局 化概率搜索算法。利用生物的遗传特性，使生物界的物种能够保持相对的稳定； 同时利用生物的变异特性，使生物个体产生新的性状，形成新的物种，并推动生 物的进化和发展。 遗传算法 2 5 堤由一群个体组成的种群p ( t x t 代表遗传代数) ，且每一个个体代 表问题的一个解，用适应值评价每一个个体的优劣，个体经历选择、交叉和变异 等的遗传操作，新产生的个体c ( t ) 继续用适应值来评价优劣，从父代种群和子代种 群中选择比较优秀的个体就形成了新的种群。在若干代后，算法收敛到一个最优 个体，该个体很有可能代表着问题最优或次优解。遗传算法就这样反复迭代，向 着更优解的方向进化，直至满足某种预定的优化指标。 遗传算法提供了一种在复杂解空间上进行有向随机搜索的方法。选择算子则 有可能将遗传搜索的方向引导到解空间的理想区域中。因此种群、适应值和选择 算子的选取就尤为重要了。作为一种新的全局优化搜索算法，遗传算法以其简单 通用、稳定性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了 广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。 4 1 1 遗传算法的基本术语 遗传算法是自然遗传学和计算机科学相互结合而成的新的计算方法，所以遗 传算法中经常使用有关自然进化中的一些基础用语，在这里先做一些介绍，如表 4 1 所示。 遗传物质的主要载体是染色体，而基因是控制生物性状的遗传物质的功能单 位和结构单位。复数个基因组成染色体，染色体中基因的位置称作基因座( l o c u s ) 。 而基因所取的值叫做等位基因( a l l e l e s ) 。基因和基因座决定了染色体的特征，也就 决定了生物个体的性状。遗传算法中，将n 维决策向量x = k ，而，而r 用疗个记 号为五( f = l ，2 ，刀) 所组成的符合串x 来表示： x = 五五kjx = k ，x 29 0 0 9 r( 4 1 ) 其中把每一个置看作一个遗传基因，它的所有可能取值称为等位基因，这样x 就 基于遗传算法的运动估计 可看做是由一个遗传基因所组成的一个染色体。一般情况下，染色体的长度以是固 定的，但对一些问题，也可以是变化的。根据不同的情况，等位基因可以是一组 整数，也可以是某一范围内的实数，或者是纯粹的一个记号。最简单的等位基因 是由0 和1 这两个整数组成的，相应的染色体就可表示为一个二进制符号串。遗 传算法处理的是染色体，编码所形成的排列形式x 是个体的基因型，与它对应的z 值是个体的表现型。通常个体的表现型和其基因型是一对应的，但有时也允许 基因型和表现型是多对一的关系。染色体x 也称为个体x 。 在遗传算法中，决策变量x 成了问题的解空间。对问题最优解的搜索是通过 对染色体石的搜索过程来进行的，从而由所有的染色体x 就组成了问题的搜索空 间。 生物的进化是以集团为主体的一定数量的个体组成了群体( p o p u l a t i o n ) ，也叫 集团。与此对应遗传算法的运算对象是由肘个个体所组成的集合，称为群体。群 体中个体的数h 称为群体的大小口( p o p u l a t i o ns i z e ) ，也叫群体规模，而各个体对 环境的适应程度叫做适应度( f i t n e s s ) ，个体的适应度与其对应的个体表现型的目标 函数值相关联。 表4 1 遗传算法基本术语 生物界遗传算法 染色体决策变量( 矢量) 或编码的字符串 基因矢量的分量值或字符串中的字符 等位基因矢量的分量的可能值或字符串中的可能字符 基因座 矢量的分量位置或字符串中字符位置 基因型矢量( 变量) 的编码结构 表现性矢量( 分量) 的解码结构 4 1 2 遗传算法的理论基础 一般认为遗传算法有5 个基本组成部分： 1 ) 问题的解的遗传表示，即编码问题 2 1 创建解的初始种群的方法 3 1 选择操作 4 ) 交叉与变异 5 ) 适应度函数 第四章基于遗传算法的运动估计 4 1 2 1 编码问题 2 1 编码是应用遗传算法时所要解决的首要问题，也是设计遗传算法时的一个关 键步骤。在遗传算法执行过程中，对具体的问题进行编码，编码的好坏直接影响 选择、交叉、变异等遗传运算。把一个问题的可行解从其解空间转换到遗传算法 搜索空间的转换方法称为编码，而由遗传算法解空间向问题空间的转换称为解码。 遗传算法的编码就是解的遗传表示，它是应用遗传算法求解问题的第一步。 如何对具体问题进行客观而无误差的编码一直是遗传算法应用的难点之一，也是 遗传算法的一个重要研究方向。人们现在己经提出了许多种不同的编码方法，通 常分为以下的几个大类：二进制编码方法、符号编码方法、浮点数编码方法和多 参数编码方法。 1 二进制编码 二进制编码是遗传算法中最主要的一种编码方法，它使用的编码符号集是由 二进制符号0 和1 所组成的二值符号集 o ，1 ) ，它所构成的个体基因型是一个二进 制编码符号串，二进制编码符号串的长度与问题所要求的求解精度有关。 二进刻编码有如下优点： ( 1 ) 编码、解码操作简单易行。 ( 2 ) 交叉、变异等遗传操作便于实现。 ( 3 ) 符合最小字符集编码原则。 ( 4 ) 便于利用模式定理对算法进行理论分析，因为模式定理是以二进制编码 为基础的。 二迸制编码有以下缺点： 首先，二进制编码存在着连续变量离散化时的映射误差。个体编码串的长度 较短时，可能达不到精度要求，而个体编码串的长度较大时，虽能提高编码精度， 但却会使遗传算法的搜索空间急剧扩大。其次它不能直接反映所求问题本身的结 构特征，这样也就不便于开发针对问题的专门的遗传运算算子。 2 浮点数编码方案 对于一些多维、高精度要求的连续函数优化问题，使用二进制编码来表示个 体时将会有一些不利之处。所谓浮点数编码方法，是指个体的每个基因值用某一 范围内的一个浮点数来表示，个体的编码长度等于其决策变量的个数。因为这种 编码方法使用的是决策变量的真实值，所以浮点数编码方法也叫做真值编码方法。 浮点数编码方法有以下几个优点： ( 1 ) 适合于在遗传算法中表示范围较大的数。 ( 2 ) 适合于精度要求较高的遗传算法。 ( 3 ) 便于较大空间的遗传搜索。 基于遗传算法的运动估计 ( 4 ) 改善了遗传算法的计算复杂性，提高了运算效率。 ( 5 ) 便于遗传算法与经典优化方法的混合使用。 ( 6 ) 便于设计针对问题专门知识的知识型遗传算子。 ( 7 ) 便于处理复杂的决策变量约束条件。 3 符号编码 符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义，而只 有代码含义的符号集。如( a ，b ，c ，d ) 、( 1 ，2 ，3 ，4 ，) 等等。符号编码便 于在遗传算法中结合所求解问题的专门知识，而且利于与相关近似算法的混合使 用。但符号编码方法的遗传算法，需要认真设计交叉、变异等遗传操作方法，以 满足问题各种约束条件，才能提高算法的搜索性能。 4 多参数编码 含有多个变量的个体进行编码的方法就称为多参数编码方法。多参数编码的 一种最常见的方法是：将各个参数分别以某种编码方法进行编码，然后再将它们 的编码按照一定的顺序连接在一起就组成了表示全部参数的个体编码。这种编码 方法称为多参数级联编码方法。在进行多参数级联编码时，每个参数的编码方式 可以是二进制编码方法，格雷码、浮点数编码或符号编码方式中的一种，每个参 数可以具有不同的上下界，也可以有不同的编码长度或编码精度。 其他常用的编码技术有格雷码，多参数交叉编码、一维染色体编码、二维染 色体编码、可变染色体编码和树结构编码。 4 1 2 2 初始种群的大小 初始种群的规模( 初始解的个数) 对遗传算法的影响非常大。遗传算子从初 始种群中生成，并在此基础上不断的优化模块，直到找到问题的最优解。群体的 规模越大，群体中个体的多样性越多，算法陷入局部解的可能性就越小，但是随 着群体规模的增大，运算量也显著增加。若群体规模太小，使遗传算法的搜索空 间受到限制，则可能产生未成熟收敛的现象。 4 1 2 3 选择 遗传算法使用适应值来对群体中个体进行优胜劣汰操作：根据每个个体的适 应度大小做出选择，适应度较高的个体被遗传到下一代群体的概率较大，适应度 较低的个体被遗传到下一代群体中的概率较小。这样就可以使群体中个体的适应 度值不断接近最优解。选择操作建立在对个体的适应度进行评价的基础之上。选 择操作的主要目的是为了避免丢失有用的遗传信息，提高全局收敛性和计算效率。 第四章基于遗传算法的运动估计 2 3 选择算子的好坏，直接影响到遗传算法的计算结果。选择算子选定不当，会造成 群体中相似度值相近的个体增加，使得后代个体与父代个体相近，导致进化停止 不前；或者使适应度值偏大的个体误导群体的发展方向，使遗传失去多样性，产 生早熟问题。 选择操作就是确定从父代群体中选取哪些个体遗传到下一代群体中的一种遗 传运算，选择操作不但确定用来交叉( 或重组) 的个体，还确定被选个体产生后代个 体的个数。选择操作的策略与编码方式无关。选择操作算子包括：轮盘赌选择、 随机竞争选择、最佳保留选择、均匀排序选择、随