基于改進的Ｋ－均值聚類圖像分割算法

摘要：K-均值聚類是一種被廣泛應用的方法。本文提出了基于K-均值聚類的改進算法，并應用于圖像分割。針對K-均值聚類算法對離群點的反應過強的缺點，通過替換中心點，比較代價函數，來達到改進劃分結果的目的。實驗結果表明，該方法能有效改善聚類中心，提高分類精度和準確性。

關鍵詞：圖像分割；K-均值；聚類

中圖分類號：TP311文獻標識碼：A 文章編號：1009-3044(2008)16-21275-02

Image Segmentation Based-on an Improved K-Means Clustering Algorithm

LIU Juan， MAN Jia-ju

(College of Mathematics and Computer Science， Hunan Normal University， Changsha 410081， China)

Abstract: K-Means clustering is a very popular clustering technique which is widely used in numerous applications. This paper presents an improved algorithm for K-Means， and applied it in image segmentation. For the disadvantage of K-Means to the outlier， we improved the result on replacing the centroids and comparing the criterion function. An inspection of the results shows that this method significantly outperformed the K-Means in image segmentation.

Key words: Image segmentation; K-Means; Clustering

1 引言

圖像分割是一種重要的圖像分析工具，是從圖像處理到圖像分割的重要步驟，也是進一步圖像理解的基礎，在機器視覺、目標識別、醫學圖像處理中都有廣泛的應用。傳統的分割方法有閾值分割、邊緣檢測、基于區域的分割、基于形態學分水嶺的分割[1]。近年來，隨著各學科許多新理論和方法的提出，人們也提出了許多結合一些特定理論、方法和工具的分割技術[2]。

聚類是將數據對象分成類或簇的過程，使同一個簇中的對象之間具有很高的相似度，而不同簇中的對象高度相異。相異度根據描述對象的屬性值評估，通常使用距離度量。聚類源于許多研究領域，包括數據挖掘、統計學、生物學和機器學習[3]。而圖像分割恰好是將圖像的像素集進行分類的問題，自然地將聚類分析用于圖像之中[7，8]。

早在1979年，Coleman和Anderews提出用聚類算法進行圖像分割。K-均值聚類[4]是聚類方法中一種無監督自適應算法，能通過迭代對給定的數據進行分類，[5]中通過基于粗糙集理論的算法求出初始聚類的數目和均值，能有效提高分類準確性。但K-均值算法對于離群點是敏感的，因為一個具有很大的極端值的對象可能顯著地扭曲數據的分布。通過我們改進的K-均值算法，有效地消除了離群點對聚類結果的影響，提高了分類的精度。

2 K-均值聚類算法

2.1 數據集的c劃分

設數據集X={x1，x2，…，xn}是聚類分析對象的全體(稱為論域)，X中的每個對象xk(k=1，2， …，n) (稱為樣本)用有限個參數值來刻畫，每個參數值刻畫xk的某個特征。聚類分析就是分析論域X中n個樣本所對應的模式向量的相似性，按照各樣本間的親疏關系，產生X的c劃分。

數據集X的c劃分得到的c個子集X1，X2， …，Xc如果滿足下列條件，則稱之為X的硬c劃分：

■

Xi∩Xj=Φ， 對于i≠j

Φ■Xi ■X， 對于所有i

2.2 K-均值聚類

K均值聚類算法[4]是聚類中硬c劃分的一種，它以K為輸入參數，把N個對象的集合分成K個簇，使得結果簇內的相似度高，而簇間的相似度低。簇的相似度是關于簇中對象的均值度量，可以看作簇的質心或重心。它的核心思想如下：

算法隨機選擇K個對象，每個對象代表一個簇的初始均值或中心。對剩余的每個對象，計算其與各個簇中心的距離，根據使距離指標的目標函數最小的原則將它劃分到最相似的簇。然后重新計算各個簇的新均值，更新簇中心。這個過程不斷重復，直到準則函數收斂。

假設要聚成K個類，由人為決定K個類的中心C1(1)，C2(1)，C3(1)，……，Ck(1)，在第k次迭代中，樣本集{X}用如下方法分類：

對所有i=1，2， …，K， i≠j

■，則X∈Sj(k)

設Sj(k)的新的類中心為Cj(k+1)

令■最小，j=1，2， …，K

則■，Nj為Sj(k)中的樣本數。

對所有j=1，2， …，K，若Cj(k+1)=Cj(k)，則終止。否則，進入以上過程的循環。

3 改進的K-均值算法

由于K-均值算法對離群點的不適應，而平方誤差函數的使用更是嚴重惡化了這一影響。所以，我們可以使用絕對誤差標準來降低K-均值算法對離群點的敏感性。可以不采用簇中對象的均值作為參照點，而是在每個簇中選出一個實際的對象來替換該簇，其余的每個對象聚類到與其最相似的代表性對象所在的簇中。這樣，劃分方法仍然基于最小化所有對象與其對應的參照點之間的相異度之和的原則來執行。使用絕對誤差標準的定義如下：

■

其中，E是數據集中所有對象的絕對誤差之和；p是空間中的點，代表簇Cj中一個給定對象；Oj是簇Cj中的代表對象。通過算法的迭代，直到每個代表對象都成為它的簇的實際中心點，或最靠中心的對象。每當重新分配發生時，絕對誤差E的差對代價函數都會有影響。因此，如果當前的代表對象被非代表對象所取代，代價函數就計算絕對誤差值的差。交換的總代價時所有非代表對象所產生的代價之和。如果總代價是負的，則E將會減小，簇中心可以被隨機簇內點所取代；如果代價是正的，則當前的簇中心是可以接受的，在本次迭代中不會發生變化。算法如下：

①從給定數據中任意選擇K個對象作為初始聚類中心；

②根據平均距離和最小的原則進行分類；

③隨機選擇一個非中心點數據代替現有中心點；

④計算交換后的總代價函數值E；

⑤ifE＜0， then 用該數據替換現有中心點成為新的中心；

⑥until不再發生變化。

4 實驗結果分析

為驗證本文算法的有效性和正確性，我們采用Matlab編程環境進行基于改進的K-均值算法的仿真實驗。本文選用了不同分辨率的多對圖像進行檢驗，將K-均值聚類算法與本文改進的聚類算法的結果進行了對比。圖1(a)、圖2(a)為原始圖像，圖1(b)、圖2(b)為使用K-均值聚類的圖像，圖1(c)、圖2(c)為使用改進的K-均值算法聚類的圖像。從實驗結果看，本文算法得到的圖像效果較清晰，突出了目標區域，提高了分割精度。

5 結束語

本文在基于K-均值聚類算法的基礎上進行了改進，通過比較替換簇中心后絕對誤差值的差的代價函數，選擇最優的代表對象作為中心點，提高了聚類中心的精準度和分類的準確度，有效地改善了基于聚類方法的圖像分割結果，是一種有效的圖像分割算法。

參考文獻：

[1] Rafael C. Gonzalez， Richard E. Woods. Digital Image Processing[M]. New York: Prentice Hall， 2002.

[2] 章毓晉. 圖像分割[M]. 北京: 科學出版社， 2001.

[3] Jiawei Han， Micheline Kamber. Data Mining: Concepts and Techniques[M]. USA: Morgan Kaufmann， 2005.

[4] J. MacQueen. Some methods for classification and analysis of multivariate observations. In L. M. Le Cam and J. Neyman， editors， Proceedings of the 5'th Berkeley Symposium on Mathematical Statistics and Probability， volume 1， pages 281-297. U. California Press， 1967.

[5] 邵銳， 巫兆聰， 鐘世明. 基于粗糙集的K-均值聚類算法在圖像分割中的應用[J]. 測繪信息與工程， 2005， 30(5).

[6] 鄭洪英. 數據挖掘聚類算法的分析和應用研究[D]. 重慶: 重慶大學， 2002.

[7] T. Kanungo， D. M. Mount， and N. S. Netanyahu， et al. The Analysis of a Simple K-Means Clustering Algorithm[J]. Symposium on Computational Geometry， 2000， January.

[8] D. Selvathi， A. Arulmurgan， et al. MRI image segmentation using unsupervised clustering techniques. Computational Intelligence and Multimedia Applications， 2005. Sixth International Conference on Volume， Issue， 16-18 Aug. 2005: 105-110.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。