基于改进遗传算法的图像分割技术:基于遗传算法的图像分割

　　[摘要]提出一种基于遗传算法的进化类图像分割方法。遗传算法是一种全局搜索的算法,但是它在解决多峰复杂问题的时候会出现局部收敛的现象,出现这个现象的主要原因在于在搜索空间中群体多样性的降低导致了搜索的停滞。基于这个原因,提出一种改进的遗传算法,改进的方法通过控制遗传算法的变异概率来平衡群体的多样性程度,改进后的方法能够在解决多峰复杂问题中较多的搜索到全局解的区域。通过将改进的算法应用于图像分割的实例验证了改进算法的有效性以及算法在收敛速度及求解成功率上的优势。
　　[关键词]遗传算法全局优化图像分割
　　中图分类号:TP3文献标识码:A文章编号:1671-7597(2009)1110130-01
　　
　　一、引言
　　
　　分割是指将具有相似特征的元素聚集在一起。图像分割是计算机视觉与图像识别一个重要的步骤。在图像分割方法的研究中,已经存在一些方法来解决其中的问题。
　　遗传算法Genetic Algorithms(GA)[2,3]是由生物进化启发而得到计算求解模型,应用于求解优化问题。遗传算法的主要特点在于个体间的信息交换,较强的搜索能力以及全局优化能力。
　　遗传算法的本质包括在原始群体上的复制操作,交叉操作和变异操作的优良性能和最优个体选择机制。但是遗传算法的一个主要问题在于其在求解多峰复杂问题中易于出现早熟的现象[1],这导致了算法性能的急剧下降和局部最优解的出现。
　　因此有必要提高遗传算法的性能以使得以更小的概率进入到局部解区域。在这篇文章中,提出了一种改进的遗传算法,即将群体多样性的计算贯穿搜索的整个过程,通过群体多样性的变化来调节算法的变异概率,使得算法的搜索具有更强的效率。改进后的算法应用于图像分割的实验表明改进的算法能够取得更好的分割结果。
　　
　　二、问题描述
　　
　　在灰度熵法中,Pun提出将信息论中熵的概念应用到了图像分割。基于这个方法,Kapur和Sahoo提出了KSW熵法[4],KSW熵法[4]利用了二次分布的假设。在这篇文章中,我们基于KSW熵法来研究图像分割。
　　
　　三、GA和改进的GA
　　
　　(一)GA简介
　　GA是一种基于群体智能的、鲁棒性较强的优化技术,GA的鲁棒性在于它能够寻找到多峰问题空间的全局最优解区域。在GA的搜索过程中,当旧的群体通过适应度函数评价后,适者生存的规则就会应用于评价后的群体来选择父代的个体。接着,交叉操作应用到选择出的父代个体从而产生新的子代个体,新的子代个体通过一定概率下的变异操作进行变异。变异后的新个体会加入到新的群体中。
　　
　　(二)遗传算法的改进
　　正如在第一部分所提到的,GA的一个主要问题在于求解复杂多峰优化问题时,会出现局部收敛的现象。出现这个问题的原因在于过高的选择压力或者个体之间过多的信息交换。选择操作会使得群体多样性很快的降低,从而使得个体会停滞在局部最优解的区域而很难跳出该区域。因此,本文通过改进遗传算法的变异概率来提高算法的性能,主要思想是:通过一定的方法实时的判断群体当前的多样性,如果群体当前多样性较高,说明群体目前的解所在的位置较广,则设定本次迭代的变异概率为一个较小的值;如果群体当前的多样性较低,说明群体目前的位置是聚集在一个较小的区域,那么设置本次迭代的变异概率为一个较大的值,从而帮助群体跳出当前聚集的位置,以便为群体在更广的范围寻找合适解。该改进方法的前提在于计算群体当前的聚集程度,即判断群体的聚集程度,本文采用如下的公式来计算:
　　其中,Div是当前群体的多样性,N是群体的规模,即染色体的个数,
　　是第i个个体的适应度值,是当前群体的平均适应度值,fmax是当前群体的最大适应度值。从这个方程可以看出,当群体聚集在一个较小区域时,Div的值将会较小;反之,如果群体分散的区域较广,则Div值将会比较大。基于这样的判断,我们设定算法的变异概率按如下公式调整:
　　Pm1是群体位置较为分散时的变异概率,Pm2是群体位置较集中时的变异概率,这两个值的具体取值可以根据实际问题来设定,div是根据求解的具体问题所设定的判断群体聚集程度的标准值。通过这样的方法可以保持群体的多样性在一定的水平上,并能够在一定程度上防止算法陷入局部收敛。
　　改进的遗传算法的过程描述如下:
　　1.确定控制参数,包括种群规模、变异率、交叉率,进化代数,div等;
　　2.初始化种群,在(0,0)～(255,255)之间随机产生N对个体,形成初始群体Pop1～Popn;
　　3.利用适应度函数计算初始群体中每个个体的适应度值;
　　4.利用轮盘赌进行选择操作,形成新的群体Pop1"～Popn";
　　5.在群体Pop1"～Popn"中,利用设定的交叉概率进行双点交叉操作,得到新的群体;
　　6.根据公式计算当前群体的聚集度Div;
　　7.由第六步计算得到的Div来决定当前的变异概率,如果Div>div,则设定较小的变异概率,并规定变异策略为单点随机变异;反之,则设定较大的变异概率,规定变异策略为两点随机变异;
　　8.判断是否满足循环终止条件,满足则转步骤;
　　9. 否则转步骤3重复这一进化过程,如此循环往复,直至满足循环终止条件。
　　
　　四、实验设置与结果
　　
　　实验的程序采用MATLAB 7编制并在其中运行,实验的机器的CPU是P4 2.0G Hz,内存为512M。标准Lenna图像用来作为分割的图像。GA和IGA都应用于该图像的分割,它们的群体大小都是20,设定最大迭代次数为500,交叉概率都是0.7。对于GA,变异概率设置为0.01,对于IGA,Pm1设置为0.1,Pm2设置为0.01,div设置为1,实验均随机的执行20次。
　　试验的时间如表1所示。平均迭代次数与成功搜索的时间如表2所示。
　　从表1中可以看出,IGA使用的时间少于GA,这表明IGA的寻优速度快于GA。从表2可以看出,IGA的收敛速度也快于GA。在所有的20次运行中,IGA的分割成功率要高于GA。从这些结果可以看出,IGA在图像分割中的执行效率以及分割效果要好于GA。
　　
　　五、结论
　　
　　在这篇文章中,提出了一种改进的GA,改进后的GA能够有较强的能力跳出局部收敛区域,具有更强的全局搜索性能。改进GA主要通过实时的判断群体的多样性,并用判断结果来控制算法的变异概率,这使得群体的多样性可以得到控制并有更多的机会寻找到全局解的区域。通过图像分割的实例证明,IGA比GA具有更好的性能。
　　
　　参考文献:
　　[1]Rasmus K.Ursem,Diversity-Guided Evolutionary Algorithms,Proce
　　edings of Parallel Problem Solving from Nature VII (PPSN-2002),pp.462-471,2002.
　　[2]J.H. Holland.Adaptation in Natural and Artificial systems.The MIT Press,Cambridge,Massuchusetts,1992.
　　[3]D.H.Goldberg.Genetic Algorithms-In Search,Optimization and Machine Learning.Addison-wesley Publishing Company,1989.
　　[4]T.Pun. A new method for grey-level picture thresholding using the entropy of the histogram. Signal Processing,1980,2(3):223～237.
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文