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

　　

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