基于k均值聚類(lèi)的圖像分割研究2012VIP

1、 多媒體通信課程論文姓 名：嚴(yán)宏海班 級(jí): 075102學(xué) 號(hào)：專(zhuān) 業(yè): 通信工程 學(xué) 院：機(jī)械與電子信息學(xué)院指導(dǎo)老師: 劉 勇 日 期：2012年10月20日 k均值聚類(lèi)在彩色圖像分割中的應(yīng)用研究摘要 基于人類(lèi)視覺(jué)將圖像分割成若干個(gè)有意義的區(qū)域是目標(biāo)檢測(cè)和模式識(shí)別的基礎(chǔ)。 圖像分割屬于圖像處理中一種重要的圖像分析技術(shù)。圖像分割的傳統(tǒng)方法是對(duì)灰度圖像分割，處理圖像的亮度分量，簡(jiǎn)單快速。本論文首先介紹了傳統(tǒng)的圖像分割與K-均值聚類(lèi)算法分割，然后重點(diǎn)介紹一種基于K-均值聚類(lèi)算法的圖像改進(jìn)分割方法。在分析聚類(lèi)結(jié)果對(duì)初值依賴性的基礎(chǔ)上,對(duì)初值選取方法進(jìn)行了分析和研究,結(jié)合粗糙集理論和K-均值聚類(lèi)算法，

2、提出了一種圖像的粗糙聚類(lèi)分割方法，試驗(yàn)結(jié)果表明，其比隨機(jī)選取聚類(lèi)的中心點(diǎn)和個(gè)數(shù)，減少了運(yùn)算量，提高了分類(lèi)精度和準(zhǔn)確性。改進(jìn)的分割方法能夠?qū)崟r(shí)穩(wěn)定的對(duì)目標(biāo)分割提取，分割效果良好。引言根據(jù)抽象程度和處理方法的不同，圖像技術(shù)可以分為三個(gè)層次：圖像處理、圖像分析和圖像理解，這三個(gè)層次的有機(jī)結(jié)合也可以稱(chēng)為圖像工程。圖像處理是較低層的操作，主要在圖像像素級(jí)上進(jìn)行操作。有代表性的圖像處理技術(shù)包括圖像降噪、圖像編碼和圖像分割。圖像分割是一種關(guān)鍵的圖像處理技術(shù)。作為后續(xù)圖像分析和圖像理解的基礎(chǔ)，圖像分割技術(shù)一直是圖像理論發(fā)展的瓶頸之一。圖像分割在實(shí)際中的應(yīng)用非常廣泛，對(duì)圖像目標(biāo)的提取、測(cè)量都離不開(kāi)圖像分割，是圖

3、象處理、模式識(shí)別和人工智能等多個(gè)領(lǐng)域中一個(gè)十分重要且又十分困難的問(wèn)題。分割的準(zhǔn)確性直接影響后續(xù)任務(wù)的有效性，因此具有十分重要的意義。圖像分割又是一種特殊的圖像處理技術(shù)。像素級(jí)的圖像處理可以分成兩類(lèi)，一類(lèi)是針對(duì)像素值的處理，另一類(lèi)是把像素分類(lèi)的處理。圖像降噪技術(shù)、圖像編碼技術(shù)、數(shù)字水印技術(shù)等雖然各有其特點(diǎn)和應(yīng)用領(lǐng)域，但其實(shí)質(zhì)都是針對(duì)像素值的操作。不同于這些技術(shù)，圖像分割，其實(shí)質(zhì)是一個(gè)按照像素屬性（灰度、紋理、顏色等）進(jìn)行聚類(lèi)的過(guò)程。一圖像分割概述 圖像分割是一種重要的圖像分析技術(shù)。在對(duì)圖像的研究和應(yīng)用中，人們往往僅對(duì)圖像中的某些部分感興趣。這些部分常稱(chēng)為目標(biāo)或前景（其他部分稱(chēng)為背景）。它們一般對(duì)

4、應(yīng)圖像中特定的、具有獨(dú)特性質(zhì)的區(qū)域。為了辨識(shí)和分析圖像中的目標(biāo)，需要將它們從圖像中分離提取出來(lái)，在此基礎(chǔ)上才有可能進(jìn)一步對(duì)目標(biāo)進(jìn)行測(cè)量，對(duì)圖像進(jìn)行利用。圖像分割就是把圖像分成各具特性的區(qū)域并提取出感興趣目標(biāo)的技術(shù)和過(guò)程?，F(xiàn)有的圖像分割方法主要分以下幾類(lèi)：基于閾值的分割方法、基于區(qū)域的分割方法、基于邊緣的分割方法以及基于特定理論的分割方法等。1. 基于閾值的分割方法包括全局閾值、自適應(yīng)閾值、最佳閾值等等。閾值分割算法的關(guān)鍵是確定閾值，如果能確定一個(gè)合適的閾值就可準(zhǔn)確地將圖像分割開(kāi)來(lái)。閾值確定后，將閾值與像素點(diǎn)的灰度值比較和像素分割可對(duì)各像素并行地進(jìn)行，分割的結(jié)果直接給出圖像區(qū)域。全局閾值是指整幅

5、圖像使用同一個(gè)閾值做分割處理，適用于背景和前景有明顯對(duì)比的圖像。它是根據(jù)整幅圖像確定的：T=T(f)。但是這種方法只考慮像素本身的灰度值，一般不考慮空間特征，因而對(duì)噪聲很敏感。常用的全局閾值選取方法有利用圖像灰度直方圖的峰谷法、最小誤差法、最大類(lèi)間方差法、最大熵自動(dòng)閾值法以及其它一些方法。2基于邊緣的分割方法檢測(cè)灰度級(jí)或者結(jié)構(gòu)具有突變的地方，表明一個(gè)區(qū)域的終結(jié)，也是另一個(gè)區(qū)域開(kāi)始的地方。這種不連續(xù)性稱(chēng)為邊緣。不同的圖像灰度不同，邊界處一般有明顯的邊緣，利用此特征可以分割圖像。圖像中邊緣處像素的灰度值不連續(xù)，這種不連續(xù)性可通過(guò)求導(dǎo)數(shù)來(lái)檢測(cè)到。對(duì)于階躍狀邊緣，其位置對(duì)應(yīng)一階導(dǎo)數(shù)的極值點(diǎn)，對(duì)應(yīng)二階導(dǎo)

6、數(shù)的過(guò)零點(diǎn)(零交叉點(diǎn))。因此常用微分算子進(jìn)行邊緣檢測(cè)。常用的一階微分算子有Roberts算子、Prewitt算子和Sobel算子，二階微分算子有Laplace算子和Kirsh算子等。在實(shí)際中各種微分算子常用小區(qū)域模板來(lái)表示，微分運(yùn)算是利用模板和圖像卷積來(lái)實(shí)現(xiàn)。這些算子對(duì)噪聲敏感，只適合于噪聲較小不太復(fù)雜的圖像。3基于聚類(lèi)分析的圖像分割方法特征空間聚類(lèi)法進(jìn)行圖像分割是將圖像空間中的像素用對(duì)應(yīng)的特征空間點(diǎn)表示，根據(jù)它們?cè)谔卣骺臻g的聚集對(duì)特征空間進(jìn)行分割，然后將它們映射回原圖像空間，得到分割結(jié)果。其中，K均值、模糊C均值聚類(lèi)(FCM)算法是最常用的聚類(lèi)算法。K均值算法先選K個(gè)初始類(lèi)均值，然后將每個(gè)像

7、素歸入均值離它最近的類(lèi)并計(jì)算新的類(lèi)均值。迭代執(zhí)行前面的步驟直到新舊類(lèi)均值之差小于某一閾值。模糊C均值算法是在模糊數(shù)學(xué)基礎(chǔ)上對(duì)K均值算法的推廣，是通過(guò)最優(yōu)化一個(gè)模糊目標(biāo)函數(shù)實(shí)現(xiàn)聚類(lèi)，它不像K均值聚類(lèi)那樣認(rèn)為每個(gè)點(diǎn)只能屬于某一類(lèi)，而是賦予每個(gè)點(diǎn)一個(gè)對(duì)各類(lèi)的隸屬度，用隸屬度更好地描述邊緣像素亦此亦彼的特點(diǎn)，適合處理事物內(nèi)在的不確定性。利用模糊C均值(FCM)非監(jiān)督模糊聚類(lèi)標(biāo)定的特點(diǎn)進(jìn)行圖像分割，可以減少人為的干預(yù)，且較適合圖像中存在不確定性和模糊性的特點(diǎn)。二K均值聚類(lèi)分割算法2.1 聚類(lèi)將物理或抽象對(duì)象的集合分成由類(lèi)似的對(duì)象組成的多個(gè)類(lèi)的過(guò)程被稱(chēng)為聚類(lèi)。由聚類(lèi)所生成的簇是一組數(shù)據(jù)對(duì)象的集合，這些對(duì)象

8、與同一個(gè)簇中的對(duì)象彼此相似，與其他簇中的對(duì)象相異。聚類(lèi)分析又稱(chēng)群分析，它是研究（樣品或指標(biāo)）分類(lèi)問(wèn)題的一種統(tǒng)計(jì)分析方法。聚類(lèi)分析計(jì)算方法主要有如下幾種：劃分方法，層次方法，基于密度的方法，基于網(wǎng)格的方法，基于模型的方法。K-均值聚類(lèi)算法是著名的劃分聚類(lèi)分割方法。劃分方法的基本思想是：給定一個(gè)有N個(gè)元組或者紀(jì)錄的數(shù)據(jù)集，分裂法將構(gòu)造K個(gè)分組，每一個(gè)分組就代表一個(gè)聚類(lèi)，K<N。而且這K個(gè)分組滿足下列條件：（1） 每一個(gè)分組至少包含一個(gè)數(shù)據(jù)紀(jì)錄；（2）每一個(gè)數(shù)據(jù)紀(jì)錄屬于且僅屬于一個(gè)分組；對(duì)于給定的K，算法首先給出一個(gè)初始的分組方法，以后通過(guò)反復(fù)迭代的方法改變分組，使得每一次改進(jìn)之后的分組方案都

9、較前一次好，而所謂好的標(biāo)準(zhǔn)就是：同一分組中的記錄越近越好，而不同分組中的紀(jì)錄越遠(yuǎn)越好。2.2 K-均值聚類(lèi)算法的工作原理：K-means算法的工作原理：算法首先隨機(jī)從數(shù)據(jù)集中選取 K個(gè)點(diǎn)作為初始聚類(lèi)中心，然后計(jì)算各個(gè)樣本到聚類(lèi)中的距離，把樣本歸到離它最近的那個(gè)聚類(lèi)中心所在的類(lèi)。計(jì)算新形成的每一個(gè)聚類(lèi)的數(shù)據(jù)對(duì)象的平均值來(lái)得到新的聚類(lèi)中心，如果相鄰兩次的聚類(lèi)中心沒(méi)有任何變化，說(shuō)明樣本調(diào)整結(jié)束，聚類(lèi)準(zhǔn)則函數(shù) 已經(jīng)收斂。本算法的一個(gè)特點(diǎn)是在每次迭代中都要考察每個(gè)樣本的分類(lèi)是否正確。若不正確，就要調(diào)整，在全部樣本調(diào)整完后，再修改聚類(lèi)中心，進(jìn)入下一次迭代。這個(gè)過(guò)程將不斷重復(fù)直到滿足某個(gè)終止條件，終止條件可

10、以是以下任何一個(gè)： （1）沒(méi)有對(duì)象被重新分配給不同的聚類(lèi)。 （2）聚類(lèi)中心再發(fā)生變化。 （3）誤差平方和局部最小。2.3 K-means聚類(lèi)算法的一般步驟：處理流程：（1） 從 n個(gè)數(shù)據(jù)對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類(lèi)中心；（2） 循環(huán)（3）到（4）直到每個(gè)聚類(lèi)不再發(fā)生變化為止；（3） 根據(jù)每個(gè)聚類(lèi)對(duì)象的均值（中心對(duì)象），計(jì)算每個(gè)對(duì)象與這些中心對(duì)象的距離；并根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行劃分；（4） 重新計(jì)算每個(gè)（有變化）聚類(lèi)的均值（中心對(duì)象），直到聚類(lèi)中心不再變化。這種劃分使得下式最小 2.4 K-均值聚類(lèi)法的缺點(diǎn)： 缺點(diǎn): （1）在 K-means 算法中 K 是事先給定的，這個(gè) K

11、值的選定是非常難以估計(jì)的。 （2）在 K-means 算法中，首先需要根據(jù)初始聚類(lèi)中心來(lái)確定一個(gè)初始劃分，然后對(duì)初始劃分進(jìn)行優(yōu)化。（3） K-means算法需要不斷地進(jìn)行樣本分類(lèi)調(diào)整不斷地計(jì)算調(diào)整后的新的聚類(lèi)中心因此當(dāng)數(shù)據(jù)量非常大時(shí)算法的時(shí)間開(kāi)銷(xiāo)是非常大的。（4）K-means算法對(duì)一些離散點(diǎn)和初始k值敏感，不同的距離初始值對(duì)同樣的數(shù)據(jù)樣本可能得到不同的結(jié)果。三基于灰度空間的彩色圖像像素聚類(lèi) 1讀取彩色圖像，將RGB值轉(zhuǎn)化為灰度值 2. 利用k均值聚類(lèi)對(duì)像素的灰度值進(jìn)行劃分，提取特征點(diǎn)（本方法采用誤差平方和準(zhǔn)則函數(shù)判斷聚類(lèi)是否合理）。 3.利用matlab編程實(shí)現(xiàn)結(jié)果如下：隨即地取c1(1)=

12、15; c2(1)=100; c3(1)=150;%選擇三個(gè)初始聚類(lèi)中心得到最終聚類(lèi)中心的灰度值如下：R =36.4825 G =165.2593 B =232.4027 隨機(jī)選取聚類(lèi)中心的K-均值聚類(lèi)結(jié)果：圖一四改進(jìn)的k-均值聚類(lèi)圖像分割算法4.1 K-均值聚類(lèi)算法中重要的一步是初始聚類(lèi)中心的選取，一般是隨機(jī)選取待聚類(lèi)樣本集的K個(gè)樣本，聚類(lèi)的性能與初始聚類(lèi)中心的選取有關(guān)，聚類(lèi)的結(jié)果與樣本的位置有極大的相關(guān)性。一旦這 K個(gè)樣本選取不合理，將會(huì)增加運(yùn)算的復(fù)雜程度，誤導(dǎo)聚類(lèi)過(guò)程，得到不合理的聚類(lèi)結(jié)果。通過(guò)粗糙集理論提供 K-均值聚類(lèi)所需要的初始類(lèi)的個(gè)數(shù)和均值，提高了聚類(lèi)的效率和分類(lèi)的精度。 于粗糙

13、集理論的灰度空間劃分1.粗糙集的研究對(duì)象是由一個(gè)多值屬性集合描述的對(duì)象集合。主要思想是在保持分類(lèi)能力不變的情況下，通過(guò)知識(shí)約簡(jiǎn)，導(dǎo)出問(wèn)題的決策和分類(lèi)規(guī)則4。粗糙集理論能很好地近似分類(lèi)。從圖像的直方圖可以看出圖形一般呈谷峰狀分布，同一區(qū)域內(nèi)像素的灰度值比較接近，而且不同區(qū)域內(nèi)像素?cái)?shù)大小不等。若灰度值相差不大的像素可歸為一類(lèi)，則可將圖像分為幾類(lèi)。為此，定義像素的灰度值差為條件屬性，等價(jià)關(guān)系R定義為：如果兩個(gè)像素灰度值差小于定間距D，則兩個(gè)像素是相關(guān)的，屬于等價(jià)類(lèi)，即R一z|z。一z，I<D(i，J一0，1，.，255)首先確定間距D，通過(guò)原圖可求出灰度值分布范圍，根據(jù)灰度值范圍可求出灰度級(jí)數(shù)

14、L。將灰度級(jí)范圍內(nèi)對(duì)應(yīng)像素個(gè)數(shù)最多的灰度值定義為中心點(diǎn)P。計(jì)算L個(gè)中心點(diǎn)之兩兩間距，若最小距離小于間距D，則將相應(yīng)中心點(diǎn)合并，并將兩點(diǎn)的算術(shù)平均值作為該中心點(diǎn)的值。重復(fù)進(jìn)行直到所有中心點(diǎn)的兩兩間距均大于間距D。中心點(diǎn)的個(gè)數(shù)和數(shù)值就是K_均值聚類(lèi)所需要的初始類(lèi)的個(gè)數(shù)和均值。2.像素的灰度值為，其中為第 i次迭代后賦給類(lèi)j的像素集合, 為第 j類(lèi)的均值。 具體步驟如下： 將粗糙集理論提供的L個(gè)中心點(diǎn)P作為初始類(lèi)均值 ,。 在第次迭代時(shí)，考察每個(gè)像素，計(jì)算它與每個(gè)灰度級(jí)的均值之間的間距，即它與聚類(lèi)中心的距離 D，將每個(gè)像素賦均值距其最近的類(lèi)，即 (3.6)則。對(duì)于,計(jì)算新的聚類(lèi)中心，更新類(lèi)均值:，式

15、中，是中的像素個(gè)數(shù)。將所有像素逐個(gè)考察，如果，有 ，則算法收斂，結(jié)束；否則返回繼續(xù)下一次迭代。 以上聚類(lèi)過(guò)程結(jié)束后，為了增強(qiáng)顯示效果，分割結(jié)果各像素以聚類(lèi)中心灰度值作為該類(lèi)最終灰度針對(duì)上圖，根據(jù)改進(jìn)后的K-均值聚類(lèi)算法： 圖二由原圖像的灰度直方圖，本文將定間距D設(shè)為32，灰度級(jí)L的個(gè)數(shù)為8。原灰度圖的灰度值范圍為0，255，被分成8個(gè)灰度級(jí)，七個(gè)灰度級(jí)對(duì)應(yīng)中心點(diǎn)P為32，64，96，128，160，192，224，256。計(jì)算這12個(gè)中心點(diǎn)之兩兩間距，若最小距離小于間距20，則將相應(yīng)中心點(diǎn)合并，并將兩點(diǎn)的算術(shù)平均值作為該中心點(diǎn)的值，處理后結(jié)果為P32,160，192下面將c1(1)=32;c2

16、(1)=160;c3(1)=192;作為初始聚類(lèi)中心，編程進(jìn)行聚類(lèi)分析。得到結(jié)果如下： 圖三圖三與圖一相比分類(lèi)結(jié)果更好，圖像分割效果更明顯，更能表現(xiàn)圖像特征。邊緣更加清晰，分割結(jié)果既突出了目標(biāo)，又保留了細(xì)節(jié)信息，達(dá)到了較好的分割效果。因此，基于粗糙集的K_均值聚類(lèi)算法可以有效地對(duì)灰度圖像進(jìn)行分割，從分割后的圖像中可獲取更多的目標(biāo)信息，為進(jìn)一步的圖像分析和理解提供了良好的基礎(chǔ)。4.2 繼續(xù)對(duì)多幅圖像用上述兩種方法進(jìn)行K-均值聚類(lèi)分割，得到如下對(duì)比圖像：K-均值聚類(lèi)得到的：根據(jù)改進(jìn)后的K-均值算法得到的：試驗(yàn)表明，基于粗糙集理論和K-均值聚類(lèi)算法的圖像分割方法，比隨機(jī)選取聚類(lèi)的中心點(diǎn)和個(gè)數(shù)減少了運(yùn)

17、算量，提高了分類(lèi)精度和準(zhǔn)確性，而且對(duì)于低對(duì)比度、多層次變化背景的圖像的形狀特征提取具有輪廓清晰、算法運(yùn)行速度快等特點(diǎn)，是一種有效的灰度圖像分割算法。參考文獻(xiàn)1 林開(kāi)顏,吳軍輝,徐立鴻. 彩色圖像分割方法綜述J . 中國(guó)圖象圖形學(xué)報(bào), 2005, 10 (1) :1- 10.2滕升華. 黑白影像的彩色化研究D . 北京:中國(guó)科學(xué)院電子學(xué)研究所, 2006.3 章毓晉圖像分割M北京：科學(xué)出版社，200l4蔡煦，朱波，曾廣周一種彩色多級(jí)闖值的圖像分割方法及在形狀特征提取方面的應(yīng)用J山東大學(xué)學(xué)報(bào)(工學(xué)版)，2002，32(4)：3333365 吳國(guó)雄，陳武凡圖像的模糊增強(qiáng)與聚類(lèi)分割J小型微型計(jì)算機(jī)系統(tǒng)

18、，1994，15(11)：21266.童星.王命延一種基于粗糙集的圖像邊緣檢測(cè)方法期刊論文-計(jì)算機(jī)與現(xiàn)代化 2009(10)7黃長(zhǎng)專(zhuān).王彪.楊忠圖像分割方法研究期刊論文-計(jì)算機(jī)技術(shù)與發(fā)展 2009(6)8 周萍. 改進(jìn)的圖像分割遺傳K􀀁均值聚類(lèi)算法 J . 海軍工程大學(xué)學(xué)報(bào), 2009, 6, 21( 3) : 75-78. 9 張忠林, 曹志宇, 李元韜. 基于加權(quán)歐式距離的K􀀁means 算法研究 J . 鄭州大學(xué)學(xué)報(bào): 工學(xué)版, 2010, 31( 1) : 89-92.10 11 附一：K-均值聚類(lèi)改進(jìn)前的matlab源程序 RGB,map= imr

19、ead ('F:a.jpg'); %讀入imshow(RGB);title(' 圖一 原圖像')img=rgb2gray(RGB);m,n=size(img);figuresubplot(2,2,1),imshow(img);title(' 圖二 原圖像的灰度圖像')subplot(2,2,2),imhist(img);title(' 圖三 聚類(lèi)前的灰度圖像直方圖') img=double(img);for i=1:m*n c1(1)=25; c2(1)=125; c3(1)=200;%選擇三個(gè)初始聚類(lèi)中心 r=abs(img-c

20、1(i); g=abs(img-c2(i); b=abs(img-c3(i);%計(jì)算各像素灰度與聚類(lèi)中心的距離 r_g=r-g; g_b=g-b; r_b=r-b; n_r=find(r_g<=0&r_b<=0);%根據(jù)K的大小改變此處條件，尋找最小的聚類(lèi)中心 n_g=find(r_g>0&g_b<=0);%尋找中間的一個(gè)聚類(lèi)中心 n_b=find(g_b>0&r_b>0);%尋找最大的聚類(lèi)中心 i=i+1;%更新聚類(lèi)中心 c1(i)=sum(img(n_r)/length(n_r);%將所有低灰度求和取平均，作為下一個(gè)低灰度中心 c

21、2(i)=sum(img(n_g)/length(n_g);%將所有低灰度求和取平均，作為下一個(gè)中間灰度中心 c3(i)=sum(img(n_b)/length(n_b);%將所有低灰度求和取平均，作為下一個(gè)高灰度中心 d1(i)=abs(c1(i)-c1(i-1);%聚類(lèi)中心收斂準(zhǔn)則 d2(i)=abs(c2(i)-c2(i-1); d3(i)=abs(c3(i)-c3(i-1); if (d1(i)=0&&d2(i)=0&&d3(i)=0) R=c1(i);%最終的聚類(lèi)中心 G=c2(i); B=c3(i); k=i; break; endendR G Bf

22、or i=1:m*n%判斷類(lèi)別 r=abs(img-R); g=abs(img-G); b=abs(img-B);%計(jì)算各像素灰度與聚類(lèi)中心的距離 r_g=r-g; g_b=g-b; r_b=r-b; n_r=find(r_g<=0&r_b<=0); n_g=find(r_g>0&g_b<=0); n_b=find(g_b>0&r_b>0);img=uint8(img);img(find(r_g<=0&r_b<=0)=uint8(R);img(find(r_g>0&g_b<=0)=uint8(G);img(find(g_b>0&r_b>0)=uint8(B);endsubplot(2,2,3),imshow(img);titl