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

高 欣， 卓东风， 刘国洋

（太原科技大学 电子信息工程学院，山西 太原 030024）

0 引言

在对图像的研究中，图像分割[1]是由图像处理到图像分析的重要步骤。图像分割是根据图像的灰度、颜色、几何特性等，把图像分成各具特色的区域，将图像中感兴趣的部分分割出来，图像分割的好坏直接影响到图像分析的结果，因此具有很重要的意义。图像分割的常用方法有阈值分割法，边缘检测法和区域分割法等，其中阈值分割法是最基本，应用最广泛的分割方法。许多学者已经提出了很多阈值分割的方法，其中OTSU提出的最大类间方差准则[2-3]来选取阈值的方法被认为是阈值分割的经典方法。由于多数图像不是简单的单峰，对于那些灰度直方图的灰度级分布谷底不明显的复杂图像，单一的使用 OTSU准则并不能从图像中稳定可靠的将目标分割出来，很难达到满意的效果。很多人用遗传算法和 OTSU法结合来解决上述问题，但是传统的遗传算法容易出现早熟收敛现象。为此本文对基本遗传算法进行改进，提出一种改进的遗传算法与 OTSU法则结合的优化算法。本文根据指数变换法的特点提出了一种基于指数变换的非线性的动态适应度函数[4]，使得对种群中个体的评价更为合理，从而保证算法的收敛性，避免早熟，提高全局搜索能力。

1 相关算法

1.1 OTSU分割方法

1979 年，N.OTSU提出最大类间方差法（称为OTSU法），是一种性能良好的自动阈值选择方法，直接计算出阈值，不需要对直方图做预处理，计算简单，稳定有效，优于其他阈值化算法，受到广泛关注。它的基本思想是以某一灰度值为阈值将图像中的像素分成两类，计算它们的方差。差值越大，目标和背景之间的差异越大，差值最大时所得的灰度值为最佳阈值[5]。

设要待分图像的像素为N，灰度级为L个（0,1,2,…,L-1），灰度值i的像素值为ni，那么各灰度值的概率设阈值k将图像分成两类c0和c1（目标和背景），则c0类和c1类的灰度值分别是（0,1,…,k）和（k+1,k+2,…,L-1）。c0类和c1类产生的概率分别为：

c0类和c1类平均灰度值分别为：

整体灰度平均值为：

其中阈值为k时灰度的平均值为：

两类方差公式为：

变化0到L-1之间的k值，使得d(k)最大，此时k的取值为则k*为最佳分割阈值。因此，要计算出maxd(k)，必须对0到L-1之间所有的灰度值进行方差计算，计算量非常大，所以寻找一种有效快速的计算方法非常重要。

1.2 遗传算法

遗传算法[6-8]（GA，Genetic Algorithm）是模拟生物进化自然选择和遗传机制的一种寻优算法。模拟了生物进化机制，自然选择和遗传进化中发生的繁殖、交配和突变现象。遗传算法在求解之前，首先要进行编码，将问题空间的可行解表示成遗传空间的串结构数据，生成一个可能潜在解集的初始种群，按照优胜劣汰，适者生存的原则，逐步演化产生出一群新的更适应环境的个体，使群体进化到搜索空间中越来越好的区域。在每一代，根据问题域中个体的适应度选择个体，进行交叉组合和变异，一代又一代不断繁殖、进化，最后收敛到一群最适应环境的个体并解码，作为问题的最优解或近似最优解。

1.3 改进遗传算法

遗传算法在搜索选择中以适应度函数为依据，利用种群中每个个体的适应度值来进行搜索，即用个体的适应度值对解的质量进行评价，适应度越高，解的质量越好，该个体被选择的几率越大，因此选择合适的评价函数至关重要。一般基于遗传算法的OTSU分割方法用公式7直接作为适应度函数。但在实际中，遗传进化初期，往往会产生一些超常个体，他们的适应度值远高于其他个体适应度值，这些超常个体因为竞争力太强而控制了选择过程，导致早熟收敛现象，影响算法的全局优化；在进化过程中，会出现群体的平均适应度已接近最佳个体适应度，减弱个体间的竞争力，使优化过程无法趋于最优解。对于这2种情况，前者需要降低个体的适应度值，后者需要放大适应度值，以保证群体的多样性。所以本文提出基于指数变换的非线性的动态适应度函数，将公式7进行改进之后作为遗传算法的评价函数。改进后的新适应度函数为：

式（8）中，d*(k)是得到的新的适应度函数，a是一个随进化代数增加而逐渐增加的动态变化的正数，t是当前的进化代数，T是最大遗传代数，davg是当前种群的平均值。

基于改进遗传算法的OTSU分割算法

算法步骤如下：

①编码：由于图像灰度值在0～255，对应一个8位二进制数，将染色体编成8位二进制码。

②生成初始种群：产生规模为100的初始种群，设置最大进化代数为50，交叉概率Pc=0.6，变异概率Pm=0.02。

③适应度评估检测：以式（8）为适应度函数。

④选择：从当前种群中选择优良的（适应度高的）个体，复制到下一代新种群中，舍弃适应度低的个体。

⑤交叉：对染色体中的某些相同的基因位按交叉概率Pc进行交换，产生新的种群。

⑥变异：变异就是对种群某个个体中的某些位进行异位，其异位的多少由变异概率Pm来决定从而形成新一代群体。

⑦终止条件：当算法执行到最大迭代次数或群体中的最高适应度值变化不大时，算法停止运行，对具有最高适应度值的个体进行解码，即可求得最佳分割阈值k。

2 实验结果

为了验证上述方法的有效性和准确性，分别用基于遗传算法的OTSU图像分割算法和基于改进遗传算法的OTSU图像分割算法在matlab环境下对灰度级为256图像进行分割实验。实验结果表明（如图1所示），采用遗传算法的OTSU图像分割算法分割的图像清晰，改进的算法较之经典遗传算法在时间方面虽略有增加，但表现出了更好的全局搜索能力，突出感兴趣的区域，获得的分割效果更佳。

图1 OTSU图像

3 结语

本文针对标准遗传算法易于早熟陷入局部最优的不足，提出了一种改进的基于遗传算法的OTSU分割方法，用动态的适应度函数评价选择个体，保证了算法初期种群的多样性，提高了后期较优个体的适应度，有效地克服了早收敛。实验结果表明，改进的算法较之传统的遗传算法，获得的分割效果更好。

[1]章毓晋.图像处理和分析[M].清华大学出版社，1999(03):179-180.

[2]刘建庄，栗文青.灰度图像的二维Otsu自动阈值分割法.[J]自动化学报，1993，19(01):101-105.

[3]肖超云，朱伟兴.基于Otsu准则及图像熵的阈值分割算法[J].计算机工程，2007，33(07)：188-189，209

[4]张思才，张方晓. 一种遗传算法适应度函数的改进方法[J].计算机应用与软件，2006，23(02):108-110.

[5]谭志存.遗传聚类算法及其在图像分割中的应用[D].重庆：西南大学，2009.

[6]李乐,陈鸿昶.一种改进的遗传算法在聚类分析中的应用[J].通信技术，2009,42(03):263-265.

[7]薛岚燕，程丽. 基于最大方差法和改进遗传算法的图像分割[J].计算机应用与软件，2008,2(25)：221-222，247.

[8]杨淑莹.模式识别与智能计算——matlab技术实现[M].北京：电子工业出版社，2008.