，，，

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

0 引言

圖像分割是一種根據(jù)紋理，顏色，灰度等視覺(jué)特征將圖像劃分成具有獨(dú)特性質(zhì)的目標(biāo)區(qū)域的技術(shù)和過(guò)程[1]，在計(jì)算機(jī)視覺(jué)領(lǐng)域中一直發(fā)揮著非常重要的作用。近年來(lái)，基于圖論的圖像分割方法已成為國(guó)內(nèi)外的一個(gè)研究熱點(diǎn)?，F(xiàn)有的基于圖論的方法[2-3]很多，其中基于圖論的最小生成樹(shù)算法因其簡(jiǎn)單，高效且能獲取全局信息，在圖像分割中得到了廣泛應(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)圖論法對(duì)圖像邊緣輪廓具有更好的表示結(jié)果而且它可以表示具有間隙或不完整信息的圖像邊緣輪廓；復(fù)雜網(wǎng)絡(luò)可以很好的表示圖像的紋理特征[5]，節(jié)點(diǎn)表示像素點(diǎn)，節(jié)點(diǎn)之間的連接表示像素點(diǎn)之間的相似性，提取場(chǎng)景中的全局紋理特征，不同類(lèi)型的紋理呈現(xiàn)出不同的節(jié)點(diǎn)度分布。最近，Mourchid Y提出將圖像用圖形表示[6]，通過(guò)應(yīng)用社區(qū)檢測(cè)算法計(jì)算出單一模塊化特征度量，該度量對(duì)于圖像旋轉(zhuǎn)和小失真是不變的。

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

在本文工作中，考慮了一種基于社團(tuán)檢測(cè)算法的特征，稱(chēng)為模塊化[9]，這是目前使用最廣泛的質(zhì)量函數(shù)，當(dāng)基礎(chǔ)社團(tuán)結(jié)構(gòu)未知時(shí)，比較不同社團(tuán)檢測(cè)算法對(duì)真實(shí)數(shù)據(jù)的有效性。實(shí)驗(yàn)采用BSDS300圖像庫(kù)[10]，并且通過(guò)實(shí)驗(yàn)結(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é)點(diǎn)群而節(jié)點(diǎn)群之間連接稀疏。復(fù)雜網(wǎng)絡(luò)的社團(tuán)檢測(cè)算法是這幾年許多不同的科學(xué)領(lǐng)域研究的熱點(diǎn)問(wèn)題。本文從復(fù)雜網(wǎng)絡(luò)的角度對(duì)彩色圖像進(jìn)行建模，圖像中的像素點(diǎn)表示網(wǎng)絡(luò)中的節(jié)點(diǎn)，像素之間的相似性表示網(wǎng)絡(luò)之間的連接。將網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)圖表示為一個(gè)數(shù)學(xué)模型，即G=(V,E)，V表示由n個(gè)節(jié)點(diǎn)組成的點(diǎn)集，E是由m條連接邊構(gòu)成的邊集。對(duì)于一副具有R、G、B三個(gè)顏色分量的彩色圖像來(lái)說(shuō)，每個(gè)像素點(diǎn)都可以表示為RGB顏色空間中的一個(gè)節(jié)點(diǎn)xi。利用下面的公式(1)，按照從左到右，從上到下的順序計(jì)算每一個(gè)像素點(diǎn)4鄰域的相似度，首先需構(gòu)造n維零矩陣A，后需計(jì)算目標(biāo)像素點(diǎn)與其鄰域像素點(diǎn)之間的RGB歐式距離，具體公式如下：

(1)

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

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

(2)

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

2 譜聚類(lèi)社團(tuán)檢測(cè)算法

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

2.1 圖的拉普拉斯矩陣

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

(3)

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

2.2 圖劃分準(zhǔn)則

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

(4)

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

(5)

(6)

其中:Tr表示矩陣的跡。

(7)

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

2.3 k-means聚類(lèi)算法

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

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

3 本文算法模型

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

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

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

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

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

本文算法具體步驟如下：

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

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

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

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

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

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

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

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

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

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

4 結(jié)果與分析

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

4.1 不同閾值對(duì)圖像分割效果的影響

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

圖1 各閾值下的實(shí)驗(yàn)分割結(jié)果

表1 圖1中的實(shí)驗(yàn)數(shù)據(jù)

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

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

圖2 圖像分割對(duì)比實(shí)驗(yàn)

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

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

5 結(jié)語(yǔ)

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