基于改进遗传算法的最佳熵阈值图像分割法

王学忠，徐丽萍，吴海燕

安徽三联学院电子电气工程学院，合肥，230601

图像分割是利用计算机对图像进行分析的第一步，也是图像处理的关键技术，是将一幅图像分解成若干具有性质特殊、互不重叠区域的过程，图像分割也是计算机图像处理与机器视觉处理的最基本的研究方向和领域，其核心的部分就是把图像内容和背景内容尽可能分割开。随着计算机技术、数字信号处理技术以及高速DSP芯片的不断发展，出现了最大类间方差法、最佳直方图熵法等多种图像分割技术。其中，阈值分割法的计算方法简明、实用性强，是图像分割最常用的方法，该分割方法的关键是确定最佳阈值。最佳阈值又有多种分割法，李贤阳和金保华等采用最大类间方差法（Otsc）进行图像分割，阈值计算比较稳定，但需要计算每个像素点对应的方差值，因此存在计算数据多、时间长、效率低等缺点［1-2］；最佳熵阈值法（简称KSW法）是由Kapur等提出［3］，该算法也存在计算过程复杂、计算量较大等不足；汪筱红等将遗传算法与最佳熵阈值分割方法相融合（Simple Genetic Algorithms KSW，SGAKSW）［4-5］进行图像分割，缩短了运算时间，具有速度快、效率高等优点，但存在收敛性差、阈值寻找不是最优，最大熵的结果不稳定，导致图像分割过当或不足等现象。

本文提出了改进型遗传阈值算法（Improve Genetic Algorithms KSW，IGA-KSW），通过精英策略和赌轮盘相结合选择法、交叉概率与变异概率随着进化代数而变化的遗传算法来计算出图像熵的阈值，从而达到阈值最佳，获得比较清晰、准确、稳定的图像。

1 KSW最佳熵阈值分割法

美国著名的数学家、信息论创始人香农先生最早于1948年提出了“信息熵”的概念，后来，人们把“信息熵”的概念用到了图像分割当中。根据香农的“信息熵”理论，一个灰度值是｛0，1，2，3，…，l-1｝的直方图图像，其熵的值可以用下面的公式计算出来。即：

式中，Pi是图像中第i个像素的灰度值在整幅图像中出现的概率，t为分割阈值。t将图像划分成两大区域，其中一个区域是有目标像素所构成的图像（称为目标图像），另一区域是有背景像素所构成的图像（称为背景图像）则：

当阈值t将图像划分成两大区域后，分别用Ⅰ和Ⅱ来表示两个区域的图像（即背景和目标图像），则Ⅰ和Ⅱ的概率分别为：

因此，目标图像熵 HⅠ（t）、背景图像 HⅡ（t）分别为：

图像总熵H（t）就是两大区域图像Ⅰ和Ⅱ的熵HⅠ（t）和 HⅡ（t）的和，即

最佳阈值t的值，就是当t取得某一数值使总熵H（t）取得最大值，即：

2 基于遗传算法最佳熵阈值分割法

遗传算法（Genetic Algorithms，GA）就是模拟生物优胜劣汰的进化过程来达到搜索最优解的目的。随着遗传算法在应用领域的不断扩展，出现了基于机器学习的遗传算法以及遗传算法向模糊推理、神经网络、人工生命、图像处理及自动控制等众多领域的渗透，开拓了智能计算领域的新局面。

2.1 SGA-KSW基本遗传算法的最佳熵阈值分割法

该方法就是借助于计算机及工程计算软件Matlab，将 遗 传 算 法 （Simple Genetic Algorithms，SGA）与KSW融合，通过多轮的循环搜索，最终找到图像的最佳阈值。算法过程如图1所示。

图1 SGA-KSW算法框图

算法步骤：

（1）编码和产生初始种群。采用二进制的方法对灰度图像的阈值进行编码。初始种群要求适中，一般取20～100之间，本文采用初始种群为20。

（2）计算适应度函数。即利用该函数求出每个个体对环境的适应能力，通过计算结果把优良的个体保留下来，适应度差的个体被淘汰掉。本文算法中采用的适应度计算公式为公式（8）。

（3）选择。采用轮盘赌法，公式如下：

其中，pi为个体i被选中的概率，fi为个体i的适应度，∑fi为群体的累加适应度。

（4）交叉。将上代父体中相邻两个体的部分基因结构按照预先设定的概率PC进行交换组合产生新的个体的过程，PC一般取值0.4～0.9之间。

（5）变异。变异就是个体中的部分基因在遗传过程中发生了突变，即基因由0变1或由1变0。Pm取值一般为0.001～0.04。

（6）终止。反复执行（2）-（5）步骤，直到循环超过最大循环次数或前后平均最佳阈值差小于某个值时终止循环搜索。

2.2 IGA-KSW改进遗传算法最佳熵阈值分割法

第一，改进基本遗传算法中的步骤（3）选择算子。传统的遗传算法是个体适应度（即个体的熵值占群体熵累加值的概率）越大，个体被选中的概率也就越大，所有的个体都需要不断地计算适应度值，从而增加了算法的运算量、降低了算法的效率，同时易破坏好的基因个体，对优秀的个体继承也不利；因此，本文中采用10%的精英策略和90%轮盘赌法相结合的选择算法，具体的做法是：把上代中10%的优秀个体（即图像熵值比较大的，对应个体被选概率前10%的图像阈值）保留下来，不参与后面的轮赌选择算法，只有余下90%的个体参与轮赌选择算法，这样既保护了好的基因个体不被破坏，也提高了搜索效率。

max_adapt_value1＝max（adapt_value1）；

s1（1）＝round（mean（X1（find（adapt_value1＝＝max_adapt_value1））））；

r＝rand（1，population-1）；

for i＝2：population

temp＝0；

for j＝1：population

temp＝temp+adapt_value1_new（j）；

if temp＞＝r（i-1）

s1（i）＝X1（j）；

break；

end

end

end

第二，改进上述算法中的步骤（4）交叉算子。传统的遗传算法中，交叉概率PC一般都是取某一个固定值，一般取值0.4～0.9之间，这种固定的交叉概率不利于图像阈值的最优解搜索，容易陷入全局最优、导致图像分割不稳定；本文把交叉概率由原先的一个固定值改为两个不同的交叉概率值，基本思路是：在搜索的早期，为了获得更多新的个体，避免图像阈值陷入局部最优而适当提高交叉概率PC的值（譬如PC为0.8）；而在搜索的中后期，为了不破坏优秀的个体，避免收敛太慢，提高搜索效率和图像的稳定性，适当降低交叉概率PC的值（譬如PC为0.6），即：

PC其中K为搜索代数

这样在搜索的初期能产生更多的新个体，避免早熟，在后期又可避免破坏优良个体。

第三，改进上述算法中的步骤（5）变异算子。

由固定的变异概率Pm改为变化的变异概率Pm，即：

通过上述的改进、优化变异算法后，避免早熟又可产生的新个体。

3 实验结果分析

本实验中，为了比较SGA-KSW和IGA-KSW两种遗传算法对同一图像的分割效果，采用了初始种群均为20，循环终止的条件相同，即循环超过200代或前后平均最佳阈值差小于0.001时终止循环搜索。每种算法都分别进行20次分割，结果如表1所示。实验采用的图像是Lena，如图2-7。图2为Lena原始图像；图5为采用穷尽法所获得的最佳阈值（142）图像；图3、图4分别为基本遗传算法所获得最佳阈值图像（其中最大阈值168，最小阈值80）；图6、图7分别为改进遗传算法所获得最佳阈值图像（其中最大阈值144，最小阈值114）。

表1 SGA-KSW算法与IGA-KSW算法的对比（20次分割）

从表1可知，两种遗传算法在搜寻的时间上仅 相差0.001 9秒，基本接近，但改进后的算法获得阈值更加稳定，更接近最优阈值，分割的图像效果更好。

4 结论

本文在基本遗传算法的最佳熵阈值分割法的基础上提出了改进型遗传阈值算法，具体的方法是改进基本遗传算法中的选择、交叉和变异的算子方法。其一，通过采用10%的精英策略和90%轮盘赌法相结合的选择算法，把上代中10%的优秀个体保留下来，不参与后面的轮赌选择算法，只有余下90%的个体参与轮赌选择算法；其二，把交叉概率由原先的一个固定值改为两个不同的交叉概率值；其三，根据搜索的代数动态调整变异的概率。结果表明，该方法在阈值的寻优方面要比SGA—KSW算法更好，所获得的阈值更集中、阈值均方差进一步缩小，平均最佳阈值得到较大改善，更接近实际最优阈值。改进后分割所得的图像比较清晰、准确、稳定，明显优于传统遗传算法所获得的图像。