（计算机软件与理论专业论文）采用mec的彩色目标识别.pdf

太原理工大学硕士学位论文 采用m e c 的彩色目标识别 摘要 思维进化计算是孙承意教授于1 9 9 8 年提出的进化计 算新方法，它是根据对遗传算法( g a s ) 存在问题的思考以 及对人类思维进步的分析，模仿人类社会中存在的趋同 和异化现象提出来的。研究已经表明，m e c 的计算效 率和收敛性能比标准g a 及其它进化算法一般要高 5 0 以上，说明m e c 是一种高效的算法。m e c 还成功 地解决了一些非数值优化问题，如t s p 、j o b s h o p 、系 统动态建模等，此外，m e c 也已被用于图像分析中，取 得了较好的结果，所有这些工作已经为m e c 建立了一 个初步完整的体系。 目标识别是计算机视觉中研究的一个热点，其主要 任务就是使计算机能够在没有人工干预地情况下，自动 地识别出目标。从7 0 年代以来，研究者们提出了许多的 识别算法，这些算法可以大致分为三类：基于模板的方 法、基于特征的方法和基于三维模型的方法。基于模板 的方法的原理是把模板覆盖在搜索图上、并在搜索图中 上下移动，寻找与模板一致的子图。基于模板的方法抗 噪性能强、具有平移、尺度等不变性，但是计算量相对 较大；基于特征的方法需要从目标的众多特征中选择出 那些对分类识别最有效的特征，通常包括两个阶段：特 征提取和特征选择。通过对选择出来的特征的属性或者 是特征之间的关系进行匹配，来识别目标。基于三维模 型的方法所识别的目标是已知的，它利用计算机辅助设 采用m e c 的彩色目标识别 计( c a d ) 来建立目标的几何模型，对模型的表面、边 界及连接关系进行完整的描述。 本文提出一种新的目标识别算法，它是把模板匹配 思想和性能优异的思维进化计算结合起来，在c i e1 9 7 6 f “+ v + 均匀颜色空间上匹配。实验结果表明，新算法实现 了平移不变、旋转不变、尺度不变、镜像不变的识别， 由于利用了目标的彩色信息，算法还具有彩色恒定性。 此外，新算法还大大地减小了模板匹配的计算量。 目标识别非常难解决的一个问题是：识别被遮挡住 了的目标。因为部分遮挡的随机性很大，遮挡的部位和 遮挡区域的大小都无法事先确定；而且实际遮挡区域可 能非常复杂，我们不可能事先知道遮挡区域的特征、纹 理等辅助信息。为了解决目标的局部被遮挡的问题，本 文提出用遮挡模板的方法解决这个问题。即：用某个圆 遮挡模板，把圆与模板相交的部分视为遮挡区域，我们 对这部分区域作特殊标记，令其在进行模板匹配时不参 加匹配运算。这样就相当于又做出了另一个模板，我们 称这个标记过遮挡区域的模板为“遮挡模板”。模板匹 配时，我们使遮挡模板不断接近实际遮挡的区域，来解 决目标识别中的遮挡问题。实验表明提出的方案不但能 够找出目标，而且能够准确地确定出遮挡区域的位置和 遮挡区域的大小。 关键字：思维进化计算，遗传算法，目标识别，彩色模 型，模板匹配 i i 太原理王大学硕士学位论文 c o l o ro b j e c tr e c o g n i t l 0 n u s i n gm i n de v o l u t i o n a r y c o m 田u 掰i o n a b s t r a c t t oo v e r c o m et h e p r o b l e m so fg a ，m i n de v o l u t i o n a r y c o m p u t a t i o n ( m e c ) w a sp r o p o s e db yc h e n g y is u ni nt 9 9 8 ， w h i c hi m i t a t e st w o p h e n o m e n a o fh u m a n s o c i e t y s i m i l a r t a x i sa n dd i s s i m i l a t i o n s t u d i e sh a v es h o w nt h a tt h e c o m p u t i n ge f f i c i e n c ya n d t h ec o n v e r g e n c er a t eo fm e ca r e g e n e r a l l yh i g h e rt h a nt h o s eo fg a sb ym o r et h a n5 0 i n t h en u m e r i c a l o p t i m i z a t i o n v a r i o u s s t r a t e g i e s o f s i m i l a r t a x i sa n dd i s s i m i l a t i o nh a v eb e e nd e v e l o p e dw i t h b e t t e r p e r f o r m a n c e t h a nt h a to fb a s i c m e c m o r e o v e r , p r e v i o u ss l 珏d yh a sa l s os h o w nt h a tm e ch a st h ea b i l i t yi n s o l v i n gs u c c e s s f u l l yt h en o n n u m e r i c a lp r o b l e m ，s u c ha s t s p , j o b s h o pa n dd y n a m i cm o d e l i n go fs y s t e m ，e t c m e c i i i 采用m e c 的彩色目标识别 h a sb e e nu s e di n i m a g ea n a l y s i sa r e a ，a n d a t t a i n e dt h e b e t t e rr e s u l t s ap r e l i m i n a r yi n t e g r a t e ds y s t e mh a sa l r e a d y b e e ne s t a b l i s h e df o rm 匣c o b j e c tr e c o g n i t i o ni sr e c e i v i n gi n c r e a s i n ga t t e n t i o ni n c o m p u t e rv i s i o n ，a n dt h eu l t i m a t eg o a lo fc o m p u t e rv i s i o n i st os i m u l a t et h eh u m a np e r c e p t i o na n di n t e r p r e t a t i o no f t h ew o r l da r o u n du s b y7 0 s ，m a n yr e c o g n i t i o na l g o r i t h m h a sb e e n p r o p o s e d ，a n da l lo f t h e mc a nb e c a t e g o r i z e di n t o 3t y p e s ：t e m p l a t e - b a s e dm e t h o d ，f e a t u r e b a s e dm e t h o da n d 3 d m o d e l b a s e dm e t h o d t h e p r i n c i p l e o ft h e t e m p l a t e - b a s e d m e t h o di st h a tt h es e a r c h e d i m a g e i s c o v e r e db yt h et e m p l a t ei m a g e ，a n dt h et e m p l a t ei sm o v e d u pa n dd o w nt ol o o kf o ras u b i m a g ew h i c hi s i d e n t i c a l w i t ht h et e m p l a t ei m a g e t h et e m p l a t e b a s e dm e t h o dh a s t h ea b i l i t yo fr e s i s t a n c en o i s ea n dt r a n s l a t i o ni n v a r i a n c ea n d s c a l i n gi n v a r i a n c e ，a l t h o u g ht h ec o m p u t a t i o ni sr e l a t i v e m o r e t h ef e a t u r em e t h o d sn e e dt os e l e c tt h em o s te f f e c t i v e f e a t u r ef r o mt h en u m e r o u sf e a t u r e s o fo b j e c t ，a n dt h e 太原理一大学硕士学位论文 m e t h o d u s u a l l yi n c l u d e st w op h a s e s ：f e a t u r ee x t r a c t i o na n d f e a t u r e s e l e c t i o n t h r o u g hm a t c h i n g t h ea t t r i b u t eo f f e a t u r e sa n dt h er e l a t i o nb e t w e e nt h e m ，o b j e c t sc a nb e r e c o g n i z e d t h e 3 d m o d e l - b a s e dm e t h o dc a i l o n l y r e c o g n i z e dt h ek n o w no b j e c t s i tm a k e st h em o d e lo ft h e o b j e c ta n dc o m p l e t e l yd e s c r i b e st h er e l a t i o n sb e t w e e nt h e s u r f a c e ，e d g e a n d p o s i t i o nt h r o u g h c a d an e wo b j e c tr e c o g n i t i o nm e t h o do fc o l o r i m a g ei s p r o p o s e d i nt h i s p a p e r , w h i c h c o m b i n e st h e t e m p l a t e m a t c h i n gw i t h t h em i n d e v o l u t i o n a r yc o m p m a t i o n ( m e c ) t h er e c o g n i t i o ni sd o n ei nc i e19 7 6l * u + v + u n i f o r mc o l o r s p a c e t h ee x p e r i m e n t a lr e s u l t ss h o w t h a tt h i sn e wm e t h o d h a st h ea b i l i t yt oi m p l e m e n tr e c o g n i t i o nw i t ht r a n s l a t i o n ， r o t a t i o n ，s c a l e a n dm i r r o r i n v a r i a n c e m o r e o v e r , n e w m e t h o dh a st h ec o l o ri n v a r i a n c eo f o b j e c tr e c o g n i t i o ns i n c e w e r e c o g n i z e st h eo b j e c ti nc i e1 9 7 6f 村+ v + u n i f o r mc o l o r s p a c e 。f u r t h e r m o r e ，t h ec o m p u t a t i o n e f f i c i e n c y o fo u r m e t h o di sh i g h v 采用m e c 的彩色目标识别 t h e d i f f i c u l t yi no b j e c tr e c o g n i t i o ni so c c l u s i o n ，t h a ti s ， t h e o b j e c t i so c c l u d e d p a r t l yb y s o m eo t h e r o b j e c t s b e c a u s et h eo c c l u d e dp a r ta n dt h eo c c l u d e da r e aa r en o t d e t e r m i n e db e f o r er e c o g n i t i o n ，t h ei n f o r m a t i o no ff e a t u r e a n dt e x t u r eo f t h eo c c l u d e da r e ac a n n o tb ek n o w n w ep r o p o s e dt h eo c c l u s i o n t e m p l a t e t os o l v et h e p r o b l e m t h e m e t h o di st h a t u s i n g ac i r c l e r e g i o n t o o c c l u d et h e t e m p l a t e ，t h eo v e r l a p p e da r e ab e t w e e nt h e t e m p l a t ea n dt h ec i r c l er e g i o ni sv i e w e da st h eo c c l u d e d a r e aw h i c hi sm a r k e dw i t hs p e c i f i c a l l y , a n dt h eo c c l u d e d a r e ai sn o tm a d et h em a t c h i n g c o m p u t a t i o n s ot h i sk i n do f t e m p l a t e i sc a l l e d “o c c l u d e d t e m p l a t e ”t h e o c c l u d e d t e m p l a t e i s a p p r o a c h i n gt h ef a c t u a lo c c l u s i o na r e aw h e n m a t c h i n g k e yw o r d s ：m i n d e v o l u t i o n a r yc o m p u t a t i o n ，g e n e t i c a l g o r i t h m ，o b j e c tr e c o g n i t i o n ，c o l o r m o d e l ，t e m p l a t e m a t c h i n g v i 太原理工大学硕士学位论文 1 1 计算机视觉 第一章目标识别 让计算机具有人的视觉、听觉等感知能力，是人类在基础研 究与应用研究中面临的最重大的挑战之一。用计算机实现模式的 自动识别，是开发智能机器的一个最关键突破口，它的成功应用 将大大推动人工智能系统的发展、拓广计算机与各种自动机器的 应用范围。 人类是通过眼睛与大脑来获取、处理和理解视觉信息的。信 号处理理论和计算机出现之后，人们试图用摄像机获取环境图像 并转换成数字信号，用计算机实现对视觉信息处理的全过程，这 样就形成了一门新兴的学科计算机视觉。 8 0 年代初m a r r 首次从信息处理的角度综合了图像处理、心理 物理学、神经生理学以及临床精神病学的研究成果，提出了第一 个较为完善的视觉系统框架。虽然这一框架在许多方面还有争议， 但至今仍是广大计算机视觉工作者接受的基本框架。m a r r 从信息 处理系统的角度出发，认为对此系统的研究应分为三个层次，即 计算理论层次、表达与算法层次、硬件实现层次f 马颂德9 7 。 计算机视觉的研究目标是，使计算机具有通过一幅或者多幅 图像认知周围环境信息的能力。这种能力不仅使机器能够感知环 境中的几何信息，包括它的形状、位置、姿态、运动等，而且能 对它们进行描述、存贮、识别与理解。完成这一任务的第一步是 把所有的目标从场景中区分出来，然后再进行运动分析、运动估 计和跟踪等后续的步骤，可见识别出目标是首先要完成的工作。 目前还有许多从事三维计算机视觉的研究工作，但是三维计 算机视觉需要通过二维图像的识别和特征检测，对目标建立模型， 采用m e c 的彩色目标识别 由二维图像定量恢复三维物体形状。可以看出，二维目标识别是 计算机视觉研究中的基础内容。 计算机视觉的发展得益于神经心理学、心理学与认知科学对 生物视觉系统的研究。虽然这种跨学科的研究还远远不够深入， 但从事计算机视觉的研究者们已经发展起一套独立的计算理论与 算法，从而能用计算机对视觉信息( 或者说，对图像) 进行分析 与处理。计算机视觉，作为- - f l 独立的学科正在受到广泛的重视。 目前，计算机视觉已应用于图像分析、文字识别、医学图像处理、 多媒体技术、图像数据库、工业检测与军事等方面。可以预见， 随着学科基础研究的不断深入、随着计算机性能的快速提高，计 算机视觉将广泛地应用于更复杂地场合。 1 2 目标识别概述 识别活动是人类社会活动、生产活动以及科研活动中最基本 最重要的活动之一。为了能让计算机自动地执行和完成识别任务， 人们做了大量的研究。但是至今尚没有一个通用的识别算法，还 限于识别特定的目标，如：人脸识别系统、指纹识别系统、汽车 牌照自动识别系统、字符识别系统。 从上个世纪7 0 年代初，开始有大量的研究者从事目标识别这 方面的研究，提出了许多识别的方法。目标识别的方法可以归纳 为三大类：基于特征的方法、基于模板的方法，基于三维模型的 方法。 基于模板的方法是最早提出的识别方法，它的基本思想是： 先把需要识别的目标做成模板或者描述成模型，然后在待测图像 中查找与模板或者模型相同或者相似的区域。该类的一些方法还 允许模板或者模型自动地发生一些合理的变形，去匹配可能也发 生了某些形变、或者被遮挡住局部的目标。根据测度函数或者概 率函数的极值，确定当前找到的目标是否是所要寻找的目标。 太原理工大学硕士学位论文 基于特征的方法在7 0 年代末、8 0 年代初开始了大量的研究。 它的基本的思想是：通常情况下每类对象具有比较一致的特征， 并且目标对象的特征往往与背景有较大的区别。因此，抽取出最 能代表对象的特征，用这些“本质的”特征识别该类的目标。特 征的选择和提取是这类方法的关键。 基于三维模型的方法是利用计算机辅助设计( c a d ) 把来自 模型的和来自传感器的对于目标表面、边界及连接关系的描述加 以匹配，以识别三维目标。 1 2 1 基于模板的方法 基于模板的方法，根据模板是否可以发生变形，分为刚性模 板的方法和变形模板的方法两类。 刚性模板：模板一旦构造完成就不能再发生变化，即只可以 对模板进行旋转、缩放平移等变换，模板各个象素的相对位 置不能改变、也不能发生任何的形变。 变形模板：模板形状能够被计算机自动地改变，根据测度函 数的指引，模板形状能够逐渐地变形成最接近目标的形状。 1 _ 2 1 1 基于刚性模板的方法 1 刚性模板的构造 为了准确的识别出图像中的目标，必须构造具有代表性的模 板，使样本中所要搜寻的目标与模板的匹配程度最高。一种简单 的方法是将同一类目标的多个样本求平均，具体方法是： 确定各个样本图像所在的区域，通过插值将其尺度标准化为 m n ： 将所有样本图像进行灰度分布标准化，即将图像的平均灰度 和灰度方差变换为标准值和6 0 。设图像i 的灰度矩阵为i w i h ( 其中w ，h 分别为图像的宽度和高度) ，计算其均值和方差 万= 击糍d i ，】 采用m e c 的彩色目标识别 = 南囊，叶刃2 一z 将图像i 的灰度分布标准化到( 卢o ，盯o ) j d d 】= 塑( i i i j 一万) + o 1 3 o 将所有样本图像取灰度平均并进一步进行重采样后得到模板 图像。 此外，在检测过程中使用该模板进行匹配之前，也用该方法 对待测图像进行标准化，这么做是为了抑制不同灰度变化对模板 匹配产生的影响。 2 模板匹配的过程 模板，的尺寸邢t h ，待测图像，的尺寸缈圩，一般情况 下彤 w ，册 0 0 0 8 8 5 6 ( r v o ) 0 ) 9 s e a r c h s p a c e ( s 月，0 ，8 ) 1 0 e n d i f 采用m e c 的彩色目标识别 1 1 e n d w h i l e pp r o c e d u r eo f s e a r c h w h o l e s p a c e | s e a r c h w h o l e s p a e e ( s i z e _ n ，n u m s ，n u m t ) 1 在整个解空间上随机散布s i z en 个个体 2 计算个体的得分 3 选出n u m s 个最好的个体作为n u m s 个优胜子群体 中心，从剩余的个体中选出n u m t 个最好的个体作为n u m t 个临 时子群体中心 注意：我们所定义的异化操作是全局搜索，在算法中体现在 步骤2 和步骤8 - 9 两个部分，这两个部分。 分) i p r o c e d u r eo fs i m i l a r t a x i s | s i m i l a r t a x i s ( c e n t e r , i ) 1 在c e m e r 周围散布，个个体 2 计算个体得分 3 选择最好的个体作为新的c e n t e r ( 精英保留) l p r o c e d u r eo f r e l e a s e | r e l e a s e ( ) 1 f o r 每个i 临时子群体 2 i f ( 临时予群体的得分高于某个优胜子群体的得 3 用临时子群体替代优胜子群体 4 释放成熟的优胜子群体中的个体 5 e l s ei f ( 1 临时子群体成熟1 6 废弃这个临时子群体 7 释放这个成熟的临时予群体中的个体 太原理工大学硕士学位论文 个体数 8 e n d i f 9 e n d l f 1 0 e n d f o r 1 1 记为被替代或废弃的子群体个数，郎为释放的 1 2 r e t u m ( ) 3 2 4 自适应调整个体散布宽度 在每一个子群体( 包括优胜子群体和初始子群体) 中，在胜 者周围按照某一分布函数形式散布个体已形成新的胜者时，对于 每一维来说( 假设所考虑问题是一个”维问题) ，设个体散布的初 始宽度为w o d ，( d 表示维数，d = 1 ，2 ， ) ，那么，在趋同过程 中，按照公式： w ( i + d d2 ( c 1 w 耐+ c 2 o d ) c 3 可进行自适应调整个体散布宽度，式中i 表示迭代次数，w 甜表示 第d 维旧的散布个体的宽度，它使得个体散布宽度保持相对稳定， 占表示第d 维新的胜者和旧的胜者之间的距离，它使得算法利用 已有的知识进行自适应调整个体散布宽度，c 1 、c 2 和q 是常数， 其中c 。和c ：是两个独立的参数，引入c ；是为了调试程序的方便。 3 2 5m e c 的特点 l 、m e c 与g a 的共同点是都使用群体和进化，且整个过 程都是随机的，具有g a 的基本优点。区别是由于g a 模拟生物 进化过程，而m e c 模拟人的思维进步过程，因此进化的运算不 同。 2 、m e c 把群体划分为子群体，这一思想类似于小生境g a 。 3 、g a 要进行选择、交叉和异化三种操作，而m e c 只有趋 采用m e c 的彩色目标识别 同与异化操作，选择是隐含在这两个操作中。 4 、m e c 具有结构上固有的并行性，类似于小生境g a ，比 基本e c 的隐含并行性更方便。 5 、类似于e c ，m e c 也具有自适应性。 6 、m e c 中的趋同和异化操作分别进行开采和勘探，这两种 功能基本是分开的，并且是非对立的、协调的，因此便于分别提 高效率，其中每一方面的改进都对提高算法的整体搜索效率有利。 7 、m e c 可以记忆不止一代的进化信息，这些信息可以指导 趋同与异化向着有利的方向进行。 8 、m e c 的搜索是定向的，而g a 是不定向的，这使得m e c 的搜索速度更快。 3 3m e c 算法中的三个实现机制 近二十多年来，人们进行了许多探索，从不同的角度改进 g a ，但是在提高效率与解决早熟两方面的效果并不理想。对于遗 传算法性能难于明显改进，而m e c 能够显著提高计算效率和收 敛性能的原因主要是由于机制上的原因 s t m 0 0 a s u n 9 8 a s u n 0 1 c 。 3 3 1m e c 的定向机制 遗传操作结果是不可预知的【f o g e l 9 4 】。首先介绍两个术语： 多表象性和多基因性。多表象性( p l e i o t r o p y ) 指的是单一的一个 基因可能同时影响一系列的表象。多基因性( p o l y g e n y ) 指的是 单一的一个表象可能同时由许多基因的交互作用决定的。由于多 表象性和多基因性的共同作用，“一对多、多对一”的交互影响， 遗传操作的结果一般是不可预知的【6 】，因而不易控制进化的方 向，使得g a 的性能改进变得困难。 3 0 太原理工大学硕士学位论文 而在m e c 中，进化操作趋同和异化都是定向的操作。趋同 操作使各个子群体向各自的局部最优的方向变化：异化操作使优 胜子群体向全局最优的方向变化。 3 3 2m e c 的记忆机制 遗传算法没有很好地利用计算机的记忆能力。“生物进化没 有记忆，有关产生个体的信息包含在个体所携带的染色体的集合 以及染色体编码的结构之中”f d a v i s l 9 1 】。模拟生物进化的遗传 算法也是这样，g a 关于环境的所有信息都保存在当前群体中的 所有的个体中，g a 先前各代从环境得到的信息，若在进化过程 中没有遗传给后代，则这些信息都没有保留下来。换句话说，g a 没有充分地利用从环境得到的信息指导进化的方向，造成g a 的 计算效率较低。 m e c 与g a 不同，m e c 可以记忆若干代的个体的信息，并 可以直接利用这些信息指导进化的方向，正是利用了m e c 的这 种记忆机制，开发出了多种改进的趋同和异化策略，指导进化的 方向，并进一步提高m e c 的计算效率。 3 3 3m e c 中勘探与开采的协调机制 许多学者从勘探与开采角度分析搜索算法，在g a 中，遗传 算子交叉和变异起“勘探”作用，选择起“开采”作用。然而， 在g a 中这两个功能的发挥并不协调，甚至还有许多学者认为在 g a 中这两种作用是对立的，这也是g a 计算效率不高的主要原 因之。关于这个问题的详细讨论请参考a e e i b e n & c a s c h i p p e r s 关于勘探与开采的总结 e i b e n 9 8 】，持有这种对立观点 的研究人员有x q i & f p a l m i e r i q i 8 9 】，l j e s h e l m a n & j d s c h a f f e r e s h e l m a n 9 3 ，k a d ej o n g & w m s p e a r s 【d e j o n 9 9 2 ， l j e s h e l m a n & r a c a r u a n a e s h e l m a n 8 9 1 ，s t s u t s u ie t a 1 采用m e c 的彩色目标识别 ( t s u t s u i 9 7 a 正是由于为了使勘探与开采协调工作的目的，我们建立了 m e c 的框架 s u n 9 8 a 。在m e c 中，进化操作“趋同”起开采的 作用，“异化”起勘探的作用。重要的是，这二者是相对独立的， 可以进行单独开发，且二者是非对立的。趋同对系统从环境得到 局部信息加以开采，迅速搜索局部的最优。若该最优不是搜索空 间中最好的解，则该子群体被废弃，若是当前最好的解，则该子 群体替代优胜子群体，并进一步进行趋同操作，使解迸一步精化。 而异化操作在整个解空间进行搜索，选择较优的个体作为中心创 建新的临时子群体。这两种作用是协调工作的，趋同或异化操作 的改进都对整个算法的搜索有贡献。 由于上述的m e c 与g a 不同的机制，使得m e c 能够比s g a 的计算效率般提高5 0 以上。并能够开发出多种不同的趋同和 异化策略，指导进化的方向，进一步提高m e c 的计算效率。 3 4m e c 算法的研究现状 m e c 自从1 9 9 8 年由孙承意教授提出以来，已经建立了一个 初步完整的理论体系，下面分别从几个不同的方面来详细介绍 m e c 已经取得的进展： 3 4 1 思维进化计算的结构框架 孙承意教授于1 9 9 8 年8 月提出了思维进化计算的理论框架 s u n 9 8 a 。以后所有的工作都是在这个框架下来完成的。在文献 s u n 9 8 a 】【s u n 9 9 a 【s u n 0 0 a 给出了m e c 的具体框架。在本章的 3 2 节已专门介绍了m e c 框架及实现方法。 3 4 2m e c 收敛性能和计算效率的实验研究 自从m e c 提出以来，已经就数值优化问题，作了大萤的实 太原理工大学硕士学位论文 验来证明m e c 算法的高效性，关于这方面的文献有 s u n 0 0 b 1 w a n g j l 0 2 】【z e n 9 9 9 】【z e n 9 0 0 a ，尤其是文献 w a n g j l 0 2 专门搜集 了许多不同类型的函数进行优化。通过这些实验发现，基本m e c 相对简单g a 的提高程度与函数的特点有关，测试过的所有函数 ( 这些函数经常用来分析g a 搜索效率) 均在5 0 以上，许多函 数能提高8 0 以上。 3 4 3m e c 与g a 机制的比较研究 近二十多年来，人们进行了许多探索，从不同的角度改进 g a ，但是提高效率与解决早熟两方面的效果并不理想。对于遗传 算法性能难于明显改进，而m e c 能够显著提高计算效率和收敛 性能的原因主要是由于机制上的原因。这些机制包括定向机制、 记忆机制、勘探与开采的协调机制，文献 s u n 9 8 a 【s t m 0 0 a 】 s u n 0 1 c 】详细比较了m e c 和g a 在这些机制上的不同，详细介绍 可参考3 3 节。 3 4 4 多种高效率趋同策略的开发 由于在予群体内部采用趋同操作找到更好的胜者的时候，如 果在开始阶段个体散布宽度较大，对搜索有利；而在最后阶段个 体散布宽度较小，则更有利于精细搜索，因此，采用统一的个体 散布宽度，将会影响趋同搜索性能。考虑到这一因素，早在文献 【s u n 9 8 a 】中孙承意教授已经提出了自适应趋同策略，该策略使得 个体散布宽度随着趋同操作的不断进行而不断调整，以使趋同更 加高效。另外，在文献 z e n g o o c 也提出了一种自适应趋同策略， 该策略是自适应地调整群体尺寸的大小，提高了趋同搜索效率。 为了提高在高维解空间的搜索能力，提出了一种更为高效的 趋同策略“线一空间交替趋同”策略 w e i 9 9 1 。 为了提高在噪声环境下的m e c 的性能，在文献 s u n 9 9 b 提 采用m e c 的彩色目标识别 出了拟合趋同策略。在噪声环境下，所有的观察值都是不精确的。 在g a 中，为了克服噪声的影响，采用对用一个值进行多次观察 并进行平均作为真值的估计值，但是计算代价成倍增加 a i z a w a 9 3 】。拟合趋同策略对子群体中个体的数据进行拟合，得 到子群体新的胜者的位置。由于在拟合的过程中采用最小二乘方 的方法，可以部分地消除噪声的影响。实验表明，在噪声环境下， 采用拟合趋同的m e c 基本不增加或增加很少的计算量就可以 得到全局最优解的精确的估值。 3 4 5 多种高效率的异化策略的开发 在m e c 中，若某些子群体在竞争过程中被淘汰( 废弃或被 替代) 根据趋同操作的定义，全局最优解肯定不会在这些子群体 胜者的邻域内，这些邻域叫做拒绝域。在基本的m e c 异化操作 中，释放的个体是在整个解空间上均匀地散布的，其中得分最高 的一些个体被选择作为新的临时子群体的初始中心，开始新的趋 同搜索过程。如果落在拒绝域内的个体被选择为新的临时子群体 的初始中心，就会造成重复搜索。为了解决这一问题，提出了一 种新的异化策略采用拒绝域异化策略 s u n 0 1 d 。该策略在趋 同操作过程中记录下搜索过的区域，即拒绝域，使得算法以后不 再搜索这些区域。这样相对地缩小了异化时搜索范围，相应地增 强了m e c 异化操作的全局搜索能力，避免了重复搜索。这也是因 为m e c 具有记忆机制才使采用拒绝域异化策略的提出成为可能。 异化操作保证了m e c 的全局收敛性能，新群体的产生若能 充分利用环境信息，避免或减少异化后的群体中的无效个体和重 复搜索，将会提高整个进化过程的速度。基于这一思想，文献 【z e n 9 0 0 b 比较了五种异化策略的优劣，它们分别是：基于优胜群 体最大模式的异化策略( 无定义最大模式) ，单纯形异化策略，启 发式异化策略，区域收缩异化策略，群体竞争异化策略，通过仿 太原理工大学硕士学位论文 真计算，并与基本异化策略进行比较，发现上述五种异化方法均 使得环境信息得到了应用，进化效果较基本m e c 要优良。 3 4 6m e c 收敛性证明与效率分析 在文献 w a n g c l 0 0 a w a n g c l 0 0 b 】【z e n 9 9 9 ，进行了m e c 算法的收敛性研究，获得了m e c 算法在离散状态和连续状态下 的收敛性，对收敛效率获得了部分成果。解决的关键技术在于：1 ) 、 离散状态空间中运用马尔可夫链、吸引域、局部最优状态等技术 获得了收敛性证明。2 ) 、在连续状态空间中运用函数的勒贝格测 度，用有限的区间逼近连续空间，即由离散逼近连续获得了连续 状态空间的收敛性证明。 3 4 7m e c 用于非数值优化问题 采用m e c 已经成功地解决了一些非数值优化问题 z h a k 0 1 ， 如t s p 、, l o b s h o p 、系统动态建模等。对于这些问题，m e c 都能 够成功地解决编码、趋同异化策略的构造，并比采用其它进化计 算方法在解的精度、计算效率和收敛性能等方面都优越，说明 m e c 具有良好的对问题的适应性和拓展性。 3 4 8m e c 的应用研究 m e c 自从提出以来，已经应用到了很多领域，包括在图像分 析、经济预测系统的构建、自动控制方向上的应用以及将m e c 用于非数值优化问题中，下面就这方面的应用研究给出一个概述： 在图像分析方面，有如下几方面的应用：1 ) 、在文献 s u n 9 8 b 1 中，采用m e c 进行了彩色图像的聚类与重建。由于 m l c n n ( m a x i m u ml i k e l i h o o dc l u s t e r i n gn e u r a ln e t w o r k ) 聚类的 初值的选择对聚类结果影响很大，而把m e c 与m l c n n 结合构 成混合系统，利用m e c 强大的优化功能可以找到m l c n n 最优 采用m e c 的彩色目标识别 的初始聚类中心，完满地解决这个问题，所以提出一个由m l c n n 和m e c 组成的混合系统。与许多聚类算法相比，该混合系统具 有一些明显的优点，实现了对具有强噪声的彩色图像的聚类；2 ) 、 文献 s u n 9 9 c 1 中采用m e c 进行小目标形状匹配，提出采用外接圆 截距特征表示形状，用4 个参数定义两个形状的相似度以及采用 m e c 优化这些参数，得到一对形状之间的匹配度的方法是有效 的，可以进行形状之间尺度不变、旋转、镜像匹配以及两个目标 之间部分形状的匹配。既可以用于基于内容的图像检索系统 ( c b i r ) 中的形状匹配，也可以用于目标识别的目的；3 ) 、利用 m e c 还实现了彩色图像的分割，见文献 s u n o o c 】【s u n 0 0 d ，在i h c 彩色空间度量象素的彩色相似性并形成0 。，即) 连通分量，采用 m e c 和m l c n n 构成的混合系统进行聚类，成功地对多幅图像 进行了分割，得到了较好的效果。另外，还把m e c 的框架应用 于灰度图像的分害- t c h e n 9 0 0 ，这种分割方法考察灰度一致性和集 合连通性。 在经济预测系统的构建方面，提出了采用m e c 的基于模型 选择的经济预测系统 s u n 9 9 d 】 s u n 0 0 e ，利用m e c 来找到时间序 列的时变特征，这使得我们可以选择适合当前时间序列的最好的 预测模型并确定预测模型的参数，该系统具有以下几个优点：a ) 、 相对于神经网络，g a 和专家系统，速度快；b ) 、强适应性：它 适用于时变环境，能在短时间内捕捉环境的变化；c ) 、与神经网 络相比学习能力灵活；d ) 、适用于黑匣子系统和灰色系统，这些 系统都很难建立数学模型。 在自动控制领域方面，将m e c 应用于了水泥生料配比当中 【x i e 0 0 a ，收敛率高，收敛速度快，取得了良好的效果；还将m e c 用于解决智能控制中的动态调整参数问题 x i e 0 0 b ，结合m e c 来 确定最终的调节规律，该方法实现简单方便，不需要专家的经验， 占用计算机的空间也少：在自适应模糊逻辑控制器的设计中，输 出规范化因子对控制品质的影响重大，将m e c 用来选取理想的 太原理工大学硕士学位论文 输出规范化因子 x i e o o c ，可使得控制系统超调量小，抗扰能力 增强，鲁棒性也增强，获得了良好的控制品质；另外，控制领域 中的控制参数由具有强烈的耦合作用，一般的方法难以达到良好 的结果，采用多参数合成的基于m e c 的方法可以有效的解决控 制系统中高维及多维参数空间的参数搜索问题 x i e o o d 】。 采用m e c 的彩色目标识别 第四章思维进化计算与目标识别 4 1 采用思维进化计算的目标识别 4 1 1 刚性模板的实质 第一章谈到模板匹配的方法，能够实现目标识别的平移、旋 转、尺度、镜像不变性：除此之外，基于模板的方法还具有很强 的噪声抑制能力，且匹配过程相对的简单。因此，我们使用模板 匹配法对目标进行识别。 在预先给定目标模板的情况下，利用模板在被搜索图像中寻 找目标最直接的方法是：把模板在待测图像上逐点上下平移，在 每一个位置上计算模扳与它下面所覆盖的区域之间的测度，找出 测度函数的最大值象素所在的位置，由这个象素所确定的区域就 是我们寻找的目标。 使用刚性模板匹配目标，其实质就是在整幅搜索图之内找出 与模板差值最小的，或者是相似度最大的区域。 4 1 2 为什么使用思维进化计算 如果采用遍历的方法搜索待测图像，计算量显然十分的庞大： 设搜索图的宽度为，高度为：模板图像的宽度为邢，高度 为t h ；则模板匹配要在w h 个，甚至比这个范围更多个参考位 置上做匹配计算，而在每一个位置上匹配都要有丁缈x 丁日个点参 加计算；在搜索图中，除一点或者几点之外，都是在非匹配点上 做“无用”工作，计算效率十分低下。因此，希望有一种快速有 效的算法加速匹配过程。 思维进化计算已经很好的解决的数值优化问题，它可以使用 多个群体同时处理多个区域，既能避免的陷入局部最优，又能加 快匹配处理的速度，同时可以保证找到全局的最优解。而且，它 太原理工大学硕士学位论文 使用测度函数来指导搜索过程，使得搜索过程几乎不再需要任何 其它的先验知识和辅助信息，也可以加快算法的执行速度。 为了减少计算量、提高识别速度，我们采用思维进化计算与 模板匹配相结合的方法寻找目标。 4 2 窗口图像的预处理 42 1 确定窗口的参数 同样是模板匹配的方法，本论文采用在待测图像上剪切下一 系列的窗口，将每个窗口内的图像与预先给定目标的模板图像进 行匹配。这一点不同于传统的刚性模板匹配方法。 待测图像中的目标的大小和旋转的角度都可能与模板的不 同。所以需要将窗口内的子图像经过缩放、旋转等处理，转化为 与模板方向相同、尺寸一致的图像，然后进行匹配。 因此，一个窗口矿可以由4 个参数确定：窗口的中心的横、 纵坐标u 川、窗口相对于水平线的旋转角度0 ( 以逆时针旋转为 正方向) 和窗口的宽度0 ( 窗口的高度可以根据窗口的宽度0 和 模板的宽高比例确定) 。把窗口内的图像经过尺度缩放和旋转变 换写入到大小与模板相同的缓冲区中，我们称该图像为样本图像， 记为s f j , o , i ( 工