【導(dǎo)讀】行研究工作所取得的成果。除文中已注明引用的內(nèi)容外，本畢業(yè)設(shè)計(jì)（論文）不。包含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的作品成果。對本研究做出過重要貢。獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明并表示了謝意。處理就變得極其重要。而圖像分割通常是為了進(jìn)一步對圖像進(jìn)行分析、識別、跟。蹤、理解、壓縮編碼等，分割的好壞直接影響后期的圖像識別和理解。本文以圖像分割的聚類實(shí)質(zhì)為線索，對近幾年國內(nèi)外最新的圖像。分割算法進(jìn)行了分析比較，指出了聚類在這個領(lǐng)域的重要性。詳細(xì)介紹當(dāng)前圖像分割以及聚類分析的研究背景，現(xiàn)狀。對基于模糊K均值的圖像分割算法進(jìn)行探討，并對K均值算法進(jìn)行改進(jìn)，效率和分類的精度。割算法進(jìn)行對比分析。

　　

【正文】 本科生畢業(yè)設(shè)計(jì) (論文 ) 22 圖 KMeans 算法 例子過程圖 從上圖中，我們可以看到， A, B, C, D, E 是五個在圖中點(diǎn)。而灰色的點(diǎn)是我們的種子點(diǎn)，也就是我們用來找點(diǎn)群的點(diǎn)。有兩個種子點(diǎn)，所以 K=2。 然后， KMeans 的算法如下： 1. 隨機(jī)在圖中取 K（這里 K=2）個種子點(diǎn)。 2. 然后對圖中的所有點(diǎn)求到這 K 個種子點(diǎn)的距離，假如點(diǎn) Pi 離種子點(diǎn) Si最近，那么 Pi 屬于 Si 點(diǎn)群。（上圖中，我們可以看到 A,B 屬于上面的種子點(diǎn)，C,D,E 屬于下面中部的種子點(diǎn)） 3. 接下來，我們要 移動種子點(diǎn)到屬于他的 “ 點(diǎn)群 ” 的中心。（見圖上的第三步） 4. 然后重復(fù)第 2）和第 3）步，直到，種子點(diǎn)沒有移動（我們可以看到圖中的第四步上面的種子點(diǎn)聚合了 A,B,C，下面的種子點(diǎn)聚合了 D， E）。 求點(diǎn)群中心的算法 一般來說，求點(diǎn)群中心點(diǎn)的算法你可以很簡的使用各個點(diǎn)的 X/Y 坐標(biāo)的平均值。不過，我這里想告訴大家另三個求中心點(diǎn)的的公式： 1） Minkowski Distance 公式 —— λ 可以隨意取值，可以是負(fù)數(shù)，也可以是正數(shù)，或是無窮大。 南京郵電大學(xué)通達(dá)學(xué)院 2020 屆本科生畢業(yè)設(shè)計(jì) (論文 ) 23 () 2） Euclidean Distance 公式 —— 也就是第一個公式 λ=2 的情況 () 3） CityBlock Distance 公式 —— 也就是第一個公式 λ=1 的情況 () 這三個公式的求中心點(diǎn)有一些不一樣的地方，我們看下圖（對于第一個 λ 在 01之間）。 （ 1） Minkowski Distance （ 2） Euclidean Distance （ 3） CityBlock Distance 圖 三個公式的中心點(diǎn) 上面這幾個圖的大意是他們是怎么個逼近中心的，第一個圖以星形的方式，第二個圖以同心圓的方式，第三個圖以菱形的方式。 kmeans 圖像分割 根據(jù)算法編寫 Matlab 代碼（具體代碼見【附錄 A】），運(yùn)行得到的基于 k?均值聚類算法的圖像分割效果 圖及相應(yīng)的灰度直方圖。 南京郵電大學(xué)通達(dá)學(xué)院 2020 屆本科生畢業(yè)設(shè)計(jì) (論文 ) 24 原始圖像及其灰度直方圖 圖 聚類后圖像及其灰度直方圖 圖 繼續(xù)對多幅圖像用上述方法進(jìn)行 K均值聚類分割，得到如下圖像： 南京郵電大學(xué)通達(dá)學(xué)院 2020 屆本科生畢業(yè)設(shè)計(jì) (論文 ) 25 圖 南京郵電大學(xué)通達(dá)學(xué)院 2020 屆本科生畢業(yè)設(shè)計(jì) (論文 ) 26 圖 圖 圖 南京郵電大學(xué)通達(dá)學(xué)院 2020 屆本科生畢業(yè)設(shè)計(jì) (論文 ) 27 性能分析 主要優(yōu)點(diǎn)： （ 1）是解決聚類問題的一種經(jīng)典算法，簡單、快速。 （ 2）對處理大數(shù)據(jù)集，該算法是相對可伸縮和高效率的。 （ 3）當(dāng)結(jié)果類是密集的，而類與類之間區(qū)別明顯時 , 它的效果較好。 主要缺點(diǎn) （ 1）在 Kmeans 算法中 K 是事先給 定的，這個 K 值的選定是非常難以估計(jì)的。 （ 2）在 Kmeans 算法中，首先需要根據(jù)初始聚類中心來確定一個初始劃分，然后對初始劃分進(jìn)行優(yōu)化。 （ 3） Kmeans 算法需要不斷地進(jìn)行樣本分類調(diào)整 不斷地計(jì)算調(diào)整后的新的聚類中心 因此當(dāng)數(shù)據(jù)量非常大時 算法的時間開銷是非常大的。 （ 4） Kmeans 算法對一些離散點(diǎn)和初始 k 值敏感，不同的距離初始值對同樣的數(shù)據(jù)樣本可能得到不同的結(jié)果。 改進(jìn)的 k均值聚類圖像分割算法 K均值聚類算法中重要的一步是初始聚類中心的選取，一般是隨機(jī)選取待聚類樣本集的 K 個 樣本，聚類的性能與初始聚類中心的選取有關(guān)，聚類的結(jié)果與樣本的位置有極大的相關(guān)性。一旦這 K 個樣本選取不合理，將會增加運(yùn)算的復(fù)雜程度，誤導(dǎo)聚類過程，得到不合理的聚類結(jié)果。通過粗糙集理論提供 K均值聚類所需要的初始類的個數(shù)和均值，提高了聚類的效率和分類的精度。 于粗糙集理論的灰度空間劃分 。主要思想是在保持分類能力不變的情況下，通過知識約簡，導(dǎo)出問題的決策和分類規(guī)則 [4]。粗糙集理論能很好地近似分類。從圖像的直方圖可以看出 圖形一般呈谷峰狀分布，同一區(qū)域內(nèi)像素的灰度值比較接近，而且不同區(qū)域內(nèi)像素?cái)?shù)大小不等。若灰度值相差不大的像素可歸為一類，則可將圖像分為幾類。為此，定義像素的灰度南京郵電大學(xué)通達(dá)學(xué)院 2020 屆本科生畢業(yè)設(shè)計(jì) (論文 ) 28 值差為條件屬性，等價關(guān)系 R定義為：如果兩個像素灰度值差小于定間距 D，則兩個像素是相關(guān)的，屬于等價類，即 R一 {z||z。一 z， ID}(i， J一 0， 1， .， 255) 首先確定間距 D，通過原圖可求出灰度值分布范圍，根據(jù)灰度值范圍可求出灰度級數(shù) L。將灰度級范圍內(nèi)對應(yīng)像素個數(shù)最多的灰度值定義為中心點(diǎn) P。計(jì)算 L個中心點(diǎn)之兩兩間距，若最小距離小于間距 D，則將相應(yīng) 中心點(diǎn)合并，并將兩點(diǎn)的算術(shù)平均值作為該中心點(diǎn)的值。重復(fù)進(jìn)行直到所有中心點(diǎn)的兩兩間距均大于間距D。中心點(diǎn)的個數(shù)和數(shù)值就是 K_均值聚類所需要的初始類的個數(shù)和均值。 ( 0,1, , 2 5 5)pxp? ，其中 ()ijQ 為第 i次迭代后賦給類 j的像素集合 , j? 為第 j類的均值。 具體步驟如下： ① 將粗糙集理論提供的 L個中心點(diǎn) P作為初始類均值 (1)1? , (2)2? , , ()ll? 。 ② 在第 i 次迭代時，考察每個像素，計(jì)算它與每個灰度級的均值之間的間距，即它與聚類中心的距離 D，將每個像素賦均值距其最近的類，即 ? ?( ) ( )m in , ( 1 , 2 , )iip l p jD x D x j l??? ? ? ? () 則 ()ipjxQ? 。 ③對于 1,2,jl? ,計(jì)算新的聚類中心，更新類均值 :()( 1 ) 1/ijij j pxQNx???? ?，式中， jN 是 ()ijQ 中的像素個數(shù)。 ④將所有像素逐個考察，如果 1,2,jK? ，有 ( 1) ( )iijj??? ? ，則算法收斂，結(jié)束；否則返回②繼續(xù)下一次迭代。 ⑤ 以上聚類過程結(jié)束后，為了增強(qiáng)顯示效果，分割結(jié)果各像素以聚類中心 灰度值作為該類最終灰度 針對上圖，根據(jù)改進(jìn)后的 K均值聚類算法： 南京郵電大學(xué)通達(dá)學(xué)院 2020 屆本科生畢業(yè)設(shè)計(jì) (論文 ) 29 圖 由原圖像的灰度直方圖，本文將定間距 D 設(shè)為 32，灰度級 L 的個數(shù)為 8。原灰度圖的灰度值范圍為 [0， 255]，被分成 8 個灰度級，七個灰度級對應(yīng)中心點(diǎn)P 為 {32， 64， 96， 128， 160， 192， 224， 256}。計(jì)算這 12 個中心點(diǎn)之兩兩間距，若最小距離小于間距 20，則將相應(yīng)中心點(diǎn)合并，并將兩點(diǎn)的算術(shù)平均值作為該中心點(diǎn)的值，處理后結(jié)果為 P{32,160， 192} 下面將 c1(1)=32。c2(1)=c3(1)=192。作為初始聚類中心，編程進(jìn)行聚類分析。得到結(jié)果如下： 圖 圖三與圖一相比分類結(jié)果更好，圖像分割效果更明顯，更能表現(xiàn)圖像特征。邊緣更加清晰，分割結(jié)果既突出了目標(biāo)，又保留了細(xì)節(jié)信息，達(dá)到了較好的分割南京郵電大學(xué)通達(dá)學(xué)院 2020 屆本科生畢業(yè)設(shè)計(jì) (論文 ) 30 效果。因此，基于粗糙集的 K_均值聚類算法可以有效地對灰度圖像進(jìn)行分割，從分割后的圖像中可獲取更多的目標(biāo)信息，為進(jìn)一步的圖像分析和理解提供了良好的基礎(chǔ)。 繼續(xù)對多幅圖像用上述兩種方法進(jìn)行 K均值聚類 分割，得到如下對比圖像： K均值聚類得到的： 圖 根據(jù)改進(jìn)后的 K均值算法得到的： 南京郵電大學(xué)通達(dá)學(xué)院 2020 屆本科生畢業(yè)設(shè)計(jì) (論文 ) 31 圖 本章總結(jié) 基于粗糙集理論和 K均值聚類算法的圖像分割方法，比隨機(jī)選取聚類的中心點(diǎn)和個數(shù)減少了運(yùn)算量，提高了分類精度和準(zhǔn)確性，而且對于低對比度、多層次變化背景的圖像的形狀特征提取具有輪廓清晰、算法運(yùn)行速度快等特點(diǎn)，是一種有效的灰度圖像分割算 南京郵電大學(xué)通達(dá)學(xué)院 2020 屆本科生畢業(yè)設(shè)計(jì) (論文 ) 32 第四章 基于 FCM 算法的圖像分割 在前面第二章我們已經(jīng)介紹了 FCM算法，現(xiàn)在我們將 FCM算法用于圖像分割。 FCM 算法 用于圖像分割是將圖像中屬性相一致的象素進(jìn)行模糊聚類后對每類象素進(jìn)行標(biāo)定，從而實(shí)現(xiàn)圖像分割的。 模糊聚類的概念 在圖像處理的過程中，圖像處理的信宿是人，因此在對圖像進(jìn)行處理和識別 的過程中，必須充分考慮圖像自身的特點(diǎn)和人的視覺特性。一方面，目標(biāo)在投影 成圖像的過程中，由于各種因素的影響，造成了目標(biāo)物的像與干擾 (或其他物的 像 )具有某種程度相似性。另外，由于成像期間空間分辨率及各種光照條件的影 響，使目標(biāo)物的像的邊界與背景之間象素灰度具有中間過渡的性質(zhì)，使目標(biāo)物的 邊界具有模糊性，這種模糊性有時 可以強(qiáng)到使目標(biāo)像的某一部分與背景之間幾乎 融為一體的程度。另一方面，人的視覺對于圖像從黑到白的灰度級又是模糊而難 以區(qū)分的。這種不確定性和不精確性主要體現(xiàn)在圖像灰度的不確定性、幾何形狀 的不確定性和不確定性知識等。這種不確定性是經(jīng)典的數(shù)學(xué)理論無法解決的，并 且這種不確定性不是隨機(jī)的，因而不適于用概率論來解決。 人們發(fā)現(xiàn)模糊理論對于圖像的這種不確定性有很好的描述能力，所以可以引 入模糊集理論作為有效描述圖像特點(diǎn)和人的視覺特性的模型和方法，分析諸如人 的判斷、感知及辨識等行為。近年來一些學(xué)者致力于將模糊理論引 入到圖像處理 中，取得很好的效果。經(jīng)過專家學(xué)者幾十年的研究，圖像的模糊處理技術(shù)獲得極 大的發(fā)展。其中基于模糊理論的圖像分割是模糊理論在圖像處理中應(yīng)用比較完善 的一個領(lǐng)域。基于模糊理論的圖像分割方法主要可分為模糊閾值分割和模糊聚類 分割，其中模糊聚類分割方法是最先提出、也是最經(jīng)典的一種圖像模糊分割方法。 實(shí)際中應(yīng)用最為廣泛的模糊聚類方法是模糊 C均值算法 (Fuzzy CMeans)， 簡稱 FCM，本文中的模糊聚類算法也特指模糊 C 均值算法。 FCM 算法最先由 Dunn 提出，后經(jīng) Bezdek 改進(jìn)，并給出了 FuzzyCMeans Clustering 的基于最小二乘南京郵電大學(xué)通達(dá)學(xué)院 2020 屆本科生畢業(yè)設(shè)計(jì) (論文 ) 33 法原理的迭代優(yōu)化算法， Bezdek 又在中證明了它的收斂性，證明了該算法收 斂于一個極值。 FCM 算法采用迭代法優(yōu)化目標(biāo)函數(shù)來獲得對數(shù)據(jù)集的模糊分類， 算法具有很好的收斂性。采用模糊 C均值聚類的方法進(jìn)行圖像分割的優(yōu)點(diǎn)是 避免了設(shè)定閾值的問題，并且能解決閾值化分割難以解決的多個分支的分割問 題； FCM 適合于圖像中存在不確定性和模糊性的特點(diǎn)；同時 FCM算法是屬于無監(jiān)督 的分類方法，聚類過程中不需要任何人工的干預(yù)，很適合于自動分割的應(yīng)用領(lǐng)域。 利用 FCM 算法進(jìn)行圖像分割主要有以下難點(diǎn)和問題： (1)聚類類別數(shù) C的確定 在聚類進(jìn)行之前必需給定類的數(shù)目，否則聚類無法進(jìn)行。在實(shí)際應(yīng)用中，尤 其是自動化的系統(tǒng)中，這是不太現(xiàn)實(shí)的。均值聚類方法中最困難的是圖像分割的 類別數(shù)的確定。 (2)初始類中心、初始隸屬度矩陣的確定 模糊聚類分割方法必須給出初始聚類中心和確定初始隸屬度矩陣。根據(jù)數(shù)學(xué) 分析理論，任何一個迭代并且最后收斂的序列，如果迭代的初始值比較接近于最 后的收斂結(jié)果的話，收斂的速度會明顯提高，迭代次數(shù)也會較大幅度地減小。同 時，也因?yàn)榻咏詈蠼Y(jié)果，陷入其 它局部最優(yōu)的可能性減小。 另外，如果聚類迭代的初始值接近于某個局部極值的話，就很有可能最終陷 入局部極值，從而得不到全局最優(yōu)值。所以 FCM 算法對初始值相當(dāng)敏感。在沒 有任何先驗(yàn)知識也沒有任何輔助手段的情況下，系統(tǒng)可以采用隨機(jī)選取類中心的 辦法。但那樣就過于盲目，而且很容易陷入局部最優(yōu)，迭代收斂速度可能很低， 迭代的次數(shù)也可能會增加很多，這樣也就會增加計(jì)算時間。所以初始參數(shù)的確定 對于計(jì)算量的降低顯得尤其重要。然而目前尚無有效的理論指導(dǎo)，如何選擇合適 的聚類初始值仍然是一個難題。 (3)空間信息的使用 模糊均值聚類方法分割的另一個問題是它只考慮到了灰度特征或彩色圖像 的顏色特征，忽略了圖像中固有的豐富的空間信息，從而導(dǎo)致它對噪聲比較敏感， 而且使得分割出的區(qū)域往往不連續(xù)，導(dǎo)致本屬于同類的象素沒有連在一起，不能 形成有意義的子圖。如何有效地利用空間信息，提高分割質(zhì)量，同時又不至于大 幅增加計(jì)算量是一個很有意義