基于改進的K_means算法在圖像分割中的應用

李棟+劉萌萌+郭莎

摘要：圖像分割是圖像處理中一種重要的圖像分析技術。對灰度圖像的分割，處理圖像的亮度分量又是圖像分割的基本方法。圖像分割方法對區域的目標檢測和模式識別有重要的意義。K_means算法是基于元素距離中心點的大小作為相似性度量的聚類算法。該文通過參數統計直方圖來預估中心點k值的個數，并根據直方圖峰值的位置來確定聚類中心的位置。該方法的初始聚類中心值與實際中心值相差不多，因此，大大減少了迭代次數，計算量更少。結果表明，改進K_Means聚類算法提高了圖像分割的效率，降低了K_means算法的時間復雜度和空間復雜度。

關鍵詞：K_means；聚類算法；圖像分割；數據挖掘；圖像處理

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2016）08-0166-03

1 概述

根據圖像處理方法和抽象程度的不同，圖像技術可以分為圖像理解、圖像分析和圖像處理三個層次，這三個層次的結合也稱為圖像工程。其中，最基本的操作是圖像處理，主要進行的操作是在像素級上的。圖像處理中比較有代表性的技術包括圖像降噪、圖像分割和圖像編碼。在圖像處理中，圖像分割是一種關鍵的技術，是圖像理解和圖像分析的基礎。圖像分割技術在圖像理論中一直是發展的瓶頸之一。圖像分割的應用非常廣，比如對圖像中目標的提取和測量都需要圖像分割。圖像分割是圖像處理、模式識別和人工智能等多個領域中一個十分重要且又十分困難的問題。后續任務的有效性直接取決于圖像分割的準確性。因此對圖像分割的研究具有十分重要的意義。

圖像分割[1-3]是一種比較特殊的圖像處理技術。圖像處理根據像素級別可以分成兩類，一類是針對像素值的處理，另一類是把像素分類的處理。圖像降噪技術、圖像編碼技術、數字水印技術等雖然各有其特點和應用領域，但其實質都是針對像素值的操作。圖像分割是指將圖像中有意義的特征或者需要應用的特征提取出來，以便進一步分析和研究。到目前為止，國內外學者已經提出了閾值法[4]、區域生長法[5]、遺傳算法[6]等方法解決圖像分割問題，取得了不少好的成果。不同于這些技術，本文提出一種基于改進的K_means算法，應用于圖像分割領域，解決K_means固有的缺陷，并且提高圖像分割的效率。

2 傳統的K_means聚類算法思想

K_means主要是基于劃分策略[9]，該方法在Data Mining領域中思想十分經典且用途廣泛。其方法的基本思想是：首先用戶根據以往經驗及專業知識等通過人機交互人為預先定義聚集初始數目k，系統在所有對象中隨機選擇k個作為最初的聚集中心，根據距離（相似度）分別將初始k個對象距離最近的其他對象跟其當前對象歸為一類。系統多次迭代該過程，逐次漸進更新各聚集中心的值，直至標準測度函數開始收斂為止。由于方差可以用來度量中心值和同類其他對象之間的偏離程度，也就是距離程度，所以一般該測度函數多采用方差表示，其定義如公式（1）所示：

其中K為預定義的歸類數目，[Xi]為簇Ci的平均值，也就是中心點值。

所獲得的聚類應滿足高內聚低耦合特性，即同一類內對象間距離??；不同類之間的對象相似度低。

2.1 傳統K_means算法

假設要把對象集D劃分為k個不同類，傳統k均值算法描述如下：

步驟1：人為預先從所有對象中隨機選擇k個的歸類中心；

步驟2：對于對象集中的任意一個對象，分別計算其到各個中心對象的相似度，選擇距離最小的那個對象作為該對象的同類對象，歸為同類；

步驟3：對于各個歸類中心的值，采用均值法更新；

步驟4：對于所有的歸類中心，多次重復步驟2和3循環更新后，若其函數收斂或達到最大更新次數，則算法結束歸類分類也結束，否則系統繼續循環更新。

2.2 傳統算法缺點

基于劃分的思想使得該算法易于理解且實現簡單，但是傳統方法在實現聚類分類對象時存在兩個主要缺點[10-11]：

1）首先該方法需要預先決定聚類的類數目，而在現實具體應用中類的數目是難以估計且難以準確確定的，不同的類數目往往在實現中可能會造成完全不同的分類結果。類的準確分類分數很難合理確定，尤其是對于復雜具有不確定性的未知對象樣本集，類數目的選擇需要根據以往的專業經驗和行業知識并經過多次試驗才能指定。為了取得較好的實驗效果，需多次試探不同歸類個數才能得到較為合理的類數目，這樣就使得類的數目難以確定。

2）在傳統算法中，需要先根據隨機選定的初始歸類中心進行初始劃分，然后進一步對該劃分進行不斷的優化。由于初始中心選擇的隨機性，在系統實現聚類時可能會導致完全不同的歸類結果，而實際的數據集不僅具有數據不確定性，且數據集中往往存在臟數據，算法實現中若取相互距離最遠的k個對象值分別代表不同的類別，極有可能會取到臟數據中的對象，也就是噪聲點，一開始的中心選取必然會影響到該數據集的聚類效果，容易使得聚類陷入局部最優，從而造成分割不準確，分割效果差的問題。

3 K_means算法的改進

針對算法固有的缺陷，近幾年越來越多的研究人員投入研究，楊善林[12]等人給出距離代價函數作為最佳聚類數的有效性檢驗函數，提出了一種新的k值優化算法，k從0到n個點遍歷，距離代價最小的k就是最終結果， 并且證明k最大為n的理論證明。但是該方法主要針對k值的優化，對于初始中心點沒有進行研究。

汪中[13]等人改進初始中心點的算法，采用基于密度初始化中心點算法，根據數據集的密度散步搜索出簇類中心，間接找到對象出現密集的區域。利用密度分布搜索到聚類中心，遍歷k，均衡化函數最小時對應個數為最優聚類個數k。解決了k需要人為指定并且原始中心隨機的問題，但是它的時間復雜度相應增大。

屈新懷[14]等人將初始中心位置設置在密集數據區域的中心，避免孤立點和噪聲的干擾，利用遺傳算法生成聚類個數k。該方法要進行基于密度的中心點選擇和遺傳算法，都增加了時間復雜度，對于實時性要求比較高的情況，該算法不適合。