基于譜分解的模糊C均值算法在彩色圖像分割中的應(yīng)用

劉 雨，周麗娟

(1.首都師范大學(xué) 信息工程學(xué)院，北京 100048;2.成像技術(shù)北京市高精尖創(chuàng)新中心 信息工程學(xué)院，北京 100048)

基于譜分解的模糊C均值算法在彩色圖像分割中的應(yīng)用

劉 雨1 ,2，周麗娟1, 2

(1.首都師范大學(xué) 信息工程學(xué)院，北京 100048;2.成像技術(shù)北京市高精尖創(chuàng)新中心 信息工程學(xué)院，北京 100048)

針對模糊C均值聚類算法對初始值敏感、易陷入局部最優(yōu)以及譜聚類算法無法處理樣本量過大的問題，提出了一種將模糊C均值聚類算法與譜聚類算法相結(jié)合的模糊譜聚類算法應(yīng)用于彩色圖像分割;大致分為三步：第一步對圖像進行預(yù)處理，將顏色空間由RGB空間轉(zhuǎn)換為Lab空間；第二步對特征空間進行冗余模糊C均值聚類算法得到冗余類；第三步由冗余類的隸屬度矩陣和聚類中心矩陣得到冗余類的特征空間，并根據(jù)貼進度和傳遞閉包將該特征空間轉(zhuǎn)換為冗余類的相似度矩陣進行譜聚類，完成冗余類的合并;實驗結(jié)果表明，與模糊C均值聚類算法相比，模糊譜聚類算法對于初始值敏感問題、易陷入局部最優(yōu)以及只能識別團狀的蔟得到了很好的解決，從而使彩色圖像分割結(jié)果更加合理。

彩色圖像分割；模糊C均值聚類；貼近度；傳遞閉包

0 引言

圖像分割實質(zhì)上就是根據(jù)圖像自己具有的某種屬性如灰度，顏色，紋理等將圖像分割成為互不重疊的多個模塊，同時對于該屬性，模塊內(nèi)的像素點是相似的，不同模塊內(nèi)的像素點是不相似的。彩色圖像分割相比于灰度圖像分割問題，就是在進行圖像分割時，圖像的屬性由灰度變?yōu)榱瞬噬臻g，特征空間由一維變成了多維，然而由于不同的顏色空間對圖像分割結(jié)果的不同，因此彩色圖像分割主要就是選擇最優(yōu)的分割算法和合適的顏色空間。

圖像分割作為圖像分析和圖像理解的前期圖像處理工作，分割結(jié)果的好壞直接影響后續(xù)對圖像進行的一系列工作，因此廣大學(xué)者針對圖像分割的方法做了很多的研究，主要有直方圖閾值法[1]、基于區(qū)域的方法[2]、基于邊緣的方法[3]、聚類方法[4-5]以及基于某種特定理論的方法等，其中聚類方法中引入模糊集理論的模糊聚類方法在圖像分割中得到了很好的應(yīng)用。聚類算法是一種無監(jiān)督學(xué)習(xí)的方法，運用數(shù)學(xué)知識將圖像分割問題轉(zhuǎn)換為非線性規(guī)劃問題，具有操作簡單、易于實現(xiàn)的優(yōu)點；模糊集理論對于圖像的一些不確定性問題具有很好的描述。

模糊C均值聚類(FCM)算法是模糊聚類中的一種經(jīng)典算法。模糊C均值聚類算法實質(zhì)上屬于非線性規(guī)劃求最優(yōu)解問題，但是非線性規(guī)劃求最優(yōu)解問題易陷入局部最優(yōu)解；同時模糊C聚類算法中相似性度量是用歐式距離來度量，故只能識別團狀的數(shù)據(jù)。譜聚類算法是一類以譜圖理論為理論基礎(chǔ)的聚類算法，可以對任意形狀的數(shù)據(jù)進行聚類，考慮數(shù)據(jù)的全局特性，且可以收斂到全局最優(yōu)，其本質(zhì)上是將聚類問題轉(zhuǎn)化成了圖的最優(yōu)劃分問題，但譜聚類算法對于數(shù)據(jù)量比較大的圖像無法進行分割。因此提出了基于譜分解的模糊C聚類算法進行彩色圖像分割。

1 相關(guān)知識

1.1 模糊C均值聚類(FCM)

對于n個向量xj(j=1,2,...,n)，即n個像素點，F(xiàn)CM把它分為c(2≤c≤n)個類，每個向量對第i個類ci(i=1,2,...,c)的隸屬度為uij(0≤uij≤1)，類的聚類中心向量為vi(1≤i≤c)，目標(biāo)函數(shù)如下：

(1)

(2)

利用拉格朗日數(shù)乘法，且在約束條件(2)下，目標(biāo)函數(shù)Jm取得最小值時uij和vi的迭代公式為：

(3)

(4)

FCM算法就是不斷迭代公式(3)、(4)，使目標(biāo)函數(shù)(1)達到最小。

1.2 譜聚類

譜聚類在圖像分割中應(yīng)用時，就是將圖像的像素點看做為圖的一個頂點，進而將圖像像素點分類問題轉(zhuǎn)化為了圖的最優(yōu)劃分問題。

對于一個加權(quán)圖G=(V,E)，其中V={v1,v2,…vn}∈Rl，是圖中所有的頂點的集合，E是所有邊的集合，將圖G劃分為C個部分，其算法如下：

3)求矩陣Lsym的前k個按從大到小順序排列的特征值，以及特征值對應(yīng)的特征向量(x1,x2,…,xk)，得到矩陣X=[x1,x2,…,xk]∈Rn×k；

5)將矩陣Y的每一行看做圖的一個頂點，采用FCM算法對其進行聚類得到C個劃分，如果yi∈Cj，則vi∈Cj；

1.3 貼近度和傳遞閉包

貼進度是用來度量模糊集[6]之間的接近程度的。隨著模糊理論的發(fā)展，根據(jù)貼進度的定義產(chǎn)生了多種貼進度[7]公式，但沒有一種貼進度可以廣泛的應(yīng)用，每種貼進度各有特點。因此，需根據(jù)具體問題選用合適的貼進度。格貼近度可以較好地度量冗余類間的“距離”。格貼進度的公式如下：

?B)]

(5)

如圖1所示，有5個模糊集，rij表示模糊集i和模糊集j之間的貼進度值，從圖中可以看出模糊集i和模糊集j之間有多個貼進度值，對于如何選擇模糊集i和模糊集j之間最優(yōu)的貼進度值，使用圖論中求解最優(yōu)路徑問題的Floyd算法來獲得模糊集間的最優(yōu)貼進度值，得到最優(yōu)貼進度矩陣。

圖1 模糊集的貼進度關(guān)系圖

定理1:設(shè)R∈μn×n是模糊相似矩陣，則存在一個最小自然數(shù)k(k≤n)，使得傳遞閉包t(R)=Rk，對于任何自然數(shù)b≥k，都有Rb=Rk，此時，t(R)是模糊等價矩陣。

設(shè)R=rn×n是初始貼進度矩陣，相當(dāng)于定理1中的模糊相似矩陣，采用平方法[8]迭代求取傳遞閉包，直到存在一個自然數(shù)k(k≤n)，使得傳遞閉包t(R)=Rk，對于任意的b≥k，都有Rb=Rk，此時，傳遞閉包t(R)具有傳遞性。操作如下式：

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

(6)

當(dāng)式(6)第一次出現(xiàn)Rk°Rk=Rk時，Rk就是模糊等價矩陣t(R)，即最優(yōu)貼近度矩陣。

2 基于譜聚類的FCM算法

2.1 圖像顏色空間轉(zhuǎn)換

RGB顏色空間主要用于圖像的顯示，對于圖像處理方面，由于RGB顏色空間的3個分量具有高度的相關(guān)性，所以將RGB顏色空間轉(zhuǎn)換為Lab空間。因為Lab顏色空間是均勻的顏色空間，能夠根據(jù)顏色屬性的距離公式比較顏色，可以對顏色差別比較小的數(shù)據(jù)進行有效的測量。Lab顏色空間由XYZ空間非線性變換得到，XYZ顏色空間由RGB顏色空間線性變換得到，公式如下：

(7)

(8)

其中：

(9)

2.2 基于譜聚類的FCM算法

首先對圖像預(yù)處理得到的特征空間進行冗余模糊C均值聚類算法得到冗余類的隸屬度矩陣和聚類中心矩陣，將隸屬度矩陣的行向量作為冗余類的特征空間，如圖2。由于冗余類的特征空間矩陣是所有像素點對于每個冗余類的接近程度，代表了一種模糊劃分，因此，可以將冗余類的特征空間矩陣的每一行作為一個模糊集(冗余類)；進而將像素點分類問題轉(zhuǎn)化為了冗余類合并問題。圖像聚類問題轉(zhuǎn)化為冗余類的合并問題，冗余類合并需遵循兩個準(zhǔn)則：一是冗余類間需滿足相似相近性原則，使用貼近度[7]來滿足；二是冗余類間的相似度需具有傳遞性，使用傳遞閉包來實現(xiàn)；將同時滿足冗余類合并兩個準(zhǔn)則的貼進度矩陣稱為標(biāo)準(zhǔn)貼進度矩陣。因為該方法得到的標(biāo)準(zhǔn)貼進度不滿足自反性，而標(biāo)準(zhǔn)貼進度矩陣是作為譜聚類的相似度矩陣，所以將其對角線上的元素設(shè)為零以滿足自反性。

圖2 隸屬度矩陣與冗余類特征空間的關(guān)系

根據(jù)譜理論，將每一個冗余類看做圖的一個頂點，將冗余類合并問題轉(zhuǎn)化為圖的最優(yōu)劃分問題。由于冗余類的類特征是模糊集，貼進度作為模糊集接近程度的度量，可以用來構(gòu)建相似度矩陣；同時為了使相似度矩陣具有傳遞性，需要求出貼進度矩陣的傳遞閉包，由傳遞閉包獲得冗余類間的標(biāo)準(zhǔn)貼進度矩陣t(R)，將其作為譜分解的相似度矩陣，在譜分解前，采用下式來構(gòu)建正則化的拉普拉斯矩陣：

(10)

1)由式(7)～(9)對圖像進行顏色空間轉(zhuǎn)換處理，將RGB顏色空間轉(zhuǎn)換為Lab顏色空間。

2)對得到的Lab顏色空間進行冗余模糊C均值算法，獲得冗余類的隸屬度矩陣U和聚類中心矩陣V。

3)將隸屬度矩陣U作為冗余類的類特征，根據(jù)格貼進度公式(5)和定理1，采用Floyd算法和求傳遞閉包的平方法，將冗余類的類特征轉(zhuǎn)換為標(biāo)準(zhǔn)貼進度矩陣t(R)。

4)將標(biāo)準(zhǔn)貼進度矩陣t(R)作為譜聚類的相似度矩陣，采用式(10)建立拉普拉斯矩陣進行譜分解，并選取除特征值為0的最小特征值和次小特征值對應(yīng)的特征向量作為冗余類的特征空間的等價特征空間。

5)對譜分解得到的新的特征空間進行模糊C均值聚類算法，完成冗余類的合并，從而完成彩色圖像的分割。

2.3 實驗結(jié)果及分析

為了證明該算法的優(yōu)越性，在保證參數(shù)一致的情況下，分別將本文方法和傳統(tǒng)FCM方法應(yīng)用于UCI數(shù)據(jù)集中的iris、wine、balance和Berkeley庫中的彩色圖像，然后比較實驗結(jié)果。本文實驗環(huán)境為Win 7操作系統(tǒng)、Intel i7處理器、8G內(nèi)存，實驗平臺為MATLAB 2012。實驗所用Berkeley庫中圖像大小均為481*321。

2.3.1 UCI數(shù)據(jù)集分割結(jié)果

由于NMI(normalized mutual information)對于聚類效果具有很好的評價，所以選用NMI對UCI數(shù)據(jù)集進行聚類效果的評價，公式如下：

(11)

其中：

(12)

(13)

其中：X是UCI數(shù)據(jù)集分類結(jié)果的向量，Y是使用本文算法分割圖像后對數(shù)據(jù)集分類結(jié)果的向量。I(X;Y)是MI，H(X)和H(Y)是X和Y的信息熵。UCI數(shù)據(jù)集聚類結(jié)果對比如表1。

表1 UCI數(shù)據(jù)集聚類結(jié)果

以Balance數(shù)據(jù)為例，圖3和圖4分別為Balance數(shù)據(jù)冗余類的初始貼進度矩陣和標(biāo)準(zhǔn)貼進度矩陣的三維曲面圖。由圖可以看出標(biāo)準(zhǔn)貼近度矩陣比初始貼近度矩陣分布更均勻，更具有對稱性，更能體現(xiàn)冗余類之間的貼進度關(guān)系；從而作為譜聚類的相似度矩陣可以使聚類結(jié)果更合理。

圖3 初始貼進度矩陣的三維曲面圖

圖4 標(biāo)準(zhǔn)貼進度矩陣的三維曲面圖

2.3.2 Berkeley庫圖像分割結(jié)果

圖5為Berkeley庫中小鳥圖像的分割結(jié)果對比圖。從該圖像可以看出圖像四周背景顏色和樹枝、小鳥差不多，當(dāng)用FCM方法進行分割時由于沒有考慮全圖特性易陷入局部最優(yōu)，將四周一圈背景和小鳥分為了一類，而且易受噪音的干擾，而提出的算法抗噪性很好，且可以收斂到全局最優(yōu)，對圖像進行了很好的分割;當(dāng)分為2類的時候，F(xiàn)CM算法沒有將圖像4個角和小鳥，樹枝分開，提出的算法得到了很好的分割；當(dāng)分為3類的時候，從FCM算法對于圖像的分割結(jié)果中可以看出分割不均勻，小鳥類中有其他類的顏色，而提出的算法分割均勻，分割結(jié)果較好。

圖5 小鳥圖像分割結(jié)果

圖6為Berkeley庫中海星圖像的分割結(jié)果對比圖。圖6中海星的顏色分布不均，且背景顏色有陰影以及和海星顏色有差不多的地方，當(dāng)分為2類的時候，用FCM算法進行分割的時候很容易分割錯誤，沒有將海星完整的分割出來，并且背景中也會分割出一些和海星相同的區(qū)域來；而使用提出的算法進行分割，將海星很好的分割了出來；當(dāng)分為3類的時候，使用FCM算法分割的結(jié)果中背景和海星分割很不均勻，海星中有背景的分割顏色，背景中有海星的分割顏色；而使用提出的方法背景和海星得到了很好的分割且分割均勻。

圖6 海星圖像分割結(jié)果

3 結(jié)論

針對模糊C均值聚類算法的聚類結(jié)果對初始值很依賴，易陷入局部最優(yōu)，提出了將模糊C均值聚類算法與譜聚類相結(jié)合的算法應(yīng)用于彩色圖像分割。該方法先對圖像進行冗余加權(quán)模糊C均值聚類算法，將圖像分割成許多的冗余類，根據(jù)貼進度和傳遞閉包的定義和公式，將冗余類的類特征空間轉(zhuǎn)換為具有相似性和傳遞性的相似度矩陣，再對相似度矩陣進行譜聚類，從而完成冗余類的合并。通過實驗結(jié)果表明。該方法克服了模糊C均值算法初始化時必須確定聚類數(shù)的問題，同時使用譜聚類實現(xiàn)冗余類合并時考慮了特征的全局性，從而可以使聚類結(jié)果不易陷入局部最優(yōu)。因此，該算法對圖像分割具有較好的效果。

[1] 周東國，高 潮，郭永彩. 自適應(yīng)分層閾值的簡化PCNN紅外人體圖像分割[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報，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] 陳驥思，余艷梅，殷 宇,等. 自適應(yīng)快速FCM彩色圖像分割研究[J]. 計算機工程與應(yīng)用，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]. 計算機應(yīng)用，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。

國家自然科學(xué)基金(31571563)；北京市屬高等學(xué)校創(chuàng)新團隊建設(shè)與教師職業(yè)發(fā)展計劃項目；高可靠嵌入式系統(tǒng)技術(shù)北京市工程研究中心。

劉 雨(1991-)，女，河南商丘人，碩士，主要從事數(shù)據(jù)挖掘方向的研究。

周麗娟(1969-)，女，北京人，教授，主要從事數(shù)據(jù)倉庫和商務(wù)智能方向的研究。

1671-4598(2016)12-0168-04

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

TP3

A