聚類分析及其在圖像處理上的應(yīng)用

1、聚類分析及其在圖像處理上的應(yīng)用1緒論1.1基于聚類的圖像處理的研究現(xiàn)狀聚類分析在圖像處理中應(yīng)用廣 泛，其中一項(xiàng)重要的應(yīng)用就是圖像分 割。圖像分割多年來一直受到人們的 高度重視，各種類型的分割算法相繼 被提出。雖然人們?cè)趫D像分割方面做 了許多工作，但是至今仍沒有通用的 分割算法，也不存在一個(gè)客觀的評(píng)價(jià) 準(zhǔn)則。大多數(shù)分割算法都是針對(duì)一種 具體類型的圖像提出的很難適用于所 有圖像。實(shí)際上由于各個(gè)領(lǐng)域的圖像 千差萬別，也很難提出萬能的分割算 法。基于聚類的圖像分割方法是圖像 分割領(lǐng)域中一類非常重要且應(yīng)用廣泛 的算法。2聚類分析概述2.1聚類的定義聚類的目的是將有限個(gè)無標(biāo)注數(shù) 據(jù)劃分到有限個(gè)離散的組或類

2、中，發(fā)現(xiàn)數(shù)據(jù)隱藏的部結(jié)構(gòu)。Backer和Jain 1指出 數(shù)據(jù)的劃分是依賴于所選擇的相似性 度量的，通過主觀地選擇相似性度量 來達(dá)到有的的劃分。至今，人們并沒有 對(duì)聚類給出一個(gè)統(tǒng)一的定義。多數(shù)研 究者都是從部同質(zhì)性和外部可分性對(duì) 聚類簇進(jìn)行描述，即同類數(shù)據(jù)對(duì)象問 應(yīng)該彼此相似，不同類間的數(shù)據(jù)對(duì)象 應(yīng)該不相似3。在給出聚類的數(shù)學(xué)描述 之前，首先介紹與聚類有關(guān)的一辟術(shù) 語和數(shù)學(xué)表達(dá)方法。樣本：指要進(jìn)行聚類的數(shù)據(jù)集中的單個(gè)數(shù)據(jù)。樣本一般是一個(gè)多維向量，向量的每個(gè)分量可以是數(shù)值型或者名詞型的數(shù)據(jù)，一般稱為特征或者屬性。樣本集：或稱數(shù)據(jù)集，是由單個(gè)樣本所 組成的集合，即是需要聚類操作的數(shù) 據(jù)整體，通常表

3、示為一個(gè)矩陣。相異度矩陣：該矩陣中的每個(gè)元素表$樣本集中的每對(duì)樣本之間的相異程 度，一般是非負(fù)值。相似度矩陣：該矩陣中的每個(gè)元素表 小？樣本集中的每對(duì)樣本之間的相似 程度，一般是非負(fù)值。類：或稱簇，指通過聚類而形成的一組 同一類中的樣本具有相似的特征。通 常用C或K表示類的個(gè)數(shù)。類原型：能夠代表某個(gè)類性質(zhì)的數(shù)據(jù)兀，可以是某類樣本中的一個(gè)樣本，或者是某類樣本的一個(gè)加權(quán)值,也可以是能描述一個(gè)類特征的向量。劃分矩陣U n*K：矩陣中的每個(gè)元素表示每個(gè)樣本屬于各個(gè)類的模糊隸屬度K0 < utk < 1 口 以法二 LM ,且止之】，在此K表?樣本標(biāo)號(hào),k表類標(biāo)標(biāo)號(hào)。通常獲得的數(shù)據(jù)類型有兩種

4、：一是數(shù) 據(jù)矩陣，二是相異度矩陣（相似度矩 陣）。假定數(shù)據(jù)集中有 n個(gè)樣本：Xi ,i=1,2,.,n,每個(gè)樣本有 p個(gè)變量（特征屬性），則這n個(gè)樣本可表 示成n*p（n個(gè)樣本xp個(gè)變量）的數(shù)據(jù) 矩陣。Ml為2工1必區(qū)2【422X2p * * *,*入門1處12-*（2-1）其中每個(gè)對(duì)象對(duì)應(yīng)為一個(gè)p維向量：r修二卜” t * .戶ip）（2-2）1.2聚類的數(shù)據(jù)類型相異度矩陣存儲(chǔ)的是n個(gè)樣本兩兩之 問的相界度，表現(xiàn)形式足一個(gè)n*n維的 矩陣。I 0妣1)0J(3,1) dt 2) 0* *魯fl4-I-din.)虹 2) 0(2-3)在這里d(i,j)是樣本i和樣本j之間 相異性的量化表示，通

5、常是一個(gè)非負(fù) 的數(shù)值，當(dāng)樣本i和樣本j越相似， d(i,j)的值就越接近0;反之，兩個(gè)樣 本越不相似，的值就越大。d(i,j)= d(j, i),且 d(i,j)=0,因此得到形如(2-3)的矩陣。圖像數(shù)據(jù)的表示日常應(yīng)用中得到的圖像一般分為兩類：灰度圖像和彩色圖像。灰度圖像的數(shù)值表示為一個(gè)二維矩陣I m*n圖像 一共包含m*n個(gè)像素。在此，m和n分 別代表圖像的高和寬，(ij)表示位于 第i行和第j列的像素，Iij表小其灰 度俏。彩色圖像的數(shù)值表示為一個(gè)三維矩陣I m*n*3,像素的個(gè)數(shù)仍為m>n,3表示三個(gè)顏色通道，每一層的二維矩 陣表示該圖像在某一個(gè)顏色通道的數(shù) 值。位于位置(i,j

6、)的像素對(duì)應(yīng)的 顏 色特征向量表示為 I(i,j,1),I(i,j,2),I(i,j,3)。在許多t#況下，色彩是描述一幅圖像 最簡(jiǎn)單有效的特征，而且人眼對(duì)色彩 的分辨率大大高于對(duì)灰度圖像的分辨 率，因此彩色圖像所攜帶的信息遠(yuǎn)遠(yuǎn) 大于灰度圖像。一般的圖像處理技術(shù) 最先應(yīng)用于灰度圖像，然后發(fā)展到彩 色圖像，圖像分割也不列外。顏色特征 可以來自于不同的顏色空間，不同的 顏色空間以不同的方式對(duì)圖像顏色進(jìn) 行描述。一共有四種不同的顏色空間： RG射色空間、XYZ顏色空間、HIS顏 色空間、Lab顏色空間。RGB®色空間 是基本的顏色空間，RGB對(duì)應(yīng)于紅(R)、 I(G)、藍(lán)(B)三種基色，其

7、余所有顏色 空間都可由RGB顏色空間經(jīng)過線性或 非線性變換得出的。給定一幅待分割的圖像，我們可以直接獲得像素的位置信息，灰度值 （灰度圖像）或者RG的色特征值（彩色 圖像），這些特征也是圖像分割中最常 用的特征屬性。但是對(duì)于一些復(fù)雜圖 像,單純依賴這些底層特征不能得到 滿意的分割結(jié)果?；谶@些底層特征， 人們提取了更多有效的特征 ，其中常 用的有描述物體表面灰度變化的紋理 特征和根據(jù)特定對(duì)象的先驗(yàn)信息加入 的形狀特征。最近，人們開始借助一辟 先進(jìn)的電子產(chǎn)品提取深度信息，通過 加入這辟高層特征來改善對(duì)特定類圖 像的分割結(jié)果。在提取特征之后，就可以得到每 個(gè)像素點(diǎn)的一個(gè)向量表小 ，也就可以 看成是

8、高維空間中的一個(gè)數(shù)據(jù)點(diǎn)。但 是，像素點(diǎn)又和傳統(tǒng)的數(shù)據(jù)不同，每個(gè) 像素點(diǎn)在閣像中的位置是固定的，每 個(gè)像素點(diǎn)的鄰域像素點(diǎn)都可以直接通 過位置信息獲得，這一特性也在圖像 數(shù)據(jù)的相似度計(jì)算上得以體現(xiàn)。2.3聚類算法近些年來，聚類分析一直是研究 熱點(diǎn)問題?；谙嗨贫染仃嚨木垲愃?法指的足給定相似度矩陣的情況下即 可進(jìn)行聚類處理的算法。只要給定相 似度計(jì)算模型，則基于相似度矩陣的 聚類算法也可以處理數(shù)據(jù)矩陣，即首 先根據(jù)數(shù)據(jù)矩陣計(jì)算出相似度矩陣，然后利用基于相似度矩陣的聚類算法 進(jìn)行聚類。2.3.1 基于數(shù)據(jù)矩陣的聚類算法基于數(shù)據(jù)矩陣的聚類算法只能處理數(shù)據(jù)矩陣對(duì)象，其中很多經(jīng)典的類原型聚類算法都可以劃分

9、到這一類聚一個(gè)簇可以由類原型表示，達(dá)到對(duì)原類算法中,如K均值型聚類算法，模糊C 均值型聚類算法（FCM）, EM®聚類算法 等。這辟算法之所以稱為類原型聚類 算法，是因?yàn)槊總€(gè)類可以由類原型來 代表，在對(duì)數(shù)據(jù)進(jìn)行劃分的同時(shí)也給 每個(gè)類找到具有代表作用的類原型。有的數(shù)據(jù)集的壓縮編碼，這也可以說(2-5)是聚類的另外一個(gè)功能。給定一數(shù)據(jù) 矩陣兇n*p表示n個(gè)p維樣本。K均值算法K均值算法將n個(gè)樣本劃分到K個(gè) 簇C = C1,C2,。9，使得簇樣本具 有較高相似度，簇間樣本具有較低相 似度。設(shè)V= VI, V2,Vk為K個(gè)類 對(duì)應(yīng)的類中心(類原型)，其中Vk是第 Ck個(gè)簇中樣本的平均值，每個(gè)

10、族可以 由對(duì)應(yīng)的類原型來表示。K均值算法通 過最小化類誤差平方和準(zhǔn)則函數(shù)來對(duì) 數(shù)據(jù)進(jìn)行劃分，其目標(biāo)函數(shù)定義如下：榮尤0 = 2 -躁儼七二1君EC*(2-4)在此Ck包含所有到第k個(gè)類中心 Vk距離最小的樣本點(diǎn)，可描述如下。C - I片 w 川k = arg min |x(- - 廣 網(wǎng)IN-用£為a為Vjk =IQI(2-6)K均值算法是一個(gè)貪心算法，通過 迭代地更新類中心和各個(gè)簇成員來得 到公式(2-4)的局部最優(yōu)解。K均值 聚類算法主要包括以下幾個(gè)步驟：1 .初始化：隨機(jī)選取個(gè)樣本作為 初始的類中心；2 .樣本指派：計(jì)算樣本到各個(gè)類 中心的歐氏距離，將樣本劃分到距離 其最近的類

11、；3 .更新：重新計(jì)算每個(gè)新簇的類 中心；4 .重復(fù)步驟2和3直到簇樣本不 再發(fā)生變化后停止。K均值算法的主要優(yōu)點(diǎn)有收斂速 度快，儲(chǔ)存空間小，時(shí)間復(fù)雜度低等。 一般的K均值型聚類算法的時(shí)間復(fù)雜 度為O (nKt),其中n是數(shù)據(jù)集中樣 本的個(gè)數(shù)，K是期望聚類的個(gè)數(shù)，t是迭代次數(shù)。要根據(jù)相似度模型計(jì)算出相似度矩模本C均值算法Dunn在1973年提出模糊C均值聚類思想，之后Bezdek把這一工作進(jìn)一 步推廣到一個(gè)模糊目標(biāo)函數(shù)聚類的優(yōu) 化算法，并證明了該算法的收斂性。模糊C均值聚類算法給出每個(gè)樣本屬 于各個(gè)類的程度，即隸屬度(menibershipvalue)。相比K均值聚類的硬化分,模糊劃分更豐富地

12、反映了樣本與各個(gè)類原型的相關(guān)度，從而可以更好的推測(cè)數(shù)據(jù)集的部結(jié)構(gòu)。2.3.2基于相似度矩陣的聚類算法基于相似度矩陣的聚類算法是以相似度(相異度)矩陣為基礎(chǔ)。如果數(shù)據(jù)是用數(shù)據(jù)矩陣的形式表現(xiàn)的，在使用基于相似度矩陣的聚類算法之前 陣。與基于數(shù)據(jù)矩陣的聚類算法相比， 這類算法使用起來更靈活，無論輸入 是數(shù)據(jù)矩陣還是相似度矩陣都能夠進(jìn) 行聚類操作，相反基于數(shù)據(jù)的聚類算 法則不能處理只給出相似度矩陣的聚 類問題。然而，一些應(yīng)用領(lǐng)域往往無法 給出明確的數(shù)據(jù)矩陣，而是給出一辟 數(shù)據(jù)點(diǎn)白關(guān)系(如相似度)，社團(tuán)分析 中常碰到這類情況。直接使用相似度 矩陣進(jìn)行聚類的典型聚類算法有基于圖的聚類算法、基于類原型的 K

13、中心算法(K-medoids)和AP聚類算法、層次聚類算法以及基于密度的聚類算法等?；趫D的聚類算法基于圖的聚類算法是一類基于無向圖的聚類算法。假定將侮個(gè)樣本看 作圖中白頂點(diǎn)V,根據(jù)樣本間的相似度 為頂點(diǎn)間的邊E賦于權(quán)重W這樣得到 一個(gè)基于樣本相似度的無向加權(quán)圖G=(V,E)。將樣本映射到圖之后，可以 使用圖論中很多成熟的理論來進(jìn)行聚類，一類非常流行的基于圖的聚類算 法是譜聚類算法，這類算法也是本文 的基礎(chǔ)算法，很多相關(guān)實(shí)驗(yàn)也是基于 這類算法完成的。因此，下面會(huì)比較詳 細(xì)的介紹幾種常用的譜聚類算法。譜 聚類算法的思想源于譜圖劃分理論，其本質(zhì)是將聚類問題轉(zhuǎn)化為圖的 最優(yōu)化分問題。與傳統(tǒng)聚類算法假

14、設(shè) 一樣，基于圖論的最優(yōu)劃分準(zhǔn)則也是 使劃分的子圖部相似度最大，子圖之 問的相似度最小。不同的劃分準(zhǔn)則會(huì)得到不同的聚類結(jié)架。表 2.1給出了 一辟常見的劃分準(zhǔn)則。由于圖劃分問題的本質(zhì)，求圖劃 分準(zhǔn)則的最優(yōu)解是一個(gè)NP難問題。求 解圖劃分問題一個(gè)主要的工具是圖的 拉普拉斯矩陣法（Laplacian matrices）。這類矩陣的學(xué)習(xí)已經(jīng)形成 了一個(gè)完整的體系，稱為譜圖論早在 1973年,Donath 和 HoffmanfN 就提出 利用圖的鄰接矩陣的特征向量來求解圖劃分問題。同年,Fiedlerl發(fā)現(xiàn)了圖的2-way劃分與該圖的拉普拉斯矩陣對(duì)應(yīng)的第二小特 征信對(duì)應(yīng)的特征向量有密切關(guān)系，并提出使用

15、這一向量對(duì)圖進(jìn)行劃分。這 一特征向量代表了最佳圖劃分的一個(gè) 解（即勢(shì)函數(shù)），后來將這一特征向量 命名為Fiedlerl 向量。基于譜圖理論，原來的圖劃分問題 就可以轉(zhuǎn)換成求解相似度矩陣或 Laplacian矩陣的譜分解問題，因此將 這類方法統(tǒng)稱為譜聚類，可以認(rèn)為譜 聚類是對(duì)圖劃分準(zhǔn)則的逼近。AuthH.lef.McAodObrcwt Rhcbuii附Minim岫 cut幽A,用= £ %ShiiVlik1*廂Mi同EL跟隊(duì)用=墮力言自強(qiáng)曖Rark加加財(cái)尚二湍蜂四明版刖3Mm（兒盼瑞1工 *I F-fr', >'D譜聚類中常用的相似性度量為空間相似性計(jì)算模型中的高

16、斯型相似性計(jì)算方法。相似度矩陣通常用W或A表示，有時(shí)也稱為親和矩陣（AffinityMatrix), Wij = Wji=Sij 。在得到相似度矩陣后即可求解拉普拉斯矩陣，不同的文獻(xiàn)可能使用不同類型的拉普拉斯矩陣，不同的拉普拉斯矩陣即得 到不同的譜映射方法。在給出不同類型的拉普拉斯矩陣之前，先引入矩陣 D。D為對(duì)角矩陣，.二小啊即可 以看作是每個(gè)頂點(diǎn)的度，所以也稱為 度矩陣。圖的拉普拉斯矩陣分為兩類：非規(guī)拉普拉斯矩陣和規(guī)拉普拉斯矩陣。非規(guī)拉普拉斯矩陣定義為：L= D-W(2-7)規(guī)的拉普拉斯矩P$有兩種形式，分別為：= D'l/2LD-lf2 =/一 DWif2(2-8)Lrw = /

17、7附(2-9)在此將第一個(gè)矩陣標(biāo)記為 Lsym, 因?yàn)樵摼仃嚍閷?duì)稱矩陣；第二個(gè)矩陣 標(biāo)記為L(zhǎng)rw,因?yàn)樵摼仃嚺c隨機(jī)游走有密切關(guān)系。根據(jù)不同的準(zhǔn)則函數(shù)及譜映射方 法，文獻(xiàn)中已提出很多種不同的譜聚 類算法。眾多的譜聚類算法中應(yīng)用最 廣的要數(shù)Shi和Malik提出的Ncut譜 聚類算法_,Ng等。人提出的NJW算法。 Ncut算法最初是用于求解兩類問題， 可以迭代地對(duì)之前步驟得到的子圖進(jìn) 行劃分來得到期望的聚類個(gè)數(shù)，所以 也屬于迭代譜聚類算法中的一種。NJW 算法是針對(duì)多類問題提出，使用更多 的特征向量并且直接計(jì)算 k路分割對(duì) 數(shù)據(jù)進(jìn)行聚類。譜聚類算法的主要優(yōu)勢(shì)在于該類 算法對(duì)簇的形狀沒有很強(qiáng)的假設(shè)

18、，可 以處理更一般化的聚類問題。K均值聚 類算法建立在球形的樣本空間上，適 合發(fā)現(xiàn)千犬簇，對(duì)于含有任意形狀簇 的數(shù)據(jù)集往往得不到期望的聚類結(jié) 果。處理更多類型的數(shù)據(jù)集是近幾年 譜聚類流行起來的主要原因。但是也 正是由于譜聚類是直接基于相似度矩陣的聚類算法，不同的相似度矩陣得 到的聚類結(jié)果可能會(huì)有很大差界。K中心點(diǎn)方法K中心點(diǎn)方法也可以看作是K均值 算法的一個(gè)變形算法，之所以將其歸 類為基于相似度（相異度）矩陣的聚類 算法是因?yàn)镵中心點(diǎn)算法選用族中位 置最中心的對(duì)象作為類代表點(diǎn) （類中 心），而不是簇中對(duì)象的平均值（質(zhì) 心）。K中心點(diǎn)方法仍是基于最小化所 有對(duì)象到類中心之間的相異度之和的 原則來

19、執(zhí)行，在已知對(duì)象與對(duì)象間的 相異度時(shí)，該方法就能對(duì)對(duì)象進(jìn)行聚 類。K中心點(diǎn)方法采用中心點(diǎn)來代替質(zhì) 心，減少了對(duì)噪聲和孤立點(diǎn)數(shù)據(jù)的敏 感程度。K中心點(diǎn)聚類算法的基本策略是： 首先為每個(gè)族隨機(jī)選擇一個(gè)代表點(diǎn)；剩余的數(shù)據(jù)點(diǎn)根據(jù)其與代表點(diǎn)的距離 分配給最近的一個(gè)簇。然后反復(fù)用非 代表點(diǎn)來替換代表點(diǎn)，以改進(jìn)聚類的 質(zhì)量，降低聚類質(zhì)量的代價(jià)函數(shù)，即數(shù) 據(jù)點(diǎn)到其類代表點(diǎn)的平方誤差和。每 次代表點(diǎn)替換發(fā)生時(shí)，檢查代價(jià)函數(shù) 是否降低，如果降低則保留替換，否則 放棄該替換，重復(fù)上述過程直到代價(jià) 函數(shù)不再發(fā)生變化為止。給定聚類數(shù) K,典型的K中心點(diǎn)聚類算法的主要步 驟概括如下：1 .初始化：隨機(jī)選取足個(gè)樣本作 為初

20、始的中心點(diǎn)；2 .樣本指派：計(jì)算樣本到各個(gè)類 中心的距離，將樣本劃分到距離其最 近的中心點(diǎn)所代表的簇；3 .類中心替換：隨機(jī)地選擇一個(gè) 非類中心點(diǎn)，計(jì)算用選中的樣本代替 原來的類中心的代價(jià)函數(shù)，如果代價(jià) 函數(shù)降低，則替換原有的中心點(diǎn)形成 新的K個(gè)中心點(diǎn)集合；4 .重復(fù)步驟2和3直到類中心點(diǎn) 不評(píng)發(fā)生變化后停止。PAM （Partitioning AroundMedoids )是最早提出的K中心點(diǎn)算 法之一。雖然K中心算法比K均值算 法在處理噪聲點(diǎn)時(shí)表現(xiàn)的要健壯，但是K中心點(diǎn)算法的執(zhí)行代價(jià)比 K均值 方法高，其時(shí)間復(fù)雜度為如果數(shù)據(jù)集 規(guī)模和類的個(gè)數(shù)較大，PAM算法的效率 會(huì)很低為了用K中心點(diǎn)方法

21、處理大規(guī) 模數(shù)據(jù)集，Kaufman和Rousseeuw將抽 樣方法和PAMT法結(jié)合提出了 一個(gè)新 的尺中心點(diǎn)方法，稱為 CLARA(Clustering LARge Applications)算法 CLARAB法 + 再考 慮整個(gè)數(shù)據(jù)集，而是從整個(gè)數(shù)據(jù)集中 進(jìn)行抽樣，選取數(shù)據(jù)中的一小部分作 為數(shù)據(jù)的樣本，然后用PAMT法從這些 選中的樣本中選擇中心點(diǎn)。為了減少 抽樣樣本對(duì)最終聚類的影響，CLARA算 法采取多次抽樣，對(duì)每次抽樣樣本應(yīng) 用PAMT法，返回這幾次抽樣最好的聚類結(jié)果作為最終 結(jié)果。通過抽樣處理，CLARA算法一次 抽樣的時(shí)間復(fù)雜度為對(duì)),其中s是抽樣樣本的大小。CLARA?法的一大缺

22、點(diǎn)是 不能保證最佳的個(gè)類中心點(diǎn)被選中為 最終的類中心點(diǎn)，如果在抽樣的時(shí)候 這辟數(shù)據(jù)點(diǎn)沒有被抽中，那么CLARAT法將永遠(yuǎn)找不到最佳聚類。為了改進(jìn)CLARAJ法的聚類質(zhì)量，Ng和Han提出 了 CLARAN潴法(Clustering LargeApplications based upon RANdomizedSearch),該算法也采用了抽樣技術(shù)，但是在搜索的每個(gè)階段不訴使用一個(gè)固定的抽樣集合，而在搜索的每一步都會(huì)隨機(jī)的抽取樣本，其時(shí)間復(fù)雜度為5島)。CLARANS法的聚類質(zhì)量也依 賴于所用的抽樣方法。3實(shí)驗(yàn)與分析針對(duì)相似度計(jì)算模型和數(shù)據(jù)特征兩方 面的工作，實(shí)驗(yàn)分為兩部分：基于不同高斯型相似度的實(shí)驗(yàn)結(jié)果和基于不同 特征的實(shí)驗(yàn)結(jié)果。每部分都使用模擬(a)(b)數(shù)據(jù)及實(shí)際數(shù)據(jù)對(duì)相應(yīng)方法進(jìn)行測(cè)試 聚類算法選用NJW倍聚類算法。3.21基于不同高斯型相似度的聚類結(jié) 果下面給山基于六種高斯型相似性度量 的聚類結(jié)果。六種相似性度量分別為： 標(biāo)準(zhǔn)高斯核相似度(SC)自適應(yīng)高斯 核相似度I(STI)、自適應(yīng)高斯核相似 度n (STH)局部密度的自適應(yīng)相似度 (CNN)加權(quán)自適應(yīng)相似度I (WSTI)以 及加權(quán)自適應(yīng)相似度n (wsTn)。3.3模擬數(shù)據(jù)首先對(duì)模擬數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，部分?jǐn)?shù)據(jù) 集來自文獻(xiàn)。對(duì)于各種相似