搜索
《人工智能》期末考查报告题目：基于遗传算法的图像阈值分割学院：物理与电子工程学院专业班级：自动化14级7班姓名：李青松学号：14520450729成绩：任课教师：刘伟摘要遗传算法是基于自然界生物进化基本法则而发展起来的一类新算法。本文在简要介绍遗传算法的起源与发展、算法原理的基础上,对算法在优化、拟合与校正、结构分析与图谱解析、变量选择、与其他算法的联用等方面的应用进行了综述。该算法由于无需体系的先验知识,是一种全局最优化方法,能有效地处理复杂的非线性问题,因此有着广阔的应用前景。关键词:遗传算法;优化第一章前言遗传算法(geneticalgorithm，GA)是基于进化论自然选择机制的、并行的、统计的、随机化搜索方法。使用遗传算法求解科学研究工作和工程技术中各种组合搜索和优化计算问题这一基本思想早在20世纪60年代初期就由美国Michigan大学的Holland教授提出，其数学框架也于20世纪60年代中期形成。由于GA的整体搜索策略和优化计算不依赖于梯度信息，所以它的应用范围非常广泛，尤其适合于处理传统方法难以解决的高度复杂的非线性问题。第二章遗传算法简介2.1历史与发展二十世纪六十年代，I.Rechenberg在他的《演化战略》中第一次引入了进化算法的思想（起初称之为Evolutionsstragegie）。他的这一思想逐渐被其他一些研究者发展。遗传算法（GeneticAlgorithms）是JohnHolland发明的，后来他和他的学生及他的同事又不断发展了它。终于，在1975年JohnHolland出版了专著《自然系统和人工系统中的自适应》（AdaptionInNaturalandArtificialSystems）。1992年，JohnKoza曾经使用遗传算法编出新的程序去做一些具体的工作。他称他的这种方法为“进化规划”（GeneticProgramming，简称GP）。其中使用了LISP规划方法，这是因为这种语言中的程序被表示为“分析树”（ParseTree），而这种遗传算法就是以这些分析树为对象的。2.2遗传算法的基本原理遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。图2-1中表示了遗传算法的执行过程。2.3遗传算法特点（1）遗传算法的操作对象是一组可行解，而非单个可行解；搜索轨道有多条，而非单条，因此具有良好的并行性。（2）遗传算法只需利用目标函数取值信息，而无须梯度等高价信息，因而实用用于大规模高度非线形的不连续多峰值函数的优化以及无解析表达式的目标函数的优化，具有很强的通用性。（3）遗传算法的择优机制是一种“软“策略，加上其良好的并行性使其具有良好的全局优化性能和稳健性鲁棒性。（4）遗传算法的可行解集是经过编码的，目标函数可解释为编码化个体的适应值因而具有良好的可操作性与简单性。2.4遗传算法的应用遗传算法已经在很多复杂问题（比如说NP-难题）、机器学习和简单的进化规划中得到了使用。遗传算法在一些艺术领域也取得了很大成就，比如说进化图片和进化音乐。遗传算法的优势在于他的并行性。遗传算法在搜索空间中非常独立地移动（按照基因型而不是表现型），所以它几乎不可能像其它算法那样“粘”在局部极值点。遗传算法更容易实现。一旦你有了一个遗传算法的程序，如果你想解决一个新的问题，你只需要针对新的问题重新进行基因编码就行。如果编码方法也相同，那你只需要改变一下适应度函数就可以了。当然，选择编码方法和适应度函数是一件非常难的问题。遗传算法的缺点是它的计算时间太长。它们可能比其他任何算法需要的时间都长。当然，对于今天的高速计算机来说，这已经不是个大问题了。这里有一个关于遗传算法应用的小列表:（1）非线性动态系统——预测，数据分析；（2）神经网络的结构和权重设计；（3）自动控制导弹的轨道设计；（4）进化LISP规划（遗传规划）；（5）战略计划；（6）蛋白质分子的形状的寻找；（7）旅行商问题和时间序列排序问题；第三章基于遗传算法的图像阈值分割3.1图像阈值一幅图像通常包括目标物体、背景高斯噪声、运动模糊等,由于目标物体和背景的灰度有较大差异,和噪声产生的麻点的灰度值相差更多,要从多值的灰度图像中提取目标物体,常用的方法就是设定某一阈值,将图像像素分成2大部分:大于阈值的像素和小于阈值的像素即灰度图像的二值化。二值化处理主要功能就是把目标物体和背景灰度差异较大的图像分成2个部分。二值化是数字图像处理中一项最简单的变换方法,通过采用固定阈值、双固定阈值等不同算法,把一幅灰度图变成二值图像,将所需的目标物体从复杂的图像背景中脱离出来。具体的操作过程是先由通过算法找到一个合适阈值,要求是阈值处于目标物体阈值和背景阈值之间。若图像中的像素灰度值小于该阈值,则将该像素的灰度值设置为0或255，若图像中的像素灰度值大于该阈值,则将该像素的灰度值设置为255或0。也就是说通过一个以阈值灰度值为跳变点的阶跃函数来实现图像处理。固定阈值法：固定阈值法就是为灰度图像设定一个阈值,把灰度值小于给定阈值的像素置为0(或者255)，大于阈值的像素置为255(或者0)，从而实现灰度图像到二值图像的变换。双固定阈值法：双固定阈值法预先设置2个阈值,当对图像进行处理时,如果某个像素的灰度值在两者之间时置0(或者255)；其余情况则置255(或者置0)。应当根据具体情况选择双固定阈值法改变图像灰度值的方向。3.2阈值分割的原理对灰度图像的阈值分割就是先确定一个处于图像灰度取值范围之中的灰度阈值，然后将图像中各个象素的灰度值都与这个阈值相比较，并根据比较结果将对应的象素分割为两类:象素的灰度值大于阈值的为一类，象素的灰度值小于阈值的为一类。这两类一般分属于图像中的两类区域:目标和背景。这样就可以将目标从背景中分离出来。由此可见，阈值化分割算法主要有两个步骤:（1）确定需要的分割阈值；（2）将阈值与象素比较以划分象素。以上步骤中，确定阈值是分割的关键。确定阈值后就可以将阈值与象素值比较以对图像进行分割。分割的结果直接给出图像区域。假设一幅原始图像为f(x,y)，则分割后的图像g(x,y)可定义为:1(,)(,)0(,)fxyTgxyfxyT其中，T为阈值。这样得到的g(x,y)是一幅二值图像，它相当于把原始图像用空间占有数组来进行表达。3.3最小误差阈值法3.3.1最小误差法图像阈值分割最小误差法由Kittler和Illingworth于1986年提出,该分割方法受目标大小和噪声影响小,能较好地克服算法的不足,是一种理论严密,效果较佳的图像阈值分割方法。定义如下:假设h(i)为图像的各级灰度值,0≤i≤255,准则函数:00110011()12[()ln()()ln()]2[()ln()()ln()]ftPttPttPtPtPtPt式中：00()()tipthi，121()()Litpthi；202000[()]()()tiithipt，1222122[()]()()Litithipt；*000()()()tihiitpt，1*121()()()Lithiitpt；则最佳阈值为:t=ArgminF(t),其中：(0,1,2,...,1)tL，)(0tp、1()pt分别为灰度值在0～t和t～(L-1)之间的像素数；20、22分别为灰度值在0～t和t～(L-1)之间的方差；0()t、1()t分别为灰度值在0～t和t～(L-1)之间的平均灰度值。3.3.2利用遗传算法来改进最小误差法由于最小误差法选取阈值的过程实质上是一种寻求最优解的过程，故可利用GA所具有的快速寻优的特点对其进行优化，以达到提高效率的目的。其具体做法如下:（1）编码和适应度函数的确定对于具有256级灰度的图像，其侯选阈值在0～255之间，故可用一个8位二进制码进行编码，即把O～255之间的值编码成00000000～11111111之间的一个码。至于适应度函数，可用最小误差法的准则函数，即:00110011()12[()ln()()ln()]2[()ln()()ln()]ftPttPttPtPtPtPt为了正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能为负数。为此，采用一种变换方法:maxmaxmax()()()0()CftftCFtftC式中Cmax为我们预先指定的一个较大的数。（2）控制参数的确定GA的控制参数主要包括群体规模、变异率和交换率等。这些参数的选择尚处于研究阶段，目前参数的选择主要靠实验确定，群体规模影响到遗传算法的最终性能和效率。若规模太小会过早收敛到局部最优解，然而群体规模太大，每一代需要的计算量也越多，这有可能导致无法接受的慢收敛率。交叉率控制交叉算子应用的频率，交叉率越高，群体中个体的更新就越快，如果交叉率过高，相对选择能够产生的改进而言，高性能的个体被破坏的要更快。如果交叉率过低，搜索会因为太小的探查率而导致停滞不前。变异是增加群体多样性的搜索算子，一个很小的变异率足以防止整个群体中任一给定位保持永远收敛到单一的值。（3）选择方法的确定采用比例选择的方法，其具体执行过程如下:①先计算出群体中所有个体的适应度总和。②其次计算出每个个体的相对适应度的大小，它即为每个个体被遗传到下一代群体中的概率。③最后再使用模拟赌盘操作(即O到1之间的随机数)来确定各个个体被选中的次数。（4）停止准则的确定根据最大迭代次数G和当前群体的平均适应度与上一代群体的平均适应度值的差是否小于某一个较小的常数来确定是否终止运算。即当迭代次数大于G或平均适应度的差小于某一个较小的常数时，终止运算。3.4.最大类间方差法（Otsu法）3.4.1最大类间方差法（Otsu法）阈值分割Otsu提出的通过求类间方差最大来选择阈值的方法是一种较为常见的方法。它的基本原理为用最佳阈值将图像的灰度直方图分割成两部分，使两部分的类间方差取最大值、即分离性最大。Otsu最多用于双阈值分割，这是因为当阈值很多时，基于一维直方图的类间方差公式不再适用。将Otsu法用于双阈值分割时，最佳阈值*t应使三类间方差最大，即2222001122()()()BTTT3.4.2Otsu阈值分割的遗传算法设计（1）染色体的编码通过编码将决策变量表示成串结构数据,采用最常用的二进制编码方案。由于图像灰度值在0～255之间，故可用00000000～11111111之间的一个八位二进制代码表示一个分割阈值。对于一维Otsu分割,染色体串长为10,其中前八位为阈值的二进制编码，后两位为阈值真值和适应度。（2）初始群体采用逐个产生初始群体的方法，若产生一个不满足约束条件，则被淘汰，重新产生。直到产生popsize个满足约束条件的初始群体为止。一维Otsu法分割设置初始群体的个数为20。（3）解码对二进制染色体数组采用公式1maxminmin11(2)2lliliUUkUb，min0U，max255U，某一个体K的二进制编码为1221lllbbbbb。（4）适应度函数遗传算法的执行过程中，每一代有许多不同的染色体同时存在，确定这些染色体中哪些遗传到下一代，是根据群体中各个个体的适应度大小决定的。适应度的大小是通过计算适应度函数的值，这个值称为适应度。适应度函数通常是根据目标函数确定的，一维Otsu法的类间方差函数就是所求目标函数，由于所求问题为最大值且为非负因此适应度函数可以直接等于目标函数。（5）遗传算子和参数设定主要的遗