用于彩圖分割的自適應(yīng)譜聚類(lèi)算法

(1.中南大學(xué) 信息科學(xué)與工程學(xué)院 智能系統(tǒng)與智能軟件研究所， 長(zhǎng)沙 410083; 2.湖南省直機(jī)關(guān)行政學(xué)院， 長(zhǎng)沙 410001)



摘 要：

針對(duì)自調(diào)節(jié)譜聚類(lèi)算法的缺陷，提出一種新的自適應(yīng)譜聚類(lèi)算法。它用全局平均N近鄰距離作為比例參數(shù)σ， 利用本征矢差異來(lái)估計(jì)最佳聚類(lèi)分組數(shù)k，達(dá)到了比前者更好的效果，且更容易實(shí)現(xiàn)。在彩色圖像分割實(shí)際應(yīng)用中的實(shí)驗(yàn)結(jié)果表明，該算法適應(yīng)性強(qiáng)、計(jì)算代價(jià)小、精度較高，性能好于或至少不差于以往的類(lèi)似算法。

 關(guān)鍵詞：譜分析; 譜聚類(lèi); 彩色圖像分割

 中圖分類(lèi)號(hào)：TP18 文獻(xiàn)標(biāo)志碼： A

文章編號(hào)：10013695(2008)12369703



Adaptive spectral clustering algorithm for color image segmentation



ZHONG Qingliu1，2， CAI Zixing1



(1.Institute of Intelligent System Software， School of Information Science Engineering， Central South University， Changsha410083， China; 

2.Direct Branch under Hunan Province Administration College， Changsha 410001， China)



Abstract:

This paper put forwarded a new algorithm， for overcoming the bug of selftuning spectral clustering， called as the adaptive spectral cluster. It took average distance of Nnearneighbour as scaling parameter σ， automatically estimated optimal clustering grouping k by means of information about enginvector difference and could get better effect and implement easyer. The results of experiments in application about color image segmentation show that the algorithm has stronger adaptability， lower calculate cost and highter precision. It’s performace exceeds or at least no lower to the others similarity one.

 Key words：spectral analysis; spectral cluster; color image segmentation



0 引言

基于譜圖理論的譜分析方法作為一種模式識(shí)別新方法，以其優(yōu)異的性能成為其他分類(lèi)方法強(qiáng)大的競(jìng)爭(zhēng)對(duì)手。譜分析方法^[1]利用基于數(shù)據(jù)點(diǎn)間距離矩陣的本征矢分解來(lái)實(shí)現(xiàn)分類(lèi)，它并不需要估計(jì)明確的數(shù)據(jù)分布模型，而是依據(jù)數(shù)據(jù)點(diǎn)對(duì)相似矩陣的譜分析。通過(guò)計(jì)算、分析矩陣本征譜，最終利用某種分類(lèi)算法將數(shù)據(jù)點(diǎn)分類(lèi)成組。它容易實(shí)現(xiàn)，組合了處理復(fù)雜多維數(shù)據(jù)集的能力，有望成為最具競(jìng)爭(zhēng)力的模式識(shí)別新技術(shù)之一。

在利用譜分析結(jié)果實(shí)現(xiàn)分類(lèi)的各種算法中，最簡(jiǎn)單且有效的莫過(guò)于譜聚類(lèi)方法。然而，基于劃分的標(biāo)準(zhǔn)譜聚類(lèi)算法通常需要事先估計(jì)聚類(lèi)參數(shù)(如聚類(lèi)分組數(shù)k、比例參數(shù)σ)。聚類(lèi)結(jié)果的優(yōu)劣通常與聚類(lèi)參數(shù)估計(jì)正確性密切相關(guān)。對(duì)復(fù)雜數(shù)據(jù)集而言，準(zhǔn)確估計(jì)其聚類(lèi)參數(shù)本身就是一個(gè)難題，因而在一般情況下難以保證聚類(lèi)效果。由于聚類(lèi)參數(shù)與被處理數(shù)據(jù)的分布密切相關(guān)，現(xiàn)實(shí)應(yīng)用的數(shù)據(jù)分布通常千差萬(wàn)別，在應(yīng)用中就必須針對(duì)不同的數(shù)據(jù)集設(shè)定不同的聚類(lèi)參數(shù)，這難免限制了它的實(shí)際應(yīng)用。如果能夠建立聚類(lèi)參數(shù)與數(shù)據(jù)分布關(guān)系的數(shù)學(xué)模型，或找到一種能夠根據(jù)數(shù)據(jù)分布自動(dòng)估計(jì)聚類(lèi)參數(shù)的方法，從而實(shí)現(xiàn)對(duì)任意數(shù)據(jù)均能自動(dòng)估計(jì)最佳聚類(lèi)參數(shù)的自適應(yīng)譜聚類(lèi)， 就能使譜聚類(lèi)方法如虎添翼。為了解決這個(gè)問(wèn)題，近年來(lái)不少學(xué)者在這方面做了不懈努力，并且已經(jīng)取得了一些成果^[2~4]。A.Ng等人^[2]于2001年提出了利用數(shù)據(jù)分布通過(guò)分析親和力矩陣本征值來(lái)確定聚類(lèi)分組數(shù)的方法，并指明 L 矩陣的第一個(gè)最大本征值是一個(gè)取值為1的重復(fù)本征值，其數(shù)量等于聚類(lèi)數(shù)，這意味著可以通過(guò)計(jì)算等于1的本征值的數(shù)量來(lái)估計(jì)聚類(lèi)數(shù)。然而，這只適用于各聚類(lèi)有明顯分隔而其間無(wú)噪聲的情況，一旦有噪聲，其本征值將與1偏離，此法就不再有用;為此，M.Polito等人^[3]于2002年提出了另一種選擇，即尋找降幅最大的本征值，但它缺乏足夠的理論依據(jù)。因?yàn)?L 的本征值是與各聚類(lèi)相應(yīng)的子矩陣本征值的組合，它們均與單個(gè)聚類(lèi)結(jié)構(gòu)相關(guān)。2005年，L. ZelnikManor等人^[4]提出STSC(selftuning spectral clustering，自調(diào)節(jié)譜聚類(lèi))算法模型。它能根據(jù)數(shù)據(jù)分布狀況來(lái)自動(dòng)估計(jì)相應(yīng)數(shù)據(jù)點(diǎn)的比例參數(shù)，利用對(duì) L 矩陣排序后的本征矢結(jié)構(gòu)，用梯度下降法尋找代價(jià)相應(yīng)最小的本征矢組合來(lái)自動(dòng)確定最佳聚類(lèi)分組數(shù)k，因而實(shí)現(xiàn)真正意義上的自動(dòng)聚類(lèi)。實(shí)驗(yàn)表明，此模型能夠處理一些復(fù)雜問(wèn)題，且能達(dá)到較高精度，在解決一些現(xiàn)實(shí)應(yīng)用問(wèn)題中表現(xiàn)出色。然而該算法的不足之處是，它通過(guò)反復(fù)重組旋轉(zhuǎn)矢量來(lái)搜索代價(jià)最小的分組數(shù)k并借此確定最佳分組數(shù)k的做法，帶來(lái)了過(guò)高計(jì)算代價(jià)而導(dǎo)致運(yùn)行緩慢;另一個(gè)缺陷是，為了使該算法能夠正確估計(jì)最佳聚類(lèi)分組數(shù)，仍需要針對(duì)不同的數(shù)據(jù)設(shè)定不同的閾值參數(shù)，否則就可能出錯(cuò)，這使它的自調(diào)節(jié)性大打折扣。圖1是將該文自己提供算法的原代碼用于圖像數(shù)據(jù)集進(jìn)行二值圖像分割的情況。其中，圖1(a)是STSC算法隨機(jī)運(yùn)行時(shí)的分割出錯(cuò)結(jié)果；(b)是經(jīng)調(diào)整參數(shù)后得到的正確結(jié)果;(c)(d)則是它用于復(fù)雜圖像分割的情況，說(shuō)明對(duì)于復(fù)雜的圖像，STSC算法的分割結(jié)果很難令人滿意。實(shí)際上圖1(c)(d)是經(jīng)過(guò)多次參數(shù)調(diào)節(jié)嘗試才找到的相對(duì)而言較好的結(jié)果，因此該算法仍需進(jìn)一步改進(jìn)。

在許多現(xiàn)實(shí)應(yīng)用中(如動(dòng)態(tài)目標(biāo)識(shí)別與追蹤)，實(shí)時(shí)性和自適應(yīng)性往往是必須考慮的重要因素之一。理想情況下最好是無(wú)須調(diào)節(jié)任何參數(shù)就能快捷地處理各種情況并保證足夠小的出錯(cuò)概率。為此，基于上述算法^[2~4]的啟發(fā)，本文提出一種新的自適應(yīng)譜聚類(lèi)(adaptative spectral clustering，ASC)算法。它采用全局平均N近鄰距離的比例參數(shù)代替局部N近鄰距離的比例參數(shù)，這可在構(gòu)造親和力矩陣時(shí)減少計(jì)算代價(jià)；采用自適應(yīng)k選擇算法來(lái)自動(dòng)估計(jì)最佳聚類(lèi)分組數(shù)k，從而避免了STSC算法計(jì)算代價(jià)過(guò)高的缺陷。仿真實(shí)驗(yàn)表明:與STSC相比，ASC實(shí)現(xiàn)更容易、計(jì)算代價(jià)更低、出錯(cuò)概率更小，能夠滿足實(shí)際應(yīng)用的大多數(shù)要求，可實(shí)現(xiàn)一般意義上的全自動(dòng)聚類(lèi)。

1 譜圖理論簡(jiǎn)述

譜圖理論將數(shù)據(jù)集X={x1，x2，…，xn}用G=(V，E)表示成由頂點(diǎn)集V和邊集E構(gòu)成的圖。其中，圖中各頂點(diǎn)V代表數(shù)據(jù)集中的相應(yīng)數(shù)據(jù)點(diǎn)， V={xi};圖中連接頂點(diǎn)間邊E的連接權(quán)W代表相應(yīng)數(shù)據(jù)點(diǎn)間的相似性，E={Wij}。兩頂點(diǎn)vi 和vj帶有非負(fù)連接權(quán)wij≥0; 圖的加權(quán)鄰接矩陣 W =(wij)，i， j=1，…，n。而wij=0表示兩個(gè)頂點(diǎn)vi和vj無(wú)連接。由于圖G是無(wú)向的，要求wij=wji。頂點(diǎn)vi∈V的度數(shù)定義為

Dii=∑ n j=1 wij; wi， j=e-‖X(i)-X(j)‖22//σ2(1) 

譜圖理論用矩陣?yán)碚摵途€性代數(shù)來(lái)分析圖的鄰接矩陣，這在處理規(guī)則性和對(duì)稱(chēng)性問(wèn)題中尤其有效。在許多情況下，某些本征值可以看做圖的代數(shù)連通性標(biāo)志，譜技術(shù)能夠很好地處理一般的圖問(wèn)題。為了能夠用代數(shù)方法進(jìn)行分析，通常將相似圖表示為一個(gè)矩陣，進(jìn)而解下面的本征問(wèn)題:

( D-W)X =λD X (2) 

其中：XA(i)= 1 if i∈A0 if iA ;L=D-W 。

通過(guò)解此矩陣本征值問(wèn)題就可以利用本征值和相應(yīng)的本征矢矩陣提供的數(shù)據(jù)分布結(jié)構(gòu)信息來(lái)進(jìn)行譜分析。這里所說(shuō)的譜，是指由(按本征值大小排序?qū)?yīng)的)一組本征矢構(gòu)成的序列。 

2 自適應(yīng)譜聚類(lèi)算法

21 比例參數(shù)σ的估計(jì)

一般聚類(lèi)算法中需要用戶(hù)設(shè)定的參數(shù)主要有比例參數(shù)σ和聚類(lèi)分組數(shù)k。前一個(gè)參數(shù)的主要作用是根據(jù)數(shù)據(jù)分布狀況(密度/間距)調(diào)節(jié)測(cè)量尺度，以確保測(cè)量對(duì)象規(guī)范化并落入測(cè)量范圍內(nèi)；后一個(gè)參數(shù)的作用主要是用最佳的劃分?jǐn)?shù)確保誤差最小。文獻(xiàn)[4]采用局部N近鄰距離作為σ參數(shù)的方法，盡管能夠按數(shù)據(jù)分布的不同逐點(diǎn)確定相應(yīng)的σ參數(shù)，較好地描述了數(shù)據(jù)集的局部特性，然而也相應(yīng)地增加了計(jì)算代價(jià)。在大多數(shù)現(xiàn)實(shí)問(wèn)題中，對(duì)同一個(gè)數(shù)據(jù)集而言，直接用全局N近鄰平均距離作為σ參數(shù)足以滿足精度要求，同時(shí)還能降低計(jì)算代價(jià)。出于這種考慮，本文采用數(shù)據(jù)集全局N近鄰平均距離作為σ參數(shù)的近似估計(jì)。

σi=d(Xi，XN)(3)

其中XN為Xi的第N個(gè)鄰域。

σ=(1/n)∑ n j=1 (1/N)∑ N i=1 σi(4) 

22 聚類(lèi)分組數(shù)k的選擇算法

仔細(xì)分析本征問(wèn)題式(4)的解可知，按 L本征值排序的本征矢矩陣X 中的每一行代表特征空間中的一個(gè)點(diǎn);而每一列對(duì)應(yīng)于特征空間的一個(gè)特征(坐標(biāo))分量。通常估計(jì)最佳聚類(lèi)分組數(shù)，實(shí)質(zhì)上是選擇能夠?qū)崿F(xiàn)對(duì)數(shù)據(jù)準(zhǔn)確劃分的最佳特征數(shù)。由于本征矢矩陣 X 的各列是按其相應(yīng)本征值的大小排序生成，最佳劃分問(wèn)題最終成為選擇多少列本征矢問(wèn)題。

為此，本文利用相鄰本征矢平均差異的方式來(lái)確定近似最佳分組數(shù)的方案，即通過(guò)計(jì)算 X 矩陣中前k個(gè)相鄰列間的平均差異與第一列的比值，直到此差異比小于給定的閾值時(shí)，此時(shí)相應(yīng)的k值便是近似最佳選擇。若式(2)的解按本征值排序生成的本征矢矩陣為 X，則相鄰列矢量間的平均差的絕對(duì)值可表示為



Hi-1，i=|Xi-1-Xi |; i=1，2，…，k，…，n(5) 

它與第一列(最大本征值對(duì)應(yīng)的本征矢)平均值之比為

Ji=Hi-1，i/|X i|; i=1，2，…，k，…，n(6) 

其中Ji是隨著i的增大而減小的變量。隨著 X 矩陣中的相鄰列(分量)差異減小，相應(yīng)列對(duì)聚類(lèi)劃分的作用也減小，當(dāng)它減少到一定程度時(shí)，繼續(xù)增加列矢量數(shù)對(duì)聚類(lèi)劃分已經(jīng)不再有益，此時(shí)的i便是最佳聚類(lèi)數(shù)。以下是實(shí)現(xiàn)上述思路的算法偽代碼。

自適應(yīng)k選擇算法: 

a)初始化。輸入 L的按本征值排序規(guī)則生成的相應(yīng)本征矢矩陣X，并設(shè)下列初值 ：

i=1;H(i)=c1;J(i)=c2;q=c3;

%% c1=c2為大于1的任意初始常數(shù)，c3=01~02。

b)計(jì)算相鄰各列差異平均比值:

while J(i)>q%q—閾值

i=i+1;

H(i)=abs(mean(X(:，i-1)-X(:，i)));

J(i)=H(i)/abs(mean(X(:，1));

end 

c)輸出選定的k值。

k=i;

23 用于彩圖分割的ASC算法

給定一組數(shù)據(jù)點(diǎn)S={s1，…，sn}∈Rl，將這些原始數(shù)據(jù)點(diǎn)聚類(lèi)成K個(gè)子集的步驟如下：

a)按式(3)(4)計(jì)算平均比例參數(shù)σI(xiàn)，σX。其中：I、X分別代表像素點(diǎn)亮度、距離信息。由此構(gòu)造親和力矩陣為

W (i， j)=e-(‖I(i)-I(j)‖22/σ2I+‖X(i)-X(j)‖22/σ2x);

if i≠j; wii=0

b)定義對(duì)角矩陣 D ii=∑ n j=1 wij，并由此構(gòu)造標(biāo)準(zhǔn)拉氏矩陣 L = D -1/2 WD -1/2。

c)解 L 的本征方程 ，求本征值及本征矢。

d)排列 L 的本征矢，以形成新矩陣 X 的各列矢量x1，x2，…，xk，…，xn。

e)運(yùn)行自適應(yīng)k選擇算法，確定最佳聚類(lèi)數(shù)k。

f)以此為依據(jù)(自動(dòng))選擇 X 矩陣中的前k列本征矢，形成新的 X 矩陣。

g)將 X 的各行按下式重新規(guī)范化為單位長(zhǎng)矢量 Y：

Y ij= X ij/(∑ jX 2ij)2;Y ∈ R  n×k 

h)將 Y 的各行視為 R  k空間的點(diǎn)，用Kmeans算法聚類(lèi)成k個(gè)聚類(lèi)。

i)標(biāo)記原始數(shù)據(jù)集。 當(dāng)且僅當(dāng) Y 的第i 行標(biāo)記為聚類(lèi)j 時(shí)，將原始數(shù)據(jù)點(diǎn)si標(biāo)記為聚類(lèi)j。 

3 實(shí)驗(yàn)分析

為了驗(yàn)證算法的有效性，本文采用Berkeley彩色圖像數(shù)據(jù)集^[5]，相應(yīng)的圖像文件名詳見(jiàn)表1，并分別用ASC與STSC算法對(duì)相同圖像數(shù)據(jù)進(jìn)行圖像分割對(duì)比實(shí)驗(yàn)。需要說(shuō)明的是，STSC算法直接采用了原始論文所提供的源代碼進(jìn)行二值圖像分割，其結(jié)果如圖1所示；而ASC算法則用于進(jìn)行彩色圖像分割，其結(jié)果如圖2所示。

表1所列的是各相應(yīng)算法在處理不同圖像分割任務(wù)時(shí)50次運(yùn)行的平均結(jié)果。實(shí)驗(yàn)表明:與STSC算法相比，ASC算法時(shí)間代價(jià)少于STSC，說(shuō)明ASC確實(shí)較STSC更高效。

表1 ASC與STSC算法比較 

其中，圖2、3中的(a)是原始圖像(照片);(b)反映了自適應(yīng)k選擇算法運(yùn)行情況，圖中的虛線曲線總體向下的趨勢(shì)顯示了本征矢差異比隨著聚類(lèi)分組數(shù)k的增加而下降的特點(diǎn)，而實(shí)曲線則顯示了隨著所選本征矢列數(shù)的增加相鄰本征矢差異逐漸減小的事實(shí)，當(dāng)本 征矢差異比減小到相應(yīng)的閾值而導(dǎo)致程序終止時(shí)，此時(shí)的k便是最佳分組數(shù); (c)反映的是相應(yīng)圖像的分割聚類(lèi)分布情況;(d)則是按分割聚類(lèi)進(jìn)行色彩平均填充后的最終結(jié)果。 

4 結(jié)束語(yǔ)

根據(jù)數(shù)據(jù)分布自動(dòng)估計(jì)聚類(lèi)參數(shù)是一個(gè)難題，而ASC算法為解決這一難題提供了又一種新的選擇方案。盡管此方案能夠較好地解決彩色圖像分割的大量應(yīng)用問(wèn)題，較以往的算法有了一些進(jìn)步，然而，譜分析理論和應(yīng)用研究遠(yuǎn)未完結(jié)，更高效實(shí)用的算法有待進(jìn)一步探索。

參考文獻(xiàn)：

[1]AZRAN A， GHAHRAMANI Z. Spectral methods for automatic multiscale data clustering[C]//Proc ofIEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington: IEEE Computer Society， 2006:190  197.

[2] NG A Y， JORDAN M I， WEISS Y. On spectral clustering: analysis and an algorithm[C]//Proc of Advances in Neural Information Processing Systems. 2001:585591.

[3] POLITO M， PERONA P. Grouping and dimensionality reduction by locally linear embedding[C]//Proc of Advances in Neural Information Processing Systems. 2002:12551262.

[4]ZELNIKMANOR L， PERONA P. Selftuning spectral clustering[C] //Proc of Advances in Neural Information Processing Systems. Cambridge:MIT Press， 2005:16011608.

[5] Berkeley segmentation dataset[EB/OL].(20031031)[20080110].http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench/BSDS300/html/dataset/images.html.