淺談聚類算法在圖像分割中的應用

王平祿 董昱威

摘 要：聚類算法在圖像分割領域有廣泛的應用，本文通過對四種聚類算法的介紹與分析，深入了解其算法原理，以及其在圖像分割領域中的應用效果，通過四種的算法的比較，總結出了各個算法的優缺點。

關鍵詞：聚類算法；K均值；模糊聚類；均值漂移；近鄰傳播算法

隨著信息技術的高速發展，人們每天都處理大量的圖像信息，然而，不是圖像中的所有信息都是我們需要的，所以，這就需要我們進一步對圖像進行處理，得到能夠滿足人們需要的信息。這就需要我們通過技術手段把圖像中特定的信息從整體中分割出來，這便是圖像分割，即將輸入的圖像分割成若干有意義的目標區域[1]。近年來，聚類算法在圖像分割中有著廣泛的應用。目前比較經典的聚類算法有：K均值聚類，模糊聚類，均值漂移算法，近鄰聚類算法。

1 聚類算法

⑴K均值聚類。K均值算法是最經典的聚類算法。由于其簡單高效，是應用最廣泛的聚類算法。它的基本思想是：預先設定K類，隨機選中K個元素作為每一類的中心。計算其它元素與K個中心之間的聚類，根據距離的大小，歸入距離最小的類中。然后重新計算每一個類的中心值，即所有類中元素的平均值，得到新的中心值后。再次重新分類，不斷重復此過程，直到目標函數收斂。通常定義的目標函數為：

式中：p為對象空間中一個數據對象；mi為類ci的均值。

⑵模糊聚類。模糊聚類算法是由K均值聚類算法發展而來的。它的基本思想是：把所有元素分為C個模糊聚簇，求出每個簇的中心，使得非相似性指標的函數達到最小值。它在確定每一個元素時，不是K均值非0即1，而是使用0～1之間的數字來賦予元素隸屬于某一簇的程度。它的目標函數為：FCM聚類算法目標函數為：

式中：Xj表示樣本；N表示樣本數目，通常表示圖像像素數；C表示聚類數目； 是矢量Xj隸屬于第i類的隸屬度函數，滿足uij∈[0，1]且 ；Z表示聚類中心。

⑶均值漂移算法。均值漂移是一種不需要參數的無監督聚類方法。它的主要思想是，在概率空間中求解概率密度極值的最優算法。它讓每一個點漂移到密度函數局部最大值出，即均值漂移向量的方向是數據的密度梯度估計方向一致。[2]文獻[3]中對均值漂移算法原理的描述如下：假設核函數H如果滿足一定的統計矩約束概率密度函數，可以用于非參數概率密度估計，若樣本集{xi}n是依密度函數f（x）經過n次獨立抽樣得到的，則給出的密度函數估計為[4]：

其中，核函數滿足：

⑷近鄰聚類算法。近鄰傳播聚類算法是一種基于近鄰信息傳播的聚類算法，其目的是找到最優的類代表點集合，一個類代表點對應為實際數據集中的一個數據點，使得所有數據點到最近的類代表點的相似度之和最大。如果設數據點的相似度為數據點的歐式距離的負數，則妙算法的目標函數與經典的K中心聚類算法的目標函數一致。近鄰傳播聚類算法還有兩個重要的信息量參數，分別是responsibility和availability，r（i，k）表示從點i發送到候選聚類中心k的數值消息，反映k點是否適合作為i點的聚類中心。a（i，k）則從候選聚類中心k發送到i的數值消息，反映i點是否選擇k作為其聚類中心。r（i，k）與a（i，k）越強，則k點作為聚類中心的可能性就越大，并且i點隸屬于以k點為聚類中心的聚類的可能性也越大。對于任意數據點xi，計算所有數據點的r（i，k）和a（i，k）。

3 小結

K均值聚類由于其簡單高效，是應用最廣泛的聚類算法。但是它也有很多局限性，其中聚類類別的數目需要先驗知識，而初試聚類中心的選擇不同也對聚類最終結果有很大的影響，所以聚類的穩定性欠缺。

模糊聚類算法，也是比較普遍使用的聚類算法。一般情況下不需要人為干預和設定閾值，就可使圖像分割區域自動化。但是模糊聚類數目的確定也是個難題，需要先驗知識，而算法本身迭代過程計算量非常大，而算法對噪音比較敏感，所以，時常會出現過分割現象。

均值漂移算法是一種無需任何參數的聚類算法，對噪音有很好的魯棒性，可以處理任意形狀和特征空間的圖像，非常適用于真實世界中的圖像。但是該算法受核函數的影響比較大，由于核函數參數的設置問題，圖像會產生過分割或欠分割現象。

近鄰傳播聚類算法，相比較其它算法能更快的處理大規模數據，得到較好的聚類結果。它對數據形成的相似矩陣的對稱性沒有任何要求，所以其應用的范圍很大。但是對于一些本書具有復雜結構的數據集，近鄰傳播算法通常得不到合理的聚類結果。

[參考文獻]

[1]Gonzalez Rafael C，Woods Richard E，Eddins Steven L.Digital Image Processing.阮秋琦，等，譯.電子工業出版社，2005.

[2]王爽，夏玉，焦李成.基于均值漂移的自適應紋理圖像分割方法[J]. Journal of Software，2010，21（6）：1451-1461.

[3]沈占鋒，駱劍承，胡曉東，孫衛剛.高分辨率遙感影像多尺度均值漂移分割算法研究[J].武漢大學學報（信息科學版），2010，03：313-316.

[4]Comaniciu D， Meer P.Mean Shift： a Robust Approach Toward Feature Space Analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（5）：603-619.