【正文】 是非常微小的，以至于人的肉眼無法察覺的到的。數(shù)據(jù)挖掘技術(shù)是從上世紀 80年代開始發(fā)展起來的一門交叉學(xué)科，涉及到數(shù)據(jù)庫、統(tǒng)計學(xué)、人工智能和機器學(xué)習(xí)多個領(lǐng)域。 其中圖像分割 的目的 是為了 后續(xù) 對圖像進行分析、識別、跟蹤、理解、壓縮編碼等，分割的準確性直接影響后續(xù)任務(wù)的 效果 ，具有 極其重要 的意義。基本內(nèi)容 圖像處理一般指數(shù)字圖像處理。 （ 4）將基于模糊 K 均值的圖像分割算法與基于標準模糊 C 均值聚類的圖像分割算法進行對比分析。本文以圖像分割的聚類實質(zhì)為線索，對近幾年國內(nèi)外最新的圖像分割算法進行了分析比較，指出了聚類在這個領(lǐng)域的重要性。對本研究做出過重要貢獻的個人和集體，均已在文中以明確方式標明 并表示了謝意 。除文中已注明引用的內(nèi)容外，本畢業(yè)設(shè)計（論文）不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的作品成果。 圖像分割是指將一幅圖像分解成若干互不相 交區(qū)域的集合，其實質(zhì)是一個像素的聚類過程。 （ 3）對基于標準模糊 C 均值聚類的圖像分割算法進行了探討，研究了基于模糊聚 類的圖像分割方法中初始類別數(shù)的選取、初始類中心和初始隸屬度矩陣的確定等問題。又稱影像處理。 常見的處理有圖像數(shù)字化、圖像編碼、圖像增強、圖像復(fù)原、圖像分割和圖像分析等。聚類分析是數(shù)據(jù)挖掘研究方向的重要研究內(nèi)容之一，在識別數(shù)據(jù)的內(nèi)在結(jié)構(gòu)方面有極其重要的作用。 在一副圖像中，我們在通常情況下只是對其中的某些目標感興趣，它們通常在要分割的圖像中占據(jù)一定的區(qū)域，而且在某些特性上與周圍的圖像存在一定的差別。圖像分割的結(jié)果是圖像特征提取和識別等圖像理解的基礎(chǔ)，對圖像分割的研究一直是數(shù)字圖像處理技術(shù)的焦點和熱點。用四個條件進行數(shù)學(xué)描述，即 6： ①1njj SF? ?； ② ? ?,jiS S i j? ? ?； ③ ? ? ? ?,jP S TRUE j??； ④ ? ? ? ?,ijP S S F L A SE i j??。 圖像工程根據(jù)抽象程度和研究方法的不同分為三個層次：圖像處理、圖像分析和圖像理解。 圖像分割技術(shù)的發(fā)展與許多其它學(xué)科和領(lǐng)域，例如數(shù)學(xué)、物理、心理學(xué)、電子學(xué)、計算機科學(xué)等學(xué)科密切相關(guān)。新的分割算法還在不斷涌現(xiàn)。聚類問題是一個古老的問題，是伴隨人類的產(chǎn)生和發(fā)展而不斷深化的一個問題，有關(guān)聚類分析的理論和應(yīng)用的研究己有大量的文獻。 用普通數(shù)學(xué)方法進行分類的聚類法稱為普通聚類分析，而把應(yīng)用模糊數(shù)學(xué)方法進行分析的聚類分析稱為模糊聚類分析。 因為模糊理論對于圖像的這種不確定性有很好的描述能力，所以可以引入模糊理論作為有效描述圖像特點和人的視 覺特性的模型和方法。 因此，聚類分析就廣泛應(yīng)用于圖像分割之中。 FCM 算法首先是由 Ruspini 提出的，但真正有效的方法是由 Dunn 給出的。 FCM 算法采用迭代法優(yōu)化目標函數(shù)來獲得對數(shù)據(jù)集的模糊分類，算法具有很好的收斂性。在實際應(yīng)用中，尤其是自動化的系統(tǒng)中這是不太現(xiàn)實的。同時，也因為接近最后結(jié)果陷入其它局部最優(yōu)的可能性減小。所以初始參數(shù)的確定，對于計算量的降低顯得尤其重要。為了解決模糊聚類中大計算量的問題，降低計算時間，人們一般從三個方面來考慮：選擇接近最后結(jié)果的初始值，盡可能地減少迭代的次數(shù)；改進算法，減少每一輪迭代的計算量；設(shè)計快速的實現(xiàn)算法。如何有效地利用空間信息，提高分割質(zhì)量，同時又不至于大 幅增加計算量 是一個很有意義的研究課題。該方法不失為一種較好的后處理方法，它排除了分割圖中的不連 續(xù)性，使得各區(qū)域之間的邊界是封閉和連續(xù)的。 本文的主要工作 本文在介紹圖像分割的定義、方法、應(yīng)用及研究意義和研究現(xiàn)狀以及支持向量機的基礎(chǔ)理論之后做了如下任務(wù)： （ 1）詳細介紹當前圖像分割以及聚類分析的研究背景，現(xiàn)狀。聚 類分析是將分類對象置于一個多維空間中，依據(jù)樣本間關(guān)聯(lián)的度量標準將其自動分成幾個群組，且使同一群組內(nèi)的樣本相似，而屬于不同群組的樣本相異的一組 方法。 聚類分析 概述 迄今為止，聚類還沒有一個學(xué)術(shù)界公認的定義，這里給出 EverittIs 在 1974 年關(guān)于聚類所下的定義：一個類簇內(nèi)的實體是相似的，不同類簇的實體是不相似的；一個類簇是測試空間中點的會聚，同一類簇的任意兩個點間的距離小于不同類簇的任意兩個點間的距離；類簇可以描述為一個包含密度相對較高的點集的多維空間中的連通區(qū)域，它們借助包含密度相對較低的點集的區(qū)域與其他區(qū)域（類簇）相分離。聚類的目標是將數(shù)據(jù)聚集成類，使得類間的相似性最小，而類內(nèi)的相似性盡可能得大。給定需要劃分的個數(shù) k，一個劃分方法 創(chuàng)建一個初始劃分，然后利用循環(huán)再定位技術(shù)，即通過移動不同劃分中的對象來 改變劃分內(nèi)容。 PAM（圍繞中心對象進行劃分）方法是最初 提出的 Kmedoid 聚類 算法之一。自下而上的層次方法從每個對象均為一個單獨的組開始 , 逐步將這些組進行合并，直到組合并到了層次頂端或滿足終止條件為止。這種方法可以用于消除數(shù)據(jù)中的噪聲（異常數(shù)據(jù)）。這種方法主要優(yōu)點就是處理事件由于與數(shù) 據(jù)對象個數(shù)無關(guān)而僅與劃分對象空間的網(wǎng)格數(shù)相關(guān)，從而顯得 相對較快。它根據(jù)標準統(tǒng)計方法并考慮到“噪聲”或異常數(shù)據(jù)，可以自 動確定聚類個數(shù)，因此它可以產(chǎn)生很魯棒的聚類方法。許多基于內(nèi)存的聚類算法常使用以下兩種有代表性的數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)矩陣和 相異度矩陣。相異度矩陣是對象－ 對象結(jié)構(gòu)的一種數(shù)據(jù)表達方式。我們需要具有高度可伸縮性的算法。基于這樣的距離度量的算法趨向于發(fā)現(xiàn)具有相近尺度合密度的球狀簇。一些聚類算法對于這樣的數(shù)據(jù)敏感，可能導(dǎo)致低質(zhì)量的聚類結(jié)果。 6）高維性（ high dimensionality） 一個數(shù)據(jù)庫或者數(shù)據(jù)倉庫可能包含若干維或者屬性。 聚類分析的一般步驟 在實際應(yīng)用聚類分析中，根據(jù)有無領(lǐng)域知識參與可將整個過程分解為三個環(huán) 節(jié)，每個環(huán)節(jié)都有其明確的任務(wù)，這樣對于整個聚類分析的過程就會有更清晰的 認識，如圖 所示。選取特征的優(yōu)劣將直接影響以后的分析和決策。比如為了統(tǒng)一量綱就對變量進行標準化處理，這樣采用不同量綱的變量才具 有可比性；有些場合可能選擇的特征變量太多，不利于以后的分析和決策，這時 可以先進行降維處理；僅憑經(jīng)驗和領(lǐng)域知識選擇的特征變量有可能是相關(guān)的，進 行主成分分析就可以消除變量間的相關(guān)性，從而得到一些相互獨立的特征變量。這一步?jīng)]有領(lǐng)域?qū)＜业膮⑴c，它除了幾何知識外不考慮任何的領(lǐng)域知 識，不考慮特征變量在其領(lǐng)域中的特定含義，僅僅認為它是特征空間中一維而己。選定閾值之后，就能夠從聚類譜系圖上直接看出分類方案。 聚類效果的好壞用目標函數(shù) J表示 :11( , )ik ij j iijnj d x c??? ?? ， () 其中 ( , )ij j id x c是jx與 ic 之間的距離函數(shù)，如歐氏距離。 Kmeans 算法描述如 下： 南京郵電大學(xué)通達學(xué)院 2020 屆本科生畢業(yè)設(shè)計 (論文 ) 13 步驟 1) 隨機選取 k 個對象作為初始的簇的質(zhì)心 。當結(jié)果簇是密集 的，而簇與簇之間區(qū)別明顯時，它的效果較好。 但是， k－ means 算法只有在簇的平均值被定義的情況下才能使用。還有，它對于噪音和孤立點數(shù)據(jù)是敏感的。 DBSCAN 通過檢查數(shù)據(jù)庫中每個點的 E 2鄰域來尋找聚類 。 STING 算法 STING（ Statistical Information Grid)算法是一種基于網(wǎng)格的多分辨率聚 類方法，它將空間區(qū)域劃分為若干矩形網(wǎng)格單元。 這 些統(tǒng)計參數(shù)包括 :屬性無關(guān)的參數(shù) count；屬性相關(guān)的參數(shù) m(平均值 )， s(標準方差 )，min(最小值 )， max(最大值 )，以及該單元中屬性值遵循的分布 (distribution)類型，例南京郵電大學(xué)通達學(xué)院 2020 屆本科生畢業(yè)設(shè)計 (論文 ) 14 如正態(tài)分布、平均分布、指數(shù)分布或無 (如果分布未知 )。通常該層包含少量的單元。此時，如果滿足查詢條件，那么返回相關(guān)單元的區(qū)域。在層次結(jié)構(gòu) 建好后，查詢處理的時間復(fù)雜度是 O(g)，其中 g 是最低網(wǎng)格單元的數(shù)目， 通常遠遠小于 n 。 模糊聚類算法 模 糊聚類算法概述 模糊聚類算法是一種基于函數(shù)最優(yōu)方法的聚類算法，使用微積分計算技術(shù)求最優(yōu)代價函數(shù)。硬聚類可以看成是模糊聚類方法的一個特例。 FCM 算法 FCM 算法是一種基于劃分的聚類算法，它的思想就是使得被劃分到同一簇的對象之間相似度最大，而不同簇之間的相似度最小。μ A(x)=1 表示 x 完全隸屬于集合 A，相當于傳統(tǒng)集合概念上的 x∈ A。閾值分割算法的關(guān)鍵是確定閾值，如果能確定一個合適的閾值就可準確地將圖像分割開來。但是這種方法只考慮像素本身的灰度值，一般不考慮空間特征，因而對噪聲很敏感。實際處理時，需要按照具體問題將圖像分成若干子區(qū)域分別選擇閾值，或者動態(tài)地根據(jù)一定的鄰域范圍選擇每點處的閾值，進行圖像分割。 ． 基于邊緣的分割方法 檢測灰度級或者結(jié)構(gòu)具有突變的地方，表明一個區(qū)域的終結(jié)，也是另一個區(qū)域開始的地方。對于階躍狀邊緣，其位置對應(yīng)一階導(dǎo)數(shù)的極值點，對應(yīng)二階導(dǎo)數(shù)的過零點 (零交叉點 )。這些算子對噪聲敏感，只適合于噪聲較小不太復(fù)雜的圖像。其中 loG算子是采用 Laplacian 算子求高斯函數(shù)的二階導(dǎo)數(shù)， Canny算子是高斯函數(shù)的一階導(dǎo)數(shù)，它在噪 聲抑制和邊緣檢測之間取得了較好的平衡 。迭代執(zhí)行前面的步驟直到新舊類均值之差小于某一閾值。 南京郵電大學(xué)通達學(xué)院 2020 屆本科生畢業(yè)設(shè)計 (論文 ) 19 第三章 基于 Kmeans 算法的圖像分割方法 對于 彩色圖像的 研究都 是在特定的顏色空間進行的，常用的顏色空間有RGB 、 HSI 、 YCbCr 等 。任何顏色都落入 RGB 彩色立方體內(nèi)。 定義和概述 南京郵電大學(xué)通達學(xué)院 2020 屆本科生畢業(yè)設(shè)計 (論文 ) 20 kmeans 算法是一種得到最廣泛使用的基于劃分的 聚類算法 ，把 n 個對象分為 k 個簇，以使簇內(nèi)具有較高的相似度。對剩余的每個對象根據(jù)其與各個簇中心的距離，將它賦給最近的簇，然后重新計算每個簇的平均值。 μi 是群組 Si 內(nèi)所有元素 xj 的重心，或叫中心點。因為前面說過 kmeans 并不能保證全局最優(yōu)，而是否能收斂到全局最優(yōu)解其實和初值的選取有很大的關(guān)系，所以有時候我們會多次選取初值跑 kmeans ，并取其中最好的一次結(jié)果 。公式如下： () 重復(fù)迭代上面的兩個步驟，直到算法收斂，既分配步驟的分配不會再改變。有兩個種子點，所以 K=2。（見圖上的第三步） 4. 然后重復(fù)第 2）和第 3）步，直到，種子點沒有移動（我們可以看到圖中的第四步上面的種子點聚合了 A,B,C，下面的種子點聚合了 D， E）。 （ 1） Minkowski Distance （ 2） Euclidean Distance （ 3） CityBlock Distance 圖 三個公式的中心點 上面這幾個圖的大意是他們是怎么個逼近中心的，第一個圖以星形的方式，第二個圖以同心圓的方式，第三個圖以菱形的方式。 （ 3）當結(jié)果類是密集的，而類與類之間區(qū)別明顯時 , 它的效果較好。 （ 4） Kmeans 算法對一些離散點和初始 k 值敏感，不同的距離初始值對同樣的數(shù)據(jù)樣本可能得到不同的結(jié)果。 于粗糙集理論的灰度空間劃分 。若灰度值相差不大的像素可歸為一類，則可將圖像分為幾類。計算 L個中心點之兩兩間距，若最小距離小于間距 D，則將相應(yīng) 中心點合并，并將兩點的算術(shù)平均值作為該中心點的值。 具體步驟如下： ① 將粗糙集理論提供的 L個中心點 P作為初始類均值 (1)1? , (2)2? , , ()ll? 。 ⑤ 以上聚類過程結(jié)束后，為了增強顯示效果，分割結(jié)果各像素以聚類中心 灰度值作為該類最終灰度 針對上圖，根據(jù)改進后的 K均值聚類算法： 南京郵電大學(xué)通達學(xué)院 2020 屆本科生畢業(yè)設(shè)計 (論文 ) 29 圖 由原圖像的灰度直方圖，本文將定間距 D 設(shè)為 32，灰度級 L 的個數(shù)為 8。c3(1)=192。因此，基于粗糙集的 K_均值聚類算法可以有效地對灰度圖像進行分割，從分割后的圖像中可獲取更多的目標信息，為進一步的圖像分析和理解提供了良好的基礎(chǔ)。一方面，目標在投影 成圖像的過程中，由于各種因素的影響，造成了目標物的像與干擾 (或其他物的 像 )具有某種程度相似性。這種不確定性是經(jīng)典的數(shù)學(xué)理論無法解決的，并 且這種不確定性不是隨機的，因而不適于用概率論來解決。其中基于模糊理論的圖像分割是模糊理論在圖像處理中應(yīng)用比較完善 的一個領(lǐng)域。 FCM 算法采用迭代法優(yōu)化目標函數(shù)來獲得對數(shù)據(jù)集的模糊分類， 算法具有很好的收斂性。均值聚類方法中最困難的是圖像分割的 類別數(shù)的確定。 另外，如果聚類迭代的初始值接近于某個局部極值的話，就很有可能最終陷 入局部極值，從而得不到全局最優(yōu)值。所以初始參數(shù)的確定 對于計算量的降低顯得