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

李棟+劉萌萌+郭莎

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

關(guān)鍵詞：K_means；聚類算法；圖像分割；數(shù)據(jù)挖掘；圖像處理

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

1 概述

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

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

2 傳統(tǒng)的K_means聚類算法思想

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

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

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

2.1 傳統(tǒng)K_means算法

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

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

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

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

步驟4：對于所有的歸類中心，多次重復步驟2和3循環(huán)更新后，若其函數(shù)收斂或達到最大更新次數(shù)，則算法結(jié)束歸類分類也結(jié)束，否則系統(tǒng)繼續(xù)循環(huán)更新。

2.2 傳統(tǒng)算法缺點

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

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

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

3 K_means算法的改進

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

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

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