控制与决策  2020, Vol. 35 Issue (10): 2345-2362  
0

引用本文 [复制中英文]

兰蓉, 赵强. 双中心组合迭代抑制式模糊C-均值聚类图像分割算法[J]. 控制与决策, 2020, 35(10): 2345-2362.
[复制中文]
LAN Rong, ZHAO Qiang. Suppressed fuzzy C-means clustering image seg mentation algorithm based on combined iteration with double centers[J]. Control and Decision, 2020, 35(10): 2345-2362. DOI: 10.13195/j.kzyjc.2019.0034.
[复制英文]

基金项目

国家自然科学基金项目(61571361, 61671377);西安邮电大学西邮新星团队计划项目(xyt2016-01)

作者简介

兰蓉(1977-), 女, 副教授, 博士, 从事模式识别和图像处理等研究, E-mail: ronglanlogic@163.com;
赵强(1993-), 男, 硕士生, 从事模式识别与图像分割的研究, E-mail: qiangzhaoaca@163.com

通讯作者

兰蓉, E-mail: ronglanlogic@163.com

文章历史

收稿日期:2019-01-07
修回日期:2019-03-05
双中心组合迭代抑制式模糊C-均值聚类图像分割算法
兰蓉 , 赵强     
西安邮电大学 通信与信息工程学院,西安 710121
摘要:针对抑制式模糊C-均值聚类算法应用于灰度图像分割时出现收敛速度较慢和像素误判的问题, 通过挖掘图像同质区域内像素间的相关性与分析像素位置对类别判定的影响, 提出一种双中心组合迭代抑制式模糊C-均值聚类图像分割算法.首先在图像上经选点、扩展、提取等环节优选出较好的初始聚类中心; 然后按该中心分别查找图像中灰度值与其相等的像素位置并遴选产生隐藏中心; 其次采用负指数函数对像素位置与隐藏中心之间的欧氏距离进行归一化, 得到位置特征; 接着在对该特征赋权后直接修正模糊划分矩阵; 最后结合抑制式思想进一步减少算法的迭代次数.与现有的多种相关算法进行对比, 实验结果表明, 所提出算法在获得致密且分离性较好聚类的同时, 能够改善图像分割的准确率和执行效率.
关键词抑制式模糊C-均值聚类    图像分割    双中心组合迭代    初始聚类中心    隐藏中心    
Suppressed fuzzy C-means clustering image seg mentation algorithm based on combined iteration with double centers
LAN Rong , ZHAO Qiang     
School of Communications and Information Engineering, Xi'an University of Posts & Telecommunications, Xi'an 710121, China
Abstract: Aiming at the problems of slow convergence speed and pixel misjudgment when a suppressed fuzzy C-means clustering algorithm is applied to gray image segmentation, the suppressed fuzzy C-means clustering image segmentation algorithm based on combined iteration with double centers is proposed via excavating the correlation between pixels in the homogeneous region of an image and analyzing the effect of pixel position on the category judgement. Firstly, by the three steps, i.e., selecting, expanding and extracting, the initial clustering centers are chosen from the pixels in an image. Then, for every initial clustering center, the pixels whose gray values are equal to that of the clustering center are searched in the image, and the hidden centers can be captured by filtering. Then, position features are calculated by the normalization of the Euclidean distance between the pixel positions and hidden centers by using a negative exponential function. Moreover, the fuzzy partition matrix is directly modified after the position features are weighted. Finally, in order to reduce the number of iteration further, the idea of the suppressed fuzzy C-means clustering algorithm is added. Experimental results show that the proposed algorithm can obtain dense and well-separated clustering in comparison with several existing algorithms, which improves accuracy and effectiveness in image segmentation.
Keywords: suppressed fuzzy C-means clustering    image segmentation    combined iteration with double centers    initial clustering centers    hidden centers    
0 引言

图像处理是一种利用计算机技术替代人类理解和感知图像的重要手段, 而图像分割则是将图像分解为特征区域并提取感兴趣目标的技术和过程, 是图像分析、识别和理解的基础[1].在各类分割方法中, 基于模糊C-均值(fuzzy C-means, FCM)聚类的图像分割算法因以软划分的方式刻画像素点与聚类中心的隶属关系而受到国内外众多专家的关注和研究.然而, 传统的FCM算法应用于图像分割时, 由于没有考虑图像的空间信息, 使得算法对噪声较为敏感, 无法对含噪图像获得满意的分割结果[2].此外, 该算法的另一个缺点是收敛速度慢[3]且聚类结果不够紧致.

针对上述问题, 国内外学者提出了一系列改进算法.为了改善FCM算法的抗噪性能, Ahmed等[4]通过在FCM的目标函数中添加局部空间惩罚项平滑像素的邻域, 从而有效去除噪声, 但该惩罚项在迭代过程中需重复计算, 导致算法的执行时间较长; Chen等[5]提出了简化空间限制项的模糊C-均值聚类算法, 通过选取像素局部空间的均值或中值, 并在迭代过程之前优先计算来替代惩罚项, 从而有效减少运算量.但图像的像素数目远比灰度级数目要多, 为了进一步加快分割速率, Szilagyi等[6]提出增强型模糊C-均值(enhanced fuzzy C-means, EnFCM)聚类算法, 定义了线性加权图替代原始图像, 并在该图的灰度直方图上进行聚类.为了进一步提升算法的抗噪性能, Zhao等[7-8]由像素间邻域窗的相似性比较引入非局部空间信息及改进算法, 有更好的去噪效果, 但算法的执行时间较长.

此外, 为了提高FCM算法的收敛速度, Fan等[9]采用竞争学习的思想, 提出抑制式模糊C-均值(suppressed fuzzy C-means, SFCM)聚类算法, 能够快速获取到类内紧致且类间分离性较好的聚类结果, 但未能解决抑制因子的自适应选取问题.兰蓉等[10]采用模糊补算子[11]生成的犹豫度作为抑制因子指导并修正隶属度, 但算子参数的选取直接影响抑制程度和聚类结果.肖满生等[12]利用样本与聚类中心的关系, 改进了SFCM算法中的抑制因子, 便于在聚类过程中根据样本自身特点进行隶属度的动态修正, 但并未具体阐述算法中阈值的选取方法.兰蓉等[13]重新选用Yager直觉模糊补函数[14]生成直觉模糊集[15]的犹豫度, 并实现了抑制因子的自适应调整, 在获得紧致性较好的聚类结果的同时进一步缩减了迭代次数, 但该算法应用于自然图像分割时, 其准确率相对于SFCM算法并未有明显提升; Chuang等[16]认为, 在图像中, 邻域像素间具有较高的相关性, 从而依次抽取每个像素的邻域隶属度作为局部特征并对其赋予权重修正隶属度, 以达到提高分割准确率的目的.受其启发, Tripathy等[17]将直觉模糊集的犹豫度与上述局部特征相结合, 进一步提高了分割准确率, 但算法的执行时间较长.

为了获得致密且分离性较好的聚类, 同时降低迭代次数、提高图像分割的准确率.本文在文献[9, 17]的基础上提出双中心组合迭代抑制式模糊C-均值聚类图像分割算法(suppressed fuzzy C-means clustering image segmentation algorithm based on combined iteration with double centers, SFCM-CDC), 并将该算法应用于多种不同类型的测试图像, 分别从聚类有效性和分割效果的评价指标、迭代次数和执行时间等方面检验所提出算法的性能和效率.

1 基础理论及相关算法 1.1 模糊集合

定义1 [18]   对于论域U上的集合Ã, 对任意xU都指定一个实数μÃ(x) ∈[0, 1]用于表示x属于Ã的程度, 即映射μÃ:U→[0, 1], 利用μÃ所确定的集合Ã称为U上的一个模糊集合, μÃ称为模糊集合, Ã的隶属度函数.

对于任意xU, μÃ(x)表示元素xÃ的隶属度. μà (x)的值越接近1, 表示x属于Ã的程度越高; μÃ(x)的值越接近0, 表示x属于Ã的程度越低.模糊集合的定义表明, 模糊集合Ã由其隶属度函数μÃ唯一确定.一个模糊集合Ã可以表示为

(1)
1.2 FCM聚类算法及其改进 1.2.1 FCM聚类算法

Bezdek等[19]于1984年提出FCM聚类算法, 描述如下.设X={x1, x2, ..., xn}为数据集, FCM算法采用下式作为目标函数:

(2)

其中: vi为第i个聚类的中心, m∈[1, ∞)为模糊指数; uij为数据点xj对于第i个聚类中心的隶属程度, 需满足

(3)
(4)
(5)

uij(1≤ ic, 1≤ jn)构成的矩阵称为模糊划分矩阵, 记为UF_matrix=(uij)c× n.

运用拉格朗日乘子法求解该极值问题, 对应的迭代过程描述如下.

初始化:设定聚类数目c, 模糊指数m, 迭代中止阈值ε, 最大迭代次数T.

step 1:令迭代次数k=1, 随机初始化聚类中心V(k).

step 2:利用下式计算模糊划分矩阵U(k)F_matrix:

(6)

step 3:利用下式更新聚类中心V(k+1):

(7)

step 4:如果║V(k+1)-V(k)║ < ε或迭代次数k> T, 则停止循环迭代, 否则令k=k+1并返回step 2.

1.2.2 SFCM聚类算法

与硬C-均值(hard C-means, HCM)聚类相比, FCM聚类过程的耗时更高.为提升算法效率, 文献[9]提出SFCM聚类算法, 其主要思想是对每一个样本的最大隶属度进行奖励, 同时抑制其他隶属度, 具体过程如下.

在迭代计算中得到uij时对其作如下修改:对每一个样本xj, 记

(8)

那么有

(9)
(10)

其中0≤ α ≤ 1为抑制因子, 用于调节抑制的程度.当α =0时, SFCM退化为HCM算法; 当α=1时, SFCM即为FCM算法.由此可见, SFCM算法兼取FCM和HCM这两种算法的优势, 既能保证良好的聚类结果, 又能降低算法的迭代次数.然而, 将该算法应用于灰度图像分割时, 由于未对初始聚类中心进行优选, 收敛速度仍然较慢, 且仅按像素的灰度值进行聚类会导致像素误判现象, 从而影响分割结果.

2 SFCM-CDC算法原理与构建 2.1 优选初始聚类中心与生成位置特征

结合高斯混合模型(GMM, Gaussians mixture model)的EM聚类[20]是一种经典的机器学习算法, 其将图像灰度直方图用GMM进行拟合并通过E-step和M-step迭代优化, 得到最佳的估计结果, 即GMM中每个组件的均值、协方差和权重, 再将每个组件的均值作为聚类中心得出分割结果.因此, 该算法的目的是获取图像灰度直方图的峰值并将其作为聚类中心.然而, SFCM聚类算法依然采用随机设定聚类中心的方式进行初始化, 导致算法的收敛速度较慢.为此, 预先获得一个较优的初始聚类中心能够有效降低算法的迭代次数.

2.1.1 基于扩展块优选初始聚类中心

李武等[21]针对K-均值聚类提出一种基于数据空间分布选取初始聚类中心的改进算法.该算法首先定义样本距离、样本平均差异度和样本集总体平均差异度; 然后将每个样本按平均差异度排序, 选择平均差异度较大且与已选聚类中心的差异度大于样本集总体平均差异度的样本作为初始聚类中心.然而, 该算法仅从数据集角度描述了优选过程, 并未涉及应用于具有明显空间位置信息且数据量较大的图像像素时的结果.

为此, 本文通过充分挖掘像素点本身与其邻域间的关系, 并结合区域增长法的思想, 提出一种优选初始聚类中心的方法, 具体步骤如下.

step 1:选点.

设图像I的大小为M× Z, 随机给定该图像中一组像素坐标之集, 有

(11)

其中: dq∈{1, 2, ..., M}, d'q∈{1, 2, ..., Z}.同时, 定义如下映射:

(12)

故∀ wqW, 有

(13)

wq表示图像I中(dq, dq')处像素的灰度值, 需满足如下约束条件:

(14)

其中: w为集合W中元素的均值, T'为选点阈值.

式(14)成立, 即表示集合P中的元素已能够选到待分割图像中每一类的像素位置,这里t为选点个数, 由聚类数c确定.为防止漏选, 选点个数t与聚类数c有如下关系:

(15)

当集合W中的元素满足式(14)时, 该步骤结束, 并得到集合P.

step 2:扩展.

根据P中每个元素在图像I中的位置进行串行扩展, 并设定每个元素的初始扩展参数E=1, 即可得扩展块集合及其内第q个扩展块分别为

(16)
(17)

设定扩展块应满足如下约束条件:

(18)

其中: bq为以(dq, d'q)为中心, 大小为(2Eq+1)×(2Eq+1)的局部邻域扩展块; D(bq)为该扩展块内像素的灰度方差; T''为扩展阈值, 用来保证此环节中的扩展块仅位于同质区域, 且不会越过该区域的边界.同时, 对于B中任意的扩展块bq, 当其满足式(18)时, 令Eq=Eq+1并再次扩展, 否则停止扩展, 最终可得到由t个不同大小扩展块组成的集合B.

step 3:提取.

由于上述步骤所得的每个扩展块均为方阵, 由扩展参数E可知, 最终得到的第q个扩展块的大小为(2Eq+1)× (2Eq+1), 即

(19)

为了后续简单表述, 记size(bq)=2Eq+1.

分别对集合B中每个扩展块内的元素求均值.结合图像的灰度直方图可以发现, 扩展块越大, 其内部像素灰度的均值越靠近直方图峰值所对应的灰度值.这是因为当step 1中的点落在大片的同质区域内时, 对该点经过step 2的处理使得其对应的扩展块迅速增大, 且该扩展块内像素的灰度值分别徘徊在直方图峰值所对应的灰度值附近.进而有

(20)

其中mq为带有扩展块大小标记size(bq)的块bq内像素的灰度均值.为了能够提取到M中最贴近峰值的扩展块均值mopt并将其作为初始聚类中心, 此处将根据聚类数的不同设计不同的提取方法.

1) 聚类数c=2.

首先按灰度均值对集合M中的元素进行归一化处理, 即

(21)

其中L为像素灰度级数.按扩展块大小size(b)对MNor中的元素进行降序处理, 有

(22)

进一步, 为了降低误差, 去除式(22)中最大和最小元素值项, 可得

(23)

其中MM=max (MDes_Nor)∪min (MDes_Nor)为MDes_Nor中最大和最小元素值组成的集合.通过以下函数可分离MDes_Nor中的两类元素:

(24)

其中: Thmax和Thmin分别为M'Des_Nor中的最大和最小元素值; |m1Nor-mqNor|表示集合MDes_Nor中首项与第q项之间的误差.按Jd中的数值对应选取MDes_Nor中的元素, 并构成两个新的集合.最后, 分别选取新集合中带有最大扩展块标记size(b)的灰度均值取整, 并组合作为两类情况下的初始聚类中心.

2) 聚类数c>2.

按灰度均值对式(20)中的元素进行升序处理, 得

(25)

同时, 计算式(25)元素间的误差, 即

(26)

对式(26)的误差进行降序处理, 可得

(27)

选出前c-1个元素作为度量参数para, 有

(28)

在error中查找度量参数para的位置, 并对位置数进行升序处理.按位置数将MAsc分离为c个子集合, 并求取每个子集合中带有最大扩展块标记size(b)的灰度均值取整.最后, 组合上述结果构成初始聚类中心.

经上述步骤可优选出较好的初始聚类中心, 从而达到有效控制算法迭代次数的目的.为了提高图像分割的准确率, 在充分挖掘像素间相关性的同时, 还需考虑像素的空间位置信息.

2.1.2 基于隐藏中心生成位置特征

图 1(a)为一幅人工图像, 对其由左向右依次编号.按照灰度值可以确定1、3、5、6号的值最大; 10、11、12号的值最小.当采用SFCM算法对该人工图像进行聚类分割时, 2号像素会因其灰度值接近7 13号而产生误判从而导致错分, 具体分割结果见图 1(b).

图 1 人工图像与SFCM算法的错分结果

出现上述错分现象的主要原因在于, SFCM算法仅按照像素的灰度值进行聚类分割, 并未考虑像素的空间位置.为此, 再次利用图像I并定义下式:

(29)

其中

(30)

Ar为灰度值与第r个聚类中心相等的像素点的位置集合, Rr, sCr, s分别为第s个像素的行标和列标, c为聚类数.

分别计算Ar内各位置间的欧氏距离, 令至其他位置距离最小的位置为第r个隐藏中心, 即

(31)

其中

Cvr≠ ∅.进一步, 定义图像的像素位置pix如下:

(32)

依次计算每个像素位置与隐藏中心之间的欧氏距离, 并对其进行如下处理:

(33)

其中∀(τ, ς)∈ pix, 有

(34)

式(34)中, 当r'=0时, Ndisτ, ς0=0, NorDis0为零矩阵.式(34)表明, 当(τ, ς)与HidCr在空间位置上距离较大时, 对应的Ndisτ, ςr也较大.

为了降低像素误判, 重新思考图 1(a) 2号像素的分割问题.由于2号像素的灰度值更接近11号像素, 从而需要一个较小值惩罚2号对11号像素灰度值的隶属度; 又需要一个较大值奖励2号对3号像素灰度值的隶属度.因此, 采用负指数函数对矩阵NorDisr作归一化处理, 有

(35)

此时, 矩阵NorDisNIr的大小与NorDisr相同.为了便于将NorDisNIrurj相联系, 按列转换矩阵NorDisNIr为行向量NorDisNIRowr, 大小为1× n, 这里n=M×Z.

最后, 按行组合多个NorDisNIRow, 得到位置特征为

(36)
2.2 SFCM-CDC算法

相较于SFCM算法, 本文提出的SFCM-CDC聚类图像分割算法将融入优选的初始聚类中心和位置特征, 以保证既能降低算法的迭代次数, 又能提高图像分割的准确率, 具体表述如下.

在FCM算法的step 1中, 用优选的初始聚类中心取代传统的随机方法, 并在step 2与step 3之间加入下述步骤.

step 2*:采用第2.1.2节的方法生成像素的位置特征Dij, 其中ji分别指代第j个像素的空间位置和第i个聚类中心对应的隐藏中心.

step 2**:计算新的模糊划分矩阵

(37)

其中φψ分别为模糊划分矩阵和位置特征的指数权值.对u'ij采用SFCM算法的抑制过程, 即式(8)~(10), 得到u''ij, 最后置uij=u''ij.

3 实验结果及分析

为了验证本文提出的双中心组合迭代抑制式模糊C-均值聚类图像分割算法的有效性, 从3个方面分别检验并分析该算法的性能.实验环境: Windows 7, Intel Core i5-2450M, 8 G RAM, Matlab R2014a.

3.1 优选初始聚类中心及位置特征的实验分析 3.1.1 优选初始聚类中心的有效性

设定7组实验, 其中选点阈值T'=3 500, 扩展阈值T''=4均由大量实验确定.将算法的输出结果与灰度直方图的峰值进行比较, 若两者误差越小, 则表明优选的初始聚类中心越有效.同时对比文献[21]基于平均差异度的优选初始聚类中心算法的结果及耗时情况.

图 2为测试图像及其灰度直方图.由于本文提出的扩展块以优选初始聚类中心在选点的初始阶段是随机的, 表 1分别列出文献[21]的初始聚类中心优选结果, 本文算法5次提取聚类中心的测试结果及灰度直方图的峰值, 同时也对比了文献[21]与本文算法的耗时情况, 现对表中结果作如下分析.

图 2 测试图像及其灰度直方图
表 1 优选初始聚类中心的有效性以及耗时比较

测试图像图 2(a)图 2(c)图 2(g)所对应的优选结果不够准确, 这是由于在上述图像直方图的每个灰度值区间内, 像素的个数近乎相等, 且均未服从高斯分布, 而经优选方法处理后的结果能够较为准确地选到灰度区间的中间值.如图 2(a)图 2(c)图 2(g)的第1个灰度区间均为0 20, 算法的优选结果均落在10的附近, 而图 2(e)图 2(i)对应的优选结果则更准确. 表 1图 2(k)图 2(m)对应优选的结果也较为准确, 这表明本文算法对于提取自然图像的初始聚类中心也是有效的.但是, 文献[21]的算法对图 2(g)图像是失效的, 这是由于样本集总体平均差异度较大而丢失了一个聚类中心.

表 1中最后两列为两种算法的耗时情况对比.显然, 本文算法能够迅速地获得图像灰度直方图的峰值, 而文献[21]在计算平均差异度和样本集总体平均差异度时则需要耗费更长时间, 尤其在对自然图像提取初始聚类中心时更为明显.

下面, 通过具体图像对本文提出的基于扩展块优选初始聚类中心的过程进行解释和说明.由于实验数据量较大, 仅选用图 2(m)为例, 单独列出该图像一次随机测试的选点、扩展、提取的具体数据, 结果见表 2. 表 2的第7列为该图像最贴近峰值的扩展块均值mopt的判定结果.

表 2 图 2(m)优选初始聚类中心过程的数值列表

表 2中, 第1列为选点环节的选点个数, 由式(15)可知t=15;第2、第3列分别为在约束条件(14)下的选点坐标; 第4列为点的灰度值; 第5、第6列分别为扩展环节所得的各扩展块大小及其灰度均值.对照图 2(m)可见, 扩展块越大则越贴近灰度直方图的峰值, 因此该图像的mopt分别为q=8、9、14时的mq, 而经过第2.1.1节提取环节对整个15组数据的mq的处理, 可有效提取mopt, 并令其为初始聚类中心.

综上所述, 虽然受经验阈值的影响, 但本文算法能够快速有效地获得更好的初始聚类中心, 从而为SFCM-CDC算法的后期迭代提供较好的初始条件.

3.1.2 位置特征的提取及其对模糊划分矩阵的影响

仅以像素灰度值进行聚类的SFCM算法的像素误判示例结果如图 1(b)所示, 而本文提出的基于隐藏中心生成位置特征的算法能够提取像素的空间位置特征, 并用其修正模糊划分矩阵, 进而减小像素误判率, 提高分割准确率.由于真实图像的尺寸较大, 难以展示整幅图像聚类过程中的数据, 本节采用图 1(a)中的人工图像验证并分析本文算法对该图像像素模糊划分矩阵的影响, 实验过程及数据如图 3所示.

图 3 位置特征提取及其对模糊划分矩阵修改的过程

图 3(a)图 1(a)中各像素的灰度值. 图 3(b)图 3(c)分别为以215和20为初始聚类中心的隐藏中心提取过程.以图 3(b)为例, A1囊括了该图像中像素灰度值等于聚类中心的所有像素位置, 此处有4对预选隐藏中心, 分别计算其间的欧氏距离, 并将所得矩阵按列求和, 最后通过式(31)的计算列出可选为隐藏中心HidC1的位置集合Cv1. 图 3(c)的过程与图 3(b)相似.由此, 可获得该图像两个类别的隐藏中心. 图 3(d)为上述图像的原始模糊划分矩阵, 第1行和第2行分别为每个像素的灰度值对以215和20为聚类中心的隶属度, 显然2号像素的类别划分出现了误判, 图 3(e)的第1行和第2行分别表示各像素位置与隐藏中心(1, 3)和(1, 11)间的欧氏距离.通过式(33)和(34)的计算可得到图 3(f)中的NorDis, 该处理能够进一步扩大隐藏中心与其他像素位置之间距离的分散度, 降低算法陷入局部最优的可能性.采用式(35)对上述结果进行负指数变换及归一化处理, 得到位置特征D图 3(g)所示.按式(37)生成新的模糊划分矩阵, 其结果为图 3(h).

通过对比图 3(d)图 3(h)可见, 2号像素的隶属度发生了较大变化.通过修正, 本文算法不仅能够将误判像素的隶属度变得模糊, 而且除了隐藏中心位置中间的部分像素(如7、8号像素)外, 其他像素的隶属度均变得更为分明.

3.2 图像分割结果比对

为客观分析算法的分割性能, 本节分4个部分进行介绍.首先介绍对比算法及其相关参数, 同时选定具体的评价指标; 其次, 选择一幅图像的部分像素作为参考, 具体分析FCM、SFCM与SFCM-CDC算法的聚类分割过程; 接着, 由于经典图像与合成孔径雷达(synthetic aperture radar, SAR)图像均无Ground_Truth, 对这两种图像通过视觉效果和聚类指标验证算法的性能; 最后, 采用Berkeley BSD500库[22]中的图像及其提供的Ground_Truth, 结合聚类指标以及分割指标测试算法对自然图像的分割性能.

3.2.1 对比算法及相关参数与性能指标

传统的FCM算法和Xu等[23]提出的直觉模糊C-均值(intuitionistic fuzzy C-means, IFCM)聚类算法均属于经典算法, 其中IFCM利用Sugeno算子[24]将图像的灰度值转化为直觉模糊集并对其进行聚类, 参数λIFCM=0.7.文献[12]提出的抑制式模糊C均值聚类惩罚因子的改进(improvement of penalty factor in suppressed fuzzy C-means clustering, IPSFCM)与文献[13]提出的基于犹豫度生成的抑制式FCM图像分割算法(suppressed FCM image segmentation algorithm based on the generated hesitation, SFCMH)均对SFCM算法进行了改进, 其中SFCM的抑制因子α=0.5, IPSFCM中参数σIPSFCM=0.01, SFCMH中参数λSFCMH=0.9.文献[17]提出的空间直觉模糊C-均值聚类的图像分割(image segmentation using spatial intuitionistic fuzzy C means clustering, SIFCM)算法利用局部空间中的隶属度信息与直觉模糊集的犹豫度构建特征项并修正隶属度, 其参数分别为pSIFCM=1, qSIFCM=2, λSIFCM=0.5.本文提出的SFCM-CDC算法中, 参数设定为:选点阈值T'=3 500, 扩展阈值T''=4, 隶属度指数权值φ=1, 位置特征指数权值ψ=2, 抑制部分与SFCM算法设定相同, 即α=0.5.

划分系数(partition coefficient, PC)[25]与划分熵(partition entropy, PE)[26]是两种常用的模糊聚类有效性的评价指标, 定义如下:

(38)
(39)

其中: uij为样本xj对第i类的隶属度; PC值越大且PE值越小, 表明算法的聚类性能越优良.

Davies-Bouldin(DB)与Dunn(DU)指标[27]为两种硬聚类的有效性评价指标.由于聚类算法最终得到的结果是分明的, 用上述指标能够测试聚类结果的类间分离性和类内紧致性, 定义为

(40)
(41)

其中: σω为聚类中心vω与其类内元素间的平均距离; dis(vω, vϖ)为聚类中心vωvϖ间的距离; c为聚类数目; DU值越大且DB值越小, 表示结果为类内致密且类间分散程度越好的聚类.

分割准确率(segmentation accuracy, SA)用来比较图像分割的性能, 定义为

(42)

其中: APω、GTω分别为经某算法处理后图像和Ground_Truth下属于第ω类的像素集; c为聚类数目; SA越接近1表示分割结果越准确.

规范化互信息(normalized mutual information, NMI)[28]定义为

(43)

其中: GTL和APL分别为Ground_Truth和聚类算法处理后的样本类别标签; MI (GTL; APL)为GTL与APL之间的互信息; H(GTL)和H(APL)分别为GTL和APL的熵; NMI越大分割结果越接近Ground_Truth.

3.2.2 单幅图像部分像素的聚类分割过程

为了详细对比经典的FCM、SFCM以及本文提出的SFCM-CDC算法的聚类分割过程, 本节选用Berkeley BSD500库中\3096图像的标记像素进行测试, 这些标记像素(飞机头前部的亮点)在原图中的位置及其灰度值由图 4得到.经过以上3种算法的处理, 分割结果依次示于图 5(a) 图 5(c), 现分别对其过程作如下简述.

图 4 ♯3096图像的标记像素及其灰度值
图 5 3种算法分割结果

对照图 4(b)中标记像素的灰度值与图 5(a)图 5(b)对应位置的分割结果可以看出, FCM与SFCM算法未能对这些像素作出正确的类别划分.这是因为两种算法对聚类中心的初始化是随机的, 并不能在初始阶段得到较准确的类别划分, 所以实验中设定上述两种算法第1次迭代的标记像素与聚类中心的距离及标记像素的模糊划分矩阵相同, 即图 6(a)图 7(a)图 6(c)图 7(c).分别经过40次和20次迭代更新, FCM和SFCM算法逐步收敛, 上述距离和模糊划分矩阵分别列于图 6(b)图 7(b)图 6(d)图 7(d).由图 6(d)可见, 各个标记像素的隶属度均位于0.5的附近, 因此在迭代结束时, 部分标记像素出现误判的情况.与FCM算法结果类似, SFCM算法处理后标记像素的隶属度也距离0.5较近, 但其误判像素的个数更少, 这是由于抑制过程的引入使得模糊隶属度变得分明.同时参考图 5(c)的分割结果可以发现, SFCM-CDC算法能够准确划分标记像素, 并且仅需迭代更新7次即可收敛. 图 8(c)中, 由于SFCM-CDC算法含有优选初始聚类中心环节, 在第1次迭代时每个标记像素的类别划分即是准确的, 而经过第3.1.2节所述的隐藏中心对模糊划分矩阵的引导, 使得标记像素在第7次迭代下的模糊划分矩阵更为分明, 类别判定也更为准确, 结果示于图 8(d)中.

图 6 FCM算法标记像素的聚类过程
图 7 SFCM算法标记像素的聚类过程
图 8 SFCM-CDC标记像素的聚类过程

上述3种算法的聚类数目、模糊性能指标、聚类中心及隐藏中心分别列于表 3.参数对比结果表明, 对于3096图像, SFCM-CDC算法在获得更为紧致的聚类结果和较为准确的分割结果的同时, 其迭代所得的聚类中心也更接近表 1图 2(k)的峰值.由于图像的数据量较大, 在后续图像聚类分割的比较分析中, 将以分割视觉效果、聚类有效性和分割准确率衡量算法对多种不同图像进行分割时的性能.

表 3 3种算法对♯3096图像聚类分割的对比参数
3.2.3 经典图像与SAR图像的分割结果

选用cameraman等常用测试图像衡量算法对经典图像的分割性能; UCMerced-LandUse数据集[29]为美国地质调查局提供的大型图像中手动提取的遥感SAR图像, 像素分辨率为1英尺, 共包含21类, 每类含有100幅256×256像素的图像.由于河流、飞机场和高速公路等图像的内容并不复杂, 分别选用一幅验证算法对SAR图像的分割性能.

图 9(a)第1幅为原始图像, 后7幅分别为7种算法对cameraman图像的分割结果.由图 9(a)可见, FCM、SFCM、SFCMH、IPSFCM算法不能有效抑制地面部分的噪声, 分割效果均不理想, IFCM与SFCM-CDC算法的分割结果相近.虽然SIFCM能去除地面的噪声, 但由于该算法加入了隶属度指导的局部空间信息, 导致分割图像丢失原本的细节信息.对照表 4的定量结果可见, 相较于其他算法, 本文提出的SFCM-CDC算法在PC和DB指标中结果更好, 而在PE和DU指标中并未获得较好的值, 这是由于位置特征对模糊划分矩阵的修正使得原本分明的隶属度变得模糊.

图 9 经典图像与SAR图像经7种算法处理的分割结果

图 9(b) 图 9(d)分别为7种算法对river75、airplane39和freeway19图像的分割结果, 每幅图展示各对比算法的结果次序与图 9(a)一致. 图 9(b) 图 9(d)的第1幅图中, 河岸与河流、中间飞机的右侧机翼与地面、高速公路与车辆的灰度值均相近, 是该组SAR图像分割的几大难点. SFCM-CDC算法能够利用位置特征对模糊划分矩阵进行修正, 从而降低误判, 改善分割效果.

结合表 4中的指标, 与其他算法相比, SFCM-CDC算法在PC、DB、DU中均表现出一定的优势, 而PE指标值较大与上述原因一致.综上所述, SFCM-CDC算法能够实现常用测试图像和SAR图像的有效分割.

表 4 7种算法对经典图像与SAR图像的分割量化结果
3.2.4 Berkeley数据库的分割结果

Berkeley BSD500数据库是加州大学伯克利分校计算机视觉组提供的BSD300的扩展版本, 其目的是为图像分割和边缘检测的研究提供实验条件.该数据库image包中含有test、train、val三个子库, 依次有200、200、100幅彩色图像, 图像大小为481×321或321×481. Ground_Truth包中含上述图像的标准分割类别标签和边缘检测标签, 且每幅图像的Ground_ Truth由多位专家人工标注.

为了测试SFCM-CDC算法对自然图像的分割性能, 此部分选定常用的10幅图像进行测试, 分别为3063、3096、12003、15088、80099、108041、147091、196027、238011、253036. 图 10给出4幅典型图像经7种算法处理后的分割结果, 表 5列出了上述10幅图像的分割量化值, 现对结果作如下分析.

图 10 7种算法对4幅Berkeley典型图像处理的分割结果
表 5 7种算法对4幅Berkeley典型图像处理的分割结果

图 10(a)中第1幅为\3063原始图像, 由于天空与飞机的灰度值差异较小, 难以准确分割.经FCM、SFCM、SFCMH、IPSFCM、IFCM、SIFCM算法处理后的分割结果显示, 上述算法无法对天空部分作出准确判别. IFCM算法仅能对飞机下方的天空作出有效分割, 但上方的天空依然存在误判.由于位置特征的引入, SFCM-CDC算法能够提升天空隶属于背景的程度, 从而将其准确划归为背景.参照表 5中对应的项, 其SA和NMI也更高, 分割结果更有效.

图 10(b)的分割难点类似于图 10(a).通过对比可发现, SFCM-CDC算法分割的结果能够降低左下角天空的误判情况, 但机身边缘保留得较差.这是由于位置特征在降低误判的同时, 因隐藏中心离机身较近而产生了新的误判.

图 10(c)中, 由于牛身的灰度值与浑水相近, 仅按照灰度值进行聚类分割的结果并不理想, 而SFCM-CDC算法能够有效地将牛与浑水进行区分.这是由于在部分浑水像素对应的模糊划分矩阵中, 像素的灰度值对两个聚类中心的隶属度均处于0.5附近, 而通过位置特征的修正和抑制式思想的指导, 能够有效减少误判情况. 表 5所列各算法对图\80099的PE指标表明, 本文算法的聚类结果在类内紧致性与类间分离性方面表现较好.

图 10(d)中, 由于受到光照不均匀的影响, 月亮周边天空区域过亮, 选择恰当的聚类中心至关重要.以Ground_Truth为基准, IPSFCM、SIFCM、SFCM-CDC算法均能够较准确地分割出月亮、天空和树木.进一步考察表 5的评价指标, 除了PC值, SFCM-CDC算法的其他值均略低于SIFCM算法.现对其原因分析如下:对于聚类指标, 即PE、DB和DU, 由于位置特征对模糊划分矩阵的影响, 原本较分明的隶属度变得模糊, 使得聚类结果变得松散, 从而造成最终的PE和DB较大, DU较小; 对于分割指标而言, SFCM-CDC算法的分割结果相比SIFCM更接近于原图, 而Ground_Truth图像的右下角对树木和天空的判定与人眼视觉感知不太相符, 这是因人工设定类别标签时存在的误差所造成的. SIFCM算法中局部空间信息的引入使得分割图像的边缘变得模糊, 从而导致SIFCM更接近于Ground_Truth, 其对应的SA和NMI值也更高.将SFCM-CDC与算法中未带局部空间信息的IPSFCM相比, 前者的SA和NMI均较高.

其余图像分割结果的性能指标值均列于表 5中, 对比表中各指标可发现, 本文提出的SFCM-CDC算法能够有效提高图像分割的准确率, 尤其当图像像素的灰度值对聚类中心的隶属度处于0.5附近时.而一些图像的分割准确率相对较低是因为隐藏中心指导的位置特征在降低误判的同时也引入了新的误判, 选择恰当的模糊划分矩阵和位置特征指数权值能够有效避免上述问题的发生.

综上, 由表 5的统计数据可知, 相比上述其他算法, 本文提出的SFCM-CDC算法在对自然图像进行分割时, 不仅能够获得较好的聚类结果, 而且其分割准确率也有所提高.

3.3 算法效率分析

迭代次数(k)与执行时间(ET)是衡量聚类算法效率的常用指标, 具体计算过程如下.

输入:待分割图像I, 聚类数目c, 模糊指数m, 迭代终止阈值ε, 最大迭代次数T, 初始迭代次数k;

输出:图像分割结果, 模糊划分矩阵UF_matrix, 聚类中心V, 隐藏中心HidC (仅限本文算法), 聚类指标(PC、PE、DB、DU), 分割指标(SA, NMI), 迭代次数k, 执行时间ET.

step 1:不同算法输入各自的相关参数(SFCM-CDC算法的参数:选点阈值T'=3 500, 扩展阈值T'' =4, 隶属度指数权值φ=1, 位置特征指数权值ψ=2, 抑制因子α=0.5).

step 2:tic(记录起始时间).

step 3:SFCM-CDC或其他对比算法.

step 4:toc(记录结束时间).

step 5:利用模糊划分矩阵及聚类中心求解模糊聚类性能指标.

step 6:去模糊化并赋类别标签, 进而求得图像分割性能指标.

由以上算法步骤可知, 迭代次数与执行时间越小, 表明算法效率越高.基于此, 在Berkeley BSD500数据库中选取15幅图像, 具体见表 6左侧第1栏所列.采用多个相关算法分别对上述图像进行分割, 统计每幅图在不同算法下的迭代次数和执行时间.统计各算法上述结果的平均值, 并以直方图的形式呈现在图 11中. FCM和IFCM为经典算法, 具有迭代次数多、执行时间短的特点, 文献[21]为K-均值聚类算法, 本文已在第3.1节具体分析了该算法优选初始聚类中心的准确性和耗时情况, 因此该部分未对上述3种算法的执行效率进行统计.

表 6 5种算法对15幅图像分割的迭代次数和执行时间统计
图 11 对15幅图像分割的平均迭代次数及执行时间

通过对比表 6中各算法的迭代次数, 相较于SFCM算法, 通过修正抑制因子而产生的SFCMH和IPSFCM算法在对多幅图像进行分割时, 其迭代次数明显减少.本文提出的SFCM-CDC算法中含有优选初始聚类中心过程, 能够为算法提供较好的优先条件, 因此SFCM-CDC较SFCM算法拥有更少的迭代次数.由于采用负指数函数归一化的位置特征在对模糊划分矩阵进行修正时, 步长较短, SFCM-CDC算法的迭代次数高于单纯改进抑制因子的算法.综合上述分析可知, 本文算法的迭代次数与SFCMH和IPSFCM相当, 图 11中的平均迭代次数对比即可印证这一点.而SIFCM算法对前述图像具有较好的分割性能, 但并未包含任何优化提速的方法, 因此相较于表中所列的其他算法, 该算法的迭代次数最高.

结合表 6图 11中各算法的执行时间和平均执行时间可以发现, SFCMH算法耗时最短.这是由于犹豫度的介入使得隶属度位于0.5附近的样本能够快速地向其对应的类别偏移, 而SFCM算法则按照固定的抑制因子对隶属度进行修正. IPSFCM算法在迭代过程中还加入了判定隶属度是否需要抑制的过程, 因此当数据量较大时, 执行时间明显更长.本文提出的SFCM-CDC算法的平均执行时间明显高于SFCM和SFCMH算法, 稍高于IPSFCM算法.对比表 6对应的项可以发现, SFCM-CDC算法对\80099和\238011图像的执行时间长达50余秒, 而对其他图像的执行时间与SFCM算法的差距较小.这是因为在上述两幅图像的灰度直方图中, 将其拟合所得的GMM组件的协方差较小, 备选隐藏中心的数目较多, 从而需要耗费大量时间进行确定, 且每次迭代均需重复操作, 导致本文算法的平均执行时间较长. SIFCM算法虽然能够获得较好的分割结果, 但执行时间长, 算法效率明显较低.

4 结论

与传统的SFCM及其改进算法相比, 本文提出的SFCM-CDC聚类图像分割算法能够通过充分挖掘图像像素间的相关性而快速优选出较好的初始聚类中心.同时, 度量每个像素与由聚类中心指导而产生的隐藏中心之间的距离, 并对其进行负指数变换和归一化处理得到位置特征.对该特征赋指数权值后直接修正模糊划分矩阵, 仿真实验和算法性能指标测试结果表明, 所提出的SFCM-CDC聚类图像分割算法不但在初始化阶段能够有效控制迭代次数, 而且聚类结果更为紧致, 且在图像分割时达到了降低误判、提高算法效率和分割准确率的目的.此外, 隐藏中心与位置特征指数权值ψ对分割结果的影响较大, 如何遴选隐藏中心以确保在降低误判的同时能够减少新误判的产生和指数权值参数的自适应是未来应当思考和研究的两大问题.

参考文献
[1]
Liu D L, Ma L, Chen H, et al. Medical image segmentation based on improved fuzzy $C$-means clustering[C]. International Conference on Smart Grid and Electrical Automation. Singapore: IEEE, 2017: 406-410.
[2]
赵凤. 基于模糊聚类的图像分割[M]. 西安: 西安电子科技大学出版社, 2015: 30.
(Zhao F. Fuzzy clustering for image segmentation[M]. Xi'an: Xidian University Press, 2015: 30.)
[3]
魏立梅, 谢维信. 对手抑制式模糊$C$-均值算法[J]. 电子学报, 2000, 28(7): 79-83.
(Wei L M, Xie W X. Rival checked fuzzy $C$-means algorithm[J]. Acta Electronica Sinica, 2000, 28(7): 79-83.)
[4]
Ahmed M N, Yamany S M, Mohamed N, et al. A modified fuzzy $C$-means algorithm for bias field estimation and segmentation of MRI data[J]. IEEE Transactions on Medical Imaging, 2002, 21(3): 193-199.
[5]
Chen S, Zhang D. Robust image segmentation using FCM with spatial constraints based on new kernel-induced distance measure[J]. IEEE Transactions on Systems, Man, and Cybernetics, 2004, 34(4): 1907-1916.
[6]
Szilagyi L, Benyo Z, Szilagyi S M, et al. MR brain image segmentation using an enhanced fuzzy $C$-means algorithm[C]. Proceedings of the 25th Annual International Conference of the IEEE Engineering in Medicine and Biology Society. Cancun: IEEE, 2003: 724-726.
[7]
Zhao F, Jiao L C, 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.
[8]
Zhao F. Fuzzy clustering algorithm with self-tunning non local spatial information for image segmentation[J]. Neurocomputing, 2013, 106(4): 115-125.
[9]
Fan J L, Zhen W Z, Xie W X. Suppressed fuzzy $C$-means clustering algorithm[J]. Pattern Recognition Letters, 2003, 24(9/10): 1607-1612.
[10]
兰蓉, 马姣婷. 基于直觉模糊$C$-均值聚类算法的图像分割[J]. 西安邮电大学学报, 2016, 21(4): 53-56.
(Lan R, Ma J T. Image segmentation based on intuitionstic fuzzy $C$-means clustering algorithm[J]. Journal of Xi'an University of Posts and Telecommunications, 2016, 21(4): 53-56.)
[11]
支晓斌, 范九伦. 一种广义模糊补运算和相应的广义模糊熵[J]. 模糊系统与数学, 2008, 22(1): 96-102.
(Zhi X B, Fan J L. Generalized fuzzy complement and corresponding generalized fuzzy entropy[J]. Fuzzy Systems and Mathematics, 2008, 22(1): 96-102.)
[12]
肖满生, 肖哲. 抑制式模糊$C$均值聚类惩罚因子的改进[J]. 计算机应用, 2016, 36(9): 2427-2431.
(Xiao M S, Xiao Z. Improvement of penalty factor in suppressed fuzzy $C$-means clustering[J]. Journal of Computer Applications, 2016, 36(9): 2427-2431.)
[13]
兰蓉, 李刘军. 基于犹豫度生成的抑制式FCM图像分割算法[J]. 西安邮电大学学报, 2017, 22(5): 50-55.
(Lan R, Li L J. Suppressed FCM image segmentation algorithm based on the generated hesitation[J]. Journal of Xi'an University of Posts and Telecommunications, 2017, 22(5): 50-55.)
[14]
Yager R R. On the measure of fuzziness and negation[J]. Information & Control, 1980, 44(3): 236-260.
[15]
Atanassov K T. Intuitionistic fuzzy sets[J]. Fuzzy Sets and Systems, 1986, 20(1): 87-96.
[16]
Chuang K S, Tzeng H L, Chen S, et al. Fuzzy c-means clustering with spatial information for image segmentation[J]. Computerized Medical Imaging and Graphics, 2006, 30(1): 9-15.
[17]
Tripathy B K, Basu A, Govel S. Image segmentation using spatial intuitionistic fuzzy $C$-means clustering[C]. International Conference on Computational Intelligence and Computing Research. Coimbatore: IEEE, 2014: 1-5.
[18]
范九伦, 赵凤, 雷博, 等. 模式识别导论[M]. 西安: 西安电子科技大学出版社, 2012: 115.
(Fan J L, Zhao F, Lei B, et al. Introduction to pattern recognition[M]. Xi'an: Xidian University Press, 2012: 115.)
[19]
Bezdek J C, Ehrlich R, Full W. FCM: The fuzzy $C$-means clustering algorithm[J]. Computers \ & Geosciences, 1984, 10(2/3): 191-203.
[20]
施海滨, 周勇. 混合聚类彩色图像分割方法研究[J]. 计算机工程与应用, 2011, 47(9): 181-184.
(Shi H B, Zhou Y. Research for color image segmentation based on hybrid clustering[J]. Computer Engineering and Applications, 2011, 47(9): 181-184.)
[21]
李武, 赵娇燕, 严太山. 基于平均差异度优选初始聚类中心的改进$K$-均值聚类算法[J]. 控制与决策, 2017, 32(4): 759-762.
(Li W, Zhao J Y, Yan T S. Improved $K$-means clustering algorithm optimizing initial clustering centers based on average difference degree[J]. Control and Decision, 2017, 32(4): 759-762.)
[22]
Arbelaez P, Maire M, Fowlkes C, et al. Contour detection and hierarchical image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(5): 898-916.
[23]
Xu Z S, Wu J J. Intuitionistic fuzzy $C$-means clustering algorithms[J]. Journal of Systems Engineering and Electronics, 2010, 21(4): 580-590.
[24]
Sugeno M. Fuzzy measures and fuzzy integral—— A survey[C]. Fuzzy Sets for Intelligent Systems. San Francisco: Morgan Kanfmann, 1993: 251-257.
[25]
Bezdek J C. Cluster validity with fuzzy sets[J]. Journal of Cybernetics, 1973, 3(3): 58-73.
[26]
Bezdek J C. Mathematical models for symantic and taxonomy[C]. Proceedings of 8th International Conference on Numerical Taxonomy. San Fransisico: Freeman, 1975: 143-166.
[27]
Maulik U, 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.
[28]
Covoes T F, Hruschka E R, Ghosh J. A study of $K$-means-based algorithm for constrained clustering[J]. Intelligent Data Analysis, 2013, 17(3): 485-505.
[29]
Yang Y, Newsam S. Bag-of-visual-words and spatial extensions for land-use classification[C]. The 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. San Jose: ACM, 2010: 270-279.