基于改進(jìn)的K—means聚類算法在圖像分割中的研究

摘 要：圖像分割是由圖像處理到圖像分析的關(guān)鍵步驟。傳統(tǒng)的K-means聚類算法在進(jìn)行圖像分割處理時，由于其算法本身的一些缺陷，使得圖像顏色像素在進(jìn)行聚類時會出現(xiàn)比較高誤分類率，為了降低這一比率本文將一種改進(jìn)的K-means聚類方法應(yīng)用于圖像分割研究中，取得了明顯的效果。

關(guān)鍵詞：K-means聚類；圖像分割；歐幾里得距離

中圖分類號：TP18

圖像分割技術(shù)在數(shù)字圖像處理領(lǐng)域是十分重要的一部分。近年來，研究人員不斷改進(jìn)原有的圖像分割方法并把其它學(xué)科的一些新理論和新方法用于圖像分割，提出了不少新的分割方法。

圖像分割就是把圖像分成若干個特定的、具有獨特性質(zhì)的區(qū)域并提出感興趣目標(biāo)的技術(shù)和過程。一般人們在研究一副圖像時，往往只對圖像中的某些部分感興趣。圖像分割就是借助場景圖像的特征信息將圖像劃分成一些有意義的區(qū)域，這些特征包括梯度、灰度、色彩和形狀等。另外，圖像分割作為從圖像處理到圖像分析的關(guān)鍵步驟，為更高層次的圖像理解奠定了基礎(chǔ)。

目前彩色圖像分割技術(shù)主要采用的方法有：直方圖閥值化，特征空間聚類分析方法，基于區(qū)域的方法，邊緣檢測，模糊技術(shù)和人工神經(jīng)網(wǎng)絡(luò)的方法等。其中特征空間聚類分析方法是一種不需先驗知識的統(tǒng)計方法，其具有算法簡單、快速，收斂性好等優(yōu)點，成為目前進(jìn)行圖像分割處理首選的方法之一。

1 傳統(tǒng)K-means聚類方法

K-means聚類方法是在1967年由Mac Queen提出的，是目前最流行的聚類分析方法之一。K-means算法的基本思想是從隨機撿取的K個聚類中心開始，根據(jù)歐幾里得距離把每個點分配到最接近其均值的聚類中，然后計算被分配到每個聚類的點的均值向量，并作為新的中心進(jìn)行遞歸，直到聚類中心不再發(fā)生變化。在這種分類情況下，同一類中的數(shù)據(jù)相似度最大，不同類間的數(shù)據(jù)差異性最大。

針對以上傳統(tǒng)的K-means算法思想，也存在著不少缺點，最主要的兩個缺陷在于：（1）初始聚類中心的選取直接影響最終的聚類結(jié)果，可能形成局部最優(yōu)解而聚類失?。唬?）聚類數(shù)目無法確定，只能根據(jù)以往經(jīng)驗進(jìn)行大概估計，這樣一般不能最佳的聚類效果。以下就針對初始聚類中心的選取對傳統(tǒng)的K-means算法進(jìn)行改進(jìn)。

2 改進(jìn)的K-means算法

由于聚類算法的目標(biāo)是要盡可能的將相似度越小的數(shù)據(jù)對象歸為一類，而將相似度越大的數(shù)據(jù)對象歸為不同類。因此，不同類別的聚類中心一般是相似度比較小的，即歐幾里得距離比較遠(yuǎn)的兩個數(shù)據(jù)對象。這樣選取出來的初始聚類中心才能達(dá)到比較好的聚類結(jié)果。根據(jù)此推論，初始聚類中心的選取，應(yīng)該盡量保證其之間的距離大。通常情況下樣本數(shù)據(jù)集是比較龐大的，我們可以采取逐一劃分依次確定聚類中心的方法：首先，我們按照經(jīng)驗給出我們要確定的聚類中心的個數(shù)K，接著，在數(shù)據(jù)集中找出距離最遠(yuǎn)的兩個數(shù)據(jù)對象作為最初的兩個聚類中心，對剩下的所有數(shù)據(jù)計算它們到這兩個中心的距離，按照距離最小劃分到離它們最近的聚類中心的所屬類中，這樣就把數(shù)據(jù)集劃分成了以這兩個數(shù)據(jù)對象為聚類中心的兩個類。接下來，對包含數(shù)據(jù)對象多的這個類以同樣的方法選出2個新的聚類中心并劃分成2個新的類，重復(fù)操作直到找出K個聚類中心為止。由于，每次劃分都是找相距最遠(yuǎn)的數(shù)據(jù)對象作為聚類中心，因此，通過以上方法所獲得的K個聚類中心兩兩之間有較大的距離。

對于初始聚類數(shù)據(jù)集M={x1，x2，x3，…，xm-1，xm}，有m個數(shù)據(jù)對象，從M中選擇K個數(shù)據(jù)對象作為初始聚類中心的具體步驟是：

（1）初始化數(shù)據(jù)集M。

（2）建立K個空類簇，對其中一個初始化為數(shù)據(jù)集M。

（3）計算所有類簇包含數(shù)據(jù)元素的個數(shù)，選擇其最多的一個類簇，標(biāo)記為N。

（4）計算N中兩兩數(shù)據(jù)對象之間的歐幾里得距離，找出其中距離最大的兩個數(shù)據(jù)對象xi和xj，將xi和xj標(biāo)記為X類和Y類，并填充到空類簇中。

（5）以xi和xj為聚類中心，分別計算N中剩余數(shù)據(jù)對象到xi和xj得歐幾里得距離，將它們劃分到離它們距離最小的類中。

（6）檢查是否將數(shù)據(jù)集M劃分為K個類簇，是則結(jié)束，否則轉(zhuǎn)至3）。

3 實驗分析

我們將改進(jìn)后的算法和傳統(tǒng)的K-means聚類算法進(jìn)行對比：對于圖像的分割結(jié)果，難免產(chǎn)生錯分的像素，而錯分像素數(shù)據(jù)是衡量圖像分割質(zhì)量的一個非常重要的數(shù)據(jù)標(biāo)準(zhǔn)。本文用具有代表性的5個圖像進(jìn)行兩種算法的聚類處理，最后統(tǒng)計出誤差概率如表1所示。

從表1我們可以看出本文改進(jìn)之后的K-means算法在對圖像顏色數(shù)據(jù)進(jìn)行聚類處理時，誤分類像素比率有明顯的降低。說明本文的算法在彩色圖像分割方面具有更好的優(yōu)越性，并具有一定的魯棒性。

4 結(jié)束語

從上面的實驗結(jié)果可以看出改進(jìn)之后的K-means聚類算法確實可以降低像素的誤分類率，但是降低的幅度比較小。因此，接下來的工作可以從K-means聚類的其他幾個缺陷處入手，結(jié)合其他學(xué)科多種方法來進(jìn)一步降低誤分率和提高算法的時間和空間效率。

參考文獻(xiàn)：

[1]Han J，Kamber M（加）.范明，孟小峰，譯.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機械工業(yè)出版社，2001：223-262.

[2]吳夙慧，成穎，鄭彥寧.K-means算法研究綜述[J].現(xiàn)代圖書情報技術(shù)，2011（05）：28-35.

[3]陳光平，王文鵬，黃俊.一種改進(jìn)初始聚類中心選擇的K-means算法[J].小型微型計算機系統(tǒng)，2012（33）：1320-1323.

[4]林開顏，吳軍輝，徐立鴻.彩色圖像分割方法綜述[J].中國圖象圖形學(xué)報，2005（10）：1-10.

[5]湯葉青.K-means算法的改進(jìn)研究[D].北京首都師范大學(xué)，2012：19-26.

[6]張玉芳，毛嘉莉，熊忠陽.一種改進(jìn)的K-means算法[J].計算機應(yīng)用，2003（23）：31-33.

作者簡介：姚麗君（1980-），女，陜西寶雞人，助教，本科，研究方向：圖形圖像處理。

作者單位：衡陽師范學(xué)院，湖南衡陽 421008

基金項目：衡陽師范學(xué)院科學(xué)基金項目（項目編號：12A20）。