基于分段自适应遗传算法的图像阈值分割

杜雯超 ，陈其松 ，周 莹

（1.贵州大学 大数据与信息工程学院，贵州 贵阳 550025；2.贵州财经大学 计算机信息学院，贵州 贵阳 550003）

0 引言

在对图像进行研究和分析时，人们往往只对某些部分区域感兴趣（称作目标或前景），其余的部分则被称作背景。为了识别、分析的需要，有必要将目标和背景分离出来。图像分割[1，2]就是将一幅数字图像细分为若干个小的子区域的过程，是进行图像处理和图像分析并进而进行图像理解的关键步骤，图像分割的好坏，对后面的分析和理解具有很大的影响。因此，好的分割方法非常重要。利用阈值分割对图像进行分割，关键是找到恰当的阈值将前景和背景区分开来，在众多的阈值分割中，如何准确快速地确定最优阈值是基于阈值分割的关键问题。而遗传算法是一类借鉴生物界的进化规律演化而来的随机全局化搜索算法，是一种具有鲁棒性、并行性和自适应性的优化算法。本文将改进的自适应遗传算法应用到图像分割中，提出了一种基于改进遗传算法的最大类间方差比的图像阈值分割算法，新算法不仅能够对图像进行准确的分割，而且能够以较少的计算代价得到最优阈值。

1 遗传算法

遗传算法（Genetic Algorithm）[3]是一种借鉴生物界自然选择和进化机制发展而来的高度并行的搜索算法。遗传算法包括三个基本的操作：选择、交叉和变异。遗传算法的交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键，直接影响算法的收敛性，Pc的大小决定种群的更新和搜索速度的快慢。Pc越大，产生新个体的速度就会越快，然而，Pc过大会使具有适应度高的个体被很快破坏；如果Pc过小，搜索过程就会变得缓慢。变异概率Pm是保持种群多样性，防止早熟的一种手段。Pm过小则不容易产生新的个体，过大则会使遗传算法变为纯粹的随机搜索。基于以上问题，Srinvivas等人提出了一种自适应遗传算法（Adaptive GA，AGA），Pc和 Pm能够随适应度的改变而自适应地做出改变。如图1、图2所示。

图1 自适应的交叉概率（k=k1=k2）

图2 自适应的变异概率（k′=k3=k4）

在传统的自适应算法中，Pc和Pm按下列公式进行自适应调整：

式中，fmax为最大的适应度值；favg为平均适应度；f′为要交叉的两个个体中较大的适应度值；f为要变异个体的适应度值。

但是这种方法在进化初期种群中较优个体几乎不会发生变化，而得到的优良个体不一定是全局最优解，可能产生局部最优解[4]。任子武等人在此基础上提出了一种改进的自适应遗传算法（IAGA）[5]。本文提出的改进的自适应遗传算法是交叉概率和变异概率随着进化代数和适应度函数的变化而改变，不会在进化的初期陷入局部最优。首先将进化分为3个阶段，每个阶段的交叉概率、变异概率的上限和下限随着进化代数的增减而逐渐减小，这种分阶段的方法能够使算法实现首先对图像进行广泛粗略搜索，再进行细致搜索。这样可以更快更好地寻找到最优解，并且不会出现早熟现象。

改进的自适应遗传算法 （称为分段自适应遗传算法）分为三个进化阶段。M为最大遗传代数，Pc为交叉概率，Pm为变异概率，f为适应度值。第一阶段为 1～0.4M代，这时 Pc1=0.9 Pc2=0.7 Pm1=0.08 Pm2=0.05；第二阶段为 第 0.4M～0.8M 代，Pc1=0.7 Pc2=0.5 Pm1=0.06 Pm2=0.03；第三阶段为第0.8M到第M代，Pc1=0.5 Pc2=0.3 Pm1=0.03 Pm2=0.01。

改进的自适应遗传算法中，Pc和Pm按下列公式分段调整：

2 最大方差比准则[6]

对于灰度级 S=（1，2，3，...，L） 的图像，T 为分割阈值，把图像分割为 S1=（1，2，3，…，T），S2=（T+1，T+2，…，L）。则类内方差分别为：

最大方差比为：

η越大，说明不同类像素之间的灰度相差越大，同类像素之间的灰度值相差越小。所以，η越大，说明分割效果越佳。

3 改进算法在图像分割中的应用

自适应遗传算法作为一种模拟生物在自然环境中遗传和进化过程的自适应全局搜索算法，其鲁棒性、适应性及全局优化性等明显优于传统遗传算法。分段的自适应遗传算法具有更高的适应性，同时可以减小进化的代数，在初始阶段保证了种群的多样性，进化的最后阶段可以很好地保持最优解的完整性。本文基于分段自适应遗传算法的图像分割，采用了方差比作为适应度函数，并与经典的Ostu图像分割方法进行比较。两种算法分割结果如图3所示。

算法步骤：

（1）图像预处理：对图像进行双线性插值处理。

（2）初始化：在改进的遗传算法中，令种群规模为15，进化代数为 50，染色体长度为 8，初始化种群（采用二进制编码），读入预处理的图像。

（3）确定自适应函数，把方差比作为适应度函数，计算个体的适应度值，并对种群进行解码。

（4）开始进行迭代，首先判断进化的代数，选择恰当的交叉概率和变异概率。

（5）进行遗传操作：选择，交叉，变异。

（6）停止准则：判断最大适应度值在连续三代中的变化是否小于0.005或者是否执行到最大代数，若否，继续循环（4）；若是则找出最佳的方差比η以及对应的灰度级θ。

（7）对图像进行阈值分割，并求出对应的类间方差、类内方差、方差比以及分割后的信息熵。

图3 两种算法的图像分割结果对比

表1 处理结果统计

由分割图像和结果统计表（表1）得出，本文算法在分割图像和参数比较方面优于Otsu方法，从直观感受，本文算法所分割图像简洁而又不失细腻，从数据方面本文算法分割图像的信息熵是0.987 3，Otsu方法分割后图像的信息熵是0.978 6。由信息熵定义判定，信息熵越大图像分割效果越好。本文算法分割后图像最大方差略大于由Otsu方法分割后图像，说明不同类像素之间的灰度相差大，同类像素之间的灰度值相差小。从这两方面比较本文算法的分割效果更好一些。

4 结论

传统自适应遗传算法容易出现早熟或是局部最优解，本文提出的分段自适应遗传算法遵循先广搜索，再细搜索的策略，在进化的初期能增加种群的多样性，而在后期较小的交叉、变异概率下很好地保证了最优解的结构不被破坏。自适应能力强，具有较好的性能。用分段自适应遗传算法结合最大方差比寻求最佳阈值进行图像分割，分割后的图像清晰简洁，算法效率比较高。

[1]BYUNGKI C，KAWANO H，SUETAKE N，et al.Minimum-Spanning-Tree-like based image segmentation[C].2008.ICNC′08 Fourth International Conference on Natural Computation（Volume：6），Jinan，2008，152-156.

[2]Zhang Jian，Chen Xiaowei.Non-subsampled contourlets and gray level co-occurrence matrix based images segmentation[C].2011 International Conference on Uncertainty Reasoning and Knowledge Engineering （URKE），Bali： 2011：168-170.

[3]Chang Chengyuan，Chen Dengrui.Active noise cancellation without secondary path identification by using an adaptive genetic algorithm[J].IEEE Transactions on Instrumentation and Measurement，2010，59（9）：2315-2327.

[4]王小平，曹立明.遗传算法：理论、应用与软件实现[M].西安：西安交通大学出版社，2002.

[5]任子武，伞冶.自适应遗传算法的改进及在系统辨别中的应用研究[J].系统仿真学报，2006，18（1）：42-66.

[6]辛国江，模拟人类视觉机理的图像处理方法[D].长沙：中南大学，2013.