人工智能控制14520450729-李青松

1、人工智能期末考查报告题 目：基于遗传算法的图像阈值分割学 院：物理与电子工程学院专业班级：自动化14级7班姓 名：李青松学 号 绩：任课教师：刘 伟摘 要遗传算法是基于自然界生物进化基本法则而发展起来的一类新算法。本文在简要介绍遗传算法的起源与发展、算法原理的基础上,对算法在优化、拟合与校正、结构分析与图谱解析、变量选择、与其他算法的联用等方面的应用进行了综述。该算法由于无需体系的先验知识,是一种全局最优化方法,能有效地处 理复杂的非线性问题,因此有着广阔的应用前景。   关键词: 遗传算法;优化 

2、第一章 前言 遗传算法(genetic algorithm，GA)是基于进化论自然选择机制的、并行的、统计的、随机化搜索方法。使用遗传算法求解科学研究工作和工程技术中各种组合搜索和优化计算问题这一基本思想早在20世纪60年代初期就由美国Michigan大学的Holland教授提出，其数学框架也于20世纪60年代中期形成。由于GA的整体搜索策略和优化计算不依赖于梯度信息，所以它的应用范围非常广泛，尤其适合于处理传统方法难以解决的高度复杂的非线性问题。  第二章  遗传算法简介  2.1 历史与发展 二十世纪

3、六十年代，I.Rechenberg在他的演化战略中第一次引入了进化算法的思想（起初称之为Evolutionsstragegie）。他的这一思想逐渐被其他一些研究者发展。遗传算法（Genetic Algorithms） 是John Holland 发明的，后来他和他的学生及他的同事又不断发展了它。终于，在1975年John Holland 出版了专著自然系统和人工系统中的自适应（Adaption In Natural and Artificial Systems）。 1992年

4、，John Koza 曾经使用遗传算法编出新的程序去做一些具体的工作。他称他的这种方法为“进化规划”（Genetic Programming，简称GP）。其中使用了LISP规划方法，这是因为这种语言中的程序被表示为“分析树”（Parse Tree），而这种遗传算法就是以这些分析树为对象的。 2.2  遗传算法的基本原理遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环

5、境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。 这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。 图2-1中表示了遗传算法的执行过程。2.3   遗传算法特点（1）遗传算法的操作对象是一组可行解，而非单个可行解；搜索轨道有多条，而非单条，因此具有良好的并行性。 （2）遗传算法只需利用目标函数取值信息，而无须梯度等高价信息，因而实用用于大规模高度非线形的不连续多峰值函数的优化以及

6、无解析表达式的目标函数的优化，具有很强的通用性。 （3）遗传算法的择优机制是一种“软“策略，加上其良好的并行性使其具有良好的全局优化性能和稳健性鲁棒性。 （4）遗传算法的可行解集是经过编码的，目标函数可解释为编码化个体的适应值因而具有良好的可操作性与简单性。 2.4  遗传算法的应用  遗传算法已经在很多复杂问题（比如说NP-难题）、机器学习和简单的进化规划中得到了使用。遗传算法在一些艺术领域也取得了很大成就，比如说进化图片和进化音乐。遗传算法的优势在于他的并行性。遗传算法在搜索空间中非常独立地移动（按照基因型而不是表现型），所以它几

7、乎不可能像其它算法那样“粘”在局部极值点。  遗传算法更容易实现。一旦你有了一个遗传算法的程序，如果你想解决一个新的问题，你只需要针对新的问题重新进行基因编码就行。如果编码方法也相同，那你只需要改变一下适应度函数就可以了。当然，选择编码方法和适应度函数是一件非常难的问题。遗传算法的缺点是它的计算时间太长。它们可能比其他任何算法需要的时间都长。当然，对于今天的高速计算机来说，这已经不是个大问题了。这里有一个关于遗传算法应用的小列表:（1）非线性动态系统预测，数据分析；（2）神经网络的结构和权重设计；（3）自动控制导弹的轨道设计；（4）进化LISP规划（遗传规划）；（5）战略计

8、划；（6）蛋白质分子的形状的寻找；（7）旅行商问题和时间序列排序问题；第三章 基于遗传算法的图像阈值分割3.1图像阈值一幅图像通常包括目标物体、背景高斯噪声、运动模糊等,由于目标物体和背景的灰度有较大差异,和噪声产生的麻点的灰度值相差更多,要从多值的灰度图像中提取目标物体,常用的方法就是设定某一阈值,将图像像素分成2大部分:大于阈值的像素和小于阈值的像素即灰度图像的二值化。二值化处理主要功能就是把目标物体和背景灰度差异较大的图像分成2个部分。二值化是数字图像处理中一项最简单的变换方法,通过采用固定阈值、双固定阈值等不同算法,把一幅灰度图变成二值图像,将所需的目标物体从复杂的图像背景中脱离出来。

9、具体的操作过程是先由通过算法找到一个合适阈值,要求是阈值处于目标物体阈值和背景阈值之间。若图像中的像素灰度值小于该阈值,则将该像素的灰度值设置为0或255，若图像中的像素灰度值大于该阈值,则将该像素的灰度值设置为255或0。也就是说通过一个以阈值灰度值为跳变点的阶跃函数来实现图像处理。固定阈值法：固定阈值法就是为灰度图像设定一个阈值,把灰度值小于给定阈值的像素置为0(或者255)，大于阈值的像素置为255(或者0)，从而实现灰度图像到二值图像的变换。双固定阈值法：双固定阈值法预先设置2个阈值,当对图像进行处理时,如果某个像素的灰度值在两者之间时置0(或者255)；其余情况则置255(或者置0)

10、。应当根据具体情况选择双固定阈值法改变图像灰度值的方向。3.2 阈值分割的原理对灰度图像的阈值分割就是先确定一个处于图像灰度取值范围之中的灰度阈值，然后将图像中各个象素的灰度值都与这个阈值相比较，并根据比较结果将对应的象素分割为两类:象素的灰度值大于阈值的为一类，象素的灰度值小于阈值的为一类。这两类一般分属于图像中的两类区域:目标和背景。这样就可以将目标从背景中分离出来。由此可见，阈值化分割算法主要有两个步骤:（1）确定需要的分割阈值；（2）将阈值与象素比较以划分象素。以上步骤中，确定阈值是分割的关键。确定阈值后就可以将阈值与象素值比较以对图像进行分割。分割的结果直接给出图像区域。假设一幅原始

11、图像为f(x,y)，则分割后的图像g(x,y)可定义为:其中，T为阈值。这样得到的g(x,y)是一幅二值图像，它相当于把原始图像用空间占有数组来进行表达。3.3 最小误差阈值法3.3.1 最小误差法图像阈值分割最小误差法由Kittler和Illingworth于1986年提出,该分割方法受目标大小和噪声影响小,能较好地克服算法的不足,是一种理论严密,效果较佳的图像阈值分割方法。定义如下:假设h(i)为图像的各级灰度值,0i255,准则函数:式中：，；，；，；则最佳阈值为: t=ArgminF(t),其中： ，、分别为灰度值在0t 和t( L- 1) 之间的像素数； 、分别为灰度值在0t和t(

12、L- 1)之间的方差； 、 分别为灰度值在0t 和t( L- 1)之间的平均灰度值。3.3.2 利用遗传算法来改进最小误差法由于最小误差法选取阈值的过程实质上是一种寻求最优解的过程，故可利用GA所具有的快速寻优的特点对其进行优化，以达到提高效率的目的。其具体做法如下:（1）编码和适应度函数的确定对于具有256级灰度的图像，其侯选阈值在0255之间，故可用一个8位二进制码进行编码，即把O255之间的值编码成0000000011111111之间的一个码。至于适应度函数，可用最小误差法的准则函数，即:为了正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能为负数。为此，采用

13、一种变换方法:式中Cmax为我们预先指定的一个较大的数。（2）控制参数的确定GA的控制参数主要包括群体规模、变异率和交换率等。这些参数的选择尚处于研究阶段，目前参数的选择主要靠实验确定，群体规模影响到遗传算法的最终性能和效率。若规模太小会过早收敛到局部最优解，然而群体规模太大，每一代需要的计算量也越多，这有可能导致无法接受的慢收敛率。交叉率控制交叉算子应用的频率，交叉率越高，群体中个体的更新就越快，如果交叉率过高，相对选择能够产生的改进而言，高性能的个体被破坏的要更快。如果交叉率过低，搜索会因为太小的探查率而导致停滞不前。变异是增加群体多样性的搜索算子，一个很小的变异率足以防止整个群体中任一给

14、定位保持永远收敛到单一的值。（3）选择方法的确定采用比例选择的方法，其具体执行过程如下:先计算出群体中所有个体的适应度总和。其次计算出每个个体的相对适应度的大小，它即为每个个体被遗传到下一代群体中的概率。最后再使用模拟赌盘操作(即O到1之间的随机数)来确定各个个体被选中的次数。（4）停止准则的确定根据最大迭代次数G和当前群体的平均适应度与上一代群体的平均适应度值的差是否小于某一个较小的常数来确定是否终止运算。即当迭代次数大于G或平均适应度的差小于某一个较小的常数时，终止运算。3.4.最大类间方差法（Otsu法）3.4.1最大类间方差法（Otsu法）阈值分割Otsu提出的通过求类间方差最大来选择

15、阈值的方法是一种较为常见的方法。 它的基本原理为用最佳阈值将图像的灰度直方图分割成两部分，使两部分的类间方差取最大值、即分离性最大。Otsu最多用于双阈值分割，这是因为当阈值很多时，基于一维直方图的类间方差公式不再适用。将Otsu法用于双阈值分割时，最佳阈值应使三类间方差最大，即3.4.2 Otsu阈值分割的遗传算法设计（1）染色体的编码通过编码将决策变量表示成串结构数据,采用最常用的二进制编码方案。由于图像灰度值在0255之间，故可用0000000011111111之间的一个八位二进制代码表示一个分割阈值。对于一维Otsu分割,染色体串长为10,其中前八位为阈值的二进制编码，后两位为阈值真值

16、和适应度。（2）初始群体采用逐个产生初始群体的方法，若产生一个不满足约束条件，则被淘汰，重新产生。直到产生popsize个满足约束条件的初始群体为止。一维Otsu法分割设置初始群体的个数为20。（3）解码 对二进制染色体数组采用公式，某一个体K的二进制编码为。（4）适应度函数遗传算法的执行过程中，每一代有许多不同的染色体同时存在，确定这些染色体中哪些遗传到下一代，是根据群体中各个个体的适应度大小决定的。适应度的大小是通过计算适应度函数的值，这个值称为适应度。适应度函数通常是根据目标函数确定的，一维Otsu法的类间方差函数就是所求目标函数，由于所求问题为最大值且为非负因此适应度函数可以直接等于目

17、标函数。（5）遗传算子和参数设定主要的遗传算子有选择、交叉、变异3种。选择算子：先采用最优保存策略，然后采用赌轮法（比例选择）。交叉算子：它是遗传算法区别于其它进化算法的重要特征，是产生新个体的主要方法。交叉算子的设计和实现与所研究的问题密切相关，它决定了遗传算法的全局搜索能力。一般要求它既不要太多地破坏个体编码串中优良模式，又要能够有效地产生出一些较好的新个体模式。对一维Otsu阈值分割法的染色体采用单点交叉的方式。分别在变量s，t的编码段内设定一个交叉点。变异算子：只是产生新个体的辅助方法，但它决定了遗传算法的局部搜索能力。在反复的试验时，发现基本位变异对结果的影响微乎其微，而一旦增大变异

18、概率，算法又近似于随机搜索算法。所以采用下面的变异策略，把进化过程分为初期、中期和后期三个阶段，分别采用不同的变异方法。进化初期以小的概率在稍大的范围内变异，维持多样性而又不破坏好的模式；进化中期以稍大的概率在中等的范围内变异，算法开始收敛；进化后期以大的概率在小的范围内变异,增加局部搜索能力。(6)终止准则设定停机准则为在达到最大进化代数50代之前，若当前群体的平均适应度值与上一代群体的平均适应度值与上一代群体的平均适应度的比值范围为1.000,1.005,则跳出循环。(7)结果处理由于在实际图像处理中。GA寻优的解可能是最优解也可能是准最优解（即与最优解相差10%左右）。对于一个有256级

19、灰度的图像，其准最优阈值与最优阈值的差值一般在25.5左右。为了适应不同图像的阈值选取，设定一个波动阈值A=25,在求出的阈值k的基础上,在范围k-A,k+A内进行局部搜索,以求得最佳阈值。下面是原图及用最大类间方差法(Otsu)分割的图像对比： 原图 最大类间方差法（otsu）3.5.KSW熵法3.5.1 KSW熵阈值分割将信息论中shannon熵概念用于图像分割时,测量图像灰度直方图的熵，由此找出最佳阈值，其出发点是使图像中目标与背景分布的信息量最大。根据shannon熵的概念，对于灰度范围0，l，ll的图像直方图，其熵测为：其中为第i个灰度出现的概率。设阈值t将图像划分为目标与背景两类,

20、责令，。由阈值t分为A,B两类后，两类的概率分布分别为，；，与每个分布有关的熵分别为和。 图像的总熵H(t)为和之和，即最佳阅值为使总熵取最大值，即。3.5.2.KSW单阈值分割的遗传算法设计编码：由于图像灰度值在0255之间，故将各个染色体编码为8位二进制码，它代表某个分割阈值。初始代人口的值为随机产生的，其相应的适应度值也各有高低。人口模型：若人口数过多，则每一代适应度值的计算量大，因此人口数设置应该合理。在此，设置人口数为l0，最大繁殖代数为50。解码：对二进制染色体数组解码为0255之间的值，以求其适应度值。适应度函数：采用(1)式为适应度值函数。同时采取对适应度函数的线性定标。选择：根据遗传算法的收敛定理，先进行赌轮法(蒙特卡罗法)，再采用精英策略。交叉：交叉互换的重要特征是它能产生不同于父体的子体。交叉概率越大，交叉操作的可能性也越大；如果交叉率太低，收敛速度可能降低。单阈值分割由于只有一个参数，所以采用一点交叉，在此设置交叉概率为0.6。变异：变异概率为0.1。终止准则：规定当算法执行到最大代数(终止条件)或经过l5代进化，群体中的最高适应度值仍未发生变化(稳定条件)时，算法停止运行，具有最高适应度值的个体即为分割阈值。3.5.3 KSW双阈值分割的遗传算法设计编码：将单阈值分割中的8位二进制码串