摘 要：針對(duì)圖像分割是典型的結(jié)構(gòu)不良問(wèn)題，將圖譜劃分理論作為一種新型的模式分析工具應(yīng)用到圖像分割并引起廣大學(xué)者關(guān)注。考慮到現(xiàn)有的圖譜閾值法中圖權(quán)計(jì)算方法采用基于歐氏距離的冪指數(shù)函數(shù)導(dǎo)致其計(jì)算量過(guò)大的不足，首先采用基于歐氏距離的分式型柯西函數(shù)代替基于歐氏距離的冪指數(shù)函數(shù)提出圖權(quán)計(jì)算的新方法，其次將其應(yīng)用基于圖譜劃分測(cè)度的圖像閾值分割算法中并得到一種改進(jìn)的圖譜閾值分割方法。實(shí)驗(yàn)結(jié)果表明，該方法的計(jì)算量小且對(duì)目標(biāo)和背景相差比例較大的圖像能獲得滿意的結(jié)果。

關(guān)鍵詞：圖像分割；閾值法；圖譜測(cè)度；圖權(quán)

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：1004373X(2008)1612505

Improved Segmentation Algorithm Based on Graph Spectral Threshold

TIAN Xiaoping，WU Chengmao

(Xi′an Institute of Posts and Telecommunications，Xi′an，710121，China)

Abstract：Aiming at the problem of image segmentation with badness structure，the graph cut measure theory is a kind of new type tool of pattern analysis，and it has been applied in the image segmentation field and brings the attention of a lot of scholars.Considering the shortage of graph spectral thresholding method with a great deal of computation because of graph weight computation method adopting power exponential function based on Euclidean distance，the new computation method of graph weights are proposed by mean of replacing power exponential function with fractional Cauchy function based on Euclidean distance，and there are applied in the image thresholding segmentation algorithm based on the measure of graph spectral.The experimental results show that the new method has a small deal of computation and is more suitable to segment the image with the bigger proportition between goal and background.

Keywords：image segmentation;thresholding method;measure of graph spectral;graph weight

1 引 言

圖像分割是圖像處理和前期視覺(jué)中的基本技術(shù)，是大多數(shù)圖像分析及視覺(jué)系統(tǒng)的重要組成部分，也是成功進(jìn)行圖像分析、理解與描述的關(guān)鍵步驟，歷來(lái)受到國(guó)內(nèi)外有關(guān)學(xué)者的高度重視。

在很多圖像處理應(yīng)用中，圖像中目標(biāo)和背景灰度值的差異使得采用某一合理的門限值可有效地將目標(biāo)和背景區(qū)分開(kāi)。事實(shí)上，由于閾值分割方法實(shí)現(xiàn)簡(jiǎn)單、實(shí)時(shí)性好，在許多圖像處理問(wèn)題中均得到廣泛應(yīng)用，如文檔處理、細(xì)胞運(yùn)動(dòng)估計(jì)以及自動(dòng)目標(biāo)識(shí)別等，閾值分割的基本原理是通過(guò)將圖像中的每個(gè)像素與某一門限值進(jìn)行比較從而將圖像區(qū)分為背景和目標(biāo)，其關(guān)鍵問(wèn)題在于尋找一個(gè)合適的門限值來(lái)區(qū)分目標(biāo)和背景而且不損害目標(biāo)的完整性，但是自動(dòng)選擇最佳閾值一直都是圖像處理中的一個(gè)懸而未解的問(wèn)題，雖然近幾十年來(lái)各種方法不斷出現(xiàn)^［15］，但根本問(wèn)題仍未解決，應(yīng)用各種新的思想和理論來(lái)解決這一難題仍然是一個(gè)具有挑戰(zhàn)性的研究領(lǐng)域。

近年來(lái)，圖譜劃分理論作為一種新型的工具被應(yīng)用到圖像分割^［69］，但這種圖像分割方法通常具有較高的復(fù)雜性，實(shí)時(shí)性較差，因而在很多實(shí)時(shí)視覺(jué)處理場(chǎng)合無(wú)法采用。針對(duì)圖像劃分的圖像分割方法存在的不足，文獻(xiàn)［10］提出一種基于圖譜劃分的閾值分割方法，采用圖譜劃分測(cè)度作為閾值分割的準(zhǔn)則來(lái)區(qū)分目標(biāo)和背景。該方法的最大優(yōu)點(diǎn)是避免了復(fù)雜的特征系統(tǒng)求解問(wèn)題，因而極大減少了算法所需的存儲(chǔ)空間以及計(jì)算的復(fù)雜度，大大提高了算法的實(shí)時(shí)性；同時(shí)，該方法的性能優(yōu)于其他類型的閾值分割方法，特別是針對(duì)具有明顯目標(biāo)和背景的實(shí)際圖像，文獻(xiàn)［10］中的方法相對(duì)文獻(xiàn)［8］中的方法更為有效。本文針對(duì)文獻(xiàn)［10］提出的圖譜閾值法在計(jì)算圖頂點(diǎn)之間的邊權(quán)值采用指數(shù)函數(shù)導(dǎo)致其計(jì)算量很大且對(duì)有些圖像無(wú)法獲得滿意分割效果的不足，提出了采用距離倒數(shù)的計(jì)算方式能降低其計(jì)算復(fù)雜性，以及對(duì)目標(biāo)和背景比例相差很大的圖像獲得更加滿意的分割效果。

2 基于圖譜理論的圖像分割方法

任意特征空間的點(diǎn)集都可以采用一個(gè)無(wú)向圖G=(V，E)來(lái)表示，其中V是節(jié)點(diǎn)的集合；E是連接節(jié)點(diǎn)的邊的集合。V的基為N=|V|，連接每2個(gè)節(jié)點(diǎn)的邊均賦予權(quán)值w(u，v)，該權(quán)值衡量節(jié)點(diǎn)u和v的相似程度。如果將節(jié)點(diǎn)集V分成兩個(gè)獨(dú)立的子集A和B，其中B=V-A，那么通過(guò)移去連接A和B中所有節(jié)點(diǎn)的邊就可以得到點(diǎn)集A和B之間的分離度，稱為劃分(cut)^［6］:cut(A，B)=∑u∈A∑v∈Bw(u，v)(1) Wu和Leahy^［6］基于最小劃分準(zhǔn)則提出一種聚類方法，但是該方法容易劃分出圖中孤立點(diǎn)。為了克服這種現(xiàn)象，Shi和Malik^［8］提出采用歸一化的劃分準(zhǔn)則來(lái)描述兩類間的分離度，定義如下:Ncut(A，B)=cut(A，B)asso(A，V)+cut(A，B)assov(B，V)(2)其中，asso(A，V)=∑u∈A∑v∈Vw(u，v)為A中的節(jié)點(diǎn)與圖中所有節(jié)點(diǎn)總的連接權(quán)值之和。采用Ncut準(zhǔn)則就可以克服劃分孤立點(diǎn)的問(wèn)題，最小的Ncut值對(duì)應(yīng)的劃分即為圖G的最優(yōu)劃分。在這種情況下，最小化Ncut可以轉(zhuǎn)化為如下的標(biāo)準(zhǔn)特征系統(tǒng)^［8］：D.-12(D-W)D.-12z=λz(3)其中，D是N×N的對(duì)角矩陣，其對(duì)角線上的元素為di=∑jw(i，j)，W是對(duì)稱矩陣，其元素為w(i，j)，λ和z分別為相應(yīng)的特征值和特征矢量。

特征系統(tǒng)(3)的第二個(gè)最小的特征值對(duì)應(yīng)的特征矢量可以用來(lái)完成全圖的最優(yōu)劃分^［8］，從而得到對(duì)應(yīng)圖像的一個(gè)分割結(jié)果。可以采用遞歸算法以相同的方式進(jìn)一步對(duì)分割得到的子圖進(jìn)行劃分，直至滿足終止條件為止。由于計(jì)算特征值和特征矢量十分耗時(shí)，一般采用近似的Lanczos方法來(lái)求解。

當(dāng)圖像的尺度較大時(shí)，采用Ncut方法其對(duì)應(yīng)的鄰接權(quán)值矩陣W的維數(shù)也相應(yīng)較大。如果采用基于像素的鄰接權(quán)值矩陣，則必須求解一個(gè)如式(3)的N×N維的特征系統(tǒng)，即使采用近似算法來(lái)優(yōu)化實(shí)現(xiàn)，對(duì)于大尺度的圖像而言其計(jì)算復(fù)雜性仍然非常高。而且劃分的穩(wěn)定性極大地依賴于參數(shù)的選擇。另外，特征系統(tǒng)的次小特征值一般非常小，所以特征值計(jì)算的微小誤差也會(huì)對(duì)相應(yīng)特征矢量劃分點(diǎn)的選擇造成影響，從而影響分割的結(jié)果。所有的這些因素都限制了Ncut方法的應(yīng)用。

3 基于圖譜測(cè)度的閾值法

設(shè)P=\\M×N表示大小為M×N的數(shù)字圖像，其灰度級(jí)為L(zhǎng)，K={0，1，…，L-1}表示所有灰度的集合，f(x，y)∈K是圖像任意位置(x，y)處的像素。將圖像P中的每個(gè)位置(x，y)(i=1，2，…，M;j=1，2，…，N)看成無(wú)向圖G的節(jié)點(diǎn)，則V和(x，y)滿足如下條件：

f(x，y)∈K，(x，y)∈V={(i，j)|i=1，2，…，M;

j=1，2，…，N}

Vi={(x，y)|f(x，y)=i，(x，y)∈V}

i=0，1，…，L-1

∪L-1i=0Vi=V，Vj∩Vk=Φ， j，k∈K

將圖像P中的每個(gè)位置看作無(wú)向圖的一個(gè)節(jié)點(diǎn)，每對(duì)節(jié)點(diǎn)均用一條邊連接起來(lái)，邊的權(quán)值反映這兩個(gè)位置所對(duì)應(yīng)的像素屬于相同目標(biāo)的可能性，那么就可以構(gòu)建一個(gè)帶權(quán)的無(wú)向圖G=(V，E)，可以定義圖G中連接2個(gè)節(jié)點(diǎn)u=(x1，y1)和v=(x2，y2)的邊的權(quán)值如下： w(u，v)=e.-‖X(u)-X(v)‖.22dX+‖F(xiàn)(u)-F(v)‖.22dL〗， ‖X(u)-X(v)‖2

0，其他(4) 其中，X(u)為節(jié)點(diǎn)u在圖像P中的位置坐標(biāo)(x1，y1)；F(u)為節(jié)點(diǎn)u在圖像P中位置坐標(biāo)(x1，y1)的灰度值f(x1，y1)；‖·‖2表示一個(gè)矢量的二范數(shù)。

另外，dL和dX分別是正的尺度因子，分別控制權(quán)值w(u，v)對(duì)2個(gè)節(jié)點(diǎn)u和v的灰度差異及空間位置差異的敏感程度。

r是一個(gè)正數(shù)，決定參與計(jì)算權(quán)值的鄰域節(jié)點(diǎn)的個(gè)數(shù)，隨著r的增加，參與計(jì)算權(quán)值的節(jié)點(diǎn)個(gè)數(shù)也增加，同時(shí)計(jì)算量也相應(yīng)地增大。因此，可將w(u，v)具體展開(kāi)寫成如下形式： w(u，v)=e.-(x1-x2).2+(y1-y2).2dX+(f(x1，y1)-f(x2，y2)).2dL〗， (x1-x2).2+(y1-y2).2

0，其他(5) 假設(shè)圖像中只有一個(gè)目標(biāo)和背景，閾值化圖像分割只需要選取一個(gè)閾值，對(duì)圖像選取某一給定閾值t(0

=∑ti=0 ∑L-1j=t+1 ∑u∈Vi ∑v∈Vjw(u，v) 同樣可得:asso(A，V)=∑ti=0∑L-1j=0∑u∈Vi ∑v∈Vjw(u，v)

asso(B，V)=∑L-1i=t+1∑L-1j=0∑u∈Vi∑v∈Vjw(u，v) 因此，基于歸一化的圖譜劃分測(cè)度的圖像閾值化分割準(zhǔn)則可表示為:t.*1(dX，dL，r)=argmin0

4 改進(jìn)圖譜邊權(quán)的閾值法

針對(duì)圖譜閾值法中圖頂點(diǎn)之間的邊權(quán)計(jì)算公式(4)或(5)因采用冪指數(shù)運(yùn)算，導(dǎo)致給定圖像構(gòu)造其圖頂點(diǎn)之間邊權(quán)的計(jì)算量很大，其原因在于計(jì)算e.-x是采用下列近似公式:e.-x1-x+x.22!-x.33!+…+(-x).nn!這就導(dǎo)致直接利用指數(shù)函數(shù)其計(jì)算量。因此，本文采用如下的計(jì)算辦法來(lái)降低其計(jì)算量：

給定大小為M×N的灰度圖像P，構(gòu)建一個(gè)帶權(quán)的無(wú)向圖G.*=(V.*，E.*)，可以定義圖G.*中連接兩個(gè)節(jié)點(diǎn)u=(x1，y1)和v=(x2，y2)的邊的權(quán)值如下：

w.*(u，v)=1/1+α.*‖X(u)-X(v)‖.22d.*X+‖F(xiàn)(u)-F(v)‖.22d.*L〗， ‖X(u)-X(v)‖2

0，其他(7)

其中，α.*>0，X(u)為節(jié)點(diǎn)u在圖像P中的位置坐標(biāo)(x1，y1)；F(u)為節(jié)點(diǎn)u在圖像P中位置坐標(biāo)(x1，y1)的灰度值f(x1，y1)；‖·‖2表示一個(gè)矢量的二范數(shù)。另外，d.*L和d.*X分別是正的尺度因子，分別控制權(quán)值w.*(u，v)對(duì)2個(gè)節(jié)點(diǎn)u和v的灰度差異及空間位置差異的敏感程度。

r.*是一個(gè)正數(shù)，決定參與計(jì)算權(quán)值的鄰域節(jié)點(diǎn)的個(gè)數(shù)，隨著r.*的增加，參與計(jì)算權(quán)值的節(jié)點(diǎn)個(gè)數(shù)也增加，同時(shí)計(jì)算量也相應(yīng)地增大。因此，可將w.*(u，v)具體展開(kāi)寫成如下形式：

w.*(u，v)=11+α.*(x1-x2).2+(y1-y2).2d.*X+(f(x1，y1)-f(x2，y2)).2d.*L〗，(x1-x2).2+(y1-y2).2

0，其他(8) 因此，基于圖頂點(diǎn)邊權(quán)計(jì)算的新公式來(lái)構(gòu)造圖譜分割新方法為:t.*2(α，d.*X，d.*L，r.*)=argmin0

為了驗(yàn)證本文方法的有效性，采用本文方法對(duì)3幅圖片進(jìn)行分割實(shí)驗(yàn)，算法采用Matlab語(yǔ)言實(shí)現(xiàn)。在實(shí)驗(yàn)過(guò)程中，為了客觀地比較算法的性能，在文獻(xiàn)［8］方法和本文方法涉及到構(gòu)造圖節(jié)點(diǎn)的邊權(quán)值表達(dá)式中的參數(shù)均采用文獻(xiàn)［10］中的設(shè)置為dX=d.*X=4，dL=d.*L=625以及r=r.*=2，以及參數(shù)α.*針對(duì)不同圖片選取大于零的值。本文方法與文獻(xiàn)［8］方法所需時(shí)間差異僅在于計(jì)算圖譜權(quán)值所利用函數(shù)不同導(dǎo)致的，其具體差異值大小也與圖像的大小有緊密關(guān)系。

圖1 辣椒圖片及兩種權(quán)方法的分割結(jié)果本文方法比文獻(xiàn)［10］方法要少，CPU時(shí)間

0.250 0 s。

圖2 攝影師圖片及兩種權(quán)方法的分割結(jié)果本文方法比文獻(xiàn)［10］方法要少，CPU時(shí)間

0.078 1 s。

圖3 Lena圖片及兩種權(quán)方法的分割結(jié)果本文方法比文獻(xiàn)［10］方法，要少CPU時(shí)間

0.078 1 s。

從圖1~圖3的典型標(biāo)準(zhǔn)圖片的實(shí)驗(yàn)結(jié)果來(lái)看，本文方法和文獻(xiàn)［10］方法的分割效果基本一致，說(shuō)明本文方法是可行的；但是，從圖4~圖7的小目標(biāo)圖片的分割結(jié)果來(lái)看，當(dāng)圖像中的目標(biāo)和背景比例相差比較懸殊時(shí)，本文所建議的圖權(quán)計(jì)算方法就顯得更有效。

圖4 坦克圖片及兩種權(quán)方法的分割結(jié)果本文方法比文獻(xiàn)［10］方法要少，CPU時(shí)間

0.312 5 s。

圖5 沙漠圖片及兩種權(quán)方法的分割結(jié)果本文方法比文獻(xiàn)［10］方法要少，CPU時(shí)間

0.328 1 s。

圖6 沙漠圖片及兩種權(quán)方法的分割結(jié)果本文方法比文獻(xiàn)［10］方法少，CPU時(shí)間0.328 1 s。

圖7 細(xì)菌圖片及兩種權(quán)方法的分割結(jié)果本文方法比文獻(xiàn)［10］方法少，CPU時(shí)間0.031 3 s。

6 結(jié) 語(yǔ)

面對(duì)圖像來(lái)源千差萬(wàn)別，其直方圖分布具有多樣性。本文對(duì)嶄新的圖譜分割方法中的圖權(quán)計(jì)算函數(shù)進(jìn)行改進(jìn)，使其圖譜分割方法的時(shí)間消耗降低，同時(shí)其分割性能有所改善，特別是對(duì)圖像中目標(biāo)和背景比例相差比較懸殊的圖像，本文方法表現(xiàn)出更好的性能。本文不足之處在于圖權(quán)計(jì)算函數(shù)參數(shù)選擇還不能自動(dòng)選取，這是更進(jìn)一步要探討的重要問(wèn)題。

參 考 文 獻(xiàn)

［1］Sahoo P K.A Survey of Thresholding Techniques Computer Vision\\.Graphics and Image Processing，1988，41:233260.

［2］Pal N R，Pal S K.A Review on Image Segmentation Techniques\\.Pattern Recognition Letters，1993，26(9):1 2771 294.

［3］Glasbey C A.An Analysis of Histogrambased Thresholding Algorithm\\.Graphical Models and Image Processing，1993，55:532537.

［4］Sezgin M，Sankur B.Survey over Image Thresholding Techniques and Quantitative Performance Evaluation\\.Journal of Electronic Image，2004，13(1):145165.

［5］Saha P K，Udupa J.Optimum Image Thresholding via Class Uncertainty and Region Homogeneity\\.IEEE Transactions on Pattern Analysis Machine Intelligence，2001，23(7):689706.

［6］Wu Z Y，Leahy R.An Optimal Graph Theories Approach to Data Clustering:Theory and Its Application to Image Segmentation\\.IEEE Transations on Pattern Analysis and Machine Intelligence，1993，15(11):1 1011 113.

［7］Sarkar S，Soundararajan P.Supervised Learning of Large Percetual Organization: Graph Spectral Partitioning and Learning Automata\\.IEEE Transations on Pattern Analysis and Machine Intelligence，2000，22(5):504525.

［8］Shi J，Malik J.Normalized Cuts and Image Segmentation\\.IEEE Transations on Pattern Analysis and Machine Intelligence，2000，22(8):888905.

［9］Wang S，Siskind J M.Image Segmentation with Ratio Cut\\.IEEE Transations on Pattern Recognition and Machine Intelligence，2003，25(6):675690.

［10］陶文兵，金海.一種新的基于圖譜理論的圖像閾值分割方法\\.計(jì)算機(jī)學(xué)報(bào)，2007，30(1):110119.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文