论 文
题 目：院 系：专 业：班级学号：****：
遗传算法应用 计算机工程系 网络工程 ********* *** 2014年10月23日
内容摘要
图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。图像的分割是以灰度值作为分割的依据,通过各个像素的灰度值和事先确定的阈值的比较来分割图像。如何确定最合适的阈值是处理好图像分割的关键,这自然成为一直以来分割算法研究的焦点。
遗传算法是对生物进化论中自然选择和遗传学机理中生物进化过程的模拟来计算最优解的方法。遗传算法具有众多的优点,如鲁棒性、并行性、自适应性和快速收敛,可以应用在图像处理技术领域中图像分割技术来确定分割阈值。
本文主要介绍基于遗传算法的最小误差阈值法、最大类间方差法（Otsu 法）以及最佳直方图熵法(KSW熵法)等三种方法分割图像。
关键词：图像分割，遗传算法，阈值分割
目录
第一章 绪论 .................................................. - 1 - 第二章 遗传算法概述 ........................................ . - 1 -
2.1遗传算法的研究历史....................................... - 1 - 2.2生物背景................................................. - 2 - 2.3遗传算法的基本思想....................................... - 2 - 2.4遗传算法的几个概念....................................... - 2 -
2.4.1适应度函数 ......................................... - 2 - 2.4.2遗传算法最常用的算子 ............................... - 3 - 2.5遗传算法运算的基本流程....................................... 4 第三章 图像分割的现状 ........................................ - 4 -
3.1图像分割简介............................................. - 4 - 3.2图像分割方法............................................. - 5 -
3.2.1基于边缘检测的分割 ..................................... 6 3.2.2基于区域的分割 ..................................... - 5 - 3.2.3边缘与区域相结合的分割 ............................. - 5 - 3.3阈值选取................................................. - 6 - 第四章 基于新的遗传算法的图像分割 ............................ - 6 -
4.1混沌遗传算法............................................. - 6 - 4.2量子遗传算法............................................. - 6 - 4.3免疫遗传算法............................................. - 6 - 结论 ........................................................... - 7 - 参考文献: ...................................................... - 7 -
太原工业学院人工智能论文 第- 1 - 页
基于遗传算法的图像阈值分割
第一章 绪论
图像分割是图像处理与计算机视觉的基本问题之一，是图像处理到图像分析的关键步骤。图像分割方法（包括阈值法、边缘检测法、区域跟踪法)的研究始于上世纪50年代。随着越来越多人的研究，近年来涌现了许多新理论、新方法，但是没有一种方法能满足所有图像分割领域。
在众多的图像分割技术中，阈值化技术是基于区域的图像分割技术，是图像分割中最重要而有效的技术之一。阈值法是一种传统的图像分割方法，因其实现简单、计算量小、性能较稳定而成为图像分割中最基本和应用最广泛的分割技术。在实际应用中，分割是对图像进一步分析、识别的前提，分割的准确性将直接影响后续任务的有效性。其中阈值的选取是图像阈值分割方法中的关键技术。
遗传算法(genetic algorithm，GA)是基于进化论自然选择机制的、并行的、统计的、随机化搜索方法。使用遗传算法求解科学研究工作和工程技术中各种组合搜索和优化计算问题这一基本思想早在20世纪60年代初期就由美国Michigan大学的Holland教授提出，其数学框架也于20世纪60年代中期形成。由于GA的整体搜索策略和优化计算不依赖于梯度信息，所以它的应用范围非常广泛，尤其适合于处理传统方法难以解决的高度复杂的非线性问题。
在分割复杂的图像时，人们往往采用多参量进行信息融合，在多参量参与的最优值的求取过程中，优化计算是最重要的，把自然进化的特征应用到计算机算法中，将能解决很多困难。遗传算法的出现为解决这类问题提供了新而有效的方法，它不仅可以得到全局最优解，而且大量缩短了计算时间。在图像分割过程中，最关键的就是找到最优的阈值，遗传算法的整体搜索策略和优化搜索方法能够快速准确地得到基于成个灰度图像的阈值最优解。
第二章 遗传算法概述
1.遗传算法的研究历史
遗传算法是演化计算的一个分枝，也是人工智能发展的一个重要领域。
它是受达尔文进化理论的思想而激发的一种用进化思想来解决问题的方法。遗传
太原工业学院人工智能论文 第- 2 - 页
算法研究的兴起是在80年代末和90年代初期，但它的历史起源可追溯至60年代初期。早期的研究大多以对自然系统的计算机模拟为主。如Fraser的模拟研究，他提出了和现在的遗传算法十分相似的概念和思想；同时代，演化计算思想首先是由I.Rechenberg于20世纪60年代在他的著作《演化策略》“Evolution strategies”()一书中提出来的，然后一些研究者发展了他们的思想。Holland和DeJong的创造性研究成果改变了早期遗传算法研究的无目标性和理论指导的缺乏。其中，Holland于1975年出版的著名著作《自然系统和人工系统的适配》系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论。这一理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。
2.生物背景
遗传算法正是模拟达尔文的这种遗传选择和自然淘汰的生物进化过程的计算模型，是一种具有“生存+检测”的迭代过程的搜索算法。它以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索.其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容；作为一种新的全局优化搜家算法，遗传算法以其简单通用、稳定性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。
3.遗传算法的基本思想
生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。
4．遗传算法的几个概念
4.1 适应度函数
在遗传算法中使用适应度来度量群体中各个个体在优化计算中有可能达到或接近或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率 就较大；而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应 度的函数称为适应度函数。
太原工业学院人工智能论文 第- 3 - 页
评价个体适应度的过程为：
（1）对个体编码串进行解码处理后，可得到个体的表现型； （2）由个体的表现型可计算出对应个体的目标函数值；
（3）根据最优化问题的类型，由目标函数按一定的转换规则求出个体的适应度。
4.2 遗传算法最常用的算子
(1)选择算子:选择算子从群体中按某一概率成对选择个体，某个体xi 被选择的概率Pi与其适应度值成正比。
选择算子有很多，最常用的是比例选择算子。它是把当前的个体按与适应度成正比的概率复制到新的群体中去。比例选择实际上也是一种赌盘选择，其基本步骤为:
①先计算出群体中所有个体的适应度的总和；
②其次计算出每个个体的相对适应度的大小，它即为各个个体被遗传到 下一代群体中的概率；
③最后再使用模拟赌盘操作(即O和1之间的随机数)来确定各个个体被选中的次数。
（2）交叉算子：交叉算子将被选中的2个个体的基因链按概率进行交叉，生成2个新的个体,交叉位置是随机的。
（3）变异算子:变异算子将新个体的基因链的各位按概率进行变异，对二值基因链来说即是取反。
在遗传算法中使用变异算子主要由以下两个目的: ①改善遗传算法的局部搜索能力；
②维持群体的多样性，防止出现早熟现象。
5.遗传算法运算的基本流程
(1)针对图像分割编写代码:遗传算法一般不直接处理空间的参数而是集进行编码,即用0和1构成的字符串形成矩阵。
(2)随机初始化像素群体X(0):=( x1,x2 ,…,xn):遗传算法从这些群体出发，
太原工业学院人工智能论文 第- 4 - 页
模拟生物进化过程进行选择,最后得出需要的个体集合,满足优化搜索的要求。
(3)对当前像素群体X(t)中每个个体xi计算其适应度F(xi)，适应度表示了该像素的灰度值:遗传算法不涉及问题的具体领域,只需依据适应度函数控制像素变化。根据适应度函数对每个像素计算其适应度，为选择提供依据。设计适应度函数的方法是把问题的目标函数转换成合适的适应度函数和辅助函数。
(4)应用选择算子产生Xr(t)。
(5)对Xr(t)应用其他的算子,产生新一代像素群体X(t+1)，应用其他的算子可以扩展图片像素的覆盖面，体现整体计算的策略。
(6)选择:这是是遗传算法的关键，它参照了适者生存的理论。
(7)变异:模拟了生物的基因突变现象。对像素进行重新评价、选择如此循环往复，使图像中目标物体平均适应度不断提高直到上限则迭代过程收敛，算法结束。
GA的计算过程流程图如下：
编码和种群生成
第三章 图像分割的现状
1.图像分割简介
图像分割是一种重要的图像技术，它不仅得到人们广泛的重视和研究，也在
变异 交叉 选择 种群适应度估计 太原工业学院人工智能论文 第- 5 - 页
实际中得到大量的应用。图像分割在不同领域有时也用其他名称，如目标轮廓 (Object Delineation)技术，阈值化(Thresholding)技术，图像区分或求差(Image discrimination)技术，目标检测(Target Detection)技术，目标识别 (Target recognition)技术，目标跟踪(Target tracking)技术等。这些技术本身或核心实际上也就是图像分割技术。图像技术在广义上是指与各种图像有关技术的总称。图像技术种类很多，跨度很大，但可以将它们归在一个整体框架—图像工程之下。图像工程是一个对整个图像领域进行研究的新学科。它的内容十分丰富，根据抽象程度和研究方法等的不同可分为三个各有特点的层次:图像处理、图像分析和图像理解(如下图所示)
2.图像分割方法
图像分割方法有很多，常见的分割包括基于边缘检测的分割、基于区域的分割、边缘与区域相结合的分割等。 2.1基于边缘检测的分割
基本思想是先检测图像中的边缘点，再按一定策略连接成轮廓，从而构成分割区域。其难点在于边缘检测时抗噪性和检测精度的矛盾。若提高检测精度则噪声产生的伪边缘会导致不合理的轮廓；若提高抗噪性，则会产生轮廓漏检和位置偏差。为此，人们提出各种多尺度边缘检测方法，根据实际问题设计多尺度边缘信息的结合方案，以较好地兼顾抗噪性和检测精度，但仍不能从根本上克服此矛盾。
2.2 基于区域的分割
基本思想是根据图像数据的特征将图像空间划分为不同区域。常用的特征包括:直接来自原始图像的灰度或彩色特征，由原始灰度或彩色值变换得到的特征。方法有阈值法、区域生长法、聚类法、松弛法等。阈值法是通过设定不同的特征值，将象素点分为若干类。其难点在于阈值的设定方法。对传统阈值法的改进包括局部阈值法、模糊阈值法、随机阈值法以及引入新的理论来优选阈值；聚类法是在特征空间对象素进行聚类。它包括硬聚类、概率聚类和模糊聚类等。聚类准则是聚类分割的关键；松弛法是一种动态调优的标号方法。它包括概率松弛、模糊松弛等。其关键在于标号相容模型和迭代方法的收敛性。 2.3 边缘与区域相结合的分割
边缘检测能够获得灰度或彩色值的局部变化强度，而区域分割能够检测特征
太原工业学院人工智能论文 第- 6 - 页
的相似性与均匀性。边缘与区域组合分割的主要思想是结合二者的优点，通过边缘点的限制，避免区域的过分割；同时通过区域分割补充漏检的边缘，使轮廓更加完整。
3.阈值选取
目前公认较好的几种方法如下所示:
（1）最佳熵法。最佳熵法对不同目标大小和信噪比的图像均产生很好的分割效果，且受目标大小的影响小，可用于小目标分割，但由于最大嫡法涉及对数运算，运算速度慢，不能用于实时处理。
（2）最大类间方差法。最大类间方差法对噪声和目标大小十分敏感，它仅对类间方差为单峰的图像产生较好的分割效果。当目标与背景的大小比例悬殊时，类间方差函数可能呈现双峰或多峰，此时用最大类间方差法选取的全局最大值并不一定是正确阈值，此方法失效。Reddi等提出了一种快速算法，提高了运算速度，但并没有解决准则函数极大值不唯一的缺陷。
（3）最小误差法。最小误差法受目标大小和噪声影响小，对小目标图像仍具。有较好的分割效果。但运算量较大，不利于实时处理。
第四章 基于新的遗传算法的图像分割
1.混沌遗传算法
是近年来提出的一种优化算法。其基本思想是利用混沌运动所具有的随机性、遍历性和初值敏感性。将混沌状态引入到优化变量中，把混沌运动的遍历范围扩大到优化变量的取值范围，并在一定程度上利用遗传算法的基本框架。与遗传算法相比，混沌遗传算法显著地提高了计算效率。 2.量子遗传算法
它是量子计算思想与遗传算法结合的产物。与遗传算法类似，它也是一个产生 —检验的过程，但其实现跟标准遗传算法不一样。量子遗传算法表现出比标准遗传算法更好的种群多样性、更强的全局搜索能力和更快的收敛速度。 3.免疫遗传算法
太原工业学院人工智能论文 第- 7 - 页
借鉴生命科学中的免疫概念，在遗传算法中引入免疫算子，通过基于个体浓度的自适应调节操作，使基因不断优化，从而找到最优个体。既保证了解群分布的多样性，又提高了算法的局部搜索能力。
结论
图像分割是图像处理和计算机视觉中基本技术，是大多数图像处理和视觉系统过程的重要预处理阶段。在图像分割过程中，最关键的就是找到最优阈值。遗传算法的整体搜索策略和优化搜索方法能够快速准确地得到基于整个灰度图像的阈值最优解。遗传算法作为一种优化算法，用于图像分割时，可以大大缩短寻找阈值的时间，从而有利于计算机视觉的后续处理。
本文主要介绍了图像阈值分割的几种方法。最小误差阈值法、最大类间方差法（Otsu）以及最佳直方图熵法(KSW熵法)等。当搜索空间越大时(如多阈值分割)，遗传算法越有效,在实际应用中应根据实际需要选取不同的图像分割方法。遗传算法是处理图像分割的优秀算法，图像分割效果相比于传统的图像分割算法更加优秀，但是也难免有一些缺点。
随着时代的进步，图像分割在日常生活中扮演越来越重要的角色。各种新方法的不断涌现，也使遗传算法不断完善。遗传算法用于图像分割前景广阔，并且在图像分割领域必将大放光彩。
参考文献:
[1]刘直芳、朱敏.数字图像处理与分析.清华大学出版社.2006. [2]夏良正.数字图像处理.东南大学出版社.1999. [3]章毓晋、图像分割.北京科学出版.2001.
[4]周明、孙树栋.遗传算法原理及应用.国防工业出版社.1999. [5]陈国良、王东生.遗传算法及其应用.人民邮电出版.1996. [6]李敏强、李全书著.遗传算法的基础理论与应用.科学出版社2003.
因篇幅问题不能全部显示，请点此查看更多更全内容