一种改进的遗传算法在图像分割中的应用

王丹　周锦程

【摘 要】二维最大熵图像阈值分割法是在整个二维灰度空间上搜索相关参数，从而使得图像的总熵取得最大值的优化问题，该算法计算量大、耗时长。为此，我们将二维最大熵的图像阈值分割方法中的相关技术引入到遗传算法中，以降低算法的复杂度。具体地，结合二维最大熵图像分割法的特点，我们对传统遗传算法中的选择算子、交叉算子和变异算子等进行了优化设计，以加快算法的收敛性。实验结果表明，本文设计的基于遗传算法的二维最大熵图像分割方法所分割的图像优于一般常用的图像分割算法。

【关键词】遗传算法；二维最大熵法；图像分割；阈值分割

An Improved Genetic Algorithm for Image Segmentation

WANG Dan ZHOU Jin-cheng

（School of Mathematics and Statistics，Qiannan Normal College for Nationalities， Duyun Guizhou 558000， China）

【Abstract】The two-dimensional maximum entropy method is an optimization problem for the parameters search in the whole two-dimensional gray space to obtain the maximum total entropy of an image. Thus， the amount of the calculation would be large and the time cost would be high. In order to reduce the complexity of the algorithm， we introduce the relevant technology of the two-dimensional maximum entropy method into the genetic algorithm for image segmentation problem. Specifically， considered with the characteristics of two-dimensional entropy image segmentation method， we optimize the selection， crossover and mutation operators in the traditional genetic algorithm， so as to accelerate the convergence of the search process. Experimental results show that our genetic algorithm with two-dimensional maximum entropy method is better than the common image segmentation algorithm.

【Key words】Genetic algorithm； Two-dimensional maximum entropy method； Image segmentation； Threshold segmentation

0 引言

遗传算法（Genetic Algorithm， GA）[1]是由美国Michigan大学的Holland于1975年提出的一种随机自适应的全局搜索算法。它是一种通过借鉴进化论中适者生存、优胜劣汰的遗传机制演化而来的计算模型。该算法的基本思想最先由Holland[2]在1962年提出，之后陆续有研究者提及了该算法的一些基本概念[3-6]，“遗传算法”这个术语在1967年首先由Bagley在其博士论文中使用，但直至1975年，遗传算法的数学框架与理论才由Holland[7]在其专著中进行了系统而详细的表述。

早期的遗传算法主要被用于求解函数优化问题和人工自适应系统的研究与设计。随着遗传算法的不断改进与完善，它为解决复杂优化问题提供了一种崭新且有效的思路，其良好的搜索能力得了广大学者的关注和认可。当前，遗传算法的应用范围已被逐渐延伸到了组合优化、图像处理、网络通信、模式识别等众多复杂优化领域。

图像分割[8]是图像处理及前期视觉中常常用到的一种基本技术，也是大多数图像分析及视觉系统的重要组成部分。所谓图像分割是指根据图像的灰度、几何形状、空间纹理、色彩等特征把图像划分成若干个互不相交的区域，使得这些特征在不同区域间表现出明显的不同，而在在同一区域内，表现出一致性或相似性。本文将主要研究遗传算法在图像分割中的应用。

1 相关概述

1.1 遗传算法

遗传算法主要是通过模拟自然界中生物的遗传进化过程，对优化问题的最优解进行搜索，它将种群中的所有个体作为潜在解的群里，引入类似自然进化中的选择、交叉和变异等算子对群体中的所有个体进行进化。遗传算法的核心内容主要包括以下五个方面：①设计相关参数的编码；②设定初始群体；③设计适应度函数；④设计遗传操作；⑤设定控制参数。与传统的搜索算法不同，遗传算法在运行中，首先要随机产生一组初始解作为种群开始搜索，种群中的每个个体（编码为染色体）被看做是问题的一个解。这些个体在后续迭代过程中不断进化。通常用适应度值来度量每一代中各个染色体对应的个体的优劣，一般来说，对应个体的适应度值越大，表示该个体越优秀，则该个体被选作种群中的父带个体的概率也越大。新个体由父代个体对应的染色体通过交叉或者变异操作而产生，这样经过若干代进化之后，算法将收敛于最好的个体，该个体很有可能就是问题的最优解或次优解。遗传算法主要包括如下步骤：

Step 1 编码：遗传算法在对解进行搜索之前，需要先将解空间的解进行编码成特点的字符串。

Step 2 初始群体的生成：随机产生N个染色体，N个染色体构成了一个种群，遗传算法以这N个染色体作为初始点开始迭代。

Step 3 个体评价：用适应值函数刻画个体的优劣性。通常，针对不同的优化问题，需要设计不同的适应性函数。

Step 4 选择运算：按照一定的规则从当前群体中选出优良的个体，其主要思想来自于达尔文的适者生存原则。

Step 5 交叉运算：新个体通过交叉操作获得且继承其父辈个体的特征，交叉体现了信息交换的思想。

Step 6 变异操作：将变异算子作用于新群体中的少部分个体，对这部分个体的染色体以一定的概率随机地改变染色体中某些基因的编码，变异是为了在群体中引入新的变种，确保种群的多样性。

1.2 图像分割

当前，常用图像分割方法主要包括边缘检测法、区域分割法以及阈值分割法等。其中，阈值分割法因其计算量小、实现简单、性能较为稳定而成为图像分割中最基本和应用最广泛的分割技术。当前，已有很多基于阈值分割的处理方法，诸如最大类别方差法[9]（OTSU法），最小误差法和最佳直方图熵法[10]（KSW熵法）等等。其中，最佳直方图熵法是将信息论中的最大熵原理应用于图像的阈值分割，往往可以找到最佳的分割阈值。

现有的阈值法，选取最佳阈值时尽管有很多准则，但大多算法需要在全灰度范围内进行搜索，因此搜索空间大、时间开销多。因此，如何寻找易计算并且自适应能力强的阈值方法在图像处理工作中一直是值得研究的重要课题。遗传算法是一种通过模拟自然进化过程搜索最优解的方法，其对全局信息的有效搜索能力，使得该方法只需检测少量的结构就能反映搜索空间较大的区域，并获得稳定的最优解。因此，本文通过有机地结合遗传算法和二维最大熵阈值法，提出了一种新的图像分割算法。该算法能有效提高图像分割的速度且能获得较好的分割结果。

2 改进遗传算法的图像分割

2.1 二维最大熵图像分割法

一般情况下，在图像质量较好和背景稳定变化时，一维最大熵图像分割算法能得到较好的分割结果，而对于具有较为复杂的背景或信噪比较低的图像，其性能往往较差。文献[11]提出了一种二维最大熵图像分割算法，该算法采用了图像各像素间的空间相关信息和像素的灰度分布信息，并使用像素灰度和邻域平均灰度构成的二维直方图来搜索阈值，实验结果表明，该算法能获得较好的分割效果。

设一幅N×N的图像I有L级灰度G={0，1，…，L-1}，其s×s的邻域的平均灰度也有L级灰度G={0，1，…，L-1}，相应的二维直方图表示为：h（i，j）=pij，0≤i，j≤L-1，其中i为像素灰度，j为s×s邻域的平均灰度。pij由下式确定：

2.2 改进遗传算法的图像分割方法

由于二维最大熵法实质上是在二维灰度空间上搜索参数从而使图像的总熵取得最大值，因此算法的计算量较大、耗时较长。为降低算法的复杂度，本文将二维最大熵的图像阈值分割方法中的相关技术引入到遗传算法中。具体地，结合二维熵图像分割法的特点，我们对传统遗传算法中的选择、交叉、变异等基本算子进行设计，以加快算法的收敛性并确保得到较好的解。本文对遗传算法的设计如下：

（1）采用均匀分布随机产生初始化种群。

（2）由于图像分割的处理对象是具有不同灰度级的像素点，本文考虑的分割图像为256个灰度级，阈值参数满足0≤s，t≤255，因此我们将灰度分割阈值（s，t）编码为一个长度恰好为16位的二进制串，并用其中的低8位用来编码t，高8位用来编码s。

（3）采用二维熵图像分割法中的图像的总熵H（s，t）作为我们算法的适应度评价函数。

（4）采用轮盘赌法和精英策略相结合的方案对染色体进行选择操作。

（5）采用随机产生的多个交叉点的方式进行多点交叉操作。

（6）采用随机随机按位取反的方式对个体进行变异操作。

（7）采用收敛程度和最大进化代数结合的停机策略，即终止条件为达到最大进化代数gmax，或者当前群体的平均适应度值与上一代群体的平均适应度值的绝对差小于ε。算法终止时，具有最高适应度值的个体作为最佳阈值。

本文构造改进遗传算法的图像分割方法的计算流程如下：

Step 1 设定种群数目N，对二维阈值进行二进制编码，并随机产生初始种群。

Step 2 对初始种群解码，并根据式（2），式（3）和式（4）计算每个基因串的适应度值。

Step 3 将适应度最大的个体，即种群中最好的个体直接复制到下一代新种群中，然后对父代种群进行采用本文提出的选择、交叉和变异等遗传算子运算，从而繁殖出下一代新种群的其它N-1个基因串（个体）。

Step 4 如果达到终止准则，则返回最好的基因串，并将其作为二维分割阈值分割图像，算法结束；否则回到Step 3继续下一代的繁衍。

3 实验结果及分析

为验证本文算法的有效性和准确性，分别用OTSU分割算法、文献[12]提出的二维直方图θ划分最大Shannon熵图像阈值分割算法和本文提出的基于改进的遗传算法的图像分割算法，在matlab环境下对灰度级为256图像进行分割实验。三种算法对米粒图像和标准Lenna图像分割的实验结果如图1、图2所示。其中，基于遗传算法的图像熵分割结果图采用随机运行20次得到的最好结果图。图1（a）是为源图像，图1（b）、（c）、（d）分别为三种算法的分割结果图。从图中可以看出，三种分割方法都能较好地分割源图像，基于遗传算法的图像熵分割方法比OTSU分割算法提取了更多的米粒目标，结果图（d）中分割的图像较图（b）和图（c）更清晰，提取了更多的米粒目标。对标准Lenna图的分割结果如图2所示，其效果也优于OTSU算法和文献[12]中的算法。因此，综合图1和图2的分割结果图可见，本文算法比基于基本遗传算法的图像熵分割方法收敛快，分割阈值与OTSU相当，能够比较理想地完成对图像的分割，分割的图像清晰，表现出了更好的全局搜索能力，更能突出感兴趣的区域，并获得更好的分割效果。

4 结语

遗传算法是一种独立于问题领域且具有快速随机搜索能力的随机算法，该算法通过模拟自然进化过程搜索最优解，（下转第117页）（上接第109页）其对全局信息的有效搜索能力，使得该方法只需检测少量的结构就能反映搜索空间较大的区域，并能获得较为稳定的最优解。由于传统的二维最大熵法实质上是在二维灰度空间上搜索参数从而使图像的总熵取得最大值，因此算法的计算量较大、耗时长。因此，本文结合二维最大熵法的特点，将二维最大熵的图像阈值分割法中的相关技术引入到遗传算法中，并设计了相应遗传算法的选择、交叉、变异等算子。实验结果表明，我们所提出的算法能有效提高图像分割的速度且能获得较好的分割结果。

【参考文献】

[1]Holland J H. Genetic algorithms[J]. Scientific American， 1992， 267（1）： 66-72.

[2]Holland J H. Outline for a logical theory of adaptive systems[J]. Journal of the ACM （JACM）， 1962， 9（3）： 297-314.

[3]Bagley J D. The behavior of adaptive systems which employ genetic and correlation algorithms[D]. Ph. D. Dissertation， University of Michigan. 1967.

[4]Cavicchio D J. Adaptive search using simulated evolution[D]. Ph. D. Dissertation， University of Michigan. 1970.

[5]Hollstien R B， Artificial Genetic Adaptation in Computer Control System. Ph. D[Z]. Dissertation， University of Michigan. 1970.

[6]De Jong K A. Analysis of the behavior of a class of genetic adaptive systems[D]. Ph. D. Dissertation， University of Michigan. 1975.

[7]Holland J H. Adaptation in natural and artificial systems[M]. 2nd ed. Cambridge： MIT Press， 1992.

[8]章毓晋.图像分割[M].北京：科学出版社，2001.

[9]Otsu N. A Threshold Selection Method from Gray Level Histogram[J]. IEEE Trans on System Man and Cybernetics， 1979，9（1）：62-66.

[10]Kapur J N， Sahoo P K， Wong A K C. A new method for gray-level picture thresholding using the entropy of the histogram[J]. Computer Vision Graphics & Image Processing， 1985，29（3）：273-285.

[11]Abutaleb A S. Automatic thresholding of gray-level pictures using two-dimensional entropy[J]. Computer Vision Graphics & Image Processing， 1989，47（1）：22-32.

[12]吴一全，张金矿.二维直方图θ划分最大Shannon熵图像阈值分割[J].物理学报，2010，59（8）：5487-5495.

[责任编辑：汤静]