基于空間距離的快速模糊C均值聚類算法

王軍玲 ，王士同 ，包 芳 ，周建林

1.江南大學 數字媒體學院，江蘇 無錫 214122

2.江蘇省信息融合軟件工程技術研發中心，江蘇 江陰 214405

3.江蘇省江陰職業技術學院 計算機科學系，江蘇 江陰 214405

1 引言

圖像分割被廣泛應用于諸多領域，例如機器視覺、目標識別、地理和醫學圖像等。一般說來圖像分割是根據灰度或者紋理信息等特征將圖像分割成一些連續不重疊區域的過程。模糊C均值聚類算法就是經典的圖像分割算法之一[1-4]，相對于硬性聚類[5]它的優點在于對每個像素引入了一個歸屬隸屬度，使得分割結果更符合現實狀況。但是在模糊C均值聚類算法中，它采用的是考察像素到聚類中心的歐幾里德距離，即它不考慮圖像紋理等任何臨近空間信息，使得算法對噪聲、孤立點很敏感。也有很多學者將考察像素臨近空間信息引入原始的FCM算法來改進分割性能[5-7]，Tolia和Panas提出了一個基于規則系統的Sugeno-type的FCM算法[6]以改進模糊分割結果。Pham[8]通過在隸屬度上引入一個空間懲罰機制，并且允許采用空間光滑隸屬度函數進行估計從而產生了類似于原始FCM的迭代算法。Ahmed[9]等人修正了FCM的目標函數用來彌補灰度分布不均衡并且將臨近元素的影響代入計算，即產生了FCM_S算法。由于FCM_S算法每次迭代的過程中臨近像素的信息都要參與運算無形中增加了時耗，陳宋燦[10]等提出了在進行迭代之前先計算出對應的均值濾波圖像或是中值濾波圖像以加快聚類速度，提出了FCM_S1、FCM_S2算法，兩種算法在一定程度上提高了算法的聚類性能。但是這幾種算法中都含有一個重要的參數a，參數的確定需要依據噪聲類型經過大量的實驗經驗來選擇，并且算法耗時隨著圖像變大而不斷增加。2007年，劉一光[11]等人提出的K-NS分類器在分類過程中，采用了空間距離公式使得分類器相對于經典的KNN算法[12]表現出了更好的性能。

針對以上的經典算法中所出現的問題，本文提出了基于空間距離的快速模糊C均值聚類算法，借鑒劉一光[11]等人的空間距離公式，使得臨近像素的灰度與位置信息同時參與考察像素與臨近像素間的相似度Sij的計算，利用該相似度得出臨近像素制約圖像，并對臨近信息制約圖像進行灰度統計后再聚類[13]，從而有效減少了聚類耗時，體現出了良好的分割性能。

2 FCM算法原理及其優化

FCM算法核心思想是首先將一個數據集X分為c個模糊組，然后求每組的聚類中心，當相似性指標的目標函數Jm達到最小時，元素就將被劃分給隸屬度最大的那個分組。FCM算法的目標函數如下所示[14]：

（1）設置c，m和ε的初始值。

（2）初始化模糊隸屬度矩陣U(0)。

（3）設置循環計算器b的值。

（4）使用U(b)更新這c個分組的中心：

（5）更新隸屬度矩陣U(b+1)：

（6）如果 {U(b)-U(b+1)}＜ε則停止計算；否則設置b=b+1，轉到（4）。

若算法應用于圖像分割則參與運算的是像素的灰度，可以看出該算法沒有考慮考察像素臨近像素的信息，圖像會受時間、光照及白噪聲的影響，從而導致這些受噪聲影響的像素被誤分類，即對孤立點敏感。

為了克服對孤立點敏感這一缺陷，也有學者將臨近像素的灰度信息引入目標公式，但是每次迭代都要計算考察像素的鄰近信息，具有代表性的如FCM_S算法，導致算法耗時量大。進一步優化的FCM_S1算法在算法開始迭代之前得到濾波圖像，然后原圖像和相應的均值濾波圖像同時參與算法的計算，不僅減少了運行時間并且增強了算法對高斯噪聲的抗干擾能力。然而，FCM_S1算法對受脈沖噪聲影響的圖像分割效果不太理想，FCM_S2算法使用中值濾波圖像來代替FCM_S1算法中的均值濾波圖像很好的解決了這個問題，但該算法對較強均勻噪聲的抵抗性較弱。綜上，由經典的FCM算法改進而來的FCM_S、FCM_S1和FCM_S2算法的共同點是都考慮了臨近像素的灰度信息，并采用參數a來控制其對考察像素的影響程度，這樣每個考察像素的臨近像素對其影響程度是一致的，都由a來決定，算法一定程度上減弱了噪聲點對分割結果的影響，但是現實中噪聲點分布狀況是隨機的，臨近像素對考察像素的影響也應因是否受噪聲干擾和位置差異而有所不同，所以算法對受不同噪聲干擾圖像分割的魯棒性還有待進一步提高。在這些經典的算法當中采用的都是歐幾里德距離，而歐幾里德距離對球體數據聚類具有較好的效果。劉一光學者提出的空間距離公式[11]在KNN算法中獲得了很好的分類效果，本文嘗試通過空間距離公式將臨近像素信息引入標準的FCM算法，從而來彌補噪聲分布不均勻等位置因素所帶來的缺陷，并且在對臨近制約圖像灰度統計的基礎上進行聚類，以適用于大圖像的分割。

3 空間距離公式

在FCM算法中都是單純的采用歐幾里德距離，通過不斷的迭代，使得聚在一類里面的像素灰度與中心像素灰度差別最小，而獲得最優結果。致使考察像素臨近像素信息無法包含在內，如果圖像受到噪聲干擾，將導致該像素誤分類。嘗試引入考察像素與臨近像素的相似度，將臨近像素的制約信息也代入目標公式以提高算法的抗干擾性能，要提出的新算法中相似度的計算采用了劉一光[11]等人提出的空間距離公式，不僅包含臨近像素的灰度信息并且包含了位置信息?？臻g距離公式[11]的原理如下所示。

3.1 空間距離

若把一條線或一個曲面看作流型拓撲空間，真實空間中相互獨立的若干元素通過一個具有足夠高階數的函數可以轉換到一個流型拓撲空間。依據給定的一組訓練樣本，可以得到多個拓撲空間同時包含這些點。

設sq為考察元素i的向量，Ni為任意k個向量元素組成的數據集；Mi是由Ni中的元素通過轉換函數得到的某個拓撲空間；Si是Ni中元素的分布空間；xij表示元素i的臨近數據集Ni中的第j個元素向量；數據集Ni與Mi之間的關系如圖1所示。

圖1 數據集Ni及其所形成的拓撲空間Mi關系圖

每個不同形式的Mi的重合部分幾乎都由空間Si包圍著，在空間Si中每個點都可以被近似看作是數據集 Ni中的一個元素，則在圖1中dsq→Ni是從sq到空間Si的距離。首先建立一個以Ni中元素向量為邊的一個超平面體，當Ni是列滿秩時，超平面體的容量是[]：

VNi和之間的關系如圖2中例子所示：

由公式（4）～（6）推出：

圖2 考察元素點向量sq到空間Mi距離的幾何展示

雖然的求解具有對稱性，但是它不滿足三角不等式[11，16]，因此不能作為樣本集合距離度量標準，需在核函數的作用下核化將空間距離公式轉化為可以使用的量度標準。

其中μ是用來量化正則化的程度；I是對應的單位矩陣。

3.2 空間距離公式的核化

從函數的角度分析，公式（8）在核函數 ker(x，y)(x，y∈Rn)的作用下可以滿足量度空間的要求：

其中 ker(x，y)是由φ(x)和φ(y)兩個映射確定的隱函數。對sq、x間的歐幾里德距離進行核化得：

空間距離核化時分別用φ(sq)和φ(Ni)代替公式（8）中的sq和x可以轉化為：

用公式（11）代替公式（8），Tikhonov正則化項μI用于避免核矩陣ker(Ni，Ni)線性相關，確保公式計算的穩定性。

4 SFGFCM算法

4.1 相似度Sij的計算

一些學者在2007年提出了相似度的計算，根據考察像素i與臨近像素j的灰度差與落在臨近窗口內所有臨近像素與考察像素灰度差的平均比值作為相似性度量來計算Sij，并且將其采用指數函數進行歸一化，則其定義為如下形式：

若將σ看作考察像素點到臨近像素點所形成曲面流型體的距離，采用上文提到的核化的空間距離公式將空間信息包含進來，即將臨近像素的位置信息也包含在內，進一步對相似性度量Sij進行優化，則可變化成如下形式：

4.2 SFGFCM算法

在引入臨近像素相似度Sij后可以得到一幅同時包含臨近像素空間灰度信息的臨近信息制約圖像ξ，圖像上像素點i的灰度值計算方式如下[18]：

表示像素i的臨近像素中的灰度最大值，ξi∈[0，255]表示臨近信息制約圖像中像素i的灰度值（顯然大于零），它同時包含原圖像中像素i的臨近像素灰度與空間信息。將臨近信息制約圖像的灰度級進行統計，并對處于同一灰度級的像素賦予相同的隸屬度，聚類的目標函數就變成了如下形式[19]：

SFGFCM算法的求解過程如下：

（1）初始化聚類中心數目c，模糊指數m和停止迭代最小差值條件ε；

（2）隨機初始化模糊劃分矩陣；

（3）設置迭代次數b=0；

（4）通過公式（16）更新聚類中心點灰度；

（5）通過公式（17）更新劃分隸屬度矩陣；

（6）當{U(b)-U(b+1)}＜ε算法收斂停止計算，否則，令b=b+1并且轉向（4）。

改進后的迭代算法類似于原始的FCM算法，但是參與聚類的灰度值包含了更多臨近像素空間及灰度信息，可以根據每個臨近像素的灰度及位置信息而計算出相似度Sij而無需過多的考慮平衡二者的關系問題。加之是對鄰近信息制約圖像的灰度統計后進行聚類，使得算法的聚類時間取決于鄰近信息制約圖像的灰度級數，而不是圖像的像素個數，從而該算法適用于大型圖像的分割。因為一般的圖像灰度是8位二進制碼（即256個灰度級），而一副圖像的灰度級數M遠遠小于圖像的像素個數N，執行時間將大大的降低。

5 實驗與性能分析

本章通過在真實和合成圖像上的分割性能和分割效率將FCM與文中的SFGFCM算法進行比較。實驗運行環境為CPU Inter雙核2.1 GHz，2 GB內存，Matlab7.1。

采用分割準確性SA對兩種算法的抗噪性能進行比較，這里的SA指被正確分割的像素點個數占參加圖像分割的像素點總數的比例[13]：

式中c是聚類數，Ai代表的是由算法劃分到第i組的像素集，Ci代表在涉及到的分割圖像中屬于第i組的像素集。

表1 被8%高斯噪聲干擾的syn圖像采用SFGFCM算法分割結果 （%）

圖3 被8%高斯噪聲干擾的syn圖像采用SFGFCM算法分割結果

表2 被8%均勻噪聲干擾的syn圖像采用SFGFCM算法分割結果 （%）

圖4 被8%均勻噪聲干擾的syn圖像采用SFGFCM算法分割結果

表3 被8%椒鹽噪聲干擾的syn圖像采用SFGFCM算法分割結果 （%）

圖5 被8%椒鹽噪聲干擾的syn圖像采用SFGFCM算法分割結果

實驗1首先用該算法對受不同性質（高斯噪聲，均勻噪聲和椒鹽噪聲）不同程度噪聲干擾的合成圖像syn進行分割，其中設置c=2。圖6顯示了被20%的高斯噪聲干擾的合成圖像syn，以及FCM、SFGFCM算法分割的效果?？梢杂^察到，FCM算法受到噪聲干擾較嚴重，SFGFCM算法幾乎可以不受噪聲影響，并且很好地保留了邊緣信息，體現出了其魯棒性。通過對SA%的計算（表4）更進一步說明了該優勢。

圖6 對合成圖像的分割效果

表4給出了兩種算法在合成圖像syn受到不同程度噪聲干擾的情況下的分割精度，每個實驗都采用了五組隨機初始化值，取其平均值作為實驗結果，數據很清楚的顯示出SFGFCM算法比FCM算法有較好的魯棒性。

表4 兩種算法在合成圖像上的分割精度（%）

實驗2從公式（13）可以看出，對噪聲和孤立點的抵抗性主要依賴于Sij的定義，在沒有噪聲的先驗知識的情況下，Sij是自動確定的而不是人工設定，被噪聲干擾的Sij應該是盡量的小，從而噪聲的干擾可以忽略。在SFGFCM算法中Sij對于不同的臨近像素可以自適應的改變，從而體現出較強的抗干擾性。孤立點和噪聲的出現主要有下兩種情況：

（1）考察像素不是噪聲點，而落在考察像素臨近窗口內的某些像素一定程度上受到了噪聲的干擾，那么受到噪聲干擾的像素灰度值和其他像素的灰度值差異性較大，根據公式（13）可知，相應的Sij值也應該小。因此計算出的加權和也會受到噪聲點的影響較小，體現出來的也就是對噪聲點和孤立點有較強的魯棒性。圖7是某像素3×3臨近窗口及對應像素的相似度，清晰地說明了這個問題，例如圖中第一個灰度值為100的像素在右邊框中對應的相似度Sij為0.123 1。

圖7 一個3×3的被噪聲干擾的窗口及對應的相似度

（2）當考察像素是一個噪聲點，而落在臨近窗口內的其他像素都是相似的，這樣的情況下由于考察像素到臨近像素點所形成流型空間的距離較大，從而導致臨近像素對應的Sij都較小且幾乎是相同的，因此計算出來的ξi受到的考察像素的影響較小，如圖8所示。

圖8 一個3×3的被噪聲干擾的窗口及對應的相似度

以上兩個例子驗證了新算法的魯棒性。

實驗3用兩種算法分別對受到30%椒鹽噪聲干擾的圖像進行圖像分割，最后的聚類分割效果如圖9、10所示。eight圖像分割過程中c=3；wheel圖像分割過程中c=4。從最后的實驗結果可以看出，FCM算法的分割效果很大程度上受到了椒鹽噪聲的影響，而本文提出的SFGFCM算法顯現出一定的抗干擾性。

圖9 兩種算法在圖像eight上的分割結果圖

圖10 兩種算法在圖像wheel上的分割結果圖

另外，采用這兩種算法對圖6～圖11中涉及到的圖像進行了分割。在實驗之前對這些圖像使用不同程度（8%、10%、15%）的高斯、均勻和椒鹽噪聲進行干擾，按照以下方法得出計算分數[13]：

其中c是聚類分組數，Ai代表的是受噪聲干擾圖像通過算法計算劃分到第i組的像素集合，Ci代表的是原圖像通過算法劃分到第i組的像素集合，r相當于是一個模糊相似度衡量，表明了Ai和Ci相等的程度，r越大越好。實驗結果如表5所示。

表5 兩種算法在各種圖像上的計算分數（%）

在表5中每個實驗都采用了五組不同的隨機初始值，被同類型噪聲干擾的圖像的計算分數取平均值，作為最后結果。

實驗4圖11則展示了本文所提算法在一些自然圖像上的分割效果，每組圖片中左邊是原圖，右邊顯示的是分割后的效果圖，每組圖片都隨機采用了五組不同的初始值，每次分割后效果都是一樣的。

實驗5最后在對各種算法進行相同的優化之后，圖12顯示了兩種算法的對不同大小圖像的平均耗時，每個大小的圖片都用采用五種不同的圖片和隨機的初始值，聚類的數目從2到5。從圖中可以看出文中的兩種算法隨圖像大小的耗時變化。

圖11 SFGFCM算法在自然圖像上的聚類分割結果

圖12 兩種算法對不同大小圖像的耗時

耗時除了受編程風格的影響，起決定性的還是算法的思想，FCM算法的時間復雜度是O(NcI1)（其中N是一幅圖像中像素的個數，c是聚類數目，I1是每次分割的迭代次數）；本文算法SFGFCM的算法復雜度是O(McI2)（其中M是一幅圖像中出現的灰度等級數，c是聚類數目，I2是每次分割的迭代次數）。同一幅圖像中，灰度等級最多是256，在一般規模的圖像中灰度等級數是遠小于像素的個數的，并且由于灰度的范圍都在[0，255]之間，從而采用不同的算法分割圖像最終的迭代次數不會有太大的差別（實驗顯示迭代次數只相差一兩次），因此算法的耗時就取決于N、M的大小，由此SFGFCM算法在保證了算法分割性能的同時，減少了時間損耗。

6 結束語

本文提出了一個基于空間距離的快速FCM算法（即SFGFCM），該算法采用空間距離計算出考察像素與其臨近像素的相似度Sij，使得在迭代計算的過程中不僅引入了臨近像素的灰度信息而且還隱含了臨近元素的位置信息，并且使得灰度與位置等空間信息得到了很好的平衡；在得到鄰近信息制約圖像之后對其灰度級進行統計之后進行聚類，從而使得聚類耗時大大減少。與傳統算法相比，不僅保證了圖像分割的性能，并且還減少了耗時；通過對一系列的合成和自然圖像進行分割實驗，與經典的FCM 算法相比，增強了對外界噪聲的抗干擾能力，具有更強的魯棒性，且該算法更適用于大幅圖像聚類。

[1]Udupa J K，Samarasekera S.Fuzzy connectedness and object definition：theory，algorithm and applicationsin image segmentation[J].Graph Models Imageprocess，1996，58（3）：246-261.

[2]Yamany S M，Farag A A，Hsu S.A fuzzy hyper spectral classifier for automatic target recognition（ATR）systems[J].Pattern Recognition Lett，1999，20：1431-1438.

[3]Yang M S，Hu Y J，Karen C R，et al.Segmentation techniques for tissue differentiation in MRI of ophthalmology using fuzzy clustering algorithms[J].Magnetic Resonance Imaging，2002，20（2）：173-179.

[4]Karmakar G C，Dooley L S.A generic fuzzy rule based image segmentation algorithm[J].Pattern Recognition Lett，2002，23（10）：1215-1227.

[5]Pham D L，Prince J L.An adaptive fuzzy c-means algorithm for image segmentation in the presence of intensity in homogeneities[J].Pattern Recognition Lett，1999，20：57-68.

[6]Tolias Y A，Panas S M.On applying spatial constraints in fuzzy image clustering using a fuzzy rule-based system[J].IEEE Signal Process Lett，1998，5：245-247.

[7]Liew A W C，Leung S H，Lau W H.Fuzzy image clustering incorporating spatialcontinuity[J].InstElec Eng Vis Image Signal Process，2000，147：185-192.

[8]Pham D L.Fuzzy clustering with spatial constraints[C]//IEEE Proceedings of the International Conference Image Processing，2002：65-68.

[9]Ahmed M N，Yam S M，Mohamed N，et al.A modified fuzzyC-means algorithm for bias field estimation and segmentation of MRI data[J].IEEE Trans on Med Imaging，2002，21：193-199.

[10]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.

[11]Liu Yiguang，Sam Shuzhi，Li Chunguang，et al.k-NS：a classifier by the distance to the nearest subspace[J].IEEE Transactions on Neural Networks，2011，22（8）：1256-1267.

[12]Cevikalp H，Larlus D，Douze M，et al.Local subspace classifiers：linear and nonlinear approaches[C]//Proc IEEE Workshop Mach Learn Signal Process，Thessaloniki，Greece，Aug 2007，2007：57-62.

[13]Krinidis S，Chatzis V.A robust fuzzy local information c-meansclustering algorithm[J].IEEE Transactionson Image Processing，2010，19（5）：1328-1337.

[14]Dunn J.A fuzzy relative of the ISODATA process and its use in detecting compact well separated clusters[J].Journal of Cybernetics，1974，3：32-57.

[15]Barth N.The gramian andk-volume inn-space：Some classical results in linear algebra[J].J Young Investigat，1999，2（1）：1-4.

[16]Deza E，Deza M M.Dictionary of distances amsterdam[M].the Netherlands：Elsevier，2006：262-272.

[17]Aster R，Borchers B，Thurber C.Tikhonov regularization[J].Parameter Estimate Inver Probl：Int Geophys，2005，90：89-118.

[18]Cai W，Chen S，Zhang D.Fast and robust fuzzy c-means clustering algorithms incorporating local information for image segmentation[J].Pattern Recognition，2007，40（3）：825-838.

[19]Szilagyi L，Benyo Z，Szilagyii S，et al.MR brain image segmentation using an enhanced fuzzyC-means algorithm[C]//Proceedings of the 25th Annual International Conference of IEEE EMBS，2003：17-21.

[20]趙磊，王斌，張立明.基于模糊C均值聚類和鄰域分析的無監督多通道遙感圖像變化檢測[J].數據采集與處理，2011，26（4）：397-401.