面向直方图加权的快速FCM的图像分割算法

陈星平，陈燕敏，楼喜中

（中国计量学院 信息工程学院，浙江 杭州 310018）

图像分割是指把图像分割成具有特定区域性质并提出感兴趣的目标之过程［1］.现有分割算法包括：基于阈值的分割算法，基于区域的分割算法，基于特定理论的分割算法和FCM算法［2］.已有的这些算法，独立且都有其局限性［3］.随着模糊理论的研究发展，FCM算法成为一种分类效果很好的算法，FCM算法是一种基于面向数据划分的、非监督的聚类算法，已大量运用到实际中［4］.FCM算法不需要事件的先验概念，依据需求可以选择不同的隶属度函数，对含有噪声的图像分割，具有一定的抗噪声能力［5］，适应范围广.但是经典的FCM算法容易陷入局部最优解，对于初始化数据比较敏感，同时数据迭代次数高.文献［6－8］使用了FFCM（fast fuzzy C－means algorithm）算法，将图像像素投影到一维灰度值空间，从而减少了迭代数目，但是忽视了不同灰度值离散程度不一样的特点.文献［9］提出了一种加权的灰度值模糊C聚类算法（SWFCM），利用领域像素灰度的相关性质，对直方图的灰度进行加权模糊聚类.本文基于直方图加权模糊聚类，首先对二维图像像素点投影到一维灰度值像素空间中，对于每一级灰度值进行线性加权.考虑到每一级灰度值像素点空间分布不同，使用四分位相对离差系数作为权值.实验表明，相比FCM算法和FFCM算法，本算法减少了迭代数量，加快了图像聚类分割速度，对含有一定噪声图像分割，减少了像素点错分比例，提高了图像的分割精度.

1 FCM算法和四分类相对离差系数

1.1 四分类相对离差系数

四分类相对离差系数反映数据的离散程度，数据的离散程度越大，对应的四分离散系数越大［11］.假设数据总量分为相同的四等份，每一个等分量为 Q1，Q2，Q3，Q4.（Q1＋Q3）／2表明的是数据集中趋势的度量，（Q3－Q1）／2表明的是数据离差程度的度量，定义四分类相对离差系数VQ：

对比图1、图2的四分类相对离差系数，得出离散程度不同，四分类相对离差系数不同.

1.2 经典FCM算法

FCM 把n个向量Xi｛i＝1，2，3，…，n｝，分为C个组，每个组的向量定义为Gj｛j＝1，2，3，…，C｝，每个组的聚类中心cj｛j＝1，2，3，…，C｝.每个向量Xi对于每个聚类组Gj定义一个隶属度uij，uij根据隶属度函数得到，uij有如下性质：

图1 离散系数为0.69的离散图Figure 1 Scattering diagram with dispersion coefficient of 0.69

图2 离散系数为0.74的离散图Figure 2 Scattering diagram with dispersion of 0.74

采用欧几里德距离作为非相似性指标，使得目标函数J最小.目标函数定义为：

γj（j从1到n）表示公式（3）的n个约束式的拉格朗日乘子，对所有输入参数进行求偏导，使得公式（6）达到最小值的必要条件为：

得到FCM算法的步骤如下：

1）输入模糊度指数m、聚类数目C和停止参数ζ.

2）初始化隶属矩阵u.使得得到的隶属矩阵满足公式（3）的要求.

3）依据u和公式（7），求出每个类的聚类中心.

4）依据公式（4）式计算价值函数.如果达到预定的迭代次数，或者目标函数J小于某个确定的阈值，或者对比上一次目标函数J变化量小于某个确定的值ζ，一般ζ取值为0.0001，算法结束.否则进入下一步.

5）用公式（8）重新计算隶属矩阵.返回步骤3）.

2 基于直方图加权快速FCM算法

经典FCM算法对于每一个像素都进行数据量的运算，运行数据迭代次数高，采用文献［6］提出的FFCM算法，将需要聚类的像素点投影到一维灰度直方图空间中，减少了算法的迭代量，加快了算法的运行速度.公式（4）式中n代表聚类样例数目，对于图像为M×N（M代表图像的宽度，N代表图像的高度）.l表示一维灰度直方图中的灰度，H（l）表示灰度值为l的样例数目，得到H（l）的表达式如下：

l对于图像，最大值255，表示最多有256种不同的灰度值，对比公式（11）和公式（4）得到算法时间复杂度O（C×M×N）转换为O（C×L），优化了运行时间.为得到上述目标函数的最小值，分别对uij和ci进行求偏导，得到新的迭代函数U 和聚类中心C：

FFCM算法在速度上比传统FCM算法运行速度快，但是它没有考虑到数据的空间信息.每一个灰度值在图像中的重要性质不一样［10］，对于每一个灰度值进行一次加权.而加权系数使用的是使用四分位相对离差系数.四分位相对离差系数能够衡量数据的离散程度，离差系数越大，数据的离散程度越大，离差系数越小，离散程度越小.对于任何一个灰度值l，灰度值为l的像素点分布在宽度为W 和高度为H 的图像中，每一个层级的灰度值空间分布不相同，充分利用图像像素的空间信息分布［11］，对于每一级灰度值进行四分位离差系数进行加权，最终得到了更好的聚类效果.灰度图如图3.

图3 灰度图Figure 3 Gray－scale image

灰度直方图如图4，当灰度值l为194时候得到的空间信息分布如图5.

根据公式（2），给定数据的下分类数Q1和上分类数Q3，（Q1＋Q3）／2表明的是数据集中趋势的度量，（Q3－Q1）／2表明的是数据离差程度的度量，求出四分类相差系数为0.671，即灰度值的样例数目 H（l）的权重W（l）系数.把权值W（l）运用到公式（11）中，每一个灰度值都得到一个对应的权值，其中一共有0到255灰度值，256种不同的灰度值.公式（11）变为

图4 灰度直方图Figure 4 Gray histogram

图5 灰度值l＝194像素点空间分布Figure 5 Spatial distribution of pixels when gray level is 194

结合SPFFCM（special weight fast fuzzy C－means）改进的算法流程如下：

1）由公式（9）和公式（10）得到图像的灰度值函数 H（l）.

2）依据图像的空间信息，得到每一个灰度值的四分类相对离差系数W（l）.

3）把W（l）×H（l）作为新的 H（l）.

4）初始化隶属矩阵u，使其满足公式（3）的要求.

5）依据u和公式（12）求出每个类的聚类中心.

6）依据公式（14）计算价值函数.如果达到预定的迭代次数，或者目标函数J小于某个确定的阈值，或者对比上一次目标函数J变化量小于某个确定的值ζ，通常ζ取值为0.0001，算法结束.否则进入下一步.

7）公式（13）重新计算隶属矩阵.返回步骤5）.

3 实验结果和分析

为了验证本文提出的算法在分割速度和精度方面的有效性，实验编程在Matlab 7.10.0实现，分别对比FCM算法、FFCM算法、SWFFCM算法在图像分割中的结果，算法设置权重指数m＝2，ζ＝0.0001，实验选择100副128×128图像，每副图像一共16384个像素点.

图像6中，原始图像包含3种（20，149，179）灰度值，原始图像中均加入均值5%的高斯噪声，分割的聚类数目C为3.图像6为样例图像，图像7为经典FCM算法的分割结果，图8为FFCM算法分割的效果，图9为SWFFCM（special weight fast FCM）算法分割的效果.图像结果中显示，经典FCM并不能很好保留图像细节，同时图像分割界限不明显.FFCM算法虽然运行速度快，但是对噪声抗干扰性能较差.SWFFCM算法不仅算法执行速度快，同时对图像具有很好的去除噪声功能，最终对图像具有良好的分割效果.

图6 加入高斯噪声后的图像Figure 6 Image with adding Gaussian noise

图7 经典FCM算法处理效果Figure 7 Processing effect with classic FCM algorithm

图8 FFCM算法处理效果Figure 8 Processing effect with FFCM algorithm

图9 SWFFCM算法处理效果Figure 9 Processing effect with SWFFCM algorithm

为了进一步客观比较各个算法的性能，采用聚类错分点数目比例和算法运行时间两个参数作为评价算法的指标，错分点数目比例定义为错分数目除以总的像素点个数.对比发现SWFFCM算法在算法分割时间上优于传统的FCM算法和FFCM算法，同时错分数目少，对噪声的容纳性能优良.

表1 FCM算法、FFCM算法、SWFFCM算法性能比较Table 1 FCM algorithm，FFCM algorithm and SWFFCM algorithm segmentation performance comparison

4 结 语

本文提出了基于加权四分位系数的快速模糊聚类算法，并将其运用在图像分割中.在得到图像的一维灰度直方图的基础上，对每一个灰度值进行加权，采用四分位相对离差系数作为其权值，既提高了图像的分割效率和速度，又减少了样例点在图像聚类结果中的错分数目.改进后的算法对图像噪声具有较好的鲁棒性，优于FFCM算法和标准的FCM算法.

［1］雷斯.数字图像处理［M］.北京：电子工业出版社，2011：100－104.

［2］尼克松.特征提取与图像处理［M］.北京：电子工业出版社，2010：200－206.

［3］崔宝珍，王泽兵，潘宏侠.改进的FCM聚类算法［J］.机械管理开发，2010，25（6）：76－78 CUI Baozhen，WANG Zebing，PAN Hongxia.An improved FCM clustering algorithm［J］.Mechanical Management and Development，2010，25（4）：76－78.

［4］景军锋，孟泰，李鹏飞.基于模糊C均值聚类的纺织品印花图像分割［J］.纺织学报，2012，33（6）：97－100.JING Junfeng，MENG Tai，LI Pengfei.Textile printimage segmentation based on FCM［J］.Journal of Textile Research，2012，33（6）：97－100.

［5］JUI S.Dynamic incorporation of wavelet filter in fuzzy CMeans for efficient and noise－insensitive MR image Segmentation［J］.International Journal of Computational Intelligence Systems，2015，8（5）：796－807.

［6］刘健庄.基于二维直方图的图像模糊聚类分割方法［J］.电子学报，1992，2（9）：40－46.LIU Jianzhuang.A fuzzy clustering method for image s－egmentation based on two dimensional Histogram［J］.Acta Electronical Sinica，1992，2（9）：40－46.

［7］彭立军，何灵敏，杨小兵.一种基于FCM的图像分割算法［J］.中国计量学院学报，2011，22（4）：369－372.PENG Lijun，HE Lingmin，YANG Xiaobing.A picture segmentation method based on FCM［J］.Journal of China University of Metrology，2011，22（4）：369－372.

［8］SU L M，ISA N.Adaptive fuzzy－K－means clustering algorithm for image segmentation［J］.IEEE Transactionson Consumer Electronics，2010，56（4）：2661－2668.

［9］董旭，魏振军.一种加权欧氏距离聚类方法［J］.信息工程大学学报，2005，6（1）：23－25 DONG Xu，WEI Zhenjun，A clustering method of euclid distance with weights［J］.Journal of Information Engineer－ing University，2005，6（1）：23－25.

［10］康家银，闵乐泉.基于顾及像素空间信息的加权FCM聚类的图像分割［J］.北京科技大学学报，2008，30（9）：1072－1078.KANG Jiayin，MIN Lequan.Image segmentation based on weighted fuzzy C－means clustering accounting for pixel spatial information［J］.Journal of University of Science and Technology Beijing，2008，30（9）：1072－1078.

［11］YUS O I，ISA M，HASIKIN K.Automated two dimensional K－means clustering algorithm for unsupervised image segmentation［J］.Computers ＆ Electrical Engineering，2013，39（3）：907－917.