基于最大熵的进化区域生长分割算法

魏光杏，周献中，李 华

（1. 滁州职业技术学院 信息工程学院，安徽 滁州 239000；2. 南京大学 工程管理学院，江苏 南京 210093）

0 引言

图像分割是图像处理和判读处理中一个非常重要的阶段，目前有许多共性的图像分割方法，其中包括基于区域的分割［1−4］、基于超像素的分割［5］和基于轮廓的分割［6］。好的分割方法可以更容易得到准确的图像信息。

按区域生长进行分割是一种快速、简单且易于实现的图像分割算法。蒋秋霖等［1］将区域生长算法应用到医学脑肿瘤图像分割上，得到较好的分割图像，但图像上点的次序对该优化算法影响较大，分割出的结果不太稳定，容易产生过分割。肖明尧等［2］引入图像的多尺度概念，提出基于多尺度区域生长的图像分割算法，利用图像多尺度的最大梯度矩阵来获得准确的分割图像，但算法的复杂度偏高。刘振宇等［3］提出基于改进区域生长算法的视杯自动分割算法，该算法依据图像灰度直方图以及阈值法对区域生长算法中的种子点定位性能进行提高，得到的分割后图像有较高准确性，但仅适用于视网膜血管分割。文献［4］给出了优化算法，该算法先计算所有像素点的直方图和邻域相似度因子，然后根据邻域相似度因子的值建立种子选择规则、种子生长准则和生长终止准则，通过相关阈值对图像进行分割。虽然该算法获得分割图的质量有较大提高，但它仍存在着不足，如对阈值敏感、对于不同的初始化点（种子点）得到的结果不同。

本研究提出了基于最大熵进化方法的区域生长分割优化算法。在分割之前，以最大熵理论为基础，从符合条件中的最大熵来确定分割后区域的数目，对进化区域生长算法中的策略进行优化，以消除区域生长分割算法中的不足，提高了分割质量，也加快图像分割速度。

1 区域生长算法

1.1 区域生长算法原理

区域生长算法是一种基于逼近区域的分割方法，其实现原理如下：

1）选择图像开始修正点（种子），这些点（种子）被称为搜索区域的细菌。

2）确定搜索区域的均匀性（阈值）准则，如灰度或纹理准则等。

3）递归过程，满足相关准则的所有点都包含在区域中。

这些点（种子）是变化的，但必须满足作为准则的区域，种子点的选择是算法的关键部分。生长阶段将使用相似性度量来选择要聚集的像素，当不再有像素满足加入这个区域的条件时，区域生长停止。

1.2 基于进化策略的区域生长算法优化

1.2.1 编码 所给出的算法是在所有可能的区域中通过最大化验证分割的准则来选择最优的区域，这将产生在该区域生长中使用的最佳种子（Psj）。因此，这里假设编码为

式中，chr染色体是C×N图像点的集合，Psj=(gsj)1≤j≤N=(gs1gs2) =(xs,ys)，基因 (gsj)1≤j≤N是种子Psj的坐标x和y。

1.2.2 约束条件 为避免初始解远离最优解，首选种子点的坐标值满足下列条件：

式中，m1和m2是图像的维数。

在所提出的算法中，如果带有不满足此约束条件的基因染色体，则通过基因的变异产生新的变异基因，用此新变异基因代替原基因。

1.2.3 适应度函数 设chr为细菌(Ps)1≤s≤C形成种群的染色体。为了计算与chr相关的适应度函数值，定义适应度函数

式中 ，MoyRi为 当 前 区 域像素Ps灰 度 的 平 均 值 ，Ngs为区域Ri中 像 素Ps的 灰 度 ，M表 示区域Ri中的像素数。如果F(chr)函数值最小，则染色体chr最优。

1.2.4 进化区域生长算法（evolutionary region growing，ERG） 进化区域生长算法步骤如下：

1）图像初始化，确定图像中区域C的数目，生产种群Pop，

并用约束条件验证种群Pop中的每个chr。

2）对每个种群Pop中的chr进行区域生长。

3）计算出每个种群Pop中chr的适应值F(chr)。

4）将计算出来的适应值F(chr)按递增顺序进行排序，选择最佳染色体chr，也就是确定这一区域的最优chr及其相应适应值F(chr)。

5）对种群Pop中染色体的chr利用标准正态分布N（0，1）函数进行变异，

式中，fm表示最优chr的适应值。

6）重复第2）至第5）步骤，若生长区域中再没有新的像素，则结束生长。

2 基于最大熵的进化区域生长图像分割

2.1 最大熵计算公式

在图像分区问题中，很难确定分区的数量C，很多学者采用最大熵的方法，比如文献［7−8］等。这里选择文献［7］侯森提出的最大熵计算公式：

则公式变形为

式中,CLj表示第j聚类的集合是对应于j类的熵，熵S最大的值即为区域类的最佳数C。

2.2 进化策略优化的最大熵

设FERG(chr)为函数，其最大熵原理定义为

从（8）式可以看出，当对于给定值C，函数FERG(chr)的值仅依赖于chr。当C固定，（8）式能计算并提供收敛全局最优分区，也就是区域中chr最优值，这时FERG(chr)的值是最大的，此值满足Cmax＝max（FERG(chr)）。此时的最大熵就是选择Cmax这样的数值。如果FERG(chr)的计算得到的是局部解，则最大熵将无法正确确定Cmax的最佳数值。

因此，为了避免在计算给定值C的FERG(chr)时出现局部解，在ERG 算法中，用选择函数FERG(chr)代替了适应度函数F(chr)。FERG(chr)函数可以针对多个C值进行计算，得到多个不同适应度函数值，当适应度函数FERG(chr)的值最大时，对应的C值为Cmax类的最佳数值。

2.3 基于最大熵的进化区域生长分割算法流程

首先对输入的图像进行初始化，利用最大熵原理计算出图像中区域C的数目，产生种群Pop。在种群Pop中任选一种子点chr，并根据（8）式计算该chr的适应度FERG(chr)，种子点chr经过正态分布变异，用中止条件来判断该种子点是否中止生长，具体流程如图1 所示。

图1 算法流程图Fig.1 Algorithm flowchart

3 实验结果与分析

为了验证所提出分割算法的性能，笔者从分割图像标准库中选择3 幅经典图像，分别采用原区域生长算法、基于多尺度的区域生长算法（文献［2］算法）和本文算法进行图形分割，并对其结果进行比较（见图2 ～ 图4）。实验环境：PC 机主频为2.5 GHz、酷睿I7 处理器，4.0 GB 内存，Windows 10 操作系统，MATLAB 2014b。

从图2 ～图4 可以看出，本文提出的基于最大熵的进化区域生长分割算法分割结果优于原区域生长算法及文献［2］算法。3 幅（d）图中的信息点保留更为完整，边缘线较清晰，分割的质量更优，而在 3 幅（b）、（c）图中，图像有些关键信息点被丢失。

为了进一步验证本文算法的优越性，采用了总体均数、标准方差、Jaccard 系数3 种常见的评价指标来进行验证。总体均数用于查找图像的平均灰度，值越小，获得聚类越优，相对图像质量越好；标准方差是指图像像素灰度值相对于均值的离散程度，标准方差值越大，表明图像中灰度级分布越分散，图像质量也就相对越好；Jaccard 系数是用来比较样本集的相似性和多样性的统计量，系数值越大，获得聚类也越优。

图2 3 种算法的Lena 图像分割结果比较Fig.2 Comparison of Lena image segmentation results of three algorithms

图3 3 种算法的Camera 图像分割结果比较Fig.3 Comparison of Camera image segmentation results of three algorithms

图4 3 种算法的Rice 图像分割结果比较Fig.4 Comparison of Rice image segmentation results of three algorithms

对Lena 图、Camera 图以及Rice 图进行有效性指数实验，实验结果如表1 所示，表中加粗数字标明为优。

表1 用有效性指数对3 种算法比较Tab.1 Comparison of three algorithms by effectiveness index

4 结语

区域生长算法是一种简单且易于实现的图像分割算法，利用该算法分割图像能获得较好的分割图，但该算法对初始化点的数目有一定的敏感性。鉴于此，文章提出了基于最大熵的进化区域生长分割算法，利用进化最大熵原理估计ERG 分割的起始点数目，克服了该算法的初始化问题。实验结果表明，本文提出的优化分割算法收敛速度较快，分割的质量也较好。使用总体均数、标准方差和Jaccard 系数3 种性能评价指标对区域生长算法及优化算法的分割结果进行比较，优化算法优于原算法。