，，，

(西安理工大學(xué) 自動化與信息工程學(xué)院，西安 710048)

0 引言

圖像分割是一種根據(jù)紋理，顏色，灰度等視覺特征將圖像劃分成具有獨特性質(zhì)的目標(biāo)區(qū)域的技術(shù)和過程[1]，在計算機(jī)視覺領(lǐng)域中一直發(fā)揮著非常重要的作用。近年來，基于圖論的圖像分割方法已成為國內(nèi)外的一個研究熱點?，F(xiàn)有的基于圖論的方法[2-3]很多，其中基于圖論的最小生成樹算法因其簡單，高效且能獲取全局信息，在圖像分割中得到了廣泛應(yīng)用，但其使用自適應(yīng)的全局閾值進(jìn)行圖像分割，分割效果并不理想尤其在圖像細(xì)節(jié)方面。復(fù)雜網(wǎng)絡(luò)理論與圖像分割方法相結(jié)合，可以避免單一算法的不足，并為該領(lǐng)域提供了更多的選擇性。2009年，Backes A R提出一種新的描述圖像邊緣特征的方法，利用復(fù)雜網(wǎng)絡(luò)給圖像邊緣特征建模[4]，該方法不僅比傳統(tǒng)圖論法對圖像邊緣輪廓具有更好的表示結(jié)果而且它可以表示具有間隙或不完整信息的圖像邊緣輪廓；復(fù)雜網(wǎng)絡(luò)可以很好的表示圖像的紋理特征[5]，節(jié)點表示像素點，節(jié)點之間的連接表示像素點之間的相似性，提取場景中的全局紋理特征，不同類型的紋理呈現(xiàn)出不同的節(jié)點度分布。最近，Mourchid Y提出將圖像用圖形表示[6]，通過應(yīng)用社區(qū)檢測算法計算出單一模塊化特征度量，該度量對于圖像旋轉(zhuǎn)和小失真是不變的。

基于復(fù)雜網(wǎng)絡(luò)理論在圖像處理應(yīng)用中展現(xiàn)的優(yōu)越性能，本文將彩色圖像分割與復(fù)雜網(wǎng)絡(luò)理論相結(jié)合，根據(jù)像素點之間的相似性，對大量的圖像數(shù)據(jù)建模，從復(fù)雜網(wǎng)絡(luò)的角度構(gòu)造社團(tuán)網(wǎng)絡(luò)結(jié)構(gòu)圖，然后用社團(tuán)檢測算法進(jìn)行社團(tuán)劃分，對圖像相似像素聚類，進(jìn)而實現(xiàn)彩色圖像分割。社團(tuán)檢測一直是復(fù)雜網(wǎng)絡(luò)學(xué)科中研究的熱點，到目前為止，比較常用的算法有GN 算法[7]、Newman 快速算法[8]等。GN 算法是由Girvan 和 Newman 在2001年提出，該算法思想基礎(chǔ)為分裂法，依次刪除網(wǎng)絡(luò)中邊介數(shù)值最高的邊，當(dāng)算法結(jié)束時整個網(wǎng)絡(luò)將被劃分成不同的社團(tuán)。但是GN算法有兩個缺點：其中一個為該方法和其他傳統(tǒng)方法一樣都無法判斷一個網(wǎng)絡(luò)最終可以被劃分成社團(tuán)的個數(shù)。另外一個缺點就是速度較慢。Newman 快速算法以貪心算法思想為基礎(chǔ)的凝聚算法。該算法可用于大型復(fù)雜網(wǎng)絡(luò)，在社區(qū)劃分過程中，經(jīng)過計算比較得到最大的模塊度值Q，所對應(yīng)的社區(qū)結(jié)構(gòu)就是該網(wǎng)絡(luò)最好的社區(qū)結(jié)構(gòu)組成，但是該算法準(zhǔn)確度沒有GN算法高。本文采用的是目前比較流行的社團(tuán)檢測算法即譜聚類算法，譜聚類算法能夠廣泛的應(yīng)用于任意的數(shù)據(jù)空間上，尤其在運行高維數(shù)據(jù)如圖像數(shù)據(jù)時，相比于傳統(tǒng)的聚類算法，該算法更加完整、更加全面，且在得到社團(tuán)劃分結(jié)果的質(zhì)量方面比其他算法要好。

在本文工作中，考慮了一種基于社團(tuán)檢測算法的特征，稱為模塊化[9]，這是目前使用最廣泛的質(zhì)量函數(shù)，當(dāng)基礎(chǔ)社團(tuán)結(jié)構(gòu)未知時，比較不同社團(tuán)檢測算法對真實數(shù)據(jù)的有效性。實驗采用BSDS300圖像庫[10]，并且通過實驗結(jié)果表明該方法在精度方面優(yōu)于傳統(tǒng)圖論分割方法，可以獲得更好的分割結(jié)果。

1 復(fù)雜網(wǎng)絡(luò)的圖像表示

Girvan和Newman在2002年最先提出網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的概念[11]，即網(wǎng)絡(luò)中存在內(nèi)部連接緊密的節(jié)點群而節(jié)點群之間連接稀疏。復(fù)雜網(wǎng)絡(luò)的社團(tuán)檢測算法是這幾年許多不同的科學(xué)領(lǐng)域研究的熱點問題。本文從復(fù)雜網(wǎng)絡(luò)的角度對彩色圖像進(jìn)行建模，圖像中的像素點表示網(wǎng)絡(luò)中的節(jié)點，像素之間的相似性表示網(wǎng)絡(luò)之間的連接。將網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)圖表示為一個數(shù)學(xué)模型，即G=(V,E)，V表示由n個節(jié)點組成的點集，E是由m條連接邊構(gòu)成的邊集。對于一副具有R、G、B三個顏色分量的彩色圖像來說，每個像素點都可以表示為RGB顏色空間中的一個節(jié)點xi。利用下面的公式(1)，按照從左到右，從上到下的順序計算每一個像素點4鄰域的相似度，首先需構(gòu)造n維零矩陣A，后需計算目標(biāo)像素點與其鄰域像素點之間的RGB歐式距離，具體公式如下：

(1)

其中：xi(k)表示節(jié)點i在第k個顏色分量上的取值，k=1,2,3分別表示R,G,B分量。

若d(xi,xj)小于等于閾值T，則認(rèn)為兩個像素點足夠相似，用一條邊將其連接并在矩陣A相應(yīng)元素aij記為1，否則認(rèn)為兩像素點之間不相似，aij記為0。其中A為相似度矩陣同時也是稀疏的鄰接矩陣，在存儲時可以節(jié)省很大的空間。本文可根據(jù)A構(gòu)造無向網(wǎng)絡(luò)拓?fù)鋱D。如公式(2)所述：

(2)

從上式中顯然可以看出，閾值T對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響產(chǎn)生著決定性作用。如果選取閾值T過小將導(dǎo)致網(wǎng)絡(luò)連接過于稀疏，但閾值T也不能過大，因為閾值T越大丟失的圖像信息就越多，這會影響最終的圖像分割結(jié)果的質(zhì)量。目前，還只能依靠經(jīng)驗或者通過實驗來確定閾值T。本文根據(jù)實驗所得的距離d的數(shù)據(jù)，設(shè)置一個閾值T的取值范圍[dmin,dmax]，在這個范圍內(nèi)采用合適的步長，選取閾值，不同的閾值對應(yīng)不同的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)圖，之后選取結(jié)構(gòu)較好的網(wǎng)絡(luò)圖進(jìn)行社團(tuán)檢測。

2 譜聚類社團(tuán)檢測算法

譜聚類算法[12-13]能夠廣泛的應(yīng)用于任意的數(shù)據(jù)空間上，理論基礎(chǔ)是以拉普拉斯矩陣研究為主的譜圖思想，而其核心的技術(shù)為通過對樣本數(shù)據(jù)進(jìn)行降維處理后進(jìn)行聚類。

2.1 圖的拉普拉斯矩陣

(1)對于任意的p∈Rn有：

(3)

(2)Lsym是半正定的矩陣并且有n個非負(fù)的實數(shù)特征值，0=λ1≤λ2≤…λn。

2.2 圖劃分準(zhǔn)則

譜聚類算法的理論基礎(chǔ)為譜圖理論，用到的主要思想為圖分割法。在圖G中，對于給定數(shù)量K個子集，將每個子集可以分別表示為A1,A2,…Ak，且它們之間沒有交集，圖的割[14]可以適當(dāng)?shù)亩x為：

(4)

K的指標(biāo)向量可以定義為hj=(h1,j,...,hn,j)，其中:

(5)

(6)

其中:Tr表示矩陣的跡。

(7)

其中:TT′=1，Lsym的前k個特征向量構(gòu)成矩陣T的列，每個特征向量與該函數(shù)的值相對應(yīng)。由此，本文可以通過對T進(jìn)行聚類得到k個子集。

2.3 k-means聚類算法

譜聚類算法最后一步經(jīng)常利用k-means聚類算法[15]對降維后的數(shù)據(jù)進(jìn)行聚類分析，k-means算法是一種基于聚類質(zhì)心技術(shù)，具有算法簡單，運行速度快等優(yōu)點。輸入?yún)?shù)k，可將數(shù)據(jù)樣本聚集成k個不同的組，在同一個組內(nèi)數(shù)據(jù)樣本的相似度高，不同組之間數(shù)據(jù)樣本不相似。

算法過程如下：首先從數(shù)據(jù)樣本中選取k個對象作為初始均值，即作為初始的類的中心，之后對于數(shù)據(jù)樣本中剩余的每個對象，按照它到每個組中心的距離，將它歸入到距離最相近的組中，遍歷完所有的對象后，再重新計算每個組的新均值作為該組的新中心。為了能達(dá)到全局最優(yōu)，重復(fù)上述步驟至平方誤差準(zhǔn)則最小時結(jié)束。通過k-means算法對處理后圖像數(shù)據(jù)進(jìn)行聚類，將像素點劃分成K個類別，相應(yīng)的相似像素在一個歸屬類，最終實現(xiàn)圖像分割。

3 本文算法模型

將基于譜聚類思想的復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法應(yīng)用于彩色圖像分割中主要分為三個階段：

第一階段將彩色圖像利用復(fù)雜網(wǎng)絡(luò)理論抽象為一個社團(tuán)網(wǎng)絡(luò)結(jié)構(gòu)圖，其中利用一定的相似性度量計算，將原圖像矩陣轉(zhuǎn)換為相似度矩陣；

第二階段將轉(zhuǎn)換后的相似度矩陣根據(jù)圖劃分準(zhǔn)則進(jìn)行聚類求精并取得相應(yīng)的社團(tuán)結(jié)構(gòu)，利用質(zhì)量函數(shù)對社團(tuán)劃分結(jié)果進(jìn)行有效性評價；

第三階段根據(jù)聚類后的相似像素數(shù)據(jù)得到圖像分割結(jié)果。

在本實驗中，預(yù)先不知道社團(tuán)劃分的數(shù)量,首先利用譜聚類的社團(tuán)檢測算法集中計算前k個最小特征值并找到相應(yīng)的特征向量。其中k的選取根據(jù)歸一化拉普拉斯矩陣的第二特性。之后，將k個特征向量構(gòu)成矩陣的列，矩陣的每一行對應(yīng)于具有k個特征的節(jié)點。最后，使用K-means的算法來計算節(jié)點之間的相似度并檢測k個社團(tuán)。

本文算法具體步驟如下：

輸入：待分割彩色圖像，閾值T，聚類數(shù)K

1)利用復(fù)雜網(wǎng)絡(luò)理論將彩色圖像表示為網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)圖。

2)利用像素之間的相似性度量計算求出相似度矩陣A。

3)計算歸一化Laplacian矩陣Lsym。

4)計算k個特征值，并對它們進(jìn)行排序0=λ1≤λ2≤...λk。

5)計算特征值λ1,λ2,...λk所對應(yīng)的特征向量μ1,μ2,...μk。

6)構(gòu)造矩陣U以μ1,μ2,...μk為列向量，且yi∈RK，i=1,...n表示矩陣U的行數(shù)。

7)利用K-means算法對(yi)i=1,...n進(jìn)行聚類，并將相應(yīng)像素點歸屬為C1,...Ck。聚類結(jié)果為網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)圖的劃分結(jié)果，也是原圖像中對應(yīng)像素點所屬的類別。

8)利用模塊化質(zhì)量函數(shù)評價社團(tuán)結(jié)構(gòu)的有效性。

輸出：分割后的彩色圖像。

4 結(jié)果與分析

為了檢驗本文算法的性能，對本文算法進(jìn)行實驗分析。算法實驗環(huán)境為：windows 7系統(tǒng)、Intel i5處理器、4GB內(nèi)存，實驗平臺為MATLAB R2014a。實驗圖像來自于BSDS300圖像庫。

4.1 不同閾值對圖像分割效果的影響

對于同一副彩色圖像在選取不同閾值時，實驗分割結(jié)果圖如圖1所示，a(1)、a(2)和a(3)分別為閾值逐漸增大時的分割效果圖，從圖1中可以看出在各個閾值下的圖像分割結(jié)果，閾值較小時，分割比較精細(xì)，能夠得到完整的邊緣信息，圖像a(1)所示；閾值過大，分割結(jié)果非常粗糙，如圖像a(3)所示，得到的分割結(jié)果沒有意義?？梢愿鶕?jù)不同的實驗要求選取合適的閾值。圖1實驗結(jié)果的相關(guān)數(shù)據(jù)如表1所示，其中模塊度Q可以用來定量的評估網(wǎng)絡(luò)社區(qū)劃分的質(zhì)量，其值越接近1，表示網(wǎng)絡(luò)劃分出的社區(qū)結(jié)構(gòu)的強(qiáng)度越強(qiáng)，則劃分質(zhì)量越好。從表1中可以看出，在一定范圍內(nèi)，隨著分割結(jié)果越細(xì)膩，模塊度越高，說明網(wǎng)絡(luò)社區(qū)劃分質(zhì)量也就越好，結(jié)構(gòu)越強(qiáng)。

圖1 各閾值下的實驗分割結(jié)果

表1 圖1中的實驗數(shù)據(jù)

4.2 相關(guān)算法的分析比較

本文算法在BSDS300圖像庫中進(jìn)行圖像分割對比實驗，實驗結(jié)果如圖2所示。第一列為原始圖像，第二列為有效的自適應(yīng)閾值分割算法[16]實驗結(jié)果，其中k取值為230，min為30，第三列為本文算法實驗結(jié)果。從圖中可以看到自適應(yīng)閾值分割算法在紋理區(qū)域容易產(chǎn)生很多細(xì)小的，離散的區(qū)域，受到紋理影響比較大；本文采用譜聚類社區(qū)劃分算法，在區(qū)域合并時聚集效果要好于自適應(yīng)閾值分割算法，極大的提高了區(qū)域合并的效果，且能夠得到完整的物體邊緣，區(qū)域輪廓清晰，同時也符合人眼的視覺直觀感受，分割結(jié)果也較為成功。

圖2 圖像分割對比實驗

表2 圖2中precision-recall實驗數(shù)據(jù)

本文采用precision-recall標(biāo)準(zhǔn)對圖2中的分割結(jié)果進(jìn)行定量評價，precision-recall廣泛用于信息檢索和統(tǒng)計學(xué)分類領(lǐng)域的兩個度量值。兩個參數(shù)取值在0和1之間，數(shù)值越接近1，查全率或查準(zhǔn)率就越高，圖像分割精度越高，F(xiàn)-Measure是Precision和Recall加權(quán)調(diào)和平均，當(dāng)F值較高時說明實驗方法比較有效。實驗中每幅圖ground truth來自于BSDS300圖像庫[15]的人工分割結(jié)果。表2中p表示precision，R表示recall，F(xiàn)表示F-measure。從表2數(shù)據(jù)中可以看出，本文圖像分割算法的實驗結(jié)果要優(yōu)于自適應(yīng)閾值分割算法，較符合人類的視覺感知，取得了更好的圖像分割效果，驗證了本文圖像分割算法的有效性。

5 結(jié)語

從復(fù)雜網(wǎng)絡(luò)的角度出發(fā)，根據(jù)圖像的相似性度量對圖像數(shù)據(jù)進(jìn)行建模，并使用譜聚類算法劃分網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)圖，進(jìn)而得到圖像的聚類結(jié)果，取得了較好的圖像分割效果。實驗表明利用網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)圖對圖像數(shù)據(jù)中的復(fù)雜非線性結(jié)構(gòu)進(jìn)行建模是有效的，這為社團(tuán)檢測算法在圖像處理方面開拓了一個有價值的研究領(lǐng)域。未來工作準(zhǔn)備改進(jìn)本文算法，提高算法運行效率，也嘗試?yán)脠D像其它特征如紋理特征或者其它圖像相似性檢測方法對圖像進(jìn)行網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)圖建模，將其更好地應(yīng)用在圖像分割領(lǐng)域當(dāng)中。