基于k均值聚類的圖像分割研究2012

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

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

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

4、應圖像中特定的、具有獨特性質的區(qū)域。為了辨識和分析圖像中的目標，需要將它們從圖像中分離提取出來，在此基礎上才有可能進一步對目標進行測量，對圖像進行利用。圖像分割就是把圖像分成各具特性的區(qū)域并提取出感興趣目標的技術和過程。現(xiàn)有的圖像分割方法主要分以下幾類：基于閾值的分割方法、基于區(qū)域的分割方法、基于邊緣的分割方法以及基于特定理論的分割方法等。1. 基于閾值的分割方法包括全局閾值、自適應閾值、最佳閾值等等。閾值分割算法的關鍵是確定閾值，如果能確定一個合適的閾值就可準確地將圖像分割開來。閾值確定后，將閾值與像素點的灰度值比較和像素分割可對各像素并行地進行，分割的結果直接給出圖像區(qū)域。全局閾值是指整幅

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

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

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

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

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

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

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

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

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

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

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

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

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

18、，1994，15(11)：21266.童星.王命延一種基于粗糙集的圖像邊緣檢測方法期刊論文-計算機與現(xiàn)代化 2009(10)7黃長專.王彪.楊忠圖像分割方法研究期刊論文-計算機技術與發(fā)展 2009(6)8 周萍. 改進的圖像分割遺傳K􀀁均值聚類算法 J . 海軍工程大學學報, 2009, 6, 21( 3) : 75-78. 9 張忠林, 曹志宇, 李元韜. 基于加權歐式距離的K􀀁means 算法研究 J . 鄭州大學學報: 工學版, 2010, 31( 1) : 89-92.10 11 附一：K-均值聚類改進前的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(' 圖三 聚類前的灰度圖像直方圖') img=double(img);for i=1:m*n c1(1)=25; c2(1)=125; c3(1)=200;%選擇三個初始聚類中心 r=abs(img-c

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

21、2(i)=sum(img(n_g)/length(n_g);%將所有低灰度求和取平均，作為下一個中間灰度中心 c3(i)=sum(img(n_b)/length(n_b);%將所有低灰度求和取平均，作為下一個高灰度中心 d1(i)=abs(c1(i)-c1(i-1);%聚類中心收斂準則 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);%最終的聚類中心 G=c2(i); B=c3(i); k=i; break; endendR G Bf

22、or i=1:m*n%判斷類別 r=abs(img-R); g=abs(img-G); b=abs(img-B);%計算各像素灰度與聚類中心的距離 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