水平集的圖像分割方法綜述

1、第13卷 第1期2008年1月中國圖象圖形學報Journa l o f I m age and G raphicsV o. l 13, N o . 1Jan . , 2008收稿日期:2006 02 28; 改回日期:2006 09 12第一作者簡介:錢蕓(1982 , 女?，F(xiàn)在西安交通大學攻讀飛行器設(shè)計專業(yè)碩士學位。研究方向是面向逆工程的圖像分割和3維建模。E i :l . co m; yahoo . co 水平集的圖像分割方法綜述錢 蕓張英杰(西安交通大學機械學院, 西安 710049摘 要 圖像分割是圖像處理中的關(guān)鍵技術(shù)之一, O sher 和Sethian 提出的水平集方法有效地解決了

2、以前算法不能解決在曲線演化過程中的拓撲變化問題。目前, 基于水平集方法的圖像分割算法很多, 對于不同應(yīng)用領(lǐng)域的圖像處理問題, 人們都提出了相應(yīng)的解決方法, 而且大量的研究者還在不斷改進和提高這些算法的效率和有效性。因此, 本文按照水平集算法在圖像分割中應(yīng)用的發(fā)展歷程將其分為3種情況進行了綜述, 以此為該領(lǐng)域讀者提供借鑒。關(guān)鍵詞 水平集 圖像分割 活動輪廓模型 M um ford Shah 模型 多相位中圖法分類號:TP391. 41 文獻標識碼:A 文章編號:1006 8961(2008 01 0007 07Level SetM ethods and Its App licati on on

3、I mage Seg m entati onQ IAN Yun, Z HANG Y i n g jie2(Sc h ool of M ec h e n i ca lE ng i n ee ring, X i an J i aotong Universit y, X i an 710049Abstrac t I mage seg m enta tion is a key proble m i n i m age processi ng . Curve evo l uti on , which i s very difficu lt to so l ve prev iousl y , w as e

4、ff ectively handled by leve l set m et hod propo sed by O sher and Seth i an . A t present , t here are so m any i m age seg m entati on methods based on l evel set , and t here are differentm ethods to different i m ages . Now, these m ethods are conti nua ll y i m proved to enhance the speed and t

5、he verac ity . So i n this paper , accord i ng t o the deve l op ment o f the i m age segmentati on m et hods based on level set , this al go rith m i s introduced for readers o f d ifferent backg rounds in t h is field to use . K eywordslevel set , i m age segm enta ti on , active contour m ode, l

6、M u m ford Shah m ode, l mu lti phase1 引 言借鑒一些流體中的重要思想, 1988年, O sher 和Seth i a n 首次提出了水平集算法1, 這是一種有效解決曲線演化問題的數(shù)值方法, 并且計算穩(wěn)定, 適宜任意維數(shù)空間。隨后, O sher 等人對水平集算法做出擴展和總結(jié)2, 3, G i g a 也做了相關(guān)的理論擴展4。近年來這種算法已被廣泛地應(yīng)用在圖像處理領(lǐng)域5中, 尤其在圖像分割中已取得了很大的進展。事實上, 用水平集來解決圖像分割問題的實質(zhì)就是與活動輪廓模型結(jié)合, 用水平集方法來求解這些模型得到的偏微分方程PDE (parti a l di

7、fferentia l equa ti o n, 屬于邊緣檢測的分割方法。2 水平集方法水平集方法將n 維曲面的演化問題轉(zhuǎn)化為n +1維空間的水平集函數(shù)曲面演化的隱含方式來求解, 主要包括3個要素:超曲面的數(shù)據(jù)表示, 控制曲面演化的一系列PDE 以及相應(yīng)的數(shù)值解法。Osher 和Fed ki w 對水平集方法做了歸納和總結(jié)6。為簡化問題,這里選擇n =2來討論。水平集的主要思想是將2維平面閉合曲線C (t 表示為水平集函數(shù) 的零水平集 (t =0, 即將界面嵌入到一個曲面中, 將2維曲線的演化轉(zhuǎn)化為3維曲面演化。具體情況如圖1所示。首先, 定義符號距離函數(shù)(si g ned d istance

8、 func tion , SDF:8 中國圖象圖形學報第13卷 第1期錢 蕓等:水平集的圖像分割方法綜述910 中國圖象圖形學報第13卷 第1期錢 蕓等:水平集的圖像分割方法綜述1112 中國圖象圖形學報 第 13卷 用窄帶方法可降低計算復雜度; 基于 M um ford Shah 模型的水平集圖像分割方法適用于模糊或噪聲較大 的圖像。在分割多相位圖像時, 也是基于這兩種基 本方法。多相位圖像的所有相位可用多個水平集函 數(shù)來表示, 也可用一個水平集函數(shù)的不同水平層來 表示, 從而達到分割目的。實踐證明, 這 3種圖像的 水平集圖像分割方法應(yīng)用廣泛, 能達到很好的分割 效果。水平集方法是一種簡單

9、、 精確、 靈活的數(shù)值方 法, 具有很多優(yōu)點, 其中最主要的優(yōu)勢在于處理外形 復雜、 拓撲結(jié)構(gòu)變化的圖像。它可以廣泛地應(yīng)用到 科學計算領(lǐng)域, 有很好的發(fā)展前景?，F(xiàn)在, 研究者們 都在基于水平集方法不斷地降低計算復雜度, 提高 算法速度和分割準確度。 參考文獻 ( Referen ces 1 O sh er S Seth ian J A. Fron ts propagat ing w ith cu rvature dep endent , speed algorithm s based on H am ilton Jacob i for u lations J . Journ al : m of

10、 C ompu tat iona l Physics 1988 79( 1 : 12 49. , , 2 O sh er S Shu C W. H igh order essent ial ly nonoscillatory schem es for , H am ilton Jacob i equ at ion J . S I AM Jou rnal of N um erica l A nalys is , 1991 28( 4 : 907 922. , 3 O sh er S S eth ian J A. Level Set M ethod s and D ynam ic I p lici

11、t Sur , m faces M . N ew Y ork: Springer V erlag, 2002: 22 114. 4 G iga Y. Surface Evolu tion Equation A Level SetM ethod M . L ip schitz L ectu re N otes 44, G er any: m U n iversity of Bonn, 2002 : 圖 5 使用 4相位分段常數(shù)模型對噪聲融入圖像的分割情況 F ig. 5 The segmentation o f the no isy i age using m 4 phases piecew i

12、se constant mode l 56 85 . 5 R ichard Tai Y H, O sher S Total V ariation and L evel Set B ased . M ethods in I mage Science D . Los A ngles U n iversity of Cam : b ridge, 2005 . 6 O sh er S Fedk i R. Level Set M ethods and D yn am ic I licit Sur , w mp faces M . N ew Y ork: Springer V erlag, 2002: 3

13、4 67 . n 式中, K ( = i= 1 ( - i。 如果滿足 K ( = 0 那 , 有 ( x = i。 7 M allad i R, Seth ian J V em uri B. Shape m odeling w ith front p ropaga , tion A level set app roach J . I : EEE T ransact ion s on Pattern A naly sis and M ach ine I telligence 1995 17 ( 2 : 158 174 n , , . 8 K ass M, W itk in A, Terzopo

14、u los D. Sn akes A ctive con tour models : J . In ternational Jou rnal of Com puter V is ion, 1995, 1( 4 : 321 331 . 9 Caselles V, Catte T, Coll T, e t al. A geom etric m odel for active con tours in i age processing J . N um eric M ath 1993 66 ( 1 : 1 m , , 31 . 10 M al lad i R, Seth ian J A, V em

15、uri B C A topology independen t shape . m od el ing sch em e A . I Proceed ings of SPIE Conference G eom et n: , ric M ethods Compu ter V ision II C . San D iego CA, U SA, 1993 , , 2031 246 258 : . 么 存在 唯一的 i 使得 每一 個 x ! 小化問題 29 L ie Lysaker 用了擴展的拉格朗日方法解決以上最 采 。但此法在表示曲線單位法矢及曲率 方面有一定的困難, 而且還用高階多項式來作為

16、基 本函數(shù), 正確的分割往 往依賴于較好 的初始曲線。 B resson等人針對這一問題提出通過尋找活動輪廓 的全局最小化算子來確定初始曲線 32 。 6 結(jié) 論 31 目前, 水平集的圖像分割算法已廣泛地應(yīng)用于 各個領(lǐng)域, 特別是醫(yī)學 和航空領(lǐng)域?；谔荻鹊?水平集圖像分割方法適用于梯度變化很大的圖像, 11 Coh en L D. O n act ive contou r m odels and balloon s J . Com puter V is ion, G raph ics and I age Processing, 1991 53( 2 : 211 218 , m , . 12

17、 Caselles V, K i m el K, Sap iro G. On geodesic act ive contours J . m International Jou rnal of Com puter V is ion, 1997, 22( 1 : 61 79. 第 1期 錢 蕓等: 水平 集的圖像分割方法綜述 13 13 A dalsteinsson D, S eth ian J A. The fast cons truct ion of ex ten sion ve locit ies in level set m ethod s J . 1( 48 : 2 22 . 14 S

18、 eth ian J A. Fast m arch ing level set m ethods for three d i ensional m photol ithography d evelopm ent A . In Proceed ing of SPIE C , San : D iego, CA, U SA, 1996, 2726: 261 272. 15 Ts itsik lis J E ff icient algorithm s for g loba lly opt i al trajectories J . . m IEEE Transact ions on A u tom a

19、t ic Contro,l 1995, 40 ( 9 : 1538. 16 Zhao H ong ka.i Fast sw eep ing m ethod for eikonal equations J . M ath Com putation 2005 74 ( 9 : 603 627. , , 17 Zhang Y ong tao Zhao H ong ka, Chen Shan q in Fixed poin t Itera , i . t ive Sw eep ing M ethods for StaticH am ilton Jacob i Equations D . Los A n

20、gles U n ivers ity of C aliforn ia, 2005 : . 18 K ao C Y, O sher S, Tai Y H. Fast Sw eep ing M ethod s for H am ilton Jacob i E qu at ion s DB . cam03 75. pd , 2002 f . 19 Tsai Y R. R ap id and accu rate compu tat ion of the d istance fun ct ion u s ing grids J . Jou rnal of Com puter Physics 2002 1

21、78( 1 : 175 , , 195. 20 Ch an T, V ese L. A ctive con tours w ithou t edages J . I EEE T ransac t ion s on I mage Process ing, 2001 10( 2 : 266 277. , 21 M u ford D, m Shah J O pt i al approx i at ion by p iecew ise s ooth . m m m ftp / / ftp m ath ucla edu /pub / cam report / : . . . 1528 C ompu ta

22、t ional Phys ics , 1999, m od el based on level set m otion for non lin ear deb lu rring and noise re m oval J . 387 405. 24 A lvarez F, G u ichard F, M orel JM, e t a l. A x iom s and fundam ental e quat ions of i age p rocess ing J . A rch ive for R at ionalM echan ics and m A n alysis 1993, 123(

23、8 : 199 257 , . 25 G ibou F, Fedk i R. A fast level set based algorithm for segm entation w A . In IEEE C on feren ce on C om puterV ision and Pattern R ecogn i : tion C , N ew Y ork, 2002, 2011: 213 222. 26 Song B, Chan T. Fast A lgorithm for Level S et Based O p ti ization m D . Los A ng les U n i

24、versity of Califor ia 2000. : n , 27 G ao S T ien D B I age segm en tat ion and selective s oothing by u , . m m sing M um ford Sh ah m od el J . IEEE T ransctions on I age Process m ing, 2005 14 ( 10 : 1537 1549. , 28 Zh ao H ong ka, Chan T, M erri an B et a l. A variat ional level set i m , approa

25、ch to m u lt iphase m otion J . Inter at ion al Journal of Com puter n Phys ics 1996, 127( 12 : 179 195 , . 29 Lie J LysakerM, Tal X. A V arian t of the Level S et M ethod and A p , p lications to I age S egm entation D . N or ay: U n ivers ity of B ergen m w , 2003 . 30 Sm ith K A, S olis F J C hopp D L. A p rojection m ethod form otion of , trip le jun ct ion s by level sets J .