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

數(shù)據(jù)隱藏的內(nèi)部結(jié)構(gòu)。Backer和Jain[1]指出數(shù)據(jù)的劃分是依賴于所選擇的相似性度量的,通過主觀地選擇相似性度量來達(dá)到有的的劃分。至今,人們并沒有對聚類給出一個統(tǒng)一的定義。多數(shù)研究者都是從內(nèi)部同質(zhì)性和外部可分性對聚類簇進(jìn)行描述,即同類內(nèi)數(shù)據(jù)對象間應(yīng)該彼此相似,不同類間的數(shù)據(jù)對象應(yīng)該不相似[3。在給出聚類的數(shù)學(xué)描述之前,首先介紹與聚類有關(guān)的一辟術(shù)語和數(shù)學(xué)表達(dá)方法。精品文檔放心下載樣本:指要進(jìn)行聚類的數(shù)據(jù)集中的單個數(shù)據(jù)。樣本一般是一個多維向量,向量的每個分量可以是數(shù)值型或者名詞型的數(shù)據(jù),一般稱為特征或者屬性。謝謝閱讀樣本集:或稱數(shù)據(jù)集,是由單個樣本所組成的集合,即是需要聚類操作的數(shù)據(jù)整體,通常表示為一個矩陣。謝謝閱讀,.相異度矩陣:該矩陣中的每個元素表$樣本集中的每對樣本之間的相異程度,一般是非負(fù)值。感謝閱讀相似度矩陣:該矩陣中的每個元素表小?樣本集中的每對樣本之間的相似程度,一般是非負(fù)值。精品文檔放心下載類:或稱簇,指通過聚類而形成的一組,同一類中的樣本具有相似的特征。通常用C或K表示類的個數(shù)。精品文檔放心下載類原型:能夠代表某個類性質(zhì)的數(shù)據(jù)兀,可以是某類樣本中的一個樣本,或者是某類樣本的一個加權(quán)值,也可以是能描述一個類特征的向量。感謝閱讀劃分矩陣[U]n*K:矩陣中的每個元素表示每個樣本屬于各個類的模糊隸屬度,且 ,在此〖表?樣本標(biāo)號,k表類標(biāo)標(biāo)號。1.2聚類的數(shù)據(jù)類型

通常獲得的數(shù)據(jù)類型有兩種:一是數(shù)據(jù)矩陣,二是相異度矩陣(相似度矩陣)。假定數(shù)據(jù)集中有n個樣本:精品文檔放心下載xi,i=1,2,....,n,每個樣本有p個變量感謝閱讀(特征屬性),則這n個樣本可表示成n*p(n個樣本xp個變量)的數(shù)據(jù)矩陣。謝謝閱讀(2-1)其中每個對象對應(yīng)為一個p維向量:(2-2)相異度矩陣存儲的是n個樣本兩兩之問的相界度,表現(xiàn)形式足一個n*n維的矩陣。謝謝閱讀,.(2-3)在這里d(i,j)是樣本i和樣本j之間相異性的量化表示,通常是一個非負(fù)的數(shù)值,當(dāng)樣本i和樣本j越相似，d(i,j)的值就越接近0；反之,兩個樣本越不相似,的值就越大。d(i,j)=d(j,i),且d(i,j)=0,因此得到形如(2-3)的矩陣。謝謝閱讀圖像數(shù)據(jù)的表示日常應(yīng)用中得到的圖像一般分為兩類：灰度圖像和彩色圖像。灰度圖像的數(shù)值表示為一個二維矩陣[I]m*n圖像謝謝閱讀一共包含m*n個像素。在此，m和n分別代表圖像的高和寬，(ij)表示位于謝謝閱讀i行和第j列的像素，Iij表示其灰度值。彩色圖像的數(shù)值表示為一個三維精品文檔放心下載矩陣[I]m*n*3，像素的個數(shù)仍為m×n，表示三個顏色通道，每一層的二維矩陣表示該圖像在某一個顏色通道的數(shù)值。位于位置(i,j)的像素對應(yīng)的顏色特征向量表示為[I(i,j,1),I(i,j,2),I(i,j,3)]。謝謝閱讀在許多情況下,色彩是描述一幅圖像最

簡單有效的特征,而且人眼對色彩的分辨率大大高于對灰度圖像的分辨率,因此彩色圖像所攜帶的信息遠(yuǎn)遠(yuǎn)大于灰度圖像。一般的圖像處理技術(shù)最先應(yīng)用于灰度圖像,然后發(fā)展到彩色圖像,圖像分割也不列外。顏色特征可以來自于不同的顏色空間,不同的顏色空間以不同的方式對圖像顏色進(jìn)行描述。一共有四種不同的顏色空間：RGB顏色空間、XYZ顏色空間、HIS顏色空間、Lab顏色空間。RGB顏色空間是基本的顏色空間,RGB對應(yīng)于紅(R)、綠感謝閱讀(G)、藍(lán)(B)三種基色,其余所有顏色空間都可由RGB顏色空間經(jīng)過線性或非線性變換得出的。謝謝閱讀給定一幅待分割的圖像,我們可以直接獲得像素的位置信息,灰度值(灰度圖像)或者RGB顏色特征值(彩色圖謝謝閱讀),這些特征也是圖像分割中最常用的特征屬性。但是對于一些復(fù)雜圖像,精品文檔放心下載單純依賴這些底層特征不能得到滿意的分割結(jié)果?；谶@些底層特征,人們謝謝閱讀,.提取了更多有效的特征,其中常用的有描述物體表面灰度變化的紋理特征和根據(jù)特定對象的先驗(yàn)信息加入的形狀特征。最近,人們開始借助一辟先進(jìn)的電子產(chǎn)品提取深度信息,通過加入這辟高層特征來改善對特定類圖像的分割結(jié)果。謝謝閱讀在提取特征之后,就可以得到每個像素點(diǎn)的一個向量表小,也就可以看成是高維空間中的一個數(shù)據(jù)點(diǎn)。但是,像素點(diǎn)又和傳統(tǒng)的數(shù)據(jù)不同,每個像素點(diǎn)在閣像中的位置是固定的,每個像素點(diǎn)的鄰域像素點(diǎn)都可以直接通過位置信息獲得,這一特性也在圖像數(shù)據(jù)的相似度計(jì)算上得以體現(xiàn)。謝謝閱讀2.3聚類算法近些年來,聚類分析一直是研究熱點(diǎn)問題?；谙嗨贫染仃嚨木垲愃惴ㄖ傅淖憬o定相似度矩陣的情況下即可進(jìn)行聚類處理的算法。只要給定相似度計(jì)算模型,則基于相似度矩陣的聚類感謝閱讀

算法也可以處理數(shù)據(jù)矩陣,即首先根據(jù)數(shù)據(jù)矩陣計(jì)算出相似度矩陣,然后利用基于相似度矩陣的聚類算法進(jìn)行聚類。感謝閱讀2.3.1基于數(shù)據(jù)矩陣的聚類算法基于數(shù)據(jù)矩陣的聚類算法只能處理數(shù)據(jù)矩陣對象,其中很多經(jīng)典的類原型聚類算法都可以劃分到這一類聚類算法中,如K均值型聚類算法,模糊C均值型聚類算法(FCM),EM型聚類算法等。這辟算法之所以稱為類原型聚類算法,是因?yàn)槊總€類可以由類原型來代表,在對數(shù)據(jù)進(jìn)行劃分的同時也給每個類找到具有代表作用的類原型。一個簇可以由類原型表示,達(dá)到對原有的數(shù)據(jù)集的壓縮編碼,這也可以說是聚類的另外一個功能。給定一數(shù)據(jù)矩陣[X]n*p感謝閱讀表示n個p維樣本。K均值算法,.K均值算法將n個樣本劃分到K個簇C={C1,C2,…,Ck},使得簇內(nèi)樣本具有較高相似度,簇間樣本具有較低相似度。設(shè)V={VI,V2,…,Vk}為K個類對應(yīng)的類中心(類原型),其中Vk是第Ck個簇中樣本的平均值,每個族可以由對應(yīng)的類原型來表示。K均值算法通過最小化類內(nèi)誤差平方和準(zhǔn)則函數(shù)來對數(shù)據(jù)進(jìn)行劃分,其目標(biāo)函數(shù)定義如下:感謝閱讀(2-4)在此Ck包含所有到第k個類中心Vk距離最小的樣本點(diǎn)，可描述如下。謝謝閱讀(2-5)(2-6)

迭代地更新類中心和各個簇成員來得到公式（2-4）的局部最優(yōu)解。K均值聚類算法主要包括以下幾個步驟:精品文檔放心下載1.初始化:隨機(jī)選取個樣本作為初始的類中心;2.樣本指派:計(jì)算樣本到各個類中心的歐氏距離,將樣本劃分到距離其最近的類;感謝閱讀3.更新:重新計(jì)算每個新簇的類中心;4.重復(fù)步驟2和3直到簇內(nèi)樣本不再發(fā)生變化后停止。精品文檔放心下載均值算法的主要優(yōu)點(diǎn)有收斂速度快,儲存空間小,時間復(fù)雜度低等。一般的K均值型聚類算法的時間復(fù)雜度謝謝閱讀O（nKt），其中n是數(shù)據(jù)集中樣本的個數(shù)，K是期望聚類的個數(shù)，t是迭代次數(shù)。感謝閱讀模糊C均值算法K均值算法是一個貪心算法,通過 Dunn在1973年提出模糊C均值精品文檔放心下載,.聚類思想，之后Bezdek把這一工作進(jìn)一步推廣到一個模糊目標(biāo)函數(shù)聚類的優(yōu)化算法，并證明了該算法的收斂性。模糊C均值聚類算法給出每個樣本屬于各個類的程度,即隸屬度(menibershipvalue)。謝謝閱讀相比K均值聚類的硬化分,模糊劃分更豐富地反映了樣本與各個類原型的相關(guān)度,感謝閱讀從而可以更好的推測數(shù)據(jù)集的內(nèi)部結(jié)構(gòu)。2.3.2基于相似度矩陣的聚類算法基于相似度矩陣的聚類算法是以相似度(相異度)矩陣為基礎(chǔ)。如果數(shù)據(jù)是用數(shù)據(jù)矩陣的形式表現(xiàn)的,在使用基于相似度矩陣的聚類算法之前要根據(jù)相似度模型計(jì)算出相似度矩陣。與基于數(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中心算法(K-medoids)和AP聚類算法、層次聚類算法以及基于密度的聚類算法等。謝謝閱讀基于圖的聚類算法基于圖的聚類算法是一類基于無向圖的聚類算法。假定將侮個樣本看作圖中的頂點(diǎn)V,根據(jù)樣本間的相似度為頂點(diǎn)間的邊E賦于權(quán)重W,這樣得到一個基于樣本相似度的無向加權(quán)圖G=(V,E)。將樣本映射到圖之后,可以使用圖論中很多成熟的理論來進(jìn)行聚類,一類非常流行的基于圖的聚類算法是譜聚類算法,這類算法也是本文的基礎(chǔ)算法,很多相關(guān)實(shí)驗(yàn)也是基于這類算法完成的。因此,下面會比較詳細(xì)的介紹幾種常用的譜聚類算法。譜聚類算法感謝閱讀,.的思想源于譜圖劃分理論，其本質(zhì)是將聚類問題轉(zhuǎn)化為圖的最優(yōu)化分問題。與傳統(tǒng)聚類算法假設(shè)一樣，基于圖論的最優(yōu)劃分準(zhǔn)則也是使劃分的子圖內(nèi)部相似度最大，子圖之間的相似度最小。不同的劃分準(zhǔn)則會得到不同的聚類結(jié)架。表2.1給出了一辟常見的劃分準(zhǔn)則。由于圖劃分問題的本質(zhì),求圖劃分準(zhǔn)則的最優(yōu)解是一個NP難問題。求解圖劃分問題一個主要的工具是圖的拉普拉斯矩陣法(Laplacianmatrices)。這類矩陣的學(xué)習(xí)已經(jīng)形成了一個完整的體系,稱為譜圖論早在1973年,Donath和Hoffmanf^l就提出利用圖的鄰接矩陣的特征向量來求解圖劃分問題。同謝謝閱讀年,Fiedlerl發(fā)現(xiàn)了圖的2-way劃分與該圖的拉普拉斯矩陣對應(yīng)的第二小特征值對應(yīng)的特征向量有密切關(guān)系,并提出使用這一向量對圖進(jìn)行劃分。這一特征向量代表了最佳圖劃分的一個解精品文檔放心下載

(即勢函數(shù)),后來將這一特征向量命名為Fiedlerl向量。感謝閱讀基于譜圖理論,原來的圖劃分問題就可以轉(zhuǎn)換成求解相似度矩陣或Laplacian矩陣的譜分解問題,因此將這類方法統(tǒng)稱為譜聚類,可以認(rèn)為譜聚類是對圖劃分準(zhǔn)則的逼近。謝謝閱讀譜聚類中常用的相似性度量為空間相似性計(jì)算模型中的高斯型相似性計(jì)算方法。相似度矩陣通常用W或A表示，有時也稱為親和矩陣(AffinityMatrix),Wij=Wji=Sij。在得到相似度矩陣后即可求解拉普拉斯矩陣,不同的文獻(xiàn)可能使用不同類型的拉普拉斯矩陣,不同的拉普拉斯矩陣即得到不同的譜映射方法。在給出不同類型的拉普拉斯矩陣之前,先引入矩陣D。D為精品文檔放心下載,.對角矩陣, 即可以看作是每個頂點(diǎn)的度,所以也稱為度矩陣。圖的拉普拉斯矩陣分為兩類:非規(guī)范拉普拉斯矩陣和規(guī)范拉普拉斯矩陣。非規(guī)范拉普拉斯矩陣定義為:(2-7)規(guī)范的拉普拉斯矩陣有兩種形式,分別為:(2-8)(2-9)在此將第一個矩陣標(biāo)記為Lsym，因?yàn)樵摼仃嚍閷ΨQ矩陣;第二個矩陣標(biāo)記為Lrw，因?yàn)樵摼仃嚺c隨機(jī)游走有密切關(guān)系。謝謝閱讀根據(jù)不同的準(zhǔn)則函數(shù)及譜映射方法,文獻(xiàn)中已提出很多種不同的譜聚類算法。眾多的譜聚類算法中應(yīng)用最廣的要數(shù)Shi和Malik提出的Ncut譜聚類算法_,Ng等。人提出的NJW算法。感謝閱讀

Ncut算法最初是用于求解兩類問題,可以迭代地對之前步驟得到的子圖進(jìn)行劃分來得到期望的聚類個數(shù),所以也屬于迭代譜聚類算法中的一種。NJW算法是針對多類問題提出,使用更多的特征向量并且直接計(jì)算k路分割對數(shù)據(jù)進(jìn)行聚類。謝謝閱讀譜聚類算法的主要優(yōu)勢在于該類算法對簇的形狀沒有很強(qiáng)的假設(shè),可以處理更一般化的聚類問題。K均值聚類算法建立在球形的樣本空間上,適合發(fā)現(xiàn)球狀簇,對于含有任意形狀簇的數(shù)據(jù)集往往得不到期望的聚類結(jié)果。處理更多類型的數(shù)據(jù)集是近幾年譜聚類流行起來的主要原因。但是也正是由于譜聚類是直接基于相似度矩陣的聚類算法,不同的相似度矩陣得到的聚類結(jié)果可能會有很大差界。謝謝閱讀K中心點(diǎn)方法K中心點(diǎn)方法也可以看作是K均,.值算法的一個變形算法,之所以將其歸類為基于相似度(相異度)矩陣的聚類算法是因?yàn)镵中心點(diǎn)算法選用族中位置最中心的對象作為類代表點(diǎn)(類中心),而不是簇中對象的平均值(質(zhì)心)。K中心點(diǎn)方法仍是基于最小化所有對象到類中心之間的相異度之和的原則來執(zhí)行,在已知對象與對象間的相異度時,該方法就能對對象進(jìn)行聚類。K中心點(diǎn)方法采用中心點(diǎn)來代替質(zhì)心,減少了對噪聲和孤立點(diǎn)數(shù)據(jù)的敏感程度。精品文檔放心下載中心點(diǎn)聚類算法的基本策略是:首先為每個族隨機(jī)選擇一個代表點(diǎn);剩余的數(shù)據(jù)點(diǎn)根據(jù)其與代表點(diǎn)的距離分配給最近的一個簇。然后反復(fù)用非代表點(diǎn)來替換代表點(diǎn),以改進(jìn)聚類的質(zhì)量,降低聚類質(zhì)量的代價函數(shù),即數(shù)據(jù)點(diǎn)到其類代表點(diǎn)的平方誤差和。每次代表點(diǎn)替換發(fā)生時,檢查代價函數(shù)是否降低,如果降低則保留替換,否則放棄該替換,重復(fù)上述過程直到代價函數(shù)不再發(fā)生變化為止。給定聚類數(shù)K,典型的K中精品文檔放心下載

心點(diǎn)聚類算法的主要步驟概括如下:1.初始化:隨機(jī)選取足個樣本作為初始的中心點(diǎn);2.樣本指派:計(jì)算樣本到各個類中心的距離,將樣本劃分到距離其最近的中心點(diǎn)所代表的簇;謝謝閱讀3.類中心替換:隨機(jī)地選擇一個非類中心點(diǎn),計(jì)算用選中的樣本代替原來的類中心的代價函數(shù),如果代價函數(shù)降低,則替換原有的中心點(diǎn)形成新的K個中心點(diǎn)集合;精品文檔放心下載4.重復(fù)步驟2和3直到類中心點(diǎn)不評發(fā)生變化后停止。感謝閱讀PAM(PartitioningAroundMedoids)是最早提出的K中心點(diǎn)算法之一。雖然K中心算法比K均值算法在處理噪聲點(diǎn)時表現(xiàn)的要健壯,但是K中心點(diǎn)算法的執(zhí)行代價比K均值方法高,其時間復(fù)雜度為如果數(shù)據(jù)集規(guī)模和類的個數(shù)較大,PAM算法的效率會很低為了用K中心點(diǎn)方法處理大規(guī)模數(shù)據(jù)集,Kaufman和Rousseeuw將抽精品文檔放心下載,.樣方法和PAM算法結(jié)合提出了一個新的尺中心點(diǎn)方謝謝閱讀法,稱為CLARA(ClusteringLARgeApplications)算法CLARA算法+再考慮整個數(shù)據(jù)集,而是從整個數(shù)據(jù)集中進(jìn)行抽樣,選取數(shù)據(jù)中的一小部分作為數(shù)據(jù)的樣本,然后用PAM算法從這些選中的樣本中選擇中心點(diǎn)。為了減少抽樣樣本對最終聚類的影響,CLARA算法采取多次抽樣,對每次抽樣樣本應(yīng)用PAM算法,返回感謝閱讀這幾次抽樣最好的聚類結(jié)果作為最終結(jié)果。通過抽樣處理,CLARA算法一次抽 樣 的 時 間 復(fù) 雜 度 為,其中s是抽樣樣本的大小。CLARA算法的一大缺點(diǎn)是不能保證最佳的個類中心點(diǎn)被選中為最終的類中心點(diǎn),如果在抽樣的時候這辟數(shù)據(jù)點(diǎn)沒有被抽中,那么CLARA算法將永遠(yuǎn)找不到最佳聚類。為了改進(jìn)CLARA算法的聚類質(zhì)量,Ng和Han提出了CLARANS算法(Clustering精品文檔放心下載

LargeApplicationsbaseduponRANdomizedSearch),該算法也采用了抽樣技術(shù),但是在謝謝閱讀搜索的每個階段不訴使用一個固定的抽樣集合,而在搜索的每一步都會隨機(jī)精品文檔放心下載的抽取樣本,其時間復(fù)雜度為。CLARANS算法的聚類質(zhì)量也依賴于所用的抽樣方法。謝謝閱讀實(shí)驗(yàn)與分析針對相似度計(jì)算模型和數(shù)據(jù)特征兩方面的工作,實(shí)驗(yàn)分為兩部分:基于不同高斯型相似度的實(shí)驗(yàn)結(jié)果和基于不同特征的實(shí)驗(yàn)結(jié)果。每部分都使用模擬數(shù)據(jù)及實(shí)際數(shù)據(jù)對相應(yīng)方法進(jìn)行測試,聚類算法選用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ù)首先對模擬數(shù)據(jù)進(jìn)行實(shí)驗(yàn),部分?jǐn)?shù)據(jù)集來自文獻(xiàn)。對于各種相似性度量中涉及到的參數(shù),包括尺度參數(shù)、近鄰數(shù)K