基于改進(jìn)的K_means算法在圖像分割中的應(yīng)用

李棟+劉萌萌+郭莎

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

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

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）08-0166-03

1 概述

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

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

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

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

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

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

2.1 傳統(tǒng)K_means算法

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

步驟1：人為預(yù)先從所有對象中隨機(jī)選擇k個(gè)的歸類中心；

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

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

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

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

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

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

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

3 K_means算法的改進(jìn)

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

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

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