【正文】 原始圖像及其灰度直方圖聚類后圖像及其灰度直方圖 繼續(xù)對(duì)多幅圖像用上述方法進(jìn)行K均值聚類分割，得到如下圖像： 性能分析主要優(yōu)點(diǎn)：（1）是解決聚類問題的一種經(jīng)典算法，簡(jiǎn)單、快速。CityBlock Distance 三個(gè)公式的中心點(diǎn)上面這幾個(gè)圖的大意是他們是怎么個(gè)逼近中心的，第一個(gè)圖以星形的方式，第二個(gè)圖以同心圓的方式，第三個(gè)圖以菱形的方式。 ()2）Euclidean Distance公式——也就是第一個(gè)公式λ=2的情況 ()3）CityBlock Distance公式——也就是第一個(gè)公式λ=1的情況 ()這三個(gè)公式的求中心點(diǎn)有一些不一樣的地方，我們看下圖（對(duì)于第一個(gè)λ在01之間）。求點(diǎn)群中心的算法一般來說，求點(diǎn)群中心點(diǎn)的算法你可以很簡(jiǎn)的使用各個(gè)點(diǎn)的X/Y坐標(biāo)的平均值。（上圖中，我們可以看到A,B屬于上面的種子點(diǎn)，C,D,E屬于下面中部的種子點(diǎn)）3. 接下來，我們要移動(dòng)種子點(diǎn)到屬于他的“點(diǎn)群”的中心。然后，KMeans的算法如下：1. 隨機(jī)在圖中取K（這里K=2）個(gè)種子點(diǎn)。而灰色的點(diǎn)是我們的種子點(diǎn)，也就是我們用來找點(diǎn)群的點(diǎn)。 簡(jiǎn)單的例子介紹 KMeans算法主要解決的問題如下圖所示。更新步驟：計(jì)算cluster的均值，并將他作為新中心點(diǎn)。算法可以分為兩個(gè)步驟：分配步驟：將每個(gè)數(shù)據(jù)點(diǎn)歸類到離它最近的那個(gè)中心點(diǎn)所代表的 cluster 中。這個(gè)過程通常是針對(duì)具體的問題有一些啟發(fā)式的選取方法，或者大多數(shù)情況下采用隨機(jī)選取的辦法。m1,…,mkkmeans 算法基本步驟：（1） 從 n個(gè)數(shù)據(jù)對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類中心；（2） 根據(jù)每個(gè)聚類對(duì)象的均值（中心對(duì)象），計(jì)算每個(gè)對(duì)象與這些中心對(duì)象的距離；并根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行劃分；（3） 重新計(jì)算每個(gè)（有變化）聚類的均值（中心對(duì)象）；（4） 計(jì)算標(biāo)準(zhǔn)測(cè)度函數(shù)，當(dāng)滿足一定條件，如函數(shù)收斂時(shí)，則算法終止；如果條件不滿足則回到步驟（2）。假設(shè)有k個(gè)群組Si, i=1,2,...,k。這個(gè)過程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂。算法首先隨機(jī)地選擇k個(gè)對(duì)象，每個(gè)對(duì)象初始地代表了一個(gè)簇的平均值或中心。相似度的計(jì)算根據(jù)一個(gè)簇中對(duì)象的平均值來進(jìn)行。（3）人眼只能夠通過感知顏色的亮度、色調(diào)以及飽和度來區(qū)分物體，不能夠直接感覺紅、綠、藍(lán)三色的比例，此外，色調(diào)和飽和度與紅、綠、藍(lán)的關(guān)系是非線性的，因此，空間中對(duì)圖像進(jìn)行分析與處理難以控制其結(jié)果。但是，存在如下一些不足：（1）空間用紅、綠、藍(lán)三基色的混合比例定義不同的色彩，從而不同的顏色難以用準(zhǔn)確的數(shù)值來表示，定量分析比較困難。 彩色空間非常簡(jiǎn)單，彩色空間是一個(gè)立方體三維坐標(biāo)空間結(jié)構(gòu)，分別用紅、綠、藍(lán)表示三個(gè)坐標(biāo)軸。顏色空間的選擇應(yīng)盡可能與人類的視覺系統(tǒng)和心理感知一致。 本章主要介紹了聚類分析的概述以及定義，聚類分析的一般步驟，常見的聚類算法Kmeans 算法，D BSCAN 算法，STING算法，F(xiàn)CM算法，和常見的圖像分割方法，本章是該研究所需要的預(yù)備基礎(chǔ)知識(shí)。模糊C均值算法是在模糊數(shù)學(xué)基礎(chǔ)上對(duì)K均值算法的推廣，是通過最優(yōu)化一個(gè)模糊目標(biāo)函數(shù)實(shí)現(xiàn)聚類，它不像K均值聚類那樣認(rèn)為每個(gè)點(diǎn)只能屬于某一類，而是賦予每個(gè)點(diǎn)一個(gè)對(duì)各類的隸屬度，用隸屬度更好地描述邊緣像素亦此亦彼的特點(diǎn)，適合處理事物內(nèi)在的不確定性。K均值算法先選K個(gè)初始類均值，然后將每個(gè)像素歸入均值離它最近的類并計(jì)算新的類均值。．基于聚類分析的圖像分割方法　　 特征空間聚類法進(jìn)行圖像分割是將圖像空間中的像素用對(duì)應(yīng)的特征空間點(diǎn)表示，根據(jù)它們?cè)谔卣骺臻g的聚集對(duì)特征空間進(jìn)行分割，然后將它們映射回原圖像空間，得到分割結(jié)果。LoG算子和Canny算子是具有平滑功能的二階和一階微分算子，邊緣檢測(cè)效果較好，如圖4所示。 由于邊緣和噪聲都是灰度不連續(xù)點(diǎn)，在頻域均為高頻分量，直接采用微分運(yùn)算難以克服噪聲的影響。在實(shí)際中各種微分算子常用小區(qū)域模板來表示，微分運(yùn)算是利用模板和圖像卷積來實(shí)現(xiàn)。因此常用微分算子進(jìn)行邊緣檢測(cè)。圖像中邊緣處像素的灰度值不連續(xù)，這種不連續(xù)性可通過求導(dǎo)數(shù)來檢測(cè)到。這種不連續(xù)性稱為邊緣。對(duì)于給定的圖像，可以通過分析直方圖的方法確定最佳的閾值，例如當(dāng)直方圖明顯呈現(xiàn)雙峰情況時(shí)，可以選擇兩個(gè)峰值的中點(diǎn)作為最佳閾值。這時(shí)的閾值為自適應(yīng)閾值。這時(shí)可以根據(jù)圖像的局部特征分別采用不同的闞值進(jìn)行分割。常用的全局閾值選取方法有利用圖像灰度直方圖的峰谷法、最小誤差法、最大類間方差法、最大熵自動(dòng)閾值法以及其它一些方法。它是根據(jù)整幅圖像確定的：T=T(f)。閾值確定后，將閾值與像素點(diǎn)的灰度值比較和像素分割可對(duì)各像素并行地進(jìn)行，分割的結(jié)果直接給出圖像區(qū)域。對(duì)所有輸入?yún)⒘壳髮?dǎo)，使式（）達(dá)到最小的必要條件為： () 和 (). 基于閾值的分割方法包括全局閾值、自適應(yīng)閾值、最佳閾值等等。一個(gè)定義在空間X={x}上的隸屬度函數(shù)就定義了一個(gè)模糊集合A，或者叫定義在論域X={x}上的模糊子集 。隸屬度函數(shù)是表示一個(gè)對(duì)象x隸屬于集合A的程度的函數(shù)，通常記做μA(x)，其自變量范圍是所有可能屬于集合A的對(duì)象（即集合A所在空間中的所有點(diǎn)），取值范圍是[0,1]，即0=1，μA(x)=1。 模糊C均值算法是普通C均值算法的改進(jìn)，普通C均值算法對(duì)于數(shù)據(jù)的劃分是硬性的，而FCM則是一種柔性的模糊劃分。3）在攝動(dòng)有意義的情況下，根據(jù)模糊相似矩陣聚類，此類方法稱為基于攝動(dòng)的模糊聚類分析法。 模糊聚類算法的分類模糊聚類分析算法大致可分為三類[4]： 1）分類數(shù)不定，根據(jù)不同要求對(duì)事物進(jìn)行動(dòng)態(tài)聚類，此類方法是基于模糊等價(jià)矩陣聚類的，稱為模糊等價(jià)矩陣動(dòng)態(tài)聚類分析法。對(duì)模糊方法而言，在不同聚類中的向量隸屬函數(shù)值是相互關(guān)聯(lián)的。在基于概率算法的聚類方法中將使用概率密度函數(shù)，為此要假定合適的模型，模糊聚類算法的向量可以同時(shí)屬于多個(gè)聚類，從而擺脫上述問題。當(dāng)粒度較小時(shí)，聚類結(jié)果的質(zhì)量好，但處理的代價(jià)會(huì)增加。 STING 算法的性能取決于最底層單元的粒度，該粒度也決定著聚類結(jié)果的質(zhì)量。STING算法通過掃描一次數(shù)據(jù)庫(kù)來計(jì)算單元的統(tǒng)計(jì)信息，產(chǎn)生聚類的時(shí)間復(fù)雜度是On)，其中n為對(duì)象的數(shù)目。否則，檢索和進(jìn)一步處理相關(guān)單元中的數(shù)據(jù)，直到它們滿足查詢條件。這個(gè)過程反復(fù)進(jìn)行，直到達(dá)到底層。對(duì)當(dāng)前層次的每個(gè)單元，我們計(jì)算置信度區(qū)間或者估算其概率范圍，用以反映該單元與給定查詢的關(guān)聯(lián)程度，不相關(guān)的單元就不再考慮。 統(tǒng)計(jì)參數(shù)的使用可以按照以下自頂向下的基于網(wǎng)格的方法:首先，在層次結(jié)構(gòu)中選定一層作為查詢處理的開始點(diǎn)。當(dāng)數(shù)據(jù)被裝載進(jìn)數(shù)據(jù)庫(kù)時(shí)，底層單元的參數(shù)count、m、s, min和max直接進(jìn)行計(jì)算。 高層單元的統(tǒng)計(jì)參數(shù)可以很容易地從低層單元的計(jì)算得到。針對(duì)不同級(jí)別的分辨率，通常存在多個(gè)級(jí)別的矩形單元，這些單元形成了一個(gè)層次結(jié)構(gòu)，高層的每個(gè)單元被劃分為多個(gè)低一層的單元。 如果采用空間索引, DBSCAN 的計(jì)算復(fù)雜度是O(n log n ) 。 如果一個(gè)點(diǎn) P 的 E 2 鄰域包含多于M inP ts 個(gè)點(diǎn), 則創(chuàng)建一個(gè)以 P 作為核心對(duì)象的新簇 。2 .2. 2　 D BSCAN 算法DBSCAN 算法可以將足夠高密度的區(qū)域劃分為簇, 并可以在帶有 “噪聲” 的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類 。 k－means算法有很多變種，例如，k模算法用模代替簇的平均值，用新的相異性度量方法來處理分類對(duì)象，用基于頻率的方法來修改聚類的模。另外，kmeans算法不適用于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇。這可能不適用于某些應(yīng)用，例如涉及有分類屬性的數(shù)據(jù)。通常情況下，算法可以終止于局部最優(yōu)解。面對(duì)大規(guī)模數(shù)據(jù)集，該算法是相對(duì)可擴(kuò)展的，并且具有較高的效率。步驟 4) 若簇的質(zhì)心不再變化，則返回劃分結(jié)果，否則轉(zhuǎn)步驟2）.kmeans 算法嘗試找出使平方誤差函數(shù)值最小的k個(gè)劃分。 步驟 2) 計(jì)算對(duì)象與各個(gè)族的質(zhì)心的距離，將對(duì)象劃分到距離其最近的簇 。根據(jù)聚類結(jié)果的表達(dá)方式可以將聚類算法劃分為：硬Kmeans（HCM）算法、模糊Kmeans（FCM）算法和概率Kmeans 算法（PCM）。目標(biāo)函數(shù)J 其實(shí)就是每個(gè)數(shù)據(jù)點(diǎn)與所在簇的質(zhì)心的距離之和，所以，J值越小，簇就越緊湊，相對(duì)越獨(dú)立。 常見的聚類算法 Kmeans 算法Kmeans 聚類算法是給定類的個(gè)數(shù) K，利用距離最近的原則，將 N 個(gè)對(duì)象分到 K 個(gè)類中去，聚類的結(jié)果由 K 個(gè)聚類中心來表達(dá)，基于給定的聚類目標(biāo)函數(shù)（或稱聚類效果判別函數(shù)），算法采用迭代更新的方法，每一次迭代過程都是向目標(biāo)函數(shù)值減少的方向進(jìn)行；在每一輪中，依據(jù) k 個(gè)參照點(diǎn)將其周圍的點(diǎn)分別組成 k 個(gè)簇，而每個(gè)簇的幾何中心將被作為下一輪迭代的參照點(diǎn)，迭代使得選取的參照點(diǎn)越來越接近真實(shí)的簇幾何中心，使得類內(nèi)對(duì)象之間的相似性最大，類之間的相似性最小。領(lǐng)域?qū)＜疫€可以對(duì)聚類結(jié)果結(jié)合領(lǐng)域知識(shí)進(jìn)行進(jìn)一步的分析，從而加深樣本點(diǎn)和特征變量的認(rèn)識(shí)。 在得到了聚類譜系圖之后，領(lǐng)域?qū)＜覒{借經(jīng)驗(yàn)和領(lǐng)域知識(shí)，根據(jù)具體的應(yīng)用場(chǎng)合，決定閾值的選取。聚類算法的輸出一般是一個(gè)聚類譜系圖，由粗到細(xì)地反映了所有的分類情況；或者直接給出具體的分類方案，包括總共分成幾類，每類具體包含那些樣本點(diǎn)等等。聚類算法的目的就是獲得能夠反映 X 維空間中這些樣本點(diǎn)之間的最本質(zhì)的“簇成一團(tuán)”性質(zhì)。第二步是執(zhí)行聚類算法，獲得聚類譜系圖。在有些應(yīng)用場(chǎng)合還需要將得到的樣本矩陣進(jìn)行一些后處理工作。如果第一步就選擇了和聚類意圖根本無關(guān)的特征變量，那企圖得到良好的聚類結(jié)果則無異于緣木求魚。它的結(jié)果輸出是一個(gè)矩陣，矩陣的每一行是一個(gè)樣本，每一列是一個(gè)特征指標(biāo)變量。 第一步是特征抽取。在高維空間中聚類數(shù)據(jù)對(duì)象時(shí)非常有挑戰(zhàn)性的，特別是考慮到這樣的數(shù)據(jù)可能非常稀疏，而且高度偏斜。許多聚類三算法擅長(zhǎng)處理低維數(shù)據(jù)，可能只涉及兩到三維。開發(fā)對(duì)數(shù)據(jù)輸入順序布敏感的算法具有重要的意義。5）對(duì)于輸入記錄的順序不敏感一些聚類算法對(duì)于輸入數(shù)據(jù)的順序是敏感的。4）處理噪聲數(shù)據(jù)的能力絕大多數(shù)現(xiàn)實(shí)世界中的數(shù)據(jù)庫(kù)都包含了孤立點(diǎn)，空缺，未知數(shù)據(jù)或者錯(cuò)誤的數(shù)據(jù)。但是，一個(gè)簇可能是任意形狀的。3）發(fā)現(xiàn)任意形狀的聚類許多聚類算法基于歐幾里的距離或者曼哈坦距離度量來決定聚類。2）處理不同類型屬性的能力許多算法被設(shè)計(jì)用來聚類數(shù)值類型的數(shù)據(jù)。1) 可伸縮性許多聚類算法在小于200 個(gè)數(shù)據(jù)對(duì)象的小數(shù)據(jù)集合上工作得很好；但是，一個(gè)大規(guī)模數(shù)據(jù)庫(kù)可能包含幾百萬個(gè)對(duì)象，在這樣的大數(shù)據(jù)集合樣本上進(jìn)行聚類又可能會(huì)導(dǎo)致偏差的結(jié)果。 聚類是一個(gè)富有挑戰(zhàn)性的研究領(lǐng)域，它的潛在應(yīng)用提出了各自特殊的要求。顯然d(i,j) ,＝d(i,j) ，且d(i,j) , =0，因此可以得到形如()的矩陣。 數(shù)據(jù)矩陣與相異度矩陣 設(shè)聚類問題中有n個(gè)對(duì)象:(i=1,2,...,n)，對(duì)每個(gè)對(duì)象選擇了P個(gè)變量，用間隔尺度測(cè)定后，第i個(gè)對(duì)象的第j個(gè)變量的觀測(cè)值用表示，則這n個(gè)對(duì)象所有P個(gè)變量的觀測(cè)值可以看成是如下的 np 矩陣: （）矩 陣 ()常被稱為數(shù)據(jù)矩陣，它是對(duì)象－變量結(jié)構(gòu)的數(shù)據(jù)表達(dá)方式，其中 第i個(gè)對(duì)象的P個(gè)變量的觀測(cè)值可以記為向量:=T ()聚類中常用的另外一種數(shù)據(jù)結(jié)構(gòu)是相異度矩陣，它存儲(chǔ)的是n個(gè)對(duì)象兩兩之間的近似性，表現(xiàn)形式為一個(gè) nn 矩陣: ()其中 d(i,j) , 是對(duì)象 i 與對(duì)象 1 之間相異性的量化表示，通常它是一個(gè)非負(fù)的數(shù)值，當(dāng)對(duì)象 i 和對(duì)象 j 越相似和越“接近”， d(i,j) , 的值就越接近。要對(duì)數(shù)據(jù)對(duì)象進(jìn)行聚類，基于統(tǒng)計(jì)方法，其最重要的前提是要計(jì)算各個(gè)數(shù)據(jù)對(duì)象之間的距離—即相異度，針對(duì)不同的數(shù)據(jù)類型有不同的相異度計(jì)算方法。如神經(jīng)網(wǎng)絡(luò)方法。一個(gè)基于模型的算法可以通過構(gòu)造一個(gè)描述數(shù)據(jù)點(diǎn)空間分布的密度函數(shù)來確定具體聚類。STING 就是一個(gè)典型的基于網(wǎng)格的方法。所有聚類操作均是在這一網(wǎng)格結(jié)構(gòu)上進(jìn)行的。DBSCAN 就是一個(gè)典型的基于密度的方法，該方法根據(jù)密度閾值不斷增長(zhǎng)聚類。3．基于密度方法基于密度的聚類方法就是不斷增長(zhǎng)所獲得的聚類直到鄰近密度小于一定閾值為止。自上而下層次方法從所有對(duì)象均屬于一個(gè)組開始，每一次循環(huán)將其分解為更小的組，直到每個(gè)對(duì)象構(gòu)成一組或滿足終止條件為止。根據(jù)層次分解形成的方式，可以將層次方法分為自下而上（也稱凝聚方式）和自上而下（也稱分割方式）兩種類型。Kmedoid 聚類算法比Kmeans 聚類算法在處理異常數(shù)據(jù)和噪聲數(shù)據(jù)方面更為魯棒，但是前者的處理時(shí)間要比后者更大。Kmeans 聚類法在處理海量數(shù)據(jù)庫(kù)方面較有效，特別是對(duì)數(shù)值屬性處理，它對(duì)異常數(shù)據(jù)很敏感。一個(gè)好的劃分衡量標(biāo)準(zhǔn)通常就是同一個(gè)組中的對(duì)象彼此相近或相關(guān)，而不同組中的對(duì)象較遠(yuǎn)或差距較大。其中每個(gè)子集均代表一個(gè)聚類（K=n）。 沒有任何一種聚類技術(shù)（聚類算法）可以普遍適用于揭示各種多維數(shù)據(jù)集中所呈現(xiàn)出來的多種多樣的結(jié)構(gòu)，根據(jù)數(shù)據(jù)在聚類中積聚規(guī)則以及應(yīng)用這些規(guī)則的方法，有多種聚類算法。 定義 (Clustering analysis)：把一個(gè)給定的數(shù)據(jù)對(duì)象集合分成不同的簇,即在空間 X 中給定一個(gè)有限的取樣點(diǎn)集或從數(shù)據(jù)庫(kù)中取得有限個(gè)例子的集合，{xi}ni=1。 定義 (Cluster)：一個(gè)數(shù)據(jù)對(duì)象的集合。聚類分析通常是基于距離的，通過構(gòu)造一個(gè) m 維空間的距離函數(shù)，利用這個(gè)距離函數(shù)來進(jìn)行聚類。聚類的樣本是用度量指針的一個(gè)向量表示，即用多維空間的一個(gè)點(diǎn)來表示。第二章 聚類分析理論聚類分析是一種新興的多元統(tǒng)計(jì)方法，是當(dāng)代分類學(xué)與多元分析的結(jié)合。（2）介紹了