一种差分进化二维熵的KFCM图像分割算法

马冬梅，武永娟，梁红博

(西北师范大学 物理与电子工程学院，甘肃 兰州 730070)

图像是自然景物在人脑里最直接的反映，是人们获取信息的主要来源.通过图像，人们很容易直观地理解所呈现出的信息，因而，图像逐渐成为人们生活中普遍存在的信息形式.图像处理是旨在提高图像所呈现出信息的效果和质量，为图像的目标识别做好准备.因此，图像处理是人们获取信息的重要手段，而图像分割是图像处理及其应用的重要组成部分，其目的是把图像分成具有不同特性的物体或者区域，将人们需要的目标或区域提取出来[1].随着科学技术的发展，图像分割在社会中发挥着越来越重要的作用，它广泛应用于数学、物理和医学及特定场景分析等各个领域.到目前为止，已经提出了多种图像分割方法[2]，但大多数都是针对具体问题具体运用分割算法的.其中，聚类方法主要是为达到同类目标尽可能相似，不同类目标尽可能不相似的目的，它是一种广泛使用的自动分割方法.聚类算法通常分为传统聚类算法和模糊聚类算法.其中，模糊C均值算法(FCM)[3]是聚类图像分割方法中最常用的方法.FCM算法在分割的过程中，只需要给出初始值，不必要设置阈值，实现了自动分割.

FCM算法最早由Dunn[4]提出，并由Bezdek[5]改进建立了FCM算法理论，是一种无监督聚类算法.它是在C均值聚类分割的基础上引入模糊理论，可以处理一些模糊不确定的图像.但是FCM算法在分割过程中存在一些不足，在对聚类中心和聚类数的确定及对线性不可分数据敏感.在图像进行聚类前必须给出聚类中心和聚类数，否则图像就不可能聚类，这些值选择的不合适则会使计算速度慢，迭代次数多，且影响最后的分割结果.而FCM算法是由相似性度量聚类的，其中样本的分布情况由聚类的相似性度量决定.当样本之间的差异较小、分布混乱时会出现线性不可分的问题，导致分割结果差.针对这两个问题，许多研究者提出了不同的改进算法.周文刚等[6]采用阶段动态递增的方法来给出聚类中心进行全局搜索，提高了聚类的稳定性，但其计算复杂；Ganesan等[7]利用爬山(HC)方法给定聚类中心，结合改进的模糊C均值算法(MFCM)提高了算法的有效性和鲁棒性；吴宇翔等[8]利用轮盘赌的思想来产生初始聚类中心，提高了算法的效率，将免疫克隆算法与FCM算法结合，但分割效果不理想；Hemalatha等[9]采用改进的粒子群优化聚类中心，克服了对初始值敏感的问题，但是与传统FCM算法结合，分割效果差；Mahajan等[10]把欧氏距离用核函数替换，实现了线性可分，使得分割结果有所改善.本文使用差分进化二维熵算法和KFCM算法相结合的图像分割方法，不但解决了对初始值敏感、陷入局部极值及计算速度慢的问题，还解决了对线性不可分数据敏感的问题，实现了线性可分.

1 模糊C均值聚类

FCM图像分割算法是计算图像中像素点和聚类中心间的相似性度量，对目标函数迭代使其最小.然后，使用最大隶属度标准对像素点进行分类完成有效分割.其目标函数为

(1)

其中，c∈[2,N)为聚类数目；N为像素的总数；m为模糊加权指数；||xi-vi||为第i个像素xi与第j个聚类中心vj之间的欧式距离；uij为xi相对于vj的模糊隶属度.目标函数式(1)满足约束条件

(2)

运用Lagrange乘子，在约束条件(2)下找到目标函数(1)式的极值，通过拉格朗日函数对uij和vj求导数，得到模糊隶属度和聚类中心的迭代公式为

FCM算法对图像分割的步骤为

1)输入要分割的图像，给出聚类数目c，初始聚类中心v，终止条件阈值ε以及最大迭代次数t;

2)由(3)式计算得到隶属度uij；

3)由(4)式计算得到聚类中心vj；

4)直到||vt-vt+1||<ε或等于最大迭代次数tmax为止；否则返回执行步骤2)直到满足条件；

5)使用最大隶属度标准，把图像中的像素点归类，完成有效分割.

Ci=argjmax(uij),

(5)

其中，Ci为第i个像素属于的类别.

从上面的步骤中可以看出，由于聚类的结果是各个像素点属于某一类的程度，而在分割的过程中必须把像素点分类才能得到我们所需要的区域，所以FCM算法在分割的过程中必须执行步骤5.

2 差分进化二维熵算法

2.1 差分进化算法的基本原理

差分进化(DE)算法[11]是在1995年由Stom等提出的一种基于鲁棒简单快速的优化方法.其利用实数编码的方式在所有解空间并行搜索问题的方法.其方法为

2)变异操作.变异算子是在两个不同的个体之间进行向量差异，然后与个体进行合成获得新的变异个体目标向量，即

(6)

其中，F为缩放因子，用来限定变异的程度，F∈[0,2]；

(7)

其中，CR∈[0,1]为交叉因子；jrand为[1,…,D]区的随机整数；

5)当达到最大迭代次数或找到最佳值时，输出结果，否则，返回执行步骤2.

2.2 二维熵算法的基本原理

二维最大熵图像分割的阈值表达式为

(9)

差分进化二维熵算法的基本思想是将阈值表达式作为DE算法的适应度函数，计算图像的二维直方图，对得到的阈值进行编码，利用DE算法来搜索得到最优的阈值φ(s*,t*)，把这个最优阈值作为FCM算法的初始聚类中心，完成有效分割.

3 算法

3.1 基于核函数的FCM算法

高斯核函数[12]是把数据映射到无穷维的，因此它是最常用的，具体可以表示为

(11)

将(11)式代入(10)式得到

||φ(x)-φ(y)||2=2(1-K(x,y)),

(12)

得到KFCM算法的目标函数为

(13)

利用Lagrange乘数法求解，得到隶属度和聚类中心函数迭代式为

KFCM算法实现了高维特征空间样本的优化，使得样本与样本之间本身没有明显的特征突现出来，实现了线性可分.

3.2 差分进化二维熵的KFCM图像分割

通过计算图像的二维直方图，找到每个像素点所对应的二维熵，根据DE算法找出其中的最大熵，当达到最大迭代次数或得到最大熵值时，停止操作；把找出的最大熵作为最优阈值是图像分割的目标和背景中心，作为FCM算法的初始聚类中心，结合KFCM算法完成有效分割.

螺旋风管的制造高度自动化，生产速度快，由于其支架、吊架需用量少，安装工作量少，所以螺旋风管的总成本较低。而且采用无法兰连接，泄漏量少，有很好的社会效益。

算法的具体实施流程如图1所示.

图1 算法流程

1)输入要分割的图像；

2)计算图像的二维直方图对得到的二维阈值进行编码，并随机生成初始种群；

3)DE算法的变异操作；

4)DE算法的交叉操作；

5)DE算法的选择操作，获得最大信息熵；

6)当等于最大迭代次数时，输出最佳阈值，否则进入变异操作.当DE算法执行选择操作时，适应度比较大的值向量可以直接代入下一代操作中使用；

7)得到的阈值作为KFCM的初始聚类中心，给出聚类数目c、加权指数m=2、终止条件阈值ε以及最大迭代次数t的值；

8)按照(14)式计算模糊隶属度uij；

9)按照(15)式计算聚类中心vj；

10)直到||v(t)-v(t+1)||<ε或等于最大迭代次数tmax为止；否则返回执行步骤8),直到满足条件；

11)依照最大隶属度标准，把图像像素点归类，完成有效分割.

4 仿真结果与分析

以给出的图像为例，通过文中算法的分割结果与FCM算法、KFCM算法进行比较，验证本文算法的有效性.参数设置为：加权指数m=2，迭代误差ε=0.001，最大迭代次数t=100，种群个数N=20.

图2 Lena图像的分割结果

图2给出了Lena图像的分割结果.从人物的外貌特征鼻子、嘴、眼睛、帽子这四部分进行比较，可以看出本文算法很好地保留了这四部分中的细节，而FCM算法、KFCM算法对这四部分的分割结果比较模糊.

图3 Ploy图像的分割结果

图3给出Ploy图像的分割结果.可以看出，FCM算法、KFCM算法中背景被错误地分为目标，使得区域模糊和离散，而本文方法区域边界清晰，目标区域被很好地分割处理，分割结果较好.

图4给出了DIP图像的分割结果，从DIP图像字母下面的那部分内容进行比较，可以很明显看出FCM算法中一些目标没有被分割出来，区域信息缺失.而KFCM算法中引入了核函数，扩大了样本与样本之间的差异，实现了线性可分，得到的区域相对连续.文中算法在此基础上，通过对聚类中心和聚类数确定的方法，得出的目标区域比较清晰，边界连续.

图4 DIP图像的分割结果

表1给出了3种算法进行时间的比较可以看出，FCM算法由于是任意选择的初始值导致分割速度慢.KFCM算法中利用核函数代替欧式距离，使其计算变得复杂，增加了运行时间.而文中研究的差分进化二维熵对聚类中心和聚类数的确定方法降低了分割速度，缩短了运行时间.

表1 分割结果运行时间/s

5 结束语

通过使用差分进化二维熵对聚类中心和聚类数的确定，提出了一种将差分进化二维熵与KFCM算法相结合的图像分割算法.该方法首先通过差分进化二维熵对图像分割得到目标和背景的中心，将其作为FCM算法的初始聚类中心，然后由KFCM算法完成有效分割.经过实验验证，本文算法可以降低分割速度，缩短运行时间，同时提高分割精度，具有一定的实用性.