基于互补空间信息的多目标进化聚类图像分割

赵 凤刘汉强范九伦

①(西安邮电大学通信与信息工程学院 西安 710061)

②(陕西师范大学计算机科学学院 西安 710062)

基于互补空间信息的多目标进化聚类图像分割

赵 凤*①刘汉强②范九伦①

①(西安邮电大学通信与信息工程学院 西安 710061)

②(陕西师范大学计算机科学学院 西安 710062)

现有的多目标进化聚类算法应用于图像分割时，没有考虑图像的任何空间信息，使得该类算法在含噪图像上的分割性能不理想。该文鉴于图像的局部空间信息和非局部空间信息的互补性，试图将这两种空间信息同时引入到聚类有效性函数中，构造了融合互补空间信息的目标函数，进而提出了应用于图像分割的基于互补空间信息的多目标进化聚类算法。该算法采用染色体可变长编码策略在进化过程中自动确定图像分割数目，减少了人为干预。自然图像的分割实验表明，该算法不但能在含噪图像上取得较为满意的分割性能，而且适用于多种类型的含噪图像。

图像分割；多目标进化聚类；互补空间信息；局部空间信息

1 引言

在过去的几十年中，学者们提出了很多图像分割方法，主要包括阈值的方法[1,2]、聚类的方法[3,4]、区域的方法[5,6]等等。其中，基于聚类的图像分割方法至今仍是国内外研究的一个热点。基于聚类的图像分割算法一般是根据某一个聚类准则来判别图像中像素的归属，并将具有一致或相似属性的像素聚为一类，因此获得的图像分割结果是在该准则下最优的或接近最优的。基于这一思想的经典聚类算法包括K-均值聚类算法(HCM)和模糊c-均值聚类算法(FCM)等，该类算法简单、快速而且有效，易被广泛应用于多个领域。然而这类方法也存在一些缺陷，例如对初始化条件比较敏感；容易陷入局部最优；聚类数目需要人为指定等。此外，这类算法还具有对噪声敏感和只适应于发现球型聚类等局限性。

不同的聚类准则函数具有不同的特性，可以满足人们的不同需求。在实际应用中，我们往往需要从多个角度来考虑图像分割问题，也就是要在多个聚类准则下取得一个均衡的结果。从数学的角度看，就是将图像分割问题转换为对多个目标函数的最优化问题。进化算法作为一种群体智能搜索方法十分适合用来求解多目标优化问题。近年来，将基于多目标进化的聚类算法(多目标进化聚类)应用于图像分割问题已经成为一个新的研究热点[7,8]。该类算法可以同时优化多个目标函数，使得算法获得的分割结果更能符合人们的预期。与基于单一聚类准则的聚类算法相比，这类算法几乎不再对初始化敏感且不易陷入局部最优，此外，该类算法通过选取适当的染色体编码策略和目标函数可以实现分割数目的自动确定，减少了人为干预。

多目标进化聚类算法最初的工作是围绕硬聚类算法展开的[9,10]。随后，文献[11]于2006年在模糊聚类算法的框架下，同时优化总体偏差和连通性函数这两个目标函数。由于该算法是在模糊聚类算法的框架下提出的，因此可以处理重叠和含噪数据的聚类问题，例如图像分割问题。同样在模糊聚类的框架下，文献[12,13]以FCM错误率函数Jm和Xie-Beni(XB)指数作为目标函数也提出了相应的多目标进化聚类算法。值得注意的是，这两个聚类有效性函数不是完全独立的。为此，文献[14]在XB和Jm的基础上引入PBM指标[15]，同时优化这3个聚类有效性函数，并通过对非支配解进行集成获得最终解。此外，2011年，文献[16]采用模糊紧致性和模糊可分性这两个完全独立的模糊聚类有效性函数作为目标函数进行多目标优化，取得了不错的聚类效果。这些多目标进化聚类算法已经被成功应用于图像分割问题。

鉴于图像是具有典型空间信息的数据，聚类算法用于图像分割时，像素的空间信息对于像素聚类具有一定的指导作用。相关学者已经把图像的邻域空间信息(又称为局部空间信息)引入到模糊聚类算法[17,18]中，在一定程度上克服了噪声对于图像分割结果的影响。实际上，对于每一个像素而言，图像中存在很多像素与它具有相似的邻域结构。与局部空间信息相比，利用和当前像素具有相似邻域结构的像素来获得空间信息显然是更合理的，这种空间信息被称之为非局部空间信息。我们在前期的工作[19,20]中已经将图像像素的非局部空间信息引入到模糊聚类算法中，该类算法不但可以克服图像噪声对于分割结果的影响，而且可以获得更加准确的图像边缘，获得的分割效果要优于结合局部空间信息的模糊聚类算法。然而，每种空间信息都有局限性。非局部空间信息是在加性噪声模型下提取的，所以融合非局部空间信息的模糊聚类算法在被加性噪声污染的图像上能够取得较好的分割效果，但在被椒盐噪声污染的图像上的性能不是很理想。局部空间信息按照采用邻域均值或邻域中值又分为两种，其中融合邻域中值空间信息的模糊聚类算法能在被椒盐噪声污染的图像上能够取得较好的分割效果。然而，由于局部空间信息仅仅考虑了像素的局部邻域，使得融合局部空间信息的模糊聚类算法在图像边缘保持上的性能不好。

现有的多目标进化聚类算法用于图像分割时，采用的目标函数都是模糊数学意义下的聚类有效性函数，并没有考虑图像的空间信息。鉴于局部空间信息和非局部空间信息的互补性，本文试图将这两种空间信息同时引入到模糊聚类有效性函数中，构造了融合互补空间信息的目标函数。然后基于该目标函数，再结合其他的模糊聚类有效性函数构成多个目标函数，最后采用NSGA-II算法[21]作为多目标框架来解决多个目标函数的优化问题，提出了应用于图像分割的多目标进化聚类算法。此外，为了减少人为干预，本文算法在进化过程中采用染色体可变长编码策略自动确定分割数目。实验结果表明，本文算法不但可以克服传统多目标进化聚类算法在含噪图像上分割效果不理想的问题，而且适用于多种类型的含噪图像。

2 基于互补空间信息的多目标进化聚类算法

2.1 染色体表示和种群初始化

本文算法对各个聚类中心进行编码，编码方式采用十进制编码。如果一个染色体是由d维数据空间中的K个聚类中心所组成，那么该染色体的长度为d×K。例如，在3维数据空间中，染色体＜24.6 2.3 11.8 13.2 7.9 2.8 0.5 6.1 13.2＞表示3个聚类中心(24.6, 2.3, 11.8), (13.2, 7.9, 2.8)和(0.5, 6.1, 13.2)。

假设种群中的一个染色体i是由Ki个聚类中心组成，Ki=(rand( )mod(Kmax-1))+2，其中，rand( )是返回随机整数的函数，Kmax是聚类数目的最大上界。因此，聚类的数目在2到Kmax之间取值。

2.2 适应度函数计算

本文算法采用两个适应度函数，一个是融合空间信息的全局模糊紧致性函数Cs，另一个是模糊可分性函数S。假设X={x1,x2,…,xn}表示一幅具有n个像素的图像，全局模糊紧致性函数Cs定义如下：

其中，δi和ϑi分别表示第i个像素的局部空间信息和非局部空间信息，β1和β2分别是控制这两种空间信息作用的加权因子，v1, v2,…, vK是从给定染色体中抽取出来的K个聚类中心，uki表示第i个像素对第k类的隶属度，采用式(2)计算：

在式(1)中，第i个像素的局部空间信息iδ是利用该像素的邻域中值获得的，即

其中，Si表示以第i个像素为中心的邻域窗内像素的集合。第i个像素的非局部空间信息iϑ采用式(4)计算：

其中，g(Ni)表示以第i个像素为中心、大小为s×s的相似窗Ni上的灰度向量，h是滤波程度参数，用来控制权值函数wij衰减程度，iz是归一化常数，具体定义为从式(5)可以看出，在搜索窗内，与第i个像素具有相似邻域结构的像素具有较大的权值。综合式(4)和式(5)可以发现，第i个像素的非局部空间信息ϑi是对所有与其具有相似邻域结构的像素进行加权平均获得的。

模糊可分性函数S定义为

其中pqμ是聚类中心vq对于vp的隶属程度，具体定义为

2.3 选择、交叉和变异算子

选择就是挑选染色体产生交配池的过程。本文采用拥挤二进制锦标赛选择方法[21]产生染色体的交配池，需指出，该方法是由传统的二进制锦标赛选择方法与拥挤比较技术相结合得到的。

在染色体中，每个聚类中心都是不可分割的，所以交叉点只能位于两个聚类中心之间。这里，以交叉概率pc对染色体进行交叉操作[16]，并需要保证后代中聚类中心的数目至少为两个。在本文中，如果一个后代染色体P的聚类数目大于Kmax，就采用K-均值聚类算法对染色体P的聚类中心进行聚类，聚类数目是2到Kmax之间的一个随机整数。

本文以变异概率pm对染色体进行变异操作。如果要对某个染色体的第k个聚类中心vk进行变异，那么vk的第p维的值将会变为vkp±10ξ，其中，ξ为一个[0, 1]上均匀分布的随机数，‘+’或 ‘-’是等概率出现的。

2.4 精英策略

我们在前面已经指出，本文采用NSGA-II算法作为多目标框架来解决聚类问题。众所周知，NSGA-II算法最具特色的部分就是它的精英操作。通过精英操作，父代和子代中的非支配解会遗传到下一代种群中，因此，迄今为止发现的最优解就会被保留下来。

2.5 最优解的选择

本文算法的最后一代将会获得一个非支配解构成的集合，从算法的角度来说，所有的非支配解都是同等重要的。然而，在实际应用中，用户往往只需要一个解。在文献[7]中，作者采用聚类有效性指数I[22]从非支配解集合中选择使得I值越大的解作为最终解。需要指出的是，由于聚类有效性指数I没有考虑任何的图像空间信息，所以它无法直接应用于含噪图像分割。为了解决这个问题，我们把局部空间信息和非局部空间信息同时引入到指数I中，提出融合互补空间信息的聚类有效性指数IS，用于从算法最终获得的非支配解集合中选择一个最优解。指数IS定义为

其中，l=1，从式(10)可以发现，聚类有效性指数IS是由1/K, ES1/ESK和DSK3部分所构成，其中，ES1对于给定的数据集来说是一个常数，ESK的定义为

式中隶属度uki采用式(2)计算，iδ和iϑ分别表示第i个像素的局部空间信息和非局部空间信息，1β和2β分别是控制这两种空间信息作用的加权因子。式(8)中DSK度量了所有可能的聚类对的最大可分性，其定义为

3 实验结果与分析

3.1 实验设置及说明

实验中采用FCM，融合邻域均值空间信息的模糊c-均值聚类算法(FCM-S1)[17]，融合邻域中值空间信息的模糊c-均值聚类算法(FCM-S2)[17]，融合非局部空间信息的模糊c-均值聚类算法(FCM_NLS)[20]和多目标可变长遗传模糊聚类算法(MOVGA)[16]作为对比算法。鉴于这些算法都是聚类算法，采用聚类准确率(CA)[23]作为算法分割性能的评价指标。对各算法涉及的参数作如下说明：所有算法的模糊指数m=2；FCM, FCM-S1, FCM-S2和FCM-NLS算法的最大迭代次数T和算法结束阈值ε分别设置为300和10-5，本文算法和MOVGA算法的最大代数和种群规模分别设置为100和50，交叉和变异概率分别设置为0.9和0.1; FCM-S1, FCM-S2和 FCM-NLS算法的加权因子β设置为6；FCM-S1，FCM-S2和本文算法提取邻域空间信息的邻域窗大小设置为3×3, FCM-NLS和本文算法提取非局部空间信息的参数r, s和h分别设置为21, 7和30。需要指出的是，本文算法和MOVGA算法能自动确定聚类数目，其他算法的聚类数目是按照图像的人工分割结果预先给定的。在实验中，聚类数目的最大上界Kmax取值为10。

3.2 加权因子β1和β2的讨论

从式(1)和式(11)可以看出，加权因子1β和2β控制了两种空间信息作用的大小。直观看来，1β取值大一点，会使得邻域中值空间信息发挥较大的作用，从而使得算法对于被椒盐噪声污染的图像的分割效果要好一些；2β取值大一点，会使得非局部空间信息发挥较大的作用，从而使得算法对于被高斯噪声污染的图像的分割效果要好一些。图1(a)给出了一幅人工合成图像，我们分别在这幅图像上添加高斯噪声((0, 0.02))、椒盐噪声((0, 0.03))以及由高斯和椒盐混合而成的噪声(高斯(0, 0.01) &椒盐(0, 0.01))，噪声图像见图1(b)～图1(d)，试图在不同类型的含噪图像上考察1β和2β的取值策略。实验中，我们在集合[0.5, 1, 1.5, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20]上测试1β和2β，图2给出了本文算法的聚类准确率随这两个参数变化的曲面，其中，图2(a)～图2(c)分别为在高斯含噪图像、椒盐含噪图像和混合含噪图像上的性能曲面。从图2(a)可以发现，对于高斯含噪图像，当2β取值比较大时，算法性能较好，此时1β的取值对算法性能影响不大；从图2(b)中的曲面可以看出，对于椒盐含噪图像，当1β取值比较大且2β的取值比较小时，算法性能较好；从图2 (c)可以发现，对于混合含噪图像，当1β和2β取值都比较大时，算法性能较好。

3.3 Berkeley图像对比实验

本节采用多幅来自于Berkeley图像库的图像进行分割实验。为了验证本文算法及其对比算法对于不同类型含噪图像的分割性能，我们在这些图像上分别添加高斯噪声、椒盐噪声以及由高斯和椒盐混合而成的噪声，表1给出了各个算法在含噪图像上获得的聚类准确率。需要指出的是，根据3.2节给出的本文算法加权因子1β和2β的取值建议，对于高斯含噪图像，这里我们把1β和2β分别赋值为6和16；对于椒盐含噪图像，1β和2β分别赋值为16和1；对于混合含噪图像，1β和2β分别赋值为16和16。从表1可以看出，考虑了空间信息的各算法的分割性能一般都要优于没有考虑空间信息的算法，本文算法在绝大多数情况下的分割性能都是所有算法中最好的，适用于多种类型的含噪图像。需指出，MOVGA算法的分割性能在多数情况下都不理想，这是因为该算法没有利用任何的图像空间信息，从而造成进化获得的分割数目不正确，这一点可以从下面将要展示的视觉分割结果中得到验证。

图1 人工合成图像及其噪声图像

图2 算法聚类准确率随1β和2β变化的曲面

表1 各个算法的性能比较

下面以一幅Berkeley图像(#238011)为例展示一下本文算法及其对比算法的视觉分割效果。#238011图像及其标准人工分割结果见图3(a)和图3(b)，该幅图像的高斯、椒盐以及由高斯和椒盐混合而成的噪声图像分别如图3(c)～图3(e)所示。

图3 #238011图像

对于#238011图像，图4给出了本文算法及其对比算法在其高斯含噪图像上的分割结果，图5给出了这些算法在其椒盐含噪图像上的分割结果，图6给出了这些算法在其混合含噪图像上的分割结果。从结果可以看出，对于高斯和混合含噪图像，本文算法获得的视觉效果比较理想，获得的分割图像中含有较少的错误分割点，其它算法的视觉效果均不理想；对于椒盐含噪图像，本文算法获得的视觉效果要明显优于其它算法，虽然MOVGA算法获得了正确的分割数目，但是结果中仍残留了大量的错误分割点。

图4 #238011图像的高斯含噪图像的分割结果

图5 #238011图像的椒盐含噪图像的分割结果

图6 #238011图像的混合含噪图像的分割结果

4 结束语

为了解决多目标进化聚类算法用于含噪图像分割时性能不理想的问题，本文基于图像的局部空间信息和非局部空间信息的互补性，同时将这两种空间信息引入到模糊聚类有效性函数中，构造了融合互补空间信息的目标函数，提出了基于互补空间信息的多目标进化聚类图像分割算法。图像分割实验表明，该算法能在含噪图像上取得较为令人满意的分割性能，而且适用于多种类型的含噪图像。

本文算法需要给定控制互补的两种空间信息作用的加权因子β1和β2。我们在实验中考察了β1和β2的取值，讨论了对于不同类型的含噪图像这两个参数的取值策略。需指出，如果能够利用噪声图像的特点，自适应地确定β1和β2将是一个有意义的研究内容，我们会在未来开展这一工作。

[1] Dirami A, Hammouche K, Diaf M, et al.. Fast multilevel thresholding for image segmentation through a multiphase level set method[J]. Signal Processing, 2013, 93(1): 139-153.

[2] 范朝冬, 欧阳红林, 张英杰. 基于小概率策略的Otsu图像分割方法[J]. 电子与信息学报, 2013, 35(9): 2081-2087.

Fan Chao-dong, Ouyang Hong-lin, and Zhang Ying-jie. Small probability strategy based Otsu thresholding method for image segmentation[J]. Journal of Electronics & Information Technology, 2013, 35(9): 2081-2087.

[3] Gong Mao-guo, Liang Yan, Shi Jiao, et al.. Fuzzy c-means clustering with local information and kernel metric for image segmentation[J]. IEEE Transactions on Image Processing, 2013, 22(2): 573-584.

[4] Caldairoua B, Passata N, Habas P A, et al.. A non-local fuzzy segmentation method: application to brain MRI[J]. Pattern Recognition, 2011, 44(9): 1916-1927.

[5] Tarabalka Y, Chanussot J, and Benediktsson J A. Segmentation and classification of hyperspectral images using watershed transformation[J]. Pattern Recognition, 2010, 43(7): 2367-2379.

[6] 黄志坚, 黎湘, 徐帆江. 基于视觉复杂度的自适应尺度遥感影像分割[J]. 电子与信息学报, 2013, 35(8): 1786-1792.

Huang Zhi-jian, Li Xiang, and Xu Fan-jiang. An adaptive scale segmentation for remote sensing image based-on visual complexity[J]. Journal of Electronics & Information Technology, 2013, 35(8): 1786-1792.

[7] Wei B C and Mandava R. Multiobjective optimization approaches in image segmentation–the directions and challenges[J]. International Journal of Advances in Soft Computing and Its Applications, 2010, 2(1): 40-65.

[8] Ooi W S and Lim C P. Multi-objective image segmentation with an interactive evolutionary computation approach[J]. Journal of Intelligent and Fuzzy Systems, 2013, 24(2): 239-249.

[9] Bandyopadhyay S and Maulik U. An evolutionary technique based on k-means algorithm for optimal clustering in RN[J]. Information Sciences, 2002, 146(1/2/3/4): 221-237.

[10] Caballero R, Laguna M, Marti R, et al.. Multiobjective clustering with metaheuristic optimization technology[R]. Technical Report of Leeds School of Business in the University of Colorado at Boulder, 2006.

[11] Handl J and Knowles J. An evolutionary approach to multiobjective clustering[J]. IEEE Transactions on Evolutionary Computation, 2006, 11(1): 56-76.

[12] Bandyopadhyay S, Maulik U, and Mukhopadhyay A. Multiobjective genetic clustering for pixel classification in remote sensing imagery[J]. IEEE Transactions on Geoscience and Remote Sensing, 2007, 45(5): 1506-1511.

[13] Mukhopadhyay A, Bandyopadhyay S, and Maulik U. Clustering using multiobjective genetic algorithm and its application to image segmentation[C]. Proceedings of the International Conference on IEEE Systems, Man and Cybernetics, Taibei, 2006: 2678-2683.

[14] Mukhopadhyay A, Maulik U, and Bandyopadhyay S. Multiobjective genetic clustering with ensemble among Pareto front solutions: application to MRI brain image segmentation[C]. Proceedings of the International Conference on Advances in Pattern Recognition, Kolkata, India, 2009: 236-239.

[15] Pakhira M, Bandyopadhyay S, and Maulik U. Validity index for crisp and fuzzy clusters[J]. Pattern Recognition, 2004, 37(3): 487-501.

[16] Mukhopadhyay A and Maulik U. A multiobjective approach to MR brain image segmentation[J]. Applied Soft Computing, 2011, 11(1): 872-880.

[17] Chen S C and Zhang D Q. Robust image segmentation using FCM with spatial constraints based on new kernel-induced distance measure[J]. IEEE Transactions on System, Man, and Cybernetics, Part B: Cybernetics, 2004, 34(4): 1907-1916.

[18] Cai W L, Chen S C, and Zhang D Q. Fast and robust fuzzy c-means clustering algorithms incorporating local information for image segmentation[J]. Pattern Recognition, 2007, 40(7): 825-838.

[19] Zhao F, Jiao L C, Liu H Q, et al.. A novel fuzzy clustering algorithm with non local adaptive spatial constraint for image segmentation[J]. Signal Processing, 2011, 91(4): 988-999.

[20] Zhao F, Jiao L C, and Liu H Q. Fuzzy c-means clustering with non local spatial information for noisy image segmentation[J]. Frontiers of Computer Science in China, 2011, 5(1): 45-56.

[21] Deb K, Agrawal S, Pratab A, et al.. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[C]. Proceedings of the Parallel Problem Solving from Nature VI Conference, Springer, Lecture Notes in Computer Science No.1917, Paris, France, 2000: 849-858.

[22] Maulik U and Bandyopadhyay S. Performance evaluation of some clustering algorithms and validity indices[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(12): 1650-1654.

[23] Wu M and Schölkopf B. A local learning approach for clustering[C]. Advances in Neural Information Processing Systems, Vancouver B.C., Canada, 2007: 1529-1536.

赵 凤： 女，1980年生，副教授，研究方向为模式识别、图像处理、模糊信息处理.

刘汉强： 男，1981年生，讲师，研究方向为模式识别、图像处理.

范九伦： 男，1964年生，教授，研究方向为模糊集理论、模式识别、信息安全.

Multi-objective Evolutionary Clustering with Complementary Spatial Information for Image Segmentation

Zhao Feng①Liu Han-qiang②Fan Jiu-lun①

①(School of Telecommunications and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710061, China)
②(School of Computer Science, Shaanxi Normal University, Xi’an 710062, China)

When existing multi-objective evolutionary clustering algorithms is applied to image segmentation, it can not obtain satisfactory segmentation performance on an image corrupted by noise due to no consideration of any spatial information derived from the image. Based on the complementarity of the local spatial information and the non local spatial information of the image, these two kinds of spatial information are introduced into a cluster validity function, and a novel objective function with complementary spatial information is constructed, and then a multi-objective evolutionary clustering algorithm with complementary spatial information for image segmentation is proposed. In order to reduce human intervention, the variable string length real coded technique is adopted to determine automatically the number of clusters during the evolving process. Natural image segmentation experiments show that the proposed method not only can obtain satisfactory segmentation performance on noisy images, but also can be suitable for many types of noisy images.

Image segmentation; Multi-objective evolutionary clustering; Complementary spatial information; Local spatial information

TP751

A

1009-5896(2015)03-0672-07

10.11999/JEIT140371

2014-03-19收到，2014-07-18改回

国家自然科学基金(61102095, 61202153, 61340040)，陕西省科技计划(2014KJXX-72)和陕西省自然科学基础研究计划(2012JQ8045, 2014JQ8336, 2014JM8307, 2013JM3081) 资助课题

*通信作者：赵凤 fzhao.xupt@gmail.com