一種改進(jìn)的Snake模型圖像分割算法

1、圖像分割是圖像處理領(lǐng)域的一個(gè)基本問(wèn)題,一直是圖像處理中的難點(diǎn)之一,也是從處理到分析的關(guān)鍵。常用的分割算法大多出現(xiàn)邊界不光滑、不連續(xù)以及與背景連成一片等問(wèn)題。而Snake模型能夠利用圖像局部與整體信息,實(shí)現(xiàn)邊界的準(zhǔn)確定位,并能得到封閉的輪廓。自1987年Kass等人提出Snake模型后1,Snake模型成為近些年專用于目標(biāo)輪廓提取的一種主流模型2。傳統(tǒng)的Snake模型也存在著不少缺點(diǎn),如結(jié)果對(duì)初值的依賴性強(qiáng)、容易收斂到噪聲點(diǎn)、對(duì)復(fù)雜區(qū)域不能收斂到邊緣且計(jì)算速度慢等。針對(duì)這些缺點(diǎn),很多研究者做了有益的修正和改進(jìn)。其中,EVIATAR H等3人提出的簡(jiǎn)化Snake模型使收斂范圍有一定擴(kuò)大,但計(jì)算面積

2、能量要對(duì)頂點(diǎn)連線作出是否交叉的判斷。王元全等4人提出的構(gòu)造曲率力思想使得輪廓點(diǎn)收斂到深凹陷區(qū)域,但該力的引入需要對(duì)輪廓點(diǎn)進(jìn)行凹凸性判斷,而輪廓點(diǎn)的凹凸性往往很難做到有效判斷。本文將傳統(tǒng)Snake模型不能收斂凹陷區(qū)域歸結(jié)為在內(nèi)部能量中。內(nèi)部力的不足,在參數(shù)個(gè)數(shù)不增加的前提下對(duì)內(nèi)部能量增加內(nèi)部力,并對(duì)改進(jìn)后的Snake模型采用分段計(jì)算的Greey算法。使改進(jìn)后的Snake模型較好地收斂到凹陷區(qū)域且抗噪性有所提高、結(jié)果對(duì)初值的依賴性減弱,適合復(fù)雜區(qū)域的圖像分割,而參數(shù)個(gè)數(shù)未增加且易調(diào)整,同時(shí)算法的實(shí)現(xiàn)無(wú)需對(duì)輪廓點(diǎn)的性質(zhì)進(jìn)行判斷,實(shí)現(xiàn)簡(jiǎn)單。1傳統(tǒng)Snake模型Snake模型是一種可形變模型(彈性模型,

3、原始的Snake是由一組輪廓點(diǎn)v(s=vx(s,y(s,s(0,1組成的輪廓參數(shù)曲線。通過(guò)構(gòu)造能量函數(shù):E snake=E internal+E external+E constraint使得總能量達(dá)到最小,從而得到一個(gè)好的輪廓。一種改進(jìn)的Snake模型圖像分割算法張輝1,吳月寧2(1.咸陽(yáng)師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院,陜西咸陽(yáng)712000;2.西北農(nóng)林科技大學(xué)理學(xué)院,陜西楊凌712000摘要:針對(duì)Snake模型不能收斂到深凹陷區(qū)域的缺點(diǎn),提出一種Snake模型的改進(jìn)算法。首先把模型不能收斂到深凹陷區(qū)域歸結(jié)為內(nèi)部能量產(chǎn)生的收縮不足,在此基礎(chǔ)上改變新的力,以調(diào)整內(nèi)部能量;然后在不增加參數(shù)個(gè)數(shù)的前提

4、下給出新的能量表達(dá)式。算法的實(shí)現(xiàn)采用貪婪算法。結(jié)果表明,改進(jìn)的Snake模型能迅速地收斂到凹陷區(qū)域,并減少了結(jié)果對(duì)初值的依賴,明顯優(yōu)于傳統(tǒng)Snake模型。關(guān)鍵詞:Snake模型;圖像分割;內(nèi)部能量;深凹陷區(qū)域中圖分類號(hào):TP751文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1674-7720(201011-0036-02The image segmentation of the complex region based on snake modelZHANG Hui1,WU Yue Ning2(1.College of Mathematics and Information Sciences,Xianyang N

5、ormal University,Xianyang712000,China;2.College of Sciences,Northwest A&F University,Yangling712100,ChinaAbstract:To resolve the problems that the traditional snake model can not converge the concavity district well in the segmentation of complex region,the paper makes improvement for the tradit

6、ional snake model in two aspects.On one hand, increasing one energy item created by doing work,on another hand,adopting greey algorithm in two stages.The result shows that the improved snake model can quickly converge the concavity region and the more complex region,and has decreased the dependence

7、of the result of segmentation to the initial value and the influence of noise point to the boundary.Key words:snake model;image segmentation;internal energy;concavity region(下轉(zhuǎn)第41頁(yè)v i -1v io 圖1銳角三角形示意圖式中,E snake 為總能量;E internal 為內(nèi)部能量,通常由曲線內(nèi)部性質(zhì)決定,要求曲線光滑、連續(xù);E external 為外部能量,通常由圖像決定,外部能量推動(dòng)輪廓點(diǎn)達(dá)到邊界;E con

8、straion 為約束條件?？偰芰康倪B續(xù)形式表示為:E snake =1乙(s Econtinuity+(s E smoothness +(s E image d s ,參數(shù)(s 、(s 、(s 控制著能量的相關(guān)影響。內(nèi)部能量表達(dá)式為:E internal (v (s =(s d v d s2+(s d 2v d s22和的兩項(xiàng)離散式為:d v id s2v i -v i -12,d 2v i d s22v i -1-2v i +v i +12外部能量表達(dá)式為:E external =(s E image ,E image =-|犖I |2式中,I 表示圖像。2Williams 提出Snake

9、 模型的貪婪算法傳統(tǒng)Snake 模型求解中通常使用變分法,這種方法雖然簡(jiǎn)單,但卻存在較多問(wèn)題,如高階導(dǎo)數(shù)的計(jì)算對(duì)噪聲敏感,有可能導(dǎo)致結(jié)果不穩(wěn)定等缺點(diǎn)。Amini 等4人指出變分法的缺點(diǎn)并提出了動(dòng)態(tài)規(guī)劃算法,克服了結(jié)果不穩(wěn)定的缺點(diǎn),但這種算法計(jì)算量大。在此基礎(chǔ)上Williams 等5人提出了解決該問(wèn)題的貪婪算法,使得計(jì)算量大大降低。但在貪婪算法中,能量函數(shù)和Kass 等人提出的稍有不同,總能量式為:E snake =Ni =1(E int (v i +E ext (v i (1式中,內(nèi)部能量E int =i E cont +i E cure ,E cont =d軈-v i -v i -1,E c

10、ure =v i -1-2v i +v i +12,d軈為相鄰兩點(diǎn)的平均距離。外部能量E ext =i E image ,E image =min-magmax-min 。mag 為輪廓點(diǎn)的梯度值;min 、max 分別為鄰域內(nèi)梯度最小、最大值。3模型改進(jìn)Snake 模型不能收斂凹陷區(qū)域可歸結(jié)為內(nèi)部力在凹陷區(qū)域不夠大或不夠合理,需對(duì)該項(xiàng)進(jìn)行一定的調(diào)整。通過(guò)增加新構(gòu)造力實(shí)現(xiàn)對(duì)內(nèi)部力的調(diào)整。引入新構(gòu)造力不應(yīng)使參數(shù)個(gè)數(shù)增加,因?yàn)檫@使得在算法實(shí)現(xiàn)時(shí)不易調(diào)整。為了構(gòu)造新的內(nèi)部能量,考慮相鄰兩點(diǎn)的作用,本文引入輪廓點(diǎn)中心的概念。設(shè)輪廓點(diǎn)為v i (i =1,2,N ,并設(shè)v i 的坐標(biāo)為(x i ,y i

11、 ,o 點(diǎn)的坐標(biāo)為(x軃,y 軃,令x 軃=1N Ni =1x i ,y 軃=1N Ni =1y i ,其中N 為輪廓點(diǎn)的個(gè)數(shù),則o (x軃,y 軃稱為輪廓點(diǎn)中心。然后連接o 與各個(gè)輪廓點(diǎn)得ov i (i =1,2,3,N ,任意相鄰兩點(diǎn)和中心點(diǎn)的連線可表示為ov 軃i 、ov 軃i +1。在參考文獻(xiàn)6中提出力為F i =f iov i|ov i |(i =1,2,3,N ;o 點(diǎn)在力F i 的作用下沿ov i +1方向上位移的大小為s i +1,則位移為S i +1=s i +1ov i +1|ov i +1|,則F i 在沿ov i +1方向上對(duì)o 作功為:F i gS i +1=f i

12、ov 軃i |ov 軃i |軃軃g s i +1ov 軃i +1|ov 軃i +1|軃軃=f i s i +1|ov 軃i |ov 軃i +1|(ov 軃i gov 軃i +1式中,f i s i +1|ov 軃i |ov 軃i +1|為常數(shù),令其為k i ,則力F i 在ov i +1方向作功所產(chǎn)生的能量為:E w (v i =k i (ov 軃i gov 軃i +1=k i (x i-x 軃(x i +1-x 軃+(y i -y軃(y i +1-y 軃,總的能量為Ni =1E w (v i 。這樣的改進(jìn)對(duì)凹陷區(qū)域的收斂有較好的效果,但增加了參數(shù)個(gè)數(shù),算法調(diào)整難度增加。E cont (v i

13、 為連續(xù)性能量即內(nèi)部力所產(chǎn)生的能量,參考文獻(xiàn)6中新構(gòu)造力E w (v i 為內(nèi)部力產(chǎn)生的能量,以下給出E w (v i 和E cure (v i 之間的關(guān)系。定理:設(shè)v i (i =1,2,n 為圖像輪廓初始邊界點(diǎn),o 為初始邊界點(diǎn)的中心,則必有:E w (v i =E cont (v i 。證明:在輪廓邊界點(diǎn)上任意取兩點(diǎn)v i 和v i -1,連接v i v i -1、v i -1o ,v i o ,則構(gòu)成三角形ov i v i -1,E cont (v i =v i -v i -12,E w (v i =ov 軃i gov 軃i +1。因?yàn)檩喞吔琰c(diǎn)的選取時(shí),為得到相對(duì)準(zhǔn)確的邊界,相鄰兩點(diǎn)

14、距離應(yīng)盡量地小,對(duì)于輪廓中心點(diǎn)而言,中心點(diǎn)離各點(diǎn)的距離一般應(yīng)遠(yuǎn)遠(yuǎn)大于兩點(diǎn)間距離,這樣便會(huì)形成如圖1所示的銳角三角形。由于ov i 與ov i -1的夾角非常小,故其余弦值可近似為1,則有:ov 軃i gov 軃i +1=v i -v i -12,即命題得以證明。在Williams 實(shí)現(xiàn)的算法中,內(nèi)部能量E cont (v i 的一階導(dǎo)數(shù)項(xiàng)|v i -v i -1|2被修正為d軈-v i -v i -1,這樣的改動(dòng)可以使得輪廓點(diǎn)趨于均勻。因此,雖然在定理中已經(jīng)證明了E w (v i >E cont (v i ,也不能將E cure (v i 舍去。對(duì)于Snake 模型的修正,為了既能夠使模

15、型效果達(dá)到優(yōu)化而又不失去Snake 模型中連續(xù)能量的功能,所以在傳統(tǒng)Snake 模型中,將原來(lái)連續(xù)性能量修正為新的內(nèi)部能量函數(shù):E cont (v i =d軈-v i -v i -1gE w (v i E w (v i =k i (x i -x軃(x i +1-x 軃+(y i -y 軃(y i +1-y 軃這樣的修正既保證了內(nèi)部力產(chǎn)生強(qiáng)大的收縮力,又保證了點(diǎn)迭代時(shí)各點(diǎn)之間的均勻性。E w (v i 推動(dòng)輪廓點(diǎn)向著凹陷區(qū)域收縮。這樣Snake 模型仍可寫為: (aWilliams 的Snake 模型分割效果圖(b改進(jìn)Snake 模型分割效果圖(cWilliams 的Snake 模型分割效果圖(

16、d改進(jìn)Snake 模型分割效果圖圖2兩種模型分割效果對(duì)比示意圖E snake =Ni =1(i E cont (v i +i E cure (v i +i E image (v i 式中,i 、i 、i 為權(quán)值,E cure (v i 是對(duì)內(nèi)部能量的修正,參數(shù)個(gè)數(shù)不變。4算法的實(shí)現(xiàn)及結(jié)果分析算法的實(shí)現(xiàn)采用貪婪算法,手工選取初始邊界點(diǎn),并分兩階段完成:(1采用改進(jìn)Snake 模型形式。由于傳統(tǒng)的Snake 模型中結(jié)果對(duì)初值依賴很強(qiáng)且容易收斂到噪聲點(diǎn),而E w產(chǎn)生的內(nèi)部收縮力可使得輪廓點(diǎn)迅速收縮到一個(gè)很好的范圍且越過(guò)噪聲點(diǎn),故在該階段采用改進(jìn)Snake 模型形式。這個(gè)階段引入能量E w 起著主要作

17、用。(2采用Williams 的Snake 模型。為了防止收縮力過(guò)大,越過(guò)邊界,所以應(yīng)在適當(dāng)?shù)臅r(shí)候減弱內(nèi)部能量而采用Williams 的Snake 模型。采用128×128的黑白圖像進(jìn)行分割實(shí)驗(yàn)并與傳統(tǒng)的Snake 模型結(jié)果進(jìn)行比較,傳統(tǒng)Snake 模型求解仍然用Williams 所提出的貪婪算法實(shí)現(xiàn)。兩種模型分割效果如圖2所示。兩幅圖像的實(shí)驗(yàn)效果圖中采用傳統(tǒng)的Snake 模型進(jìn)行分割時(shí)參數(shù)取值均為:=1,=1,=1,迭代100次。在采用改進(jìn)Snake 模型進(jìn)行分割時(shí)參數(shù)為:圖2(a、(b中參數(shù)分別為:=2,=1,=1,第1階段迭代10次,第2階段迭代15次,共25次。圖2(c、(d

18、中參數(shù)分別為:=3,=1,=1,第1階段迭代10次,第2階段迭代15次,共25次。本文采用改進(jìn)Snake 模型和傳統(tǒng)Snake 模型相結(jié)合的方法并用兩階段貪婪算法實(shí)現(xiàn)圖像分割。實(shí)驗(yàn)結(jié)果表明,該方法對(duì)深凹陷及更復(fù)雜區(qū)域都是有效的;分割結(jié)果受初始輪廓點(diǎn)影響不大、不易收斂到局部噪聲點(diǎn);對(duì)于各種類型圖像,實(shí)現(xiàn)算法時(shí)參數(shù)易調(diào)整。該模型和算法求解的改進(jìn)主要解決了復(fù)雜區(qū)域分割問(wèn)題,新的能量函數(shù)的引入使得初始輪廓點(diǎn)向邊緣收縮能力大大增強(qiáng)且減弱了結(jié)果對(duì)初值的依賴,但在減弱分割結(jié)果對(duì)初值的依賴性方面還不夠理想,如何更大程度地降低分割結(jié)果對(duì)初值的依賴仍需要進(jìn)一步研究。參考文獻(xiàn)1KASS M ,WITKIN A ,T

19、ERZOPOULOUSE D.Snakes:ac -tive contour model in brady IM ,rosenfield a eds proceed -ings of the 1st international confererce on computer Vision C.London:IEEE Computer Society Press ,1987:259-268.2DUNCAN J S ,AYACHE N.Medical image analysis:progress over two decades and the challenges ahead J.IEEE Trans.Patt.Anal.Mach.Intel.,2000,22(1:85-106.3DAVISON N E ,EVIATAR H ,SOMORJAI R L.SnakessimplifiedJ.Pattern Recognition ,2000,(33:1651-1664.4王元全,湯