（计算机软件与理论专业论文）基于改进遗传算法的图像分割.pdf

摘要 遗传算法作为一种求解问题的高效并行的全局搜索方法，以其固 有的鲁棒性、并行性和自适应性，使之非常适于大规模搜索空间的寻 优，已广泛应用许多学科及工程领域。在计算机视觉领域中的应用也 正日益受到重视，为图像分割问题提供了新而有效的方法。 本论文对图像分割算法进行了研究与比较；对遗传算法理论、遗 传算法在图像分割领域的应用现状及遗传分割算法的原理、过程、结 果等几方面做了研究。 通过对遗传算法运行机理的深入研究，针对一些有噪声的图像， 本文提出一种基于改进遗传算法的图像分割方法。算法中采用二维编 码机制；为保持种群的多样性，随机均匀地产生初始种群；遗传操作 中的交叉操作中引入了一项规则防止种群退化；为使遗传算法保持种 群的多样性，以防止出现未成熟收敛，本文设计了一个自适应变异算 子；以及在种群更新机制方面，提出了新的解决方案。 实验结果表明，本文提出的基于改进的遗传算法优化了图像的分 割，运算速度明显比传统分割算法快，而且取得了比传统算法更好的 分割质量。本文程序采用v c + + 6 0 在w i n x p 环境下编译完成。 关键字：遗传算法；图像分割；阈值；遗传算子 a b s t r a c t g e n e t i ca l g o r i t h m ( g a ) i sas o r to f e f f i c i e n t ，p a r a l l e d ，f u l ls e a r c h m e t h o dw i t hi t si n h e r e n tv i r t u e so f r o b u s t n e s s ，p a r a l l e la n ds e l f - a d a p t i v e c h a r a c t e r s i ti ss u i t a b l ef o rs e a r c h i n gt h eo p t i m i z a t i o nr e s u l ti nt h el a r g e s e a r c hs p a c e n o wi th a sb e e na p p l i e dw i d e l ya n d p e r f e c t l yi nm a n ys t u d y f i e l d sa n de n g i n e e r i n ga r e a s i nc o m p u t e rv i s i o nf i e l dg a i si n c r e a s i n g l y a t t a c h e dm o r ei m p o r t a n c e i tp r o v i d e st h ei m a g es e g m e n t a t i o nan e wa n d e f f e c t i v em e t h o d a l g o r i t h m sa n da n a l y s e sa b o u ti m a g es e g m e n t a t i o na r ep r e s e n t e d a n o v e r v i e wo nt h et h e o r i e sa n dt h er e c e n td e v e l o p m e n ti s g i v e n a l s ot h e s t a t u so fg a a p p l i e d i nt h ei m a g es e g m e n t a t i o nf i e l di sp r e s e n t e d ，a n dt h e t h e o r i e s ， s t e p s ， r e s u l t sa n d a n a l y s e so f s e v e r a lg a a p p l i e di nt h ei m a g e s e g m e n t a t i o na r eg i v e i l t h r o u g ht h ed e e pr e s e a r c h a n d c o m p a r e o nt h eg af i e l d s ，a n i m p r o v e dg e n e t i ca l g o r i t h m i n i m a g es e g m e n t a t i o n i s p r o p o s e d t o e f f e c t i v e l ya c c o m p l i s ha n a l y s i s t a s k sf o r n o i s yi m a g e s i n t h en e w a l g o r i t h m s ：c o d i n gw i t h2 - d i n a e n t i o nc h r o m o s o m e i sa d o p t e d ；i n i t i a l i z a t i o n o f p o p u l a t i o nw i t hs t o c h a s t i ca n ds y m m e t r i c a l m e t h o d si sp r o d u c e dt ok e e p t h ev a r i e t yo ft h ep o p u l a t i o n ；an e wr u l ei s i m p o r t e di nt h ec r o s s o v e r o p e r a t i o n t oa v o i dt h e p o p u l a t i o nd e g e n e r a t i n g ；aa d a p t i v e m u t a t i o n o p e r a t o r i s p r o p o s e di n t h em u t a t i o no p e r a t i o nt oa v o i dt h ei m m a t u r e c o n v e r g e n c e ；an e wm e t h o d i s d e s i g n e d i nt h e f o r m i n go ft h e n e w p o p u l a t i o n t h er e s u l to f e x p e r i m e n ts h o w st h a tt h en e wa l g o r i t h mc a ni m p r o v e g r e a t l yt h es p e e d a n d g e tt h e b e t t e rq u a l i t yt h a nt h et r a d i t i o n a la l g o r i t h m p r o g r a m sw e r e a l lc o m p i l e di nt h ew i n d o w sx p b y v c + + 6 0 k e y w o r d s ：g e n e t i ca l g o r i t h m ；i m a g es e g m e n t a t i o n ；t h r e s h o l d ；g ao p e r a t o r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得东北师范大学或其他教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 十，7 学位论文作者签名：巧显辔 日期： 趁坚：乏 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论 文的规定，即：东北师范大学有权保留并向国家有关部门或机构送 交学位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权东 北师范大学可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：扭指导教师签名； 日 期：鑫鲤业：上：j 日 期： 学位论文作者毕业后去向： 工作单位：二荭盥l 弛盘；二强援! 薹p 釉电话：鲤! 垡 通讯地址：蓝a 望! i 查左三土豆! a 型耋f ；乏邮编：z 丕丝丝 东北师范大学硕士学位论文 第一章引言 1 1 本论文的研究目的和意义 图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标 的技术和过程。这里所说的特性可以是灰度、颜色、纹理等，而目标 可以对应单个区域，也可以对应多个区域。分割出的区域需同时满足 均匀性和连通性的条件。其中均匀性是指该区域中的所有像素点都满 足基于灰度、纹理、颜色等特征的某种相似性准则，连通性是指该区 域内存在连接任意两点的路径。 目前，已提出很多种类型的分割算法，大致可以分为基于边缘检 测的方法和基于区域的方法。在实际应用中，从不同的理论角度提出 了许多方法，这些方法中主要可划分为三种类型：阈值型、边缘检测 型和区域跟踪型。 图像分割的应用非常广泛，几乎出现在有关图像处理的所有领域， 并涉及各种类型的图像。例如：在医学图像处理与分析中，无论对于 三维显示还是对目标物体( 组织、器官) 的分析，图像分割都占有十 分重要的地位。在交通图像分析中，将目标车辆从复杂背景中分割出 来等等。通常，图像分割是为了进一步对图像进行分析、识别、压缩、 编码等，图像分割的准确性将直接影响后继的工作。因此，分割的方 法和精确程度是至关重要的。 通常图像具有不确定性，即模糊性，因此图像分割问题目前尚未 对不同的图像形成统一的能达到最优分割质量的方法。多年来，图像 分割一直得到人们的高度重视，但它的研究进展比较缓慢，被认为是 计算机视觉中的一个瓶颈。 遗传算法( g e n e t i ca l g o r i t h m ) 是模拟生物学的自然遗传和达尔文 进化理论的自适应随机优化搜索算法。它起源于6 0 年代，由美国学者 j o h nh o l l a n d 提出，已经在许多领域有应用研究。遗传算法的操作对 象是一群二进制串( 称为染色体、个体) ，即种群，每个染色体都对应 东北师范大学硕士学位论文 于问题的一个解。从初始种群出发，采用基于适应值比例的选择策略 在当前种群中选择个体，使用交叉和变异来产生下一代种群。如此一 代代演化下去，直到满足期望的终止条件。遗传算法作为一种求解问 题的高效并行的全局搜索方法，其主要特点是群体搜索策略和群体中 个体之间的信息交换，它能在搜索过程中自动获取和积累有关搜索空 间的知识，自适应地控制搜索过程以求得最优解或近似最优解，即满 意解。 现有的图像分割算法都是针对某一类特定的图像，因此，图像分 割至今为止尚无通用的自身理论。近年来，遗传算法、数学形态学、 人工神经网络、小波变换已应用于图像分割领域。遗传算法作为一种 基于达尔文生物进化论的全局优化搜索算法，以其固有的鲁棒性、并 行性和自适应性，为图像分割问题提供了新而有效的方法。它不仅可 以得到全局最优解，而且大量缩短了计算时间。文献 3 将遗传算法应 用在小目标图像分割中，利用遗传算法能自动在搜索空间内快速寻优 的特点，取得了良好的分割质量，而且运算速度提高了2 1 。5 。文献 4 采用多参量的遗传算法分割目标图像比传统分割方法具有更好的 分割效果。文献 5 利用遗传算法改进k a p u r 等人提出的最佳熵闽值确 定法( k s w 熵法) ，缩短了运算时间。 本文的工作就是从理论上对遗传算法的工作过程做了分析研究， 将其引入图像分割的算法中，用来提高分割质量，同时加快分割速度。 1 2 本论文的主要工作 本文所做的研究工作主要有： 1 综述遗传算法的发展历史、遗传算法的理论基础、特点，及其应 用概况。 2 分析了现有的图像分割方法。 3 针对现有的图像分割方法存在的缺陷，分析了一些结合遗传算法 的图像分割算法。 4 根据对各种基于遗传算法的图像分割方法研究比较，提出一种改 进的遗传算法来优化图像分割。从编码到种群的初始化、遗传操 东北师范大学硕士学位论文 作中交叉操作及变异算子的选择，以及种群更新机制，提出了新 的解决方案。尤其是自适应的变异算子选择，提出了自己的观点。 1 3 本论文的内容安排 本论文的主要内容安排如下： 第一章引言。简要介绍了图像分割技术，及遗传算法在图像分割 领域的应用现状。提出本论文的主要工作及全文的内容安排。 第二章介绍了遗传算法的发展历史，特点，基本原理以及其应用 研究概况。 第三章图像分割算法综述部分主要介绍了现有的图像分割技术， 描述了边缘检测分割算法，区域跟踪分割法及阈值分割法。着重描述 了阈值分割法。 第四章遗传算法在图像分割中的应用研究阐述了遗传算法在图像 分割领域的应用现状，并给出了遗传算法应用于图像分割时的一股步 骤。 第五章基于改进遗传算法的图像分割，在这章中提出了一种新的 基于遗传算法的图像分割方法，算法在几个方面做了技术上的改进， 通过分析实验结果，得出结论。 第六章总结全文，并给出进一步研究方向及展望。 东北师范大学硕士学位论文 第二章遗传算法综述 遗传算法是一种借签生物界自然选择和进化机制发展起来的高度 并行、随机、自适应搜索算法。其主要特点是它使用了群体搜索技术， 将种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一 系列遗传操作，从而产生新一代的种群，并逐步使种群进化到包含近 似最优解状态。由于其思想简单、易于实现以及表现出来的健壮性， 遗传算法已广泛应用于许多领域。 2 1 遗传算法的发展历史 遗传算法( g a ) 是由美国密歇根大学j h h o l l a n d 等人在七十年 代首次提出，并发表了第一本比较系统论述遗传算法的专著自然系 统与人工系统中的适应性( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a l s y s t e m s ) ，该书比较全面地介绍了遗传算法，并建立了它的数学框架。 该方法一经提出便受到了关注，到8 0 年代中期其研究开始进入高潮。 遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的， 它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当 时人工智能的发展服务的。迄今为止，遗传算法是进化算法中最广为 人知的算法。g o l d b e r g 和m i c h a l e w i c z 进行了大量的研究工作，并成 功地将它应用到各种领域的优化问题。 遗传算法主要在复杂优化问题求解和工业工程领域应用，取得了 一些令人信服的结果，所以引起了很多人的关注。遗传算法成功的应 用包括：旅行商( t s p ) 问题、煤气管道的优化、自动控制、车辆路径 选择与调度、交通问题等等。近年来迅速扩展到机器人工智能控制、 设计规划、机器学习、神经网络优化、核反应堆控制、喷气发动机设 计、通信网络设计、人工生命等领域，这些充分显示了遗传算法应用 的巨大潜力。目前，遗传算法作为一种基于统计理论的优化和搜索技 术，在计算机视觉领域中的应用也正日益受到重视，如在特征提取、 图像匹配、图像分割中的应用。 东北师范大学硕士学位论文 2 2 遗传算法概述 2 2 1 遗传算法的基本概念 遗传算法是基于自然选择，在计算机上模拟生物进化机制的寻优 搜索算法。在自然界的演化过程中，生物体通过遗传( 传种接代，后 代与父辈非常相像) 、变异( 后代与父辈又不完全相像) 来适应外界 环境，一代又一代地优胜劣汰，发展进化。遗传算法则模拟了上述进 化现象。它把搜索空问( 欲求解问题的解空间) 映射为遗传空间，即 把每一个可能的解编码为一个向量( 二进制或十进制数字串) ，称为 一个染色体，向量的每一个元素称为基因。所有染色体组成群体，并 按预定的目标函数( 或某种评价指标) 对每个染色体进行评价，根据 其结果给出一个适应度的值。算法开始时先随机地产生一些染色体( 欲 求问题的候选解) ，计算其适应度，根据适应度对各染色体进行选择复 制、交叉、变异等遗传操作，剔除适应度低( 性能不佳) 的染色体， 留下适应度高( 性能优良) 的染色体，从而得到新的群体。由于新群 体的成员是上一代群体的优秀者，继承了上一代的优良性态，因而明 显优于上一代。遗传算法就这样反复迭代，向着更优解的方向进化， 直至满足某种预定的优化指标。 遗传算法中的基本术语： 群体( p o p u l a t i o n ) ：又称种群、染色体群，个体( i n d i v i d u a l ) 的集合，代表问题的解空间子集。 群体规模( p o p u l a t i o ns i z e ) ：染色体群中个体的数目称为群体的 大小或群体规模。 适应度( f i t t n e s s ) ：用来度量种群中个体优劣( 符合条件的程度) 的指标值，它通常表现为数值形式。 选择( s e l e c t i o n ) ：根据染色体对应的适应值和问题的要求，筛选 种群中的染色体，染色体的适应度越高，保存下来的概率越大，反 之则越小，甚至被淘汰。 交叉( c r o s s o v e r ) ：指在一定条件下两条染色体上的一个或几个基 因相互交换位置。 东北师范大学硕士学位论文 交叉概率：判断是否满足交叉条件的一个小于1 的阀值。 变异( m u t a t i o n ) ：指在一定条件下随机改变一条染色体上的一个 或几个基因值 变异概率：判断是否满足变异条件的一个小于1 的阀值。 后代：染色体经过交换或变异后形成的新的个体。 2 2 2 遗传算法的基本流程 遗传算法的基本流程如图2 1 所示，其中选择( s e l e c t i o n ) 、交 叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 是遗传算法中的三种基本遗传操 作。遗传算法的主要步骤如下： ( 1 ) 确定编码。 ( 2 ) 随机产生初始群体。 ( 3 ) 对染色体群体迭代地执行下面的步骤，直到满足停止准则： 计算群体中每个染色体的适应度值； 应用选择、交叉和变异算子产生下一代群体。 ( 4 ) 输出最佳个体，算法结束。这个最佳个体做为结果可以表示问题 的一个解( 或近似解) 。 东北师范大学硕士学位论文 开始 图2 1 遗传算法基本流程图 遗传算法搜索可能的特征空间来寻找高适应度的染色体，通过执 行选择、交叉和变异操作来完成它的搜索。在实际应用中，遗传算法 能够快速有效地搜索复杂、高度非线性和多维空间。 2 3 遗传算法的构成 遗传算法中包含了五个基本要素 ( 1 ) 编码； 东北师范火学硕+ 学位论文 ( 2 ) 确定初始群体； ( 3 ) 适应度函数设计： ( 4 ) 遗传操作； ( 5 ) 控制参数的设定。 这五个要素构成了遗传算法的核心内容。 1 编码 在遗传算法中，编码方法是把问题的搜索空间中每个可能的点表 示为确定长度的特征串。编码方法的确定需要选择串长和字母表规模。 在染色体串和问题的搜索空间中的点之间选择映射有时容易实现，有 时又非常困难。选择一个便于遗传算法求解问题的编码方法经常需要 对问题有深入的了解。二进制串是遗传算法中常用的表示方法，即o 、 l 字符串。例如；对于 0 ，2 5 5 之间的数，可用8 位二进制码串来表示， 用0 0 0 0 0 0 0 0 1 1 1 1 1 i i i 来表示 0 ，2 5 5 之间的数。 2 确定初始群体 由多个染色体组成具有一定群体规模的染色体集合或称解的集 合。遗传算法将基于这个集合进行遗传操作，每一轮操作( 包括选择、 交叉、变异) 后生存下来的染色体组成新的种群，形成可以繁衍下一 代的群体。初始种群的选取与实际问题有关，通常初始种群是随机产 生的。 3 适应度函数 适应度( f i t t n e s s ) ，用来度量种群中个体优劣( 符合条件的程度) 的指标值，适应函数基本上依据优化问题的目标函数而定。当适应函 数确定以后，自然选择规律是以适应函数值的大小以及问题的要求来 确定哪些染色体适应生存，那些被淘汰。适应度函数为群体中每个可 能的染色体指定一个适应度值。同时，适应度函数必须有能力计算搜 索空间中每个确定的染色体的适应度值。它通常表现为数值形式。 4 遗传操作 选择( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 是 遗传算法中的三种基本遗传操作。下面分别加以介绍。 1 ) 选择操作 东北师范大学硕士学位论文 选择( s e l e c t i o n ) ，根据染色体对应的适应度值和问题的要求， 筛选种群中的染色体，染色体的适应度越高，保存下来的概率越大， 反之则越小，甚至被淘汰。选择操作通常选用适应度比例法( 轮盘赌 方式) ，它是以适应度的大小为比例进行遗传过程中的父体选择，适应 度越高的个体被选中的机率就越大。也就是处于优势的个体有更多的 繁衍机会。具体做法是：首先计算群体中各个体的适应度，得相应的 累计值s i ，最后一个累计和为s 。；第二，在 0 ，s 。 区间内随机的生成 o s 。之间随机数k ；第三，依次用s ，与k 相比较，从第一个个体开始累 加，直到累加值大于此随机数k ，此时最后个累加的个体便是要选择 的个体。重复二、三步，直至满足所需的个体数目。 2 ) 交叉操作 交叉操作模拟生物进化过程中的繁殖现象，通过两条染色体上的 一个或几个基因相互交换位置，来产生新的优良品种。 交叉算子有多种，其中最简单的单点交叉算子的作用过程如下： 首先，在匹配集中任选两个染色体，这对染色体称为双亲染色体；第 二，随机选择一点交换点位置k ( k 1 ，是染色体数字串的 长度) ；第三，按交叉概率p c 交换双亲染色体交换点右边的部分，生 成后代染色体。表2 1 是交叉操作示例，字符串内的下横线表示交叉点 的位置。 表2 1 交叉操作示例 序号交叉前交叉后 1 父代个体1 ：1 0 1 0 1 1 0 1子代个体1 ：1 0 1 0 0 0 1 0 2父代个体2 ：1 0 0 1 0 0 1 0 子代个体2 1 0 0 1 1 1 0 1 单点交叉算子的一个重要特性是它可产生与原配对串完全不同的 子代串；另一个重要特性是它不会改变原配对串中相同的位，一个极 端情况是当两个配对串相同时，交叉算子不起作用。 3 ) 变异操作 变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引 起的基因突变，它以一个很小的变异概率p 埘随机地改变遗传基因( 表 东北师范大学硕士学位论文 示染色体的符号串的某一位) 的值。在染色体以二进制编码的系统中， 它随机地将染色体的某一个基因由1 变成0 ，或由o 变成1 。表2 2 是 变异操作示例，字符串内的下横线表示变异点的位置。 表2 2 变异操作示例 序号变异前变异后 1 父代个体1 一1 0 1 0 1 1 0 1 子代个体1 ：0 0 1 0 1 1 0 1 2 父代个体2 i1 0 0 1 1 0 0 1子代个体2 1 1 0 1 1 0 0 1 5 控制参数 控制遗传算法的主要参数有群体规模和算法执行的最大代数，次 要参数有交叉概率p a 并1 3 变异概率p m 等参数。 一般从运算的角度考虑，种群的规模不要选取过大也不能太小。 选择较大数目的初始种群可以同时处理更多的解，因而容易找到全局 r 2 1 最优解，其缺点是增加了每次迭代的时间，文献一建议的最佳参数范 围是：初始种群n = 2 0 1 0 0 。交叉率的选择决定了交叉操作的频率，频 率越高，可以越快地收敛到最有希望的最优解区域，因此一般选取较 大的交叉率，但太高的频率也可能导致过早收敛，一般取值p c = o 4 0 9 。变异率的选取一般受种群大小、染色体长度等因素影响，通常选 取很小的值，一般取p m = o 0 0 1 o 1 。若选取高的变异率，虽然增加样 本模式的多样性，但可能会引起不稳定。种群大小及染色体长度越大， 变异率选取越小。 在基本遗传算法中，这些参数是不变的。如果要提高遗传算法的 性能，则往往需要借助对基本遗传算法的改进，改进的手段可以是多 方面的，如适应度比例调整、引入自适应交叉率和变异率等。 遗传算法迭代地执行从父代产生子代的过程，直到满足某个停止 准则。目前使用严格的数学方法判定遗传算法的终止( 收敛) 条件还 比较难。因此，大多数应用系统在实际中采用的主要是启发式方法， 如用以下条件来判定算法的终止： 是否到了预定算法的最大代数； 东北师范大学硕士学位论文 是否找到某个较优的染色体； 连续几次迭代后得到的解群中最好解是否变化等。 2 4 遗传算法的基本理论 遗传算法作为一种复杂问题的智能算法，它的理论基础是模 式定理和积木假说。 2 4 1 模式定理 定义1 ( 模式) ：基于三值字符集 0 、1 、 ) 所产生的能描述具有某 些结构相似的0 、1 字符串集的字符串称作模式。 定义2 ( 模式阶) ：模式h 中确定位置的个数称作该模式的模式阶 ( s c h e m ao r d e r ) ，记作0 ( h ) 。 例如，模式0 1 1 i * 的阶数为0 ( 0 1 1 i * ) = 4 ，而模式0 $ 十 的 阶数为0 ( 0 $ $ $ ) = 1 。显然一个模式的阶越高，其所代表的集合所 包含的个体数目越少，因而确定性越高。 定义3 ( 定义距) ：模式h 中的第一个确定位置和最后一个确定位 置之间的距离称作该模式的定义距( d e f i n i n gi e n g t h ) ，记作6 ( h ) 。 比如模式0 1 1 $ 1 十的定义距为6 ( 0 1 1 1 ) = 4 ，而模式0 十十的 定义距为6 ( 0 木) = 0 。 模式定理 ：在遗传操作数选择、交叉和变异的作用下，具有低 阶、短定义距以及平均适应度的模式越来越多，最后得到这些模式的 组合，性能得到改善，最终趋向全局的最优解。因此，在考虑选择、 交叉和变异操作的作用下，一个特定模式在下一代中期望出现的数目 可以近似地表示为： m ( h t 十1 ) m ( h ，t ) 掣 1 他翼一d ( h ) p 。 ( 2 1 ) ， f l 式中，m ( h ，t + 1 ) ：表示在t + l 代种群中存在模式h 的个体数目； m ( h ，t ) ：表示在t 代种群中存在模式h 的个体数目； ，( 月) ：表示在t 代种群中存在模式h 的个体数目； 东北师范大学硕士学位论文 厂：表示在t 代种群中所有个体的平均适应度 z ：表示个体的长度； p 一：表示交叉概率； p 。：表示变异概率。 2 4 2 积木块假设 由前面的模式定理可知，具有低阶、短定义距以及平均适应度高 于群体适应度的模式在后代中将以指数级增长。这类模式在遗传算法 中非常重要，我们称之为“积木”或“基因块”( b u i l d i n gb l o c k ) 。 如同搭“积木”一样，这些“好”的模式在遗传操作下相互拼接、结 合，产生适应度更高的个体，从而找到更优的可行解。这正是“积木 假说”( b u i i d i n gb l o c kh y p o t h e s i s ) 所揭示的内容。 积木块假设 ：低阶、短定义距、高平均适应度的模式在遗传算子作 用下，相互结合，能生成高阶、长定义距、高平均适应度的模式，可 最终生成全局最优解。 前面的模式定理保证了在一定条件下较优的模式的样本数呈指数 级增长，从而满足了寻找最优解的必要条件，即遗传算法存在找到全 局最优解的可能性。而积木假说则指出了遗传算法具备找到全局最优 解的能力。 2 5 遗传算法的特点 与传统算法相比，遗传算法以其固有的鲁棒性、并行性等特点 使它能够适用于求解不同类型的问题。 2 5 1 传统优化算法的特点 传统的优化算法的类型与特点： 1 枚举法 枚举出可行解集合内的所有可行解，以求出精确最优解。对于连 东北师范大学硕士学位论文 续函数，该方法要求先对其进行离散化处理，这样就可能因离散处理 而永远达不到最优解。此外，当枚举空间比较大时，该方法的求解效 率比较低，有时甚至在目前先进计算工具上无法求解。 2 启发式算法 寻求一种能产生可行解的启发式规则，以找到个最优解或近似 最优解。该方法的求解效率比较高，但对每一个需求解的问题必须找 出其特有的启发式规则，这个启发式规则般无通用性，不适合于其 他问题。 3 搜索算法 寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索 操作，以找到问题的最优解或者近似最优解。该方法虽然保证不了一 定能够得到问题的最优解，但若适当地利用一些启发知识，就可在近 似解的质量和效率上达到一种较好的平衡。 随着问题种类的不同以及问题规模的扩大，要寻求一种能以有限 的代价来解决搜索和优化的通用方法，遗传算法正是为我们提供的一 个有效的途径，它不同于传统的搜索和优化方法。 2 5 2 遗传算法的特点 遗传算法的主要特点有： i 遗传算法不是直接作用在参变量上，而是利用参变量集的某种编 码； 遗传算法把欲求解问题的解空间映射为遗传空间，将待优化问题 的原始参数进行编码。这样做的好处是大大减少了约束条件的限制， 如连续性、可导性等。 2 遗传算法在点群中而不是在一个单点上进行寻优； 许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。 遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行 评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。 3 遗传算法只利用适应度信息，无需导数或其他辅助信息； 以往很多搜索方法都需要辅助信息才能正常工作。而遗传算法基 东北师范大学硕士学位论文 本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评 估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的 约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范 围大大扩展。 4 遗传算法利用概率转换规则，而非确定性规则。 遗传算法用随机选择作为工具去指导搜索向着搜索空间中可能的 更好区域进行。遗传算法能以很大的概率找到全局最优解。 遗传算法的优越性主要表现在：首先，它在搜索过程中不容易陷 入局部最优，即使在所定义的适应度函数是不连续的、非规则的或有 噪声的情况下，它也能以很大的概率找到整体最优解；其次，由于它 固有的并行性，遗传算法非常适用于大规模并行计算机。 遗传算法具有很高的鲁棒性和并行性，并且不受连续性、单峰等 假设的限制，能够有效地解决全局优化问题。但它也存在收敛速度慢、 算法运算量较大的缺点。 由于遗传算法没有利用目标函数的梯度等信息，无法确定染色体 在解空间中的位置，无法用常规数学方法确定遗传算法是否收敛。有 人已经证明，在任意初始化、任意交叉算子以及任意适应度函数下， 遗传算法都不能收敛到全局最优。而通过改进遗传算法，即不按比例 法进行选择复制，而是在选择复制前( 或后) 保留当前所得最优解， 则能收敛至全局最优解。但是收敛到最优解的时间可能非常长。基本 遗传算法的一个主要的实用局限性就是较慢的收敛性。因此，通过引 进适用于特定应用的新算子，改进的遗传算法的收敛速度将大为提高。 2 。6 遗传算法的应用研究概况 目前，遗传算法在很多科学、工程领域得到了广泛的应用。下面 列举了一些遗传算法的应用领域： ( 1 ) 优化：遗传算法可用于各种优化问题。既包括数量优化问题， 也包括组合优化问题。 ( 2 ) 程序设计：遗传算法可以用于某些特殊任务的计算机程序设 计，如元胞计算机。 东北帅范大学硕士学位论文 ( 3 ) 机器学习：遗传算法可用于许多机器学习的应用，包括分类 问题和预测问题等，如预测天气或预测蛋白质的结构。 ( 4 ) 经济学：应用遗传算法对经济创新的过程建立模型，可以研 究投标的策略，还可以建立市场竞争的模型。 ( 5 ) 免疫系统：应用遗传算法可以对自然界中免疫系统的多个方 面建立模型，研究个体的生命过程中的突变现象以及发掘进化过程中 的基因资源。 ( 6 ) 生态学：遗传算法可以应用于对生态学的一些现象进行建模， 包括生物间的生存竞争，宿主寄生物的共同进化，共生现象，甚 至包括生物学“军备竞赛”。 ( 7 ) 进化现象和学习现象：遗传算法可以用来研究个体是如何学 习生存技巧的，一个物种的进化对其他物种会产生何种影响等等。 ( 8 ) 社会经济问题：遗传算法可以用来研究社会系统中的各种演 化现象，例如在一个多主体系统中，协作与交流的是如何演化出来的。 东北师范大学硕士学位论文 第三章图像分割算法综述 图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标 的技术和过程。这旱所说的特性可以是灰度、颜色、纹理等，而目标 可以对应单个区域，也可以对应多个区域。图像分割是自动目标识别 的关键和首要步骤，也是一种基本的计算机视觉技术。图像分割的准 确性将直接影响后继的工作。因此，分割的方法和精确程度是至关重 要的。 目前，已提出很多种类型的分割算法，大致可以分为基于边缘检 测的方法和基于区域的方法。在实际应用中，从不同的理论角度提出 了许多方法，这些方法中主要可划分为三种类型：阈值型、边缘检测 型和区域跟踪型。随着新理论、新技术的发展，一些新的图像分割方 法也随之出现，下面分别加以介绍。 3 1 边缘检测分割法 边缘检测分割法是先检测图像中的边缘点，再按一定策略连接成 轮廓，从而构成分割区域。边缘是指图像中像素坎度有阶跃变化或屋 顶状变化的那些像素的集合。它存在于目标与背景、目标与目标、区 域与区域、基元与基元之间。边缘是灰度值不连续的结果，这种不连 续常可利用求一阶和二阶导数方便地检测到。 实际上数字图像中求导数是利用差分近似微分来进行的，故边缘 的检测常借助于空域微分算子通过卷积完成。边缘检测算子检查每个 像素的邻域并对灰度变化率进行量化，通常也包括方向的确定。算子 运算时是采取类似卷积的方式，将模板在图像上移动并在每个位置计 算对应中心像素的梯度值。 目前比较常用的有一阶导数算子如：罗伯特边缘( r o b e r tc r o s s ) 算子，它用的是如图3 1 所示的2 个2 2 模板。r o b e r t 算子对具有陡 峭的低噪声图像响应最好。 东北师范大学硕士学位论文 口匪 图3 一lr o b e r t s 边缘算子 为在检测边缘的同时减少噪声的影响，蒲瑞维特( p r e w i t t ) 算子 加大了检测算子模板的大小，由2 2 扩大到3 x3 模板，如图3 2 所 不o | _ 1 01 i _ 1 01 | 1 0 1 | _ 1 - 1- 1 0 0 0 1 1 1 图3 - 2p r e w i t t 边缘算子 索贝尔( s o b e l ) 在p r e w i t t 算子的基础上，对4 一领域采用带权的方 法计算差分，对应的模板如图3 3 所示。 i - i 01 l ， 0 2 l _ 1 0 1 l 一1- 2 1 0 0 0 l2 1 图3 3s o b e l 边缘算子 拉普拉斯算子( l a p l a c e ) 是不依赖于边缘方向的二阶微分操作数， 该算子对应的模板如图3 4 所示。它是一个与方向无关的各向同性边 缘检测算子。若只关心边缘点的位置而不顾其周围的实际灰度差时， 一般选择该算子。 0 1 0 l - 4 1 0 1 0 图3 4l a p l a c e 算子 下面对各种操作数作一下比较。图3 4 为各种边缘检测算予进行 图像分割的结果。 东北师范大学硕士学位论文 ( a ) 原始图像( b ) r o b e r t 算子分割结果 ( c ) p r e w i t t 算子分割结果( d ) s o b d 算子分割结果 ( e ) l a p l a c i a n 算子分割结果 图3 - 5 边缘检测结果 如图所示，采用p r e w i t t 算子不仅能检测边缘点，而且能抑制噪 东北师范大学硕士学位论文 声的影响。s o b e l 算子能检删边缘点，且能进一步抑制噪声的影响，但 检测的边缘较宽。在边缘灰度值过渡比较尖锐且图像中噪声比较小时， 梯度算子工作效果较好。对于二阶导数拉普拉斯( l a p l a c j a n ) 算子， 它对图像中的噪声相当敏感，常产生双像素宽的边缘，对噪声有双倍 加强的作用。所以它常用于己知边缘像素后确定该像素是在图像的暗 区或明区一边。在噪声较大的情况下常用的边缘检测算法还有m a r t 算 子，c a n n y 算子等，它们都是先对图像进行适当的平滑，抑制噪声，然 后求导数，或者先对图像进行局部拟合，然后再用拟合的光滑函数的 导数来代替直接的数值导数。 3 2 区域跟踪分割法 3 2 1 区域生长法 区域跟踪是寻找具有相似性的像素群。目前常用的方法有区域生 长方法、区域分裂合并法。 区域生长方法从若干种子点或种子区域出发，按照一定的生长准 则，对邻域像素点进行特征判别，将特征相似的相邻像素合并为同一 区域；以合并像素为生长点，继续重复以上操作，最终形成具有相似 特征的像素的最大连通集合。其中种子点可采用人机交互或自动方法 设定。用于区分不同物体内像素的性质包括平均灰度值、纹理或颜色 信息。相似性准则可以取像素的灰度值与邻域的灰度均值比较，若差 值在接受范围内则进行合并。这种方法若不考虑像素间的连通性和邻 近性，会出现毫无意义的分类结果。 用区域生长法进行图像分割效果如图3 6 所示。这里依次用图像 的每一个像素的灰度值和标准阈值相减，判断结果是否小于标准差， 是则将该点和种子点合并，不是则保持像素点的灰度值不变。 东北师范大学硕士学位论文 ( a ) 原始图像区域生长法分割结果 图3 6 区域生长法分割 3 2 2 区域分裂合并法 区域分裂合并法首先将图像分割为初始的区域，然后按性质相似 的准则，反复分开特性不一致的区域、合并具有一致特性的相邻区域， 直至形成一张区域图。这种方法能充分组合图像的全局和局部信息。 下面给出一种用金字塔形四叉树数据结构指导下的分割方法，其步骤 如下： ( 1 ) 确定均匀性测试准则t ，将原始图像构造成四叉树数据结 构。 ( 2 ) 将图像四叉树结构中的某一中间层作为初始的区域划分。如 果对任何区域r ，有t ( r ) = f a l s e ，则把区域分裂成4 个子区，若任一 1 4 子区r ；，有h ( r ，) = f a l s e ，则再将该子区一分为4 个区域。如果 对任一恰当的4 个子区有h ( r a l u r a 2 u r a 3 u r a 4 ) = t r u e ，则再把4 个 子区合并成一个区。重复上述操作，直到不可再分或再合为止。 ( 3 ) 若有不同大小的两个相邻区域r ，和r ，满足h ( r ，u r ，) - t r u e ，则合并这两个区域。 区域分裂一合并法能够较好的保持原图像的特性，这点优于区域增 长法处理。但也存在区域初始划分和选择区域性质一致性度量、边界 模糊性度量两个重要的问题。而且算法结构本身及对数据结构的要求 都比较复杂，因此计算量很大。 东北师范大学硕士学位论文 3 3 阈值分割法 阈值分割法是一种简单有效的图像分割方法，最大的特点是计算 简单。它用一个或几个阈值将图像的灰度级分为几个部分，所有灰度 值大于或等于某闽值的像素认为属于物体，所有灰度值小于该闽值的 像素认为属于背景。 设( x ，y ) 是二维数字图像的平面坐标，图像狄度级的取值范围是 g = 0 ，l ，2 ，l - 1 ) ( 习惯上0 代表最暗的像素点，l - 1 代表最亮的像 素点) ，位于坐标点( x ，y ) 上的像素点的灰度级表示为f ( x ，y ) 。设t g 为分割阈值，b = b o ，b 1 ) 代表一个二值灰度级，并且b 0 ，b 1 b 。 于是图像函数f ( $ ，$ ) 在阈值t 上的分割结果可以表示为： i b 0 ，( x ，y ) t t ( x ，y ) = ( 3 1 ) 1 6 1 ，( x ，j ，) i t 闽值分割法实际就是按某个准则函数求最优阈值t 的过程。阈值 一般可写成如下的形式： t ：t i x ，y ，f ( x ，y ) ，p ( x ，y ) j 其中f ( x ，y ) 是在像素点( x ，y ) 处的灰度值，p ( x ，y ) 是该点邻域 的某种局部性质。借助上式，将阈值分割方法分为3 类： ( 1 ) 全局阈值：t = t p ( x ，y ) ，即仅根据f ( x ，y ) 来选取阈值， 阈值仅与各个图像像素的本身性质有关。 ( 2 ) 局部闽值：t = t f ( x ，y ) ，p ( x ，y ) ，闽值与图像像素的本 身性质和局部区域性质相关。 ( 3 ) 动态闽值：t = t x ，y ，f ( x ，y ) ，p ( x ，y ) ，阈值与像素坐 标，图像像素的本身性质和局部区域性质相关。 全局阈值对整幅图像仅设置一个分割闽值，通常在图像不太复杂、 灰度分布较集中的情况下采用；局部阈值则将图像划分为若干个子 图像，并对每个子图像设定局部阈值；动态阈值是根据空间信息和 灰度信息确定。局部阈值分割法虽然能改善分割效果，但存在几个 缺点： 查! ! 堕堕查堂堡主堂垡笙塞 ( 1 ) 每幅予图像的尺寸不能太小，否则统计出的结果无意义。 ( 2 ) 每幅图像的分割是任意的，如果有一幅子图像正好落在目标 区域或背景区域，而根据统计结果对其进行分割，也许会产生更差的 结果。 ( 3 ) 局部闽值法对每一幅子图像都要进彳亍、统计，速度慢，难以适 应实时性的要求。 全局阈值分割方法在图像处理中应用比较多，它在整幅图像内采 用固定的闽值分割图像。阈值分割的方法很多，本文针对实际应用情 况，介绍几种常用的阈值分割方法。 3 3 1p - t i l e 法 p t i l e 法是早期的基于灰度直方图的自动阈值选择方