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

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

中圖分類號：TP18

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

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

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

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

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

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

2 改進的K-means算法

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

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

（1）初始化數據集M。

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

（3）計算所有類簇包含數據元素的個數，選擇其最多的一個類簇，標記為N。

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

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

（6）檢查是否將數據集M劃分為K個類簇，是則結束，否則轉至3）。

3 實驗分析

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

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

4 結束語

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

參考文獻：

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

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

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

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

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

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

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

作者單位：衡陽師范學院，湖南衡陽 421008

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