5.2 常用的圖像聚類分割算法

在圖像分割中，根據(jù)圖像中要處理的數(shù)據(jù)、分割的目的以及用途，可選取不同的聚類算法以實(shí)現(xiàn)圖像分割的目的，目前常用于圖像分割的聚類算法大體上可分為劃分聚類算法、層次聚類算法、基于密度的聚類算法、基于模型的聚類算法以及基于網(wǎng)格的聚類算法。

5.2.1 劃分聚類算法

劃分聚類算法采用目標(biāo)函數(shù)最小化策略把一個(gè)確定的N個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集分成k個(gè)組，并且該算法使得每一組中的對(duì)象相似度相當(dāng)高，而不同組的對(duì)象相似度比較低，由此可知相似度的定義是劃分聚類算法的關(guān)鍵環(huán)節(jié)。該算法的目標(biāo)函數(shù)一般定義為式（5-5），其中x_i表示對(duì)象空間中一個(gè)數(shù)據(jù)對(duì)象，且x_i是第i類的均值，J為集合A中全部對(duì)象與對(duì)應(yīng)的聚類中心的均方差之和。最常用的劃分聚類算法包含k-means算法和k-medoids算法。

1.k-means算法

k-means算法的原理是將恒定的N個(gè)數(shù)據(jù)目標(biāo)的數(shù)據(jù)集分成事先給定的數(shù)目為k的簇，首先隨機(jī)選擇k個(gè)對(duì)象作為初始的k個(gè)聚類中心C=（C₁，C₂，…，C_k），接著通過算出其余的所有樣本到各自聚類中心的距離，把該樣本劃分到距離它很近的類中，之后再使用平均值的方法計(jì)算調(diào)整后的新類的聚類中心，重復(fù)上述步驟直到計(jì)算出的兩次類中心保持不變時(shí)，標(biāo)志著數(shù)據(jù)集中的樣本分類結(jié)束且聚類平均誤差準(zhǔn)則函數(shù)F處于收斂狀態(tài)，聚類平均誤差準(zhǔn)則函數(shù)F的表達(dá)式見式（5-6），其中q為數(shù)據(jù)集的數(shù)據(jù)對(duì)象，m_i是第i類聚類中心C_i的平均值，F代表數(shù)據(jù)集中全部數(shù)據(jù)對(duì)象的平方誤差的總和。

k-means算法雖然容易實(shí)現(xiàn)，但是該算法也具有一些缺陷：k-means算法當(dāng)選用不一樣的初始值時(shí)，能夠得到不相同的聚類結(jié)果，因此該算法對(duì)初始聚類中心的依賴性較大；k-means算法對(duì)獨(dú)立點(diǎn)及噪聲點(diǎn)反應(yīng)較為敏銳，嚴(yán)重時(shí)會(huì)導(dǎo)致聚類中心的偏離；k-means算法需要預(yù)先掌握的知識(shí)來求出待生成的簇的數(shù)目。

2.k-medoids算法

k-medoids算法的處理過程如下：先隨意選出k個(gè)對(duì)象作為初始的k個(gè)聚類的代表點(diǎn)，接著算出其余的樣本到其最靠近聚類中心的對(duì)象的距離，把該樣本歸類到離它最近的聚類中，并依據(jù)某代價(jià)函數(shù)估算目標(biāo)與代表點(diǎn)間的相異度平均值，若對(duì)象與代表點(diǎn)相似則替換代表點(diǎn)，反復(fù)進(jìn)行上述過程直到不再有對(duì)象替換代表點(diǎn)為止。k-medoids算法包括PAM算法、CLARANS算法以及CLARA算法。當(dāng)數(shù)據(jù)集和簇的數(shù)目較大時(shí)，PAM算法的性能就會(huì)變得很差；CLARANS算法不能辨認(rèn)套嵌或其余繁雜形狀的聚類形狀，而且該算法具有運(yùn)算效率低、沒有處理高維數(shù)據(jù)的能力以及不能準(zhǔn)確找到局部極小點(diǎn)產(chǎn)生錯(cuò)誤的聚類結(jié)果的缺陷；CLARA算法的聚類結(jié)果與抽樣的樣本大小有關(guān)，當(dāng)抽樣的樣本發(fā)生偏差時(shí)，CLARA算法的性能就會(huì)變差而不能得到良好的聚類結(jié)果。

5.2.2 層次聚類算法

層次聚類算法分為凝聚層次聚類算法和分裂層次聚類算法。凝聚層次聚類認(rèn)為每一個(gè)對(duì)象是一個(gè)簇，遵循自下而上的原則逐步歸并簇，繼而構(gòu)成很大的簇，反復(fù)這一過程直到圖像中所有的對(duì)象都在同一個(gè)簇中或滿足某一約束條件時(shí)，該算法結(jié)束。分裂層次聚類的過程與凝聚層次聚類的過程相反，分裂層次聚類認(rèn)為圖像中所有的對(duì)象已經(jīng)在一個(gè)簇中，遵循自上而下的原則逐漸將圖像中的對(duì)象從一個(gè)簇中劃分為越來越小的簇，反復(fù)這一過程直到圖像中每一個(gè)對(duì)象被分為單獨(dú)的一簇或滿足某一約束條件時(shí)，該算法結(jié)束。經(jīng)常使用的層次聚類算法有BIRCH算法、ROCK算法、CURE算法、Chameleon算法等。BIRCH算法通過掃描數(shù)據(jù)來建立一個(gè)有關(guān)聚類結(jié)構(gòu)的CF樹，并對(duì)此CF樹的葉節(jié)點(diǎn)進(jìn)行聚類；ROCK算法根據(jù)相似度閾值與共同鄰域的基本概念計(jì)算出圖像的相似度矩陣，接著從圖像的相似度矩陣中構(gòu)建一個(gè)稀疏圖，并對(duì)該稀疏圖進(jìn)行聚類；CURE算法依據(jù)收縮因子的值調(diào)整每個(gè)簇的大小和形狀，從而形成不同類型的簇而完成聚類；Chameleon算法依據(jù)若圖像中存在兩個(gè)簇之間相似性以及互聯(lián)性高度相關(guān)的對(duì)象，則動(dòng)態(tài)地合并這兩個(gè)簇，重復(fù)上述過程直到不能合并為止，該算法結(jié)束。

層次聚類算法雖然易處理不同粒度水平上的數(shù)據(jù)，但是該算法的結(jié)束條件模糊；其擴(kuò)展性不良，因而要求預(yù)先算出圖像中大部分的簇才可完成合并或分裂操作；并且該算法的歸并或割裂簇的處理是不可修正的，因此該算法聚類質(zhì)量較低。

5.2.3 基于密度的聚類算法

基于密度的聚類算法彌補(bǔ)了劃分聚類算法和層次聚類算法的不足，不僅可以處理凸形簇的聚類，而且可以處理任意形狀簇的聚類，該算法依據(jù)圖像中數(shù)據(jù)集密度的相似度，把密度相近的數(shù)據(jù)集劃分為一個(gè)簇，反之，把密度不接近的數(shù)據(jù)集劃分為不同的簇，從而完成聚類的目的。常用的基于密度的聚類算法有DBSCAN算法、DENCLUE算法以及OPTICS算法等。DBSCAN算法通過圖像中對(duì)象集合的每個(gè)對(duì)象的特定鄰域來確定簇的區(qū)域，該算法的聚類結(jié)果不受數(shù)據(jù)輸入順序的影響，但此算法在執(zhí)行的時(shí)候，需要事先知道圖像中確定輸入的聚類參數(shù)，但由于現(xiàn)實(shí)中的高維數(shù)據(jù)集不容易確定出聚類參數(shù)，因此該方法具有一定的局限性；DENCLUE算法依據(jù)圖像中數(shù)據(jù)集的影響函數(shù)來計(jì)算數(shù)據(jù)空間的整體密度，接著確定出密度吸引點(diǎn)并尋找到確定的各個(gè)簇的區(qū)域而完成聚類的目的，但是該算法受聚類參數(shù)的影響較大，往往參數(shù)值的輕微變化會(huì)引發(fā)差別較大的聚類結(jié)果；OPTICS算法可以自動(dòng)、交互地算出圖像中簇的次序，并且此次序表示數(shù)據(jù)集的聚類結(jié)構(gòu)，但是由于該算法所確定的聚類結(jié)構(gòu)是從一個(gè)寬泛的參數(shù)所設(shè)置的范圍中所獲得，因此該算法不能產(chǎn)生一個(gè)數(shù)據(jù)集的合簇，因而聚類結(jié)果不太理想。

5.2.4 基于模型的聚類算法

基于模型的聚類算法依據(jù)圖像中的數(shù)據(jù)集符合某一概率分布這一假設(shè)，把數(shù)據(jù)集表示為某一數(shù)學(xué)模型來實(shí)現(xiàn)聚類的目的，因而該方法劃分的每一個(gè)簇的形式均是通過概率描述來表示的。常用的基于模型的聚類算法有統(tǒng)計(jì)方法和神經(jīng)網(wǎng)絡(luò)方法，此外還有一些新的模型聚類算法，例如，支持矢量方法的聚類算法、SPC算法以及SyMP算法等。

統(tǒng)計(jì)聚類方法有COBWEB算法、CLASSIT算法、AutoClass算法以及高斯混合模型算法等。COBWEB算法是最著名的基于統(tǒng)計(jì)聚類的方法，該算法用一個(gè)啟發(fā)式估算度量將數(shù)據(jù)集中的對(duì)象加入到能夠產(chǎn)生最高分類效果分類樹的位置，于是會(huì)不斷地創(chuàng)建出新的類，從而完成聚類的目的。COBWEB算法不需要事先提供數(shù)據(jù)集的聚類參數(shù)就可以自動(dòng)地修正并劃分出數(shù)據(jù)集的簇的數(shù)目，但是由于該方法進(jìn)行的前提是假設(shè)每個(gè)簇的概率分布是相互獨(dú)立的，因而該方法具有局限性；此外該方法在存儲(chǔ)和更新數(shù)據(jù)集的每個(gè)簇的概率分布的時(shí)候，均會(huì)付出較高的代價(jià)而效率變低。CLASSIT算法可以處理連續(xù)性數(shù)據(jù)集的增量的聚類，并且該算法是COBWEB算法的一個(gè)衍生算法，因而該算法存在與COBWEB算法相同的缺陷，因此該算法也不適用于解決大型數(shù)據(jù)集的聚類問題。

神經(jīng)網(wǎng)絡(luò)方法將數(shù)據(jù)集的每一個(gè)簇看作是一個(gè)例證，并將該例證視為聚類的初始點(diǎn)，接著該算法依據(jù)某種相似度，將新的對(duì)象分配到與其最相似的簇中而完成聚類的目的。主要的神經(jīng)網(wǎng)絡(luò)方法包含競爭學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)方法和自組織特征映射神經(jīng)網(wǎng)絡(luò)方法。基于神經(jīng)網(wǎng)絡(luò)的聚類算法處理數(shù)據(jù)需要的時(shí)間較長，并且不適合將其用于大型數(shù)據(jù)集的處理。

5.2.5 基于網(wǎng)格的聚類算法

基于網(wǎng)格的聚類算法是首先將圖像空間數(shù)據(jù)量化成某些單元，然后該算法對(duì)這些量化單元進(jìn)行聚類。經(jīng)典的基于網(wǎng)格的聚類算法有STING算法、CLIQUE算法以及WaveCluster算法。STING算法是一種針對(duì)不同級(jí)別的分辨率將圖像空間分為多個(gè)級(jí)別的長方形單元的多分辨率的聚類方法；CLIQUE算法是一種綜合密度與網(wǎng)格的針對(duì)處理高維數(shù)據(jù)集的聚類算法；WaveCluster算法采用小波變換把圖像的數(shù)據(jù)集的空間域轉(zhuǎn)變?yōu)槠漕l率域，并在這個(gè)頻率域中找到密集的數(shù)據(jù)區(qū)域而實(shí)現(xiàn)數(shù)據(jù)聚類。基于網(wǎng)格的聚類算法雖然能快速聚類，但是該算法只能對(duì)垂直和水平邊界執(zhí)行聚類，不能對(duì)斜邊界執(zhí)行聚類，因此該算法具有一定的局限性；其時(shí)間復(fù)雜程度通常與數(shù)據(jù)集的規(guī)模無關(guān)而與網(wǎng)格數(shù)目相關(guān)，若網(wǎng)格單元數(shù)太大，則其時(shí)間復(fù)雜度就會(huì)變大，反之若網(wǎng)格單元數(shù)太小，該算法的聚類精確度就會(huì)受影響，因此該算法選取恰當(dāng)?shù)木W(wǎng)格數(shù)是取得良好的聚類效果的關(guān)鍵環(huán)節(jié)。