基于最大熵和遗传算法的图像分割方法研究∗

余荣泉 段先华

（江苏科技大学计算机学院 镇江 212003）

1 引言

图像分割是图像处理和计算机视觉领域的一个重要分支，是后续的分类、跟踪、识别等处理的基础，具有重要的研究意义。图像分割是把图像分成若干个特定的、具有独特性质的区域，然后从中找出感兴趣目标的技术和过程。在所有的图像分割方法中，阈值法因快速、简单而得到了广泛的应用。阈值分割的方法有很多，例如:直方图阈值分割［1］、最大类间方差法［2］、基于最大熵的阈值分割［3］等。其中，基于最大熵的阈值分割算法利用图像的空间信息和灰度分布信息来定义图像的信息熵，不需要先验知识，根据假设的不同或视角的不同提出熵函数准则，通过优化得到最佳阈值。该方法的缺陷是在确定阈值尤其是多阈值的时候，计算量比较大，算法复杂度高。

随着科学技术的不断发展，一些新理论、新方法逐渐运用到图像分割领域中，如人工神经网络［4］、深度学习［5］、模式识别［6］、模糊数学［7］、蚁群算法［8］、机器学习［9］和遗传算法［10］等。通过阅读文献，阈值法与这其中的某些方法结合使用，可以得到较好的分割效果，无论是在算法复杂度还是图像分割精确度上都有了较大的提升。

本文利用遗传算法具有的并行性、鲁棒性和自适应性的优点结合最大熵算法，对几幅经典的图像进行分割。仿真结果表明，改进的算法与传统的图像分割算法相比，分割效率高，分割速度有所提高，图像分割更加精确。

2 传统最大熵阈值分割

2.1 一维最大熵阈值分割

在信息论中，熵是事件出现概率不确定性的量度，在图像中它是图像统计特性的一种表现形式，反映了图像包含信息量的大小。将信息论中熵的概念应用于图像分割［11］，把图像中目标与背景视为两个独立的信源，通过分析图像灰度直方图的熵，找到最佳分割阈值。设图像的灰度范围是{0,1,…,L-1} ，图像的分割阈值为 τ ，Pi为灰度i 出现的概率，i ∊{0 ,1,…,L-1} 。假设图像中像素灰度在{0 ,1,…,τ} 范围内的构成目标区域( T )，像素灰度在{τ +1,τ+2,…,L-1} 范围内的构成背景区域( B )，那么它们的概率分布为

其中

对于数字图像，定义与目标区域和背景区域概率分布相关的熵为

其中

准则函数定义为

使准则函数φ( τ )取最大值的灰度级τ 即是所求出的最优阈值τ*，即

2.2 二维最大熵阈值分割

二维最大熵法［12］是在一维最大熵法的基础上进行改进，利用图像中各像素的灰度值分布，结合像素点之间的空间分布，建立二维直方图，计算最大熵值，并以此作为最佳阈值进行图像分割。和一维最大熵法相比，二维最大熵法不仅考虑了像素间的空间关系，还考虑了像素的灰度分布关系，具有更好的抗噪性能。

二维最大熵阈值分割法综合运用图像像素点灰度和区域灰度特征表示图像信息，具体方法如下。

设原始图像 f( x,y )是灰度级为 L ，大小为M×N 的灰度图像，以原始图像中各像素及其四邻域的四个像素为一个区域，计算出区域的灰度均值图像。采用点灰度—区域灰度均值对，这样的数据对共有L×L 对。令Pij=nij(M×N)。根据香农熵的定义，二维离散熵定义为其中，nij表示当前点灰度值为i，其四邻域平均灰度为 j 的像素点对的个数，Pij是该事件发生的概率。 Pij就是该图像关于点灰度—区域灰度均值的二维直方图。如图1 所示，阈值( )s,t 将图像分为目标区A 和背景区B，远离对角线的为边界区C和噪声区D。所以二维熵包含了目标区A 和背景区B 的最大信息量，同时也能够保留细节部分。在区A 和区B 上运用点灰度—区域灰度均值二维最大熵法确定最大阈值，使得目标区和背景区的信息量达到最大。

图1 图像二维平面直方图

假设待分割的图像目标区域和背景区域都具有不同的概率分布，目标区A 和背景区B 的概率分布分别为

目标区A 和背景区B 的二维熵函数分别为

其中

由于边界区C 和噪声区D 发生的概率微小，几乎可以忽略不计，假设它们的Pij=0，由此得:

其中

则

图像熵的判别函数定义为

最佳阈值向量( )s,t 应该满足如下条件:

3 基于最大熵和遗传算法的图像分割

遗传算法［13］是一种模仿生物在自然环境中遗传和进化，通过“优胜劣汰”的方式，不断遗传变异，产生最佳适应个体的方法。二维最大熵在本质上是对图像在二维灰度空间上搜索参数，使得目标函数取得最大值的优化问题，该算法计算量较大、耗时多。因此，将遗传算法运用于最大熵的图像阈值分割［14～15］中，可以降低算法的复杂度。

在本文中，根据图像区域的灰度直方图信息，对遗传算法的种群进行初始化，将最大熵值函数作为遗传算法的适应度函数或目标函数，对群体中的个体施加遗传操作（选择、交叉、变异），实现群体内个体结构重组，使得群体中的个体不断得以优化，最终获得最大熵值图像的最优分割阈值。将遗传算法应用于图像分割，算法流程如图2 所示，算法步骤如下:

Step1:随机产生初始种群。本文设置其初始代数Gen为0；

Step2:编码。编码是遗传算法的基础，编码的好坏直接影响后续遗传算法的选择、交叉和变异的运算。编码［16］的方式有很多，由于图像的灰度级在［0，255］范围内，所以，本文采用16 位二进制编码的方式对染色体进行编码，每个染色体都代表一个分割阈值；

Step3:设定种群规模。种群规模的设置应该合理，规模过大，会导致每一代适应度值的计算量增加；规模过小，会导致未成熟收敛的现象。实验中，设置种群规模为20，最大繁殖代数为100；

Step4:解码。将二进制染色体组解码为［0，255］范围内的值，文中采用二维熵函数作为适应度函数，对每个个体通过φ( s,t )=MAX{φ( s,t )}计算其适应度值；

Step5:选择。选择的目的是从群体中选出优良的个体，让这些个体作为父代为下一代的繁殖做好准备。文中采用了轮盘赌的方式，首先计算群体中所有个体的适应度总和，然后计算每个个体的相对适应度大小，最后用轮盘赌的操作确定每个个体的选中次数；

Step6:交叉。交叉也可以称为重组，按照较大的概率（概率太低影响收敛速度）从群体中选择两个个体，交换两个个体的某个或者某些位，产生不同于母体的子体。文中采用了单点交叉，交叉概率设置为0.6；

Step7:变异。变异是以较小的概率对个体编码串上的某个或某些值进行改变，从而产生新个体。采用基本的变异运算，将染色体编码串中的某个或某些基因座上的基因值用它的等位基因来替换，形成新个体。实验中设置变异概率为0.03；

Step8:判断终止准则。预先设定最大代数为20，当算法执行到最大代数或经过20 代进化，群体中的最高适应度值仍未发生变化时，算法中止，具有最高适应度值的个体即为分割阈值。若没有执行到最大代数，则重复Step4至Step7；

Step9:分割图像。将得到的最高适应度值作为分割阈值进行图像分割。

图2 图像阈值分割的遗传算法流程图

4 实验结果与分析

本文所有的仿真实验都是在Intel Core i3-380M、4GB 内存，Matlab R2014a 软件环境下完成的。为了验证本文提出的基于最大熵和遗传算法的图像分割算法的有效性，对几幅经典的图像进行了仿真。在仿真过程中，首先将图像转换成灰度级在［0，255］范围内的灰度图像，然后绘制直方图，最后用传统的最大熵阈值分割法和本文的分割算法对图像进行了分割。

分别对比图3、4、5 中的实验结果我们可以发现:

图3 Girl图像分割

在分割效果上，与传统最大熵分割结果相比，本文算法的分割效果更加逼真和精确，更富有层次感，特别是对于一些细节的分割效果。例如，图3中的图（d），女孩的头发、眉毛、眼睛、嘴以及人物的轮廓，对这些细节的分割效果要优于图（c），人物也更加逼真；图4 中的图（d），左侧的树叶、草丛、房屋屋顶瓦片、树影以及附近的那辆小轿车这些细节用本文算法都很好地分割了出来，而图（c）则没有体现；图5 中的图（d），左侧两个苹果（特别是最左侧的苹果）以及苹果上面的斑块在本文算法的分割结果中都较好地体现出来了，分割结果也更有立体感，视觉效果明显优于图（c）。

图4 风景图像分割

图5 水果图像分割

在分割时间上，本文算法对图像分割所用的时间要比传统的最大熵图像分割算法少。本文算法和传统最大熵阈值分割算法对每幅图像分割耗费的时间如表1所示。

表1 两种算法运行时间对比

5 结语

针对传统的最大熵阈值分割存在的算法复杂度高、计算多阈值时运算时间长、对目标细节分割模糊以及分割结果不精确的问题，本文将最大熵阈值分割和遗传算法相结合，利用遗传算法具有的并行性、鲁棒性和自适应性的优点来快速准确地确定灰度图像直方图熵的最佳分割阈值，实现图像分割。实验结果表明，本文算法能够缩短寻找阈值的时间，对图像的细节分割效果要优于传统算法，具有较好的理论意义和实践意义。