基于谱分解的模糊C均值算法在彩色图像分割中的应用

刘 雨，周丽娟

(1.首都师范大学 信息工程学院，北京 100048;2.成像技术北京市高精尖创新中心 信息工程学院，北京 100048)

基于谱分解的模糊C均值算法在彩色图像分割中的应用

刘 雨1 ,2，周丽娟1, 2

(1.首都师范大学 信息工程学院，北京 100048;2.成像技术北京市高精尖创新中心 信息工程学院，北京 100048)

针对模糊C均值聚类算法对初始值敏感、易陷入局部最优以及谱聚类算法无法处理样本量过大的问题，提出了一种将模糊C均值聚类算法与谱聚类算法相结合的模糊谱聚类算法应用于彩色图像分割;大致分为三步：第一步对图像进行预处理，将颜色空间由RGB空间转换为Lab空间；第二步对特征空间进行冗余模糊C均值聚类算法得到冗余类；第三步由冗余类的隶属度矩阵和聚类中心矩阵得到冗余类的特征空间，并根据贴进度和传递闭包将该特征空间转换为冗余类的相似度矩阵进行谱聚类，完成冗余类的合并;实验结果表明，与模糊C均值聚类算法相比，模糊谱聚类算法对于初始值敏感问题、易陷入局部最优以及只能识别团状的蔟得到了很好的解决，从而使彩色图像分割结果更加合理。

彩色图像分割；模糊C均值聚类；贴近度；传递闭包

0 引言

图像分割实质上就是根据图像自己具有的某种属性如灰度，颜色，纹理等将图像分割成为互不重叠的多个模块，同时对于该属性，模块内的像素点是相似的，不同模块内的像素点是不相似的。彩色图像分割相比于灰度图像分割问题，就是在进行图像分割时，图像的属性由灰度变为了彩色空间，特征空间由一维变成了多维，然而由于不同的颜色空间对图像分割结果的不同，因此彩色图像分割主要就是选择最优的分割算法和合适的颜色空间。

图像分割作为图像分析和图像理解的前期图像处理工作，分割结果的好坏直接影响后续对图像进行的一系列工作，因此广大学者针对图像分割的方法做了很多的研究，主要有直方图阈值法[1]、基于区域的方法[2]、基于边缘的方法[3]、聚类方法[4-5]以及基于某种特定理论的方法等，其中聚类方法中引入模糊集理论的模糊聚类方法在图像分割中得到了很好的应用。聚类算法是一种无监督学习的方法，运用数学知识将图像分割问题转换为非线性规划问题，具有操作简单、易于实现的优点；模糊集理论对于图像的一些不确定性问题具有很好的描述。

模糊C均值聚类(FCM)算法是模糊聚类中的一种经典算法。模糊C均值聚类算法实质上属于非线性规划求最优解问题，但是非线性规划求最优解问题易陷入局部最优解；同时模糊C聚类算法中相似性度量是用欧式距离来度量，故只能识别团状的数据。谱聚类算法是一类以谱图理论为理论基础的聚类算法，可以对任意形状的数据进行聚类，考虑数据的全局特性，且可以收敛到全局最优，其本质上是将聚类问题转化成了图的最优划分问题，但谱聚类算法对于数据量比较大的图像无法进行分割。因此提出了基于谱分解的模糊C聚类算法进行彩色图像分割。

1 相关知识

1.1 模糊C均值聚类(FCM)

对于n个向量xj(j=1,2,...,n)，即n个像素点，FCM把它分为c(2≤c≤n)个类，每个向量对第i个类ci(i=1,2,...,c)的隶属度为uij(0≤uij≤1)，类的聚类中心向量为vi(1≤i≤c)，目标函数如下：

(1)

(2)

利用拉格朗日数乘法，且在约束条件(2)下，目标函数Jm取得最小值时uij和vi的迭代公式为：

(3)

(4)

FCM算法就是不断迭代公式(3)、(4)，使目标函数(1)达到最小。

1.2 谱聚类

谱聚类在图像分割中应用时，就是将图像的像素点看做为图的一个顶点，进而将图像像素点分类问题转化为了图的最优划分问题。

对于一个加权图G=(V,E)，其中V={v1,v2,…vn}∈Rl，是图中所有的顶点的集合，E是所有边的集合，将图G划分为C个部分，其算法如下：

3)求矩阵Lsym的前k个按从大到小顺序排列的特征值，以及特征值对应的特征向量(x1,x2,…,xk)，得到矩阵X=[x1,x2,…,xk]∈Rn×k；

5)将矩阵Y的每一行看做图的一个顶点，采用FCM算法对其进行聚类得到C个划分，如果yi∈Cj，则vi∈Cj；

1.3 贴近度和传递闭包

贴进度是用来度量模糊集[6]之间的接近程度的。随着模糊理论的发展，根据贴进度的定义产生了多种贴进度[7]公式，但没有一种贴进度可以广泛的应用，每种贴进度各有特点。因此，需根据具体问题选用合适的贴进度。格贴近度可以较好地度量冗余类间的“距离”。格贴进度的公式如下：

⊗B)]

(5)

如图1所示，有5个模糊集，rij表示模糊集i和模糊集j之间的贴进度值，从图中可以看出模糊集i和模糊集j之间有多个贴进度值，对于如何选择模糊集i和模糊集j之间最优的贴进度值，使用图论中求解最优路径问题的Floyd算法来获得模糊集间的最优贴进度值，得到最优贴进度矩阵。

图1 模糊集的贴进度关系图

定理1:设R∈μn×n是模糊相似矩阵，则存在一个最小自然数k(k≤n)，使得传递闭包t(R)=Rk，对于任何自然数b≥k，都有Rb=Rk，此时，t(R)是模糊等价矩阵。

设R=rn×n是初始贴进度矩阵，相当于定理1中的模糊相似矩阵，采用平方法[8]迭代求取传递闭包，直到存在一个自然数k(k≤n)，使得传递闭包t(R)=Rk，对于任意的b≥k，都有Rb=Rk，此时，传递闭包t(R)具有传递性。操作如下式：

R→R2→R4→...→Rk→Rq→...

(6)

当式(6)第一次出现Rk°Rk=Rk时，Rk就是模糊等价矩阵t(R)，即最优贴近度矩阵。

2 基于谱聚类的FCM算法

2.1 图像颜色空间转换

RGB颜色空间主要用于图像的显示，对于图像处理方面，由于RGB颜色空间的3个分量具有高度的相关性，所以将RGB颜色空间转换为Lab空间。因为Lab颜色空间是均匀的颜色空间，能够根据颜色属性的距离公式比较颜色，可以对颜色差别比较小的数据进行有效的测量。Lab颜色空间由XYZ空间非线性变换得到，XYZ颜色空间由RGB颜色空间线性变换得到，公式如下：

(7)

(8)

其中：

(9)

2.2 基于谱聚类的FCM算法

首先对图像预处理得到的特征空间进行冗余模糊C均值聚类算法得到冗余类的隶属度矩阵和聚类中心矩阵，将隶属度矩阵的行向量作为冗余类的特征空间，如图2。由于冗余类的特征空间矩阵是所有像素点对于每个冗余类的接近程度，代表了一种模糊划分，因此，可以将冗余类的特征空间矩阵的每一行作为一个模糊集(冗余类)；进而将像素点分类问题转化为了冗余类合并问题。图像聚类问题转化为冗余类的合并问题，冗余类合并需遵循两个准则：一是冗余类间需满足相似相近性原则，使用贴近度[7]来满足；二是冗余类间的相似度需具有传递性，使用传递闭包来实现；将同时满足冗余类合并两个准则的贴进度矩阵称为标准贴进度矩阵。因为该方法得到的标准贴进度不满足自反性，而标准贴进度矩阵是作为谱聚类的相似度矩阵，所以将其对角线上的元素设为零以满足自反性。

图2 隶属度矩阵与冗余类特征空间的关系

根据谱理论，将每一个冗余类看做图的一个顶点，将冗余类合并问题转化为图的最优划分问题。由于冗余类的类特征是模糊集，贴进度作为模糊集接近程度的度量，可以用来构建相似度矩阵；同时为了使相似度矩阵具有传递性，需要求出贴进度矩阵的传递闭包，由传递闭包获得冗余类间的标准贴进度矩阵t(R)，将其作为谱分解的相似度矩阵，在谱分解前，采用下式来构建正则化的拉普拉斯矩阵：

(10)

1)由式(7)～(9)对图像进行颜色空间转换处理，将RGB颜色空间转换为Lab颜色空间。

2)对得到的Lab颜色空间进行冗余模糊C均值算法，获得冗余类的隶属度矩阵U和聚类中心矩阵V。

3)将隶属度矩阵U作为冗余类的类特征，根据格贴进度公式(5)和定理1，采用Floyd算法和求传递闭包的平方法，将冗余类的类特征转换为标准贴进度矩阵t(R)。

4)将标准贴进度矩阵t(R)作为谱聚类的相似度矩阵，采用式(10)建立拉普拉斯矩阵进行谱分解，并选取除特征值为0的最小特征值和次小特征值对应的特征向量作为冗余类的特征空间的等价特征空间。

5)对谱分解得到的新的特征空间进行模糊C均值聚类算法，完成冗余类的合并，从而完成彩色图像的分割。

2.3 实验结果及分析

为了证明该算法的优越性，在保证参数一致的情况下，分别将本文方法和传统FCM方法应用于UCI数据集中的iris、wine、balance和Berkeley库中的彩色图像，然后比较实验结果。本文实验环境为Win 7操作系统、Intel i7处理器、8G内存，实验平台为MATLAB 2012。实验所用Berkeley库中图像大小均为481*321。

2.3.1 UCI数据集分割结果

由于NMI(normalized mutual information)对于聚类效果具有很好的评价，所以选用NMI对UCI数据集进行聚类效果的评价，公式如下：

(11)

其中：

(12)

(13)

其中：X是UCI数据集分类结果的向量，Y是使用本文算法分割图像后对数据集分类结果的向量。I(X;Y)是MI，H(X)和H(Y)是X和Y的信息熵。UCI数据集聚类结果对比如表1。

表1 UCI数据集聚类结果

以Balance数据为例，图3和图4分别为Balance数据冗余类的初始贴进度矩阵和标准贴进度矩阵的三维曲面图。由图可以看出标准贴近度矩阵比初始贴近度矩阵分布更均匀，更具有对称性，更能体现冗余类之间的贴进度关系；从而作为谱聚类的相似度矩阵可以使聚类结果更合理。

图3 初始贴进度矩阵的三维曲面图

图4 标准贴进度矩阵的三维曲面图

2.3.2 Berkeley库图像分割结果

图5为Berkeley库中小鸟图像的分割结果对比图。从该图像可以看出图像四周背景颜色和树枝、小鸟差不多，当用FCM方法进行分割时由于没有考虑全图特性易陷入局部最优，将四周一圈背景和小鸟分为了一类，而且易受噪音的干扰，而提出的算法抗噪性很好，且可以收敛到全局最优，对图像进行了很好的分割;当分为2类的时候，FCM算法没有将图像4个角和小鸟，树枝分开，提出的算法得到了很好的分割；当分为3类的时候，从FCM算法对于图像的分割结果中可以看出分割不均匀，小鸟类中有其他类的颜色，而提出的算法分割均匀，分割结果较好。

图5 小鸟图像分割结果

图6为Berkeley库中海星图像的分割结果对比图。图6中海星的颜色分布不均，且背景颜色有阴影以及和海星颜色有差不多的地方，当分为2类的时候，用FCM算法进行分割的时候很容易分割错误，没有将海星完整的分割出来，并且背景中也会分割出一些和海星相同的区域来；而使用提出的算法进行分割，将海星很好的分割了出来；当分为3类的时候，使用FCM算法分割的结果中背景和海星分割很不均匀，海星中有背景的分割颜色，背景中有海星的分割颜色；而使用提出的方法背景和海星得到了很好的分割且分割均匀。

图6 海星图像分割结果

3 结论

针对模糊C均值聚类算法的聚类结果对初始值很依赖，易陷入局部最优，提出了将模糊C均值聚类算法与谱聚类相结合的算法应用于彩色图像分割。该方法先对图像进行冗余加权模糊C均值聚类算法，将图像分割成许多的冗余类，根据贴进度和传递闭包的定义和公式，将冗余类的类特征空间转换为具有相似性和传递性的相似度矩阵，再对相似度矩阵进行谱聚类，从而完成冗余类的合并。通过实验结果表明。该方法克服了模糊C均值算法初始化时必须确定聚类数的问题，同时使用谱聚类实现冗余类合并时考虑了特征的全局性，从而可以使聚类结果不易陷入局部最优。因此，该算法对图像分割具有较好的效果。

[1] 周东国，高 潮，郭永彩. 自适应分层阈值的简化PCNN红外人体图像分割[J]. 计算机辅助设计与图形学学报，2013,25(2): 208-214.

[2] Wang L, Wu H, Pan C. Region-based image segmentation with local signed difference energy [J]. Pattern Recognition Letters, 2013, 34(6): 637-645.

[3] 贺 强，晏 立. 基于LOG和Canny算子的边缘检测算法[J]. 计算机工程，2011,37(3): 210-212.

[4] Yu Z, Au O C, Zou R, et al. An adaptive unsupervised approach toward pixel clustering and color image segmentation [J]. Pattern Recognition, 2010, 43(5): 1889-1906.

[5] 陈骥思，余艳梅，殷 宇,等. 自适应快速FCM彩色图像分割研究[J]. 计算机工程与应用，2010,46(7):178-180.

[6] Zaedh L A. Fuzzy sets [J]. Information and control, 1965, 8(3):338-353.

[7] Tong X J, Zhang S M. Similarity and nearness of fuzzy sets[A]. Proceeding of 2005 International Conference on Machine Learning and Cybernetics, ICMLC 2005[C]. Guangzhou, 2005,8: 2668-2670.

[8] 周 娟，熊中阳，张玉芳,等. 基于最大最小距离法的多中心聚类算法[J]. 计算机应用，2006,26(6): 1425-1427.

Application of Fuzzy C Means Algorithm Based on Spectral Decomposition in Color Image Segmentation

Liu Yu1,2，Zhou Lijuan1,2

(1.College of Information Engineering, Capital Normal University,Beijing 100048, China; 2.Beijing Advanced Innovation Center for Imaging Technology,Beijing 100048, China)

Aiming at the fuzzy C-means clustering algorithm to the initial value sensitive, easy to fall into local optimum and spectral clustering algorithm cannot handle the sample volume is too large, a fuzzy C-means clustering algorithm and spectral clustering algorithm combining fuzzy spectral clustering algorithm is applied to color image segmentation is proposed. Roughly divided into three steps. The first step of image of pretreatment, the color space by the RGB color space conversion for lab space; the second step of feature space redundancy fuzzy C-means clustering algorithm to obtain the redundant; the third step by the redundancy class membership matrix and the cluster center matrix are redundant feature space and according to the closeness degree and transitive closure convert the feature space for redundancy of the similarity matrix for spectral clustering, merging redundant. Experimental results show that and fuzzy C-means clustering algorithm compared to fuzzy spectral clustering algorithm for the initial value sensitivity, is easy to fall into local optimal and can identify clusters of cocooning has been very good solution, so that the color image segmentation results are more reasonable.

color image segmentation; fuzzy C-means clustering;closeness degree; transitive closure

2016-06-21；

2016-07-16。

国家自然科学基金(31571563)；北京市属高等学校创新团队建设与教师职业发展计划项目；高可靠嵌入式系统技术北京市工程研究中心。

刘 雨(1991-)，女，河南商丘人，硕士，主要从事数据挖掘方向的研究。

周丽娟(1969-)，女，北京人，教授，主要从事数据仓库和商务智能方向的研究。

1671-4598(2016)12-0168-04

10.16526/j.cnki.11-4762/tp.2016.12.048

TP3

A