復(fù)雜網(wǎng)絡(luò)理論在彩色圖像分割中的應(yīng)用研究

，，，

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

0 引言

圖像分割是一種根據(jù)紋理，顏色，灰度等視覺特征將圖像劃分成具有獨特性質(zhì)的目標區(qū)域的技術(shù)和過程[1]，在計算機視覺領(lǐng)域中一直發(fā)揮著非常重要的作用。近年來，基于圖論的圖像分割方法已成為國內(nèi)外的一個研究熱點?，F(xiàn)有的基于圖論的方法[2-3]很多，其中基于圖論的最小生成樹算法因其簡單，高效且能獲取全局信息，在圖像分割中得到了廣泛應(yīng)用，但其使用自適應(yīng)的全局閾值進行圖像分割，分割效果并不理想尤其在圖像細節(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)造社團網(wǎng)絡(luò)結(jié)構(gòu)圖，然后用社團檢測算法進行社團劃分，對圖像相似像素聚類，進而實現(xiàn)彩色圖像分割。社團檢測一直是復(fù)雜網(wǎng)絡(luò)學(xué)科中研究的熱點，到目前為止，比較常用的算法有GN 算法[7]、Newman 快速算法[8]等。GN 算法是由Girvan 和 Newman 在2001年提出，該算法思想基礎(chǔ)為分裂法，依次刪除網(wǎng)絡(luò)中邊介數(shù)值最高的邊，當算法結(jié)束時整個網(wǎng)絡(luò)將被劃分成不同的社團。但是GN算法有兩個缺點：其中一個為該方法和其他傳統(tǒng)方法一樣都無法判斷一個網(wǎng)絡(luò)最終可以被劃分成社團的個數(shù)。另外一個缺點就是速度較慢。Newman 快速算法以貪心算法思想為基礎(chǔ)的凝聚算法。該算法可用于大型復(fù)雜網(wǎng)絡(luò)，在社區(qū)劃分過程中，經(jīng)過計算比較得到最大的模塊度值Q，所對應(yīng)的社區(qū)結(jié)構(gòu)就是該網(wǎng)絡(luò)最好的社區(qū)結(jié)構(gòu)組成，但是該算法準確度沒有GN算法高。本文采用的是目前比較流行的社團檢測算法即譜聚類算法，譜聚類算法能夠廣泛的應(yīng)用于任意的數(shù)據(jù)空間上，尤其在運行高維數(shù)據(jù)如圖像數(shù)據(jù)時，相比于傳統(tǒng)的聚類算法，該算法更加完整、更加全面，且在得到社團劃分結(jié)果的質(zhì)量方面比其他算法要好。

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

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

Girvan和Newman在2002年最先提出網(wǎng)絡(luò)社團結(jié)構(gòu)的概念[11]，即網(wǎng)絡(luò)中存在內(nèi)部連接緊密的節(jié)點群而節(jié)點群之間連接稀疏。復(fù)雜網(wǎng)絡(luò)的社團檢測算法是這幾年許多不同的科學(xué)領(lǐng)域研究的熱點問題。本文從復(fù)雜網(wǎng)絡(luò)的角度對彩色圖像進行建模，圖像中的像素點表示網(wǎng)絡(luò)中的節(jié)點，像素之間的相似性表示網(wǎng)絡(luò)之間的連接。將網(wǎng)絡(luò)社團結(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，后需計算目標像素點與其鄰域像素點之間的RGB歐式距離，具體公式如下：

(1)

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

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

(2)

從上式中顯然可以看出，閾值T對網(wǎng)絡(luò)拓撲結(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ò)社團結(jié)構(gòu)圖，之后選取結(jié)構(gòu)較好的網(wǎng)絡(luò)圖進行社團檢測。

2 譜聚類社團檢測算法

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

2.1 圖的拉普拉斯矩陣

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

(3)

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

2.2 圖劃分準則

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

(4)

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

(5)

(6)

其中:Tr表示矩陣的跡。

(7)

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

2.3 k-means聚類算法

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

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

3 本文算法模型

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

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

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

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

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

本文算法具體步驟如下：

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

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

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

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

4)計算k個特征值，并對它們進行排序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進行聚類，并將相應(yīng)像素點歸屬為C1,...Ck。聚類結(jié)果為網(wǎng)絡(luò)社團結(jié)構(gòu)圖的劃分結(jié)果，也是原圖像中對應(yīng)像素點所屬的類別。

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

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

4 結(jié)果與分析

為了檢驗本文算法的性能，對本文算法進行實驗分析。算法實驗環(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é)果，閾值較小時，分割比較精細，能夠得到完整的邊緣信息，圖像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)的強度越強，則劃分質(zhì)量越好。從表1中可以看出，在一定范圍內(nèi)，隨著分割結(jié)果越細膩，模塊度越高，說明網(wǎng)絡(luò)社區(qū)劃分質(zhì)量也就越好，結(jié)構(gòu)越強。

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

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

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

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

圖2 圖像分割對比實驗

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

本文采用precision-recall標準對圖2中的分割結(jié)果進行定量評價，precision-recall廣泛用于信息檢索和統(tǒng)計學(xué)分類領(lǐng)域的兩個度量值。兩個參數(shù)取值在0和1之間，數(shù)值越接近1，查全率或查準率就越高，圖像分割精度越高，F(xiàn)-Measure是Precision和Recall加權(quán)調(diào)和平均，當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ù)進行建模，并使用譜聚類算法劃分網(wǎng)絡(luò)社團結(jié)構(gòu)圖，進而得到圖像的聚類結(jié)果，取得了較好的圖像分割效果。實驗表明利用網(wǎng)絡(luò)社團結(jié)構(gòu)圖對圖像數(shù)據(jù)中的復(fù)雜非線性結(jié)構(gòu)進行建模是有效的，這為社團檢測算法在圖像處理方面開拓了一個有價值的研究領(lǐng)域。未來工作準備改進本文算法，提高算法運行效率，也嘗試利用圖像其它特征如紋理特征或者其它圖像相似性檢測方法對圖像進行網(wǎng)絡(luò)社團結(jié)構(gòu)圖建模，將其更好地應(yīng)用在圖像分割領(lǐng)域當中。