顾英杰， 贾振红， 覃锡忠， 杨 杰， 庞韶宁

（①新疆大学 信息科学与工程学院，新疆 乌鲁木齐 830046；②上海交通大学 图像处理与模式识别研究所, 上海 200240；③新西兰奥克兰理工大学 知识工程与开发研究所，新西兰 奥克兰1020）

0 引言

现代人类接收的信息中，有80%来自视觉，或者说为图像信息，但是大多数人并不是对整幅图像感兴趣，而是对图像中的一部分感兴趣，所以图像分割技术已经成为了研究热点。现在，人们常用的图像分割方法有K均值聚类、模糊C均值聚类(FCM)、ISODATA等[1-3]。其中 FCM是比较常用的方法，但是FCM算法是一种局部搜索优化算法，如果初始值选择不当，它就会收敛到局部极小点上，这对聚类效果会产生较大的影响[4-5]。为了克服这种缺陷，近期有文献提出用FPSO与FCM结合的方法对图像进行分割[6-7]，其分割效果优于遗传算法和OTSU算法。为了进一步提高图像分割的效果和效率，文中首次将混合蛙跳算法与模糊C-均值算法相结合。实验表明，该方法具有搜索全局最优解的能力，可以有效地克服FCM对于初始值选择的敏感性，分割效果好。

1 混合蛙跳算法的模型概述

1.1 基本概念

随机生成F只青蛙组成初始群体，第i只青蛙表示问题的解为Xi=(xi1,xi2,…,xis)，其中s表示变量的个数即解空间的维数。在生成初始群体之后，根据式（1）计算青蛙个体的适应度f(xi)：

将种群内青蛙个体按适应度降序排列，然后将整个青蛙群体分成m个子群,每个子群包含n只青蛙,满足关系F=m×n。其中第1只青蛙分入第1子群，第2只青蛙分入第2子群，第m只青蛙分入第m子群，第m+1只青蛙分入第1子群，第m+2只青蛙分入第2子群，以此类推，直到全部青蛙分完毕。

1.2 局部搜索

青蛙种群中各族群执行局部搜索策略的目的是在不同的搜索方向上搜索局部最优，搜索迭代一定次数后使得族群中局部最优个体逐步趋向于全局最优个体。首先将青蛙种群划分成多个族群，对每个族群进行局部搜索，但是为了避免青蛙个体过早陷入局部最优，同时加快收敛速度，在每个族群中按照特定的原则选择一定数目的青蛙构成该族群的子族群。

对于青蛙群体，具有全局最好适应度的解表示为Ug；对于每一个子族群，具有最好适应度的解表示为UB，最差适应度的解表示为 UW。首先对每个子族群进行局部搜索，即对子族群中最差适应度的青蛙个体进行更新操作，更新策略为：

其中，s表示青蛙个体的调整矢量，smax表示青蛙个体允许改变的最大步长。

1.3 全局信息交换

全局信息交换有助于收集各族群搜索的局部信息，通过模因在全局中的传递，获得新的搜索全局最优解。当所有族群经过一定次数的局部搜索后，将各族群中青蛙个体混合在一起，按适应度f(xi)降序排列后，重新划分族群，这样使得青蛙个体间的模因信息得到充分的传递，然后继续进行局部搜索，如此反复直到满足收敛条件算法为止。

2 蛙跳结合模糊C-均值的图像分割算法

基于混合蛙跳与模糊C-均值结合的图像分割算法步骤：

①初始化算法参数，其中包括：运行次数，变异概率，青蛙族群数，每族青蛙个数，每个青蛙种群的子种群青蛙个数，允许最大步长，以及青蛙个体；

②计算初始化聚类中心的适应度值，对适应度进行排序；

③生成种群和子种群，对适应度差的个体进行更新；

④若分类数为 3，且第一类聚类中心与第二类聚类中心之差小于第二类局类中心与第三类聚类中心之差时，则对第一类的聚类中心进行变异。变异目的是为了找到更优的解；

⑤如果当前的迭代次数达到预先设定的最大次数，则停止迭代，找到最优解，否则返回到步骤③。

3 实验结果与讨论

采用混合蛙跳与模糊 C-均值结合的图像分割算法的参数设定：类别数取3，变异概率为0.05，青蛙种群数为10，每一个青蛙种群的青蛙个数为10，每个青蛙种群的子种群青蛙个数为8，允许最大步长为4。

将所提算法与FCM结合FPSO的算法进行比较，在初始条件相同的情况下分别采用两种方法对图像进行分割实验。

为了获取一个定量的实验结果比较，笔者引入有效性评价函数，在聚类方法中，它们经常用来评价聚类效果的好坏。其中最具代表性的是分割系数 Vpc和分割熵 Vpe[8],它们分别定义如下：

当两个有效性评价函数达到最优值，即Vpc达到最大值，Vpe达到最小值时，模糊聚类分割的效果最好。

以下是几幅航拍图的分割效果。

图1 航拍原图

图2 基于FPSO和FCM结合算法的分割

图3 所提算法的 图像分割图像

可以看出，在相同初始条件下，所提出的算法可以更加有效地分割背景与目标，取得了更好的分割结果。

表1汇总了两种分割方法所对应的分割系数Vpc和分割熵Vpe的值。

从表1中可以看出所提算法与FCM结合FPSO算法相比提高了聚类的精度，并且缩短了分割所用时间，在图像聚类分割方面有更好的表现能力。

表1 两种算法的分割结果

作为一种全新的生物进化算法，混合蛙跳结合了基于基因进化的模因演算法（MA）和基于群体行为的粒子群算法（PSO）两者的优点，具有概念简单，参数少（比 PSO更少的算法参数），易于实现的特点。从实验数据来看，分割系数Vpc值大于FCM结合FPSO算法的值，分割熵Vpe的值小于FCM结合FPSO算法的值，因此提高了图像分割的精度。综上所述，所提方法对图像进行分割不但能得到较好的图像分割效果而且提高了图像分割效率。

4 结语

所提出的图像分割算法是将混合蛙跳算法引入到 FCM聚类算法中。实验表明，该算法能有效解决传统FCM对于初始化比较敏感以及容易陷入局部极小的问题，具有较强的全局搜索能力，并且在图像分割的效果方面优于FCM结合其他算法。

[1]WANG Xiang-yang, WANG Chun-hua. An Adaptive FCM Image Segmentation Algorithm Based on the Feature Divergence[J].Image and Graphic, 2008, 13(05): 906-910.

[2]BEZDEK J C, EHRLICH R, FULL W. The Fuzzy C-means Clustering Algorithm[J]. Computers and Geosciences, 1994, 10(2):191-203.

[3]ADEL H, BERTRAND Z. FCM with Spatial and Multi-resolution Constraints for Image Segmentation[J].Lecture Notes in Computer Science,2005,3656(10): 17-23.

[4]INGUNN BERGET, BJM-HELGE MEVIKC, TORMOD NAS. New Modifications and Applications of Fuzzy C-means Methodology[J].Computational Statistics＆Data Analysis, 2008,52: 2403-2418.

[5]DU Gen-yuan, MIAO Fang. A Modified Fuzzy C-means Algorithm in Remote Sensing Image Segmentation[C]//IEEE. 2009 IEEE International Conference on Environmental Science and Information Application Technology. [s.l.]:IEEE, 2009:447-450.

[6]JING Zang, Image Segmentation Using Possibilistic C Means Based on Particle Swarm Optimization[C]// IEEE. IEEE Global Congress on intelligent Systems. [s.l.]:IEEE,2009: 119-123.

[7]张蕾, 吕振肃. 基于改进的自适应克隆选择粒子群优化算法的多用户检测[J]. 通信技术, 2007, 40(12):190-192.

[8]CHUANG K S, TZENG H L, CHEN S W, et al. Fuzzy C-means Clustering with Spatial Information for Image Segmentation[J].Comp.Med.Imag.Graph, 2006,30: 9-15.