劉賀鵬，呂建平

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710121)

?

基于形態(tài)學(xué)分水嶺的Normalized Cut圖像分割方法

劉賀鵬，呂建平

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710121)

針對(duì)傳統(tǒng)分水嶺分割后所產(chǎn)生的過分割問題，提出了一種基于形態(tài)學(xué)分水嶺算法和NormalizedCut算法相結(jié)合的圖像分割方法。在傳統(tǒng)分水嶺分割的基礎(chǔ)上，融合形態(tài)學(xué)算法進(jìn)行初步分割，并將分割后各個(gè)子區(qū)域的形心和平均灰度值作為NormalizedCut算法的輸入?yún)?shù)，完成圖像分割。結(jié)果表明，組合算法既避免了過分割現(xiàn)象，也達(dá)到了NormalizedCut算法的分割精度，是一種有效的圖像分割算法。

圖像分割；分水嶺；形態(tài)學(xué)；NormalizedCut

圖像分割是圖像處理領(lǐng)域以及計(jì)算機(jī)視覺中一個(gè)經(jīng)典問題，圖像分割的主要目的是將一幅圖像分解成互不交疊的若干灰度一致性區(qū)域，并將人們感興趣的部分凸顯出來，為后續(xù)的圖像分析、理解、目標(biāo)跟蹤、分類與識(shí)別等處理提供理論支撐。由于應(yīng)用場(chǎng)景的不同，人們所感興趣的目標(biāo)也各不相同。因此，圖像分割始終是圖像處理中的一個(gè)難點(diǎn)，如何使分割算法充分地適應(yīng)不同的場(chǎng)景且具有較快的運(yùn)算速度一直是圖像分割研究的熱點(diǎn)。

近年來，眾多成功應(yīng)用于其他領(lǐng)域的理論方法被引入到圖像分割的研究中，這使得圖像分割的研究取得了很大進(jìn)展。其中，較成功的包括分水嶺算法與種子生長結(jié)合的算法[1]、主動(dòng)輪廓模型、閾值分割方法[2]、基于圖論的方法等?；趫D論的方法是近年來國內(nèi)外學(xué)者竟相追逐的研究熱點(diǎn)。圖論中較為經(jīng)典的分割算法是Leahy 和 Wu[3]提出的最小割算法(Cut)，但該算法只考慮了兩個(gè)子圖之間的割最小，偏向于分離單個(gè)或小簇頂點(diǎn)，易劃分出極小子圖，對(duì)噪音敏感，分割效果不理想。1997年，Shi 和 Malik 在最小割的基礎(chǔ)上得到了一種更好的分割方法：歸一化圖割 (Nomalized Cut, Ncut)[4]，其同時(shí)度量了不同分割區(qū)域的差異以及同一分割區(qū)域的相似性，對(duì)圖像的全局信息進(jìn)行提取，解決了最小割準(zhǔn)則的固有缺陷。然而，Ncut算法會(huì)隨著圖中結(jié)點(diǎn)數(shù)的遞增，計(jì)算量呈幾何級(jí)數(shù)增加，導(dǎo)致在分割較大的圖像時(shí)會(huì)非常耗時(shí)。因此，如何減少Ncut方法計(jì)算量成為眾多學(xué)者關(guān)注的焦點(diǎn)。

Vincent[5]等人提出的分水嶺分割算法因具有計(jì)算量小、分割精度高的優(yōu)點(diǎn)在圖像分割領(lǐng)域引起了廣泛關(guān)注。但原始分水嶺算法更多地局限于圖像的局部信息，過度分割現(xiàn)象[6-7]嚴(yán)重，較少直接用于實(shí)際。為充分結(jié)合分水嶺和Ncut方法的優(yōu)點(diǎn)，本文采用基于數(shù)學(xué)形態(tài)學(xué)分水嶺的Ncut算法，其初步分割區(qū)域個(gè)數(shù)得到了很好的控制，有效降低了運(yùn)算量，同時(shí)組合算法也繼承了Ncut算法分割精度高、對(duì)噪聲魯棒性強(qiáng)的優(yōu)點(diǎn)。

1　形態(tài)學(xué)分水嶺算法

分水嶺算法是一種傳統(tǒng)的分割技術(shù)，該算法最初是在20世紀(jì)70年代末，由C.Digabel和H.Lantuejoul引入到二值黑白圖像的分析過程中，再經(jīng)過Beucher、Vincent等人的深入研究，建立了比較完善的分水嶺理論體系，并在20世紀(jì)80年代用于灰度圖像的分割[8]。1991年，Vincent等人又深入改進(jìn)了算法，提出了浸沒算法，大幅縮短了算法時(shí)間。

由于圖像在成像的過程中存在噪聲、光照等復(fù)雜因素的影響，組成目標(biāo)的這些極值區(qū)域、噪聲區(qū)域以及中間區(qū)域在梯度圖像中都會(huì)變成極小區(qū)域被分割出來，這是造成分水嶺算法過分割的主要原因。為了有效減少過分割現(xiàn)象，可通過對(duì)原始待分割圖像進(jìn)行平滑濾波的方式減少脊線的產(chǎn)生。然后，結(jié)合形態(tài)學(xué)開運(yùn)算和閉運(yùn)算對(duì)平滑后的邊緣圖像做進(jìn)一步的噪聲和邊緣抑制，從而獲得形態(tài)學(xué)分水嶺變換。圖1顯示了傳統(tǒng)的分水嶺變換和形態(tài)學(xué)分水嶺變換對(duì)經(jīng)典的Cameraman圖像進(jìn)行初步分割的結(jié)果。從圖像中可看出，形態(tài)學(xué)濾波變換保留了圖像中主要的邊緣細(xì)節(jié)信息，同時(shí)有效減少了脊線的產(chǎn)生。

圖1　經(jīng)典Cameraman圖像分水嶺及形態(tài)學(xué)分水嶺初分割結(jié)果

2　Normalized Cut方法

對(duì)于一個(gè)給定的帶權(quán)圖G={V,E}，其中V是結(jié)點(diǎn)的集合，E是連接結(jié)點(diǎn)的邊的集合，頂點(diǎn)之間邊的連接權(quán)值 表示兩點(diǎn)之間的相似程度，通常使用高斯核函數(shù)來計(jì)算結(jié)點(diǎn)間的權(quán)值。移去結(jié)點(diǎn)A與B之間的邊可將其拆分為兩個(gè)不相交的部分A與B，A∪B=V，A∩B=?。該圖定義一個(gè)割如式(1)[9-10]

(1)

即A與B之間所有邊的權(quán)值之和，NormalizedCut方法定義其不相似度量為

(2)

將元素向量記為y，每個(gè)分量對(duì)應(yīng)圖的一個(gè)結(jié)點(diǎn)，其值是l或-1，用于區(qū)分圖的不同部分。將相似性矩陣記為W，W為對(duì)稱陣，第i行第j列元素為w(i,j)。次數(shù)矩陣記為D，D為對(duì)角矩陣，其對(duì)角線上的元素記為d(i),等于相應(yīng)結(jié)點(diǎn)的權(quán)值之和，即

(3)

該標(biāo)記下準(zhǔn)則為

(4)

為找出最小的Ncut值對(duì)應(yīng)的y，可轉(zhuǎn)換成如式(5)的特征向量求解問題

(D-W)y=λDy

(5)

在問題求解上用y作為指示向量，NormalizedCut方法使用的是特征方程的第二個(gè)最小特征值所對(duì)應(yīng)的特征向量作為該問題的解。在向量y中選擇一個(gè)分割數(shù)值，使y中大于該數(shù)的部分所對(duì)應(yīng)的結(jié)點(diǎn)在A中，其余的在B中，這樣就將圖G中的結(jié)點(diǎn)分成兩個(gè)部分。若所分割的部分需要再細(xì)分，可遞歸地調(diào)用該算法。

3　Normalized Cut方法

由于分水嶺算法對(duì)噪聲敏感，易造成過分割的問題，并不能將圖像中有意義的區(qū)域表示出來，所以必須對(duì)分割結(jié)果進(jìn)行2次合并。同時(shí)，分水嶺脊線用于區(qū)分不同子區(qū)域的邊界，并不屬于任何子類。因此，文中采用局部最近鄰規(guī)則，首先將分水嶺脊線上的像素點(diǎn)劃分為局部子區(qū)域內(nèi)包含某一個(gè)子區(qū)域最多像素點(diǎn)所在區(qū)域。然后再計(jì)算各子區(qū)域形心和灰度均值。將形心當(dāng)作圖的各個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)與其他結(jié)點(diǎn)連接建立一個(gè)濃縮的帶權(quán)圖G={V,E}，權(quán)值的計(jì)算融合了結(jié)點(diǎn)之間的距離和各子區(qū)域灰度均值信息。由于結(jié)點(diǎn)的個(gè)數(shù)遠(yuǎn)小于圖像像素點(diǎn)的個(gè)數(shù)，因此基于形態(tài)學(xué)分水嶺NormalizedCut方法所產(chǎn)生的權(quán)值矩陣較小，有利于數(shù)值求解。

基于形態(tài)學(xué)分水嶺的NormalizedCut方法主要流程：(1)使用形態(tài)學(xué)分水嶺算法對(duì)輸入圖像做初步分割；(2)提取分水嶺分割圖像各子區(qū)域的形心與區(qū)域灰度均值；(3)使用如下方式構(gòu)造相似性矩陣即權(quán)值矩陣w。

(6)

式(6)中，G(i)、G(j)分別為結(jié)點(diǎn)i、j所在區(qū)域的灰度均值；σs表示結(jié)點(diǎn)i、j像素值標(biāo)準(zhǔn)差；P(i)、P(j)分別為結(jié)點(diǎn)i、j空間位置坐標(biāo)；σt表示結(jié)點(diǎn)i、j空間位置標(biāo)準(zhǔn)差。顯然，結(jié)點(diǎn)之間的距離越小、灰度差異越小，其之間的連接權(quán)值就越大；(4)求解特征方程(D,W)y=λDy，利用與第2個(gè)最小特征值相應(yīng)的特征向量,對(duì)圖中的結(jié)點(diǎn)進(jìn)行劃分,進(jìn)而完成對(duì)圖像的分割。

4　實(shí)驗(yàn)結(jié)果

為驗(yàn)證所提出的組合算法的有效性，本文比較了傳統(tǒng)的分水嶺算法、Normalized Cut方法以及形態(tài)學(xué)分水嶺-Normalized Cut組合方法在分割精度、運(yùn)行時(shí)間上的差異。

圖2和圖3為分別使用傳統(tǒng)的分水嶺方法、Normalized Cut方法以及基于形態(tài)學(xué)分水嶺的Normalized Cut方法對(duì)不同的兩組圖像進(jìn)行分割的結(jié)果。3種算法對(duì)應(yīng)的時(shí)間如表1所示。使用傳統(tǒng)的Normalized Cut方法和形態(tài)學(xué)分水嶺-Normalized Cut方法分別將圖2分割成5類、圖3分割成9類。如圖2(b)和圖3(b)所示，傳統(tǒng)的分水嶺方法出現(xiàn)了嚴(yán)重的過分割現(xiàn)象。

對(duì)比圖2(c)～圖2(d)及圖3(c)～圖3(d)可發(fā)現(xiàn)，Normalized Cut方法和形態(tài)學(xué)分水嶺-Normalized Cut方法分割結(jié)果視覺效果上總體趨于一致，但Normalized Cut方法在圖像的邊緣區(qū)域過渡更為平滑，具有更好的分割精度。從表1可看出，3種分割方法中，分水嶺方法占用的時(shí)間最少，但分割效果最差；形態(tài)學(xué)分水嶺-Normalized Cut方法本質(zhì)上等同于Normalized Cut方法，但其運(yùn)行速度較Normalized Cut方法具有較大的優(yōu)勢(shì)，更適用于對(duì)算法時(shí)間要求嚴(yán)格的場(chǎng)景。

表1　3種分割算法運(yùn)行時(shí)間表　/s

圖2　3種不同的方法Cameraman分割結(jié)果

圖3　3種不同的方法Car分割結(jié)果

5　結(jié)束語

提出了一種形態(tài)學(xué)分水嶺算法與Normalized Cut算法相結(jié)合的組合分割方法，該方法能以接近5～10倍的運(yùn)行效率獲得近似Normalized Cut方法的分割精度，有效消除了傳統(tǒng)分水嶺方法中的過分割問題，并具有較好的實(shí)用性。

[1]呂建平,司維.基于分水嶺和種子生長的彩色圖像分割[J].西安郵電大學(xué)學(xué)報(bào),2014,19(2):52-55.

[2]謝勰,王輝,張雪鋒.圖像閾值分割技術(shù)中的部分和算法綜述[J].西安郵電大學(xué)學(xué)報(bào),2011,16(3):1-5.

[3]Wu Z,Leahy R.Anoptimal graph theoretic approach to data clustering:theory and its applicationto image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1993,15(11):1101-1113.

[4]Shi J,Malik J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905.

[5]Vincent L,Soille P.Watershed in digitalspaces:anefficientalgorithmbased on immersion simulation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1991,13(6):583-598.

[6]Gonzalez R C,Woods R E.Digitalimage processing[M].阮秋琦,阮宇智,譯.北京:電子工業(yè)出社,2004.

[7]姚敏.數(shù)字圖像處理[M].北京:機(jī)械工業(yè)出版社,2006.

[8]Rafael C Gonzalez,Richard E Woods.數(shù)字圖像處理[M].阮秋琦,阮宇智,譯.2版.北京:電子工業(yè)出版社,2003.

[9]黃一岑,沈一帆.基于Normalized Cut 的圖像分割改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(34):179-181.

[10]任愛紅,白婷婷.結(jié)合圖論Normalized Cut方法的彩色圖像分割研究[J].甘肅科學(xué)學(xué)報(bào),2012,24(3):147-150.

A Normalized Cut Image Segmentation Method Based on Morphological Watersheds

LIU Hepeng, Lü Jianping

(School of Computer Science and Technology, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

In view of the over-segmentation caused by traditional watershed segmentation, a normalized cut image segmentation method combined on morphological watershed transformation is proposed in this paper. On the basis of traditional watershed segmentation, the morphology algorithm is adopted for initial segmentation, and the average grey value of each segmented area is used as input parameters for the normalized cut algorithm to complete the image segmentation. The results show that combined algorithm not only avoids over-segmentation, but also achieves as good accuracy as the normalized cut algorithm segmentation.

simage segmentation; watershed segmentation; morphology; Normalized Cut

2015- 12- 18

劉賀鵬(1988-)，男，碩士研究生。研究方向：數(shù)字圖像處理。呂建平(1957-)，男，教授。研究方向：數(shù)字圖像處理。

10.16180/j.cnki.issn1007-7820.2016.09.004

TP391.41

A

1007-7820(2016)09-012-03