計算機視覺主動輪廓線模型Snake模型PPT課件

1、常見的圖像分割算法:(a) 主動輪廓線(b) 水平集(c) 基于圖的分割算法(d) Mean shift(e) Ncuts(f) Graph cut第1頁/共46頁常見的圖像分割算法:(a) 主動輪廓線(b) 水平集(c) 基于圖的分割算法(d) Mean shift(e) Ncuts(f) Graph cut第2頁/共46頁主動輪廓線模型主動輪廓線模型(Snake(Snake模型模型) )第3頁/共46頁1.引言引言 MarrMarr視覺計算理論的不足視覺計算理論的不足 三個獨立的層次三個獨立的層次, ,底層缺乏約束導致病態(tài)問題底層缺乏約束導致病態(tài)問題 自下而上自下而上, ,底層的錯誤將被帶

2、給高層無法修正底層的錯誤將被帶給高層無法修正 Snakes: active contour models Kass,1987,ICCV 對傳統(tǒng)的視覺計算理論的挑戰(zhàn)對傳統(tǒng)的視覺計算理論的挑戰(zhàn) 設(shè)計這樣一個能量函數(shù)設(shè)計這樣一個能量函數(shù): : 其局部極值組成了可供高層視覺處理進行選其局部極值組成了可供高層視覺處理進行選擇的方案擇的方案, ,高層機制可能通過將圖像特征推向一個適當?shù)木植繕O值點從高層機制可能通過將圖像特征推向一個適當?shù)木植繕O值點從該組方案中選擇最優(yōu)的一種該組方案中選擇最優(yōu)的一種第4頁/共46頁1.1 Snake1.1 Snake模型的基本原理模型的基本原理 基本原理是表征擬合誤差的基本原

3、理是表征擬合誤差的“能量能量”為最小化的為最小化的曲線曲線. . 設(shè)對于擬合目標有一個待選曲線集設(shè)對于擬合目標有一個待選曲線集, ,定義能量函數(shù)定義能量函數(shù)與待選集中每一條曲線相關(guān)聯(lián)與待選集中每一條曲線相關(guān)聯(lián), ,能量函數(shù)的設(shè)計原能量函數(shù)的設(shè)計原則就是則就是: :有利屬性要能導致能量縮小。有利屬性要能導致能量縮小。 有利屬性包括有利屬性包括: :曲線連續(xù)、平滑、曲線與高梯度區(qū)曲線連續(xù)、平滑、曲線與高梯度區(qū)域接近以及其他一些具體的先驗知識。域接近以及其他一些具體的先驗知識。 活動輪廓在取值范圍內(nèi)移動時活動輪廓在取值范圍內(nèi)移動時, ,就能在能量函數(shù)的就能在能量函數(shù)的指導下收斂到局部邊界指導下收斂到

4、局部邊界, ,且能保持曲線的連續(xù)和平且能保持曲線的連續(xù)和平滑。滑。第5頁/共46頁1.1 Snake1.1 Snake模型的基本原理模型的基本原理 蛇模型是在曲線本身的內(nèi)力和圖像數(shù)據(jù)的外部約束力作用下的移動的變形蛇模型是在曲線本身的內(nèi)力和圖像數(shù)據(jù)的外部約束力作用下的移動的變形輪廓線。輪廓線。 作用在蛇模型上的力依據(jù)輪廓所在的位置及其形狀決定如何在空間局部的作用在蛇模型上的力依據(jù)輪廓所在的位置及其形狀決定如何在空間局部的變化。變化。 內(nèi)力和外力的作用是不同的內(nèi)力和外力的作用是不同的: :內(nèi)力起平滑約束作用內(nèi)力起平滑約束作用, ,外力則引導蛇模型向圖外力則引導蛇模型向圖像特征移動。像特征移動。 施

5、加在蛇模型上的外力來自于圖像或更高層的處理外力施加在蛇模型上的外力來自于圖像或更高層的處理外力, ,將蛇模型推離不將蛇模型推離不期望的特性。期望的特性。 蛇模型的內(nèi)力包含兩項蛇模型的內(nèi)力包含兩項. .形象的說形象的說, ,可以認為蛇模型是由兩種抽象的彈性材可以認為蛇模型是由兩種抽象的彈性材料構(gòu)成料構(gòu)成: :弦與桿。前者使輪廓抵抗韌性弦與桿。前者使輪廓抵抗韌性, ,而后者使輪廓抵抗彎曲。而后者使輪廓抵抗彎曲。第6頁/共46頁第7頁/共46頁1.2 Snake1.2 Snake模型的特點模型的特點 SnakeSnake模型的優(yōu)點模型的優(yōu)點 圖像數(shù)據(jù)、初始估計、目標輪廓及基于知識的約束統(tǒng)一于一個特征

6、提圖像數(shù)據(jù)、初始估計、目標輪廓及基于知識的約束統(tǒng)一于一個特征提取過程中取過程中; ; 經(jīng)適當?shù)爻跏蓟蠼?jīng)適當?shù)爻跏蓟? , 它能夠自主地收斂于能量極小值狀態(tài)它能夠自主地收斂于能量極小值狀態(tài); ; 尺度空間中由粗到精地極小化能量可以極大地擴展捕獲區(qū)域和降低計尺度空間中由粗到精地極小化能量可以極大地擴展捕獲區(qū)域和降低計算復雜性算復雜性 SnakeSnake模型的缺點模型的缺點 對初始位置敏感對初始位置敏感, , 需要依賴其他機制將需要依賴其他機制將Snake Snake 放置在感興趣的圖像特放置在感興趣的圖像特征附近征附近; ; 它有可能收斂到局部極值點它有可能收斂到局部極值點, , 甚至發(fā)散甚

7、至發(fā)散. .第8頁/共46頁2.Snake2.Snake模型的數(shù)學模型模型的數(shù)學模型蛇模型的總能量函數(shù)是定義Snake模型為一可變形曲線S為歸一化的曲線長度,變化范圍(0,1)第9頁/共46頁2.Snake2.Snake模型的數(shù)學模型模型的數(shù)學模型 外部能量外部能量Eext 決定著向某種固定的特征移動蛇模型決定著向某種固定的特征移動蛇模型, ,吸吸引蛇模型到顯著的圖像特征。因為這些特征只能根據(jù)引蛇模型到顯著的圖像特征。因為這些特征只能根據(jù)特定的問題而定義特定的問題而定義, ,所以一般的外部能量函數(shù)不易確定。所以一般的外部能量函數(shù)不易確定。因此因此, , Eext沒有統(tǒng)一的數(shù)學表達式?jīng)]有統(tǒng)一的數(shù)

8、學表達式, ,必須從問題本身的必須從問題本身的特性出發(fā)特性出發(fā), ,根據(jù)實際情況處理根據(jù)實際情況處理Eint是內(nèi)部能量, ,控制蛇模型特性, ,定義為 分別是v v 對s s 的一階和二階導數(shù), ,系數(shù)、分別是控制蛇模型的彈性和剛性, , 這些參數(shù)操縱著模型的物理行為和局部連續(xù)性第10頁/共46頁外部能量外部能量 ( (E Eextext) ) 圖像能量圖像能量 定義函數(shù)定義函數(shù) Eimage(x,y) ，反映的是對圖像特征（如，反映的是對圖像特征（如邊界）的興趣程度邊界）的興趣程度E Eimageimage(x,y)(x,y)函數(shù)的定義是一個關(guān)鍵問題函數(shù)的定義是一個關(guān)鍵問題. . 典型的例子

9、為典型的例子為 ( ( )extimagesEEv sds2( , )|, )|imageEx yx y 2( , )|( , )* ( , )|imageEx yGx yI x y 第11頁/共46頁能量與內(nèi)外力平衡方程能量與內(nèi)外力平衡方程 目標輪廓的確定就被轉(zhuǎn)化成了極小化如下的能量泛目標輪廓的確定就被轉(zhuǎn)化成了極小化如下的能量泛函的問題函的問題 由變分法的原理出發(fā)由變分法的原理出發(fā), ,可以將其轉(zhuǎn)化為可以將其轉(zhuǎn)化為Euler Euler 方程方程 這一方程可以被看作是輪廓內(nèi)外力的平衡公式這一方程可以被看作是輪廓內(nèi)外力的平衡公式. . 每個力都有對應(yīng)的意義，在這些力的作用下輪廓發(fā)每個力都有對應(yīng)

10、的意義，在這些力的作用下輪廓發(fā)生形變。生形變。221( )|( )| )( ( )2snakesssimagesEsvsvEv s ds0ssssssimagevvE第12頁/共46頁彈性力彈性力 由輪廓的彈性能量產(chǎn)生由輪廓的彈性能量產(chǎn)生 特性特性 這個力使得輪廓連續(xù)這個力使得輪廓連續(xù). .elasticssFv 第13頁/共46頁剛性力剛性力 對應(yīng)著輪廓的剛性能量，也就是曲率對應(yīng)著輪廓的剛性能量，也就是曲率 特性特性 這個力使得輪廓盡量平滑這個力使得輪廓盡量平滑. .Initial curve(High bending energy)Final curve deformed by bendi

11、ng force. (low bending energy)第14頁/共46頁外部力外部力 外部力作用在使得外部能量減小的方向上外部力作用在使得外部能量減小的方向上ImageExternal forceextimageFE Zoomed in第15頁/共46頁離散化離散化 輪廓輪廓 v(s) v(s) 由一系列控制點組成由一系列控制點組成 輪廓通過依次連接更個控制點并分段線性化得到輪廓通過依次連接更個控制點并分段線性化得到. . 平衡力方程獨立作用于各個控制點平衡力方程獨立作用于各個控制點 每個控制點在內(nèi)外力的作用下是可以移動的每個控制點在內(nèi)外力的作用下是可以移動的. . 能量以及平衡力的方程

12、均作離散化處理。能量以及平衡力的方程均作離散化處理。01n -1v,v,.,v第16頁/共46頁3.Snake模型用于輪廓提取的實例模型用于輪廓提取的實例在實際應(yīng)用中, ,我們需要對Snake模型離散化, ,計算的是曲線的各個控制點的能量值, ,定義的能量函數(shù)如(1) 內(nèi)部能量的連續(xù)性項能量dmean 表示曲線上相鄰點的平均距離, 相鄰點間的間距與平均值越接近, 其能量值越小,這樣即保證了平滑,又避免了堆積。是待考察點的3 3 鄰域第17頁/共46頁(2) 內(nèi)部能量的曲率項能量是向量和之間的夾角的余弦值夾角越小,越小,用來估計曲線上各點的曲率第18頁/共46頁(3) 圖像能量是邊緣檢測算子,這

13、一項表示圖像的約束條件,根據(jù)有利邊界點的原則,邊界點應(yīng)具有較小的值是待考察點的3 3 鄰域內(nèi)的最大值,是最大值.這樣的計算用于歸一化(4)在確定能量函數(shù)后, 對曲線按照能量最小進行迭代.第19頁/共46頁3.Snake3.Snake模型用于輪廓提取的實例模型用于輪廓提取的實例第20頁/共46頁4.4.傳統(tǒng)傳統(tǒng)SnakeSnake方法的不足方法的不足 參數(shù)敏感參數(shù)敏感,對初始輪廓要求高對初始輪廓要求高 搜索范圍小搜索范圍小 容易陷入局部極小點容易陷入局部極小點 對于邊界上的凹點無法有效跟蹤對于邊界上的凹點無法有效跟蹤第21頁/共46頁4.Snake模型的改進模型的改進 改善改善Snake Sna

14、ke 對初始化輪廓的敏感性對初始化輪廓的敏感性; ; 保證保證Snake Snake 能夠收斂到全局極值能夠收斂到全局極值; ; 改善改善Snake Snake 在能量極小化過程中的收斂速度或數(shù)值穩(wěn)定性在能量極小化過程中的收斂速度或數(shù)值穩(wěn)定性. .第22頁/共46頁氣球力氣球力balloon forceballoon force Cohen L D, On active contour models and balloons.1991, Image Understanding 在輪廓線上施加另一外部約束力在輪廓線上施加另一外部約束力, ,使輪廓線向目使輪廓線向目標靠攏。在該力的作用下輪廓線不斷

15、的向外膨標靠攏。在該力的作用下輪廓線不斷的向外膨脹脹, ,最終進化到目標輪廓最終進化到目標輪廓, ,可以形象的稱之為氣可以形象的稱之為氣球力球力 由氣球力所構(gòu)造的能量項由氣球力所構(gòu)造的能量項, ,在能量函數(shù)中的數(shù)學在能量函數(shù)中的數(shù)學形式可以表達為形式可以表達為: : 為以控制點vi 為中心的大小為n m 的領(lǐng)域內(nèi)的第(j ,k) 個鄰點, 代表矢量間的點乘運算. ni 是輪廓線上控制點vi 處的單位法線矢量,這樣在規(guī)定的領(lǐng)域內(nèi),在法線矢量ni 方向上離控制點vi 最遠的點將擁有最小的能量值第23頁/共46頁在引入氣球力能量項之后, Snake模型的外部能量項可以描述為其中參數(shù)k 用來控制氣球力

16、的方向,當k 為負數(shù)時,氣球力使輪廓線向內(nèi)收縮,相反當k為正數(shù)時,氣球力使輪廓向外膨脹;在選擇參數(shù)k 和l 的大小時,一般將它們置于同一數(shù)量級,且l 稍大于k ,這是為了在邊緣點時輪廓線能夠停止運動。這樣,原始模型的缺點得到改善,對輪廓線的初始化位置要求明顯降低,即使在初始位置離希望提取的邊緣相當遠時,Snake照樣能夠進化到目標輪廓。該模型改善了蛇模型對初始輪廓的敏感性,并且能夠跨越圖像中的偽邊緣點。氣球力氣球力balloon forceballoon force第24頁/共46頁梯度矢量流梯度矢量流- -Gradient Vector Flow(GVF) Xu C. and JL Prin

17、ce. 1998. Snakes, shapes, and gradient vector flow. IEEE Trans Image Processing. 7(3): 359-363 它的數(shù)學基礎(chǔ)來源于電磁場理論中的亥姆霍茲理論它的數(shù)學基礎(chǔ)來源于電磁場理論中的亥姆霍茲理論, ,這種理論闡這種理論闡明了可以將一種普通的靜態(tài)矢量場分解為兩個組成部分明了可以將一種普通的靜態(tài)矢量場分解為兩個組成部分, ,即無旋即無旋場部分和有旋場部分。場部分和有旋場部分。 在傳統(tǒng)的主動輪廓模型中在傳統(tǒng)的主動輪廓模型中, ,圖像梯度信息僅僅是作為一個靜態(tài)的圖像梯度信息僅僅是作為一個靜態(tài)的無旋場來平衡方程。但是實際

18、上我們能得到一個更加一般化的無旋場來平衡方程。但是實際上我們能得到一個更加一般化的靜態(tài)矢量場靜態(tài)矢量場, ,它不僅包含無旋場部分它不僅包含無旋場部分, ,還包含有旋場部分。還包含有旋場部分。 GVF GVF 的提取可以有效的解決曲率變化很大的控制點的收斂效果的提取可以有效的解決曲率變化很大的控制點的收斂效果, ,但是相對的計算會很慢。但是相對的計算會很慢。第25頁/共46頁 GVF 定義一個力的向量場 V(x,y) = GVF snake的內(nèi)外力平衡方程為 GVF snake定義的能量泛函為梯度矢量流梯度矢量流- -Gradient Vector Flow(GVF)222222() | |xy

19、xyEuuvvfVfdxdy 0ssssssvvV( ( , ), ( , )u x y v x y第26頁/共46頁 GVF場可以通過求解下述方程得到場可以通過求解下述方程得到 2 是拉普拉斯算子是拉普拉斯算子. 上述方程的求解是通過順序迭代上述方程的求解是通過順序迭代u u和和v v實現(xiàn)的實現(xiàn)的 能夠檢測邊界上凹點的原因能夠檢測邊界上凹點的原因. . 使得使得 f 由由| f|大的地方向大的地方向| f|小的地方小的地方擴散擴散, ,因而擴大了因而擴大了Snake Snake 模型的捕捉范圍模型的捕捉范圍, ,也也能較好地進入深度凹陷區(qū)域能較好地進入深度凹陷區(qū)域22()()0 xxyuuf

20、ff22()()0yxyvvfff第27頁/共46頁GVF GVF 方法與傳統(tǒng)方法與傳統(tǒng)SnakeSnake方法的比較方法的比較Traditional forceGVF force(Diagrams courtesy “Snakes, shapes, gradient vector flow”, Xu, Prince)第28頁/共46頁第29頁/共46頁u(x,y)v(x,y)內(nèi)外力的示意圖內(nèi)外力的示意圖第30頁/共46頁實驗結(jié)果實驗結(jié)果Traditional snakeGVF snake第31頁/共46頁經(jīng)過動態(tài)參數(shù)修正以后經(jīng)過動態(tài)參數(shù)修正以后Final shape detected第32頁

21、/共46頁Medical Imaging即使在原始圖像質(zhì)量很差時即使在原始圖像質(zhì)量很差時, ,也能很好的提取輪廓也能很好的提取輪廓左心房的磁共振圖片左心房的磁共振圖片第33頁/共46頁第34頁/共46頁初始輪廓甚至可以與真實輪廓相交初始輪廓甚至可以與真實輪廓相交傳統(tǒng)的傳統(tǒng)的SnakeSnake方法是無法實現(xiàn)的方法是無法實現(xiàn)的初始輪廓的選取是任意的嗎？初始輪廓的選取是任意的嗎？第35頁/共46頁GVF snakeGVF snake的問題的問題 參數(shù)敏感參數(shù)敏感 計算代價高，速度慢計算代價高，速度慢 初始輪廓的選取有臨界點初始輪廓的選取有臨界點第36頁/共46頁其它的改進方法其它的改進方法 B -

22、 Snake B - Snake 模型模型 目標輪廓用目標輪廓用B - B - 樣條來表達樣條來表達 利用參數(shù)利用參數(shù)B B 樣條的局部控制能力及參數(shù)連續(xù)性等特點樣條的局部控制能力及參數(shù)連續(xù)性等特點, ,改進了原模型中存在的一些缺陷改進了原模型中存在的一些缺陷, ,例如不穩(wěn)定地例如不穩(wěn)定地數(shù)據(jù)特性、收斂速度慢、很難處理不連貫性及對噪聲的敏感性。數(shù)據(jù)特性、收斂速度慢、很難處理不連貫性及對噪聲的敏感性。第37頁/共46頁其它的改進方法其它的改進方法 雙主動輪廓模型雙主動輪廓模型 所謂雙主動輪廓模型所謂雙主動輪廓模型, ,就是指在所需要提取的目標輪廓的內(nèi)部和外部各就是指在所需要提取的目標輪廓的內(nèi)部和

23、外部各放置一個主動輪廓線放置一個主動輪廓線, ,分別為內(nèi)輪廓線和外輪廓線。分別為內(nèi)輪廓線和外輪廓線。 在初始情況下在初始情況下, ,兩個輪廓線獨立進行兩個輪廓線獨立進行, ,分別向目標輪廓收斂分別向目標輪廓收斂, ,互不影響互不影響; ;當兩個輪廓線都靜止不動時當兩個輪廓線都靜止不動時, ,則分別對內(nèi)外輪廓進行能量計算并比較則分別對內(nèi)外輪廓進行能量計算并比較, ,選擇能量較大的一個輪廓線選擇能量較大的一個輪廓線, ,對其施加一個外部作用力對其施加一個外部作用力, ,該力的方向指該力的方向指向另外一個輪廓線向另外一個輪廓線, ,強制使當前輪廓線從當前平衡位置離開強制使當前輪廓線從當前平衡位置離開

24、, ,然后重新然后重新啟動進化過程啟動進化過程, ,當達到平衡時當達到平衡時, ,再次進行能量比較并重復以上步驟再次進行能量比較并重復以上步驟, ,直至直至最終內(nèi)外輪廓線的能量之差減小到允許的范圍。最終內(nèi)外輪廓線的能量之差減小到允許的范圍。 可有效解決由于被噪聲所引起的奇異點吸引而陷入能量局部最小的問可有效解決由于被噪聲所引起的奇異點吸引而陷入能量局部最小的問題題.第38頁/共46頁Snake模型的應(yīng)用模型的應(yīng)用 輪廓跟蹤輪廓跟蹤 目標識別目標識別 使目標提取從一開始就處于受控的狀態(tài)使目標提取從一開始就處于受控的狀態(tài), ,并且直接面向所希望提取的并且直接面向所希望提取的目標。同時還給出了對目標

25、輪廓形狀的約束目標。同時還給出了對目標輪廓形狀的約束, ,從而可以快速準確的對目從而可以快速準確的對目標標進行定位進行定位. 三維重建三維重建 三維表面用序列圖像中的輪廓曲線來表達和重建三維表面用序列圖像中的輪廓曲線來表達和重建. 立體匹配立體匹配 如果兩幅圖像中的輪廓線如果兩幅圖像中的輪廓線( (基元基元) ) 互相對應(yīng)互相對應(yīng), , 那么沿著那么沿著3D 3D 輪廓的其他輪廓的其他幾何形狀應(yīng)具有相似性幾何形狀應(yīng)具有相似性. .第39頁/共46頁Snake模型的應(yīng)用模型的應(yīng)用 變形模板變形模板 由于自然物體形狀的多樣性和復雜性以及圖像的噪聲由于自然物體形狀的多樣性和復雜性以及圖像的噪聲等復雜因素的影響等復雜因素的影響, , 在使用剛性模型提取圖像輪廓在使用剛性模型提取圖像輪廓時遇到了極大的困難時遇到了極大的困難. . 基于基于Snake Snake 模型的變形模板模型的變形模板方法方法, , 為解決這一問題展現(xiàn)了令人鼓舞的前景為解決這一問題展現(xiàn)了令人鼓舞的前景. . 相對于剛性模板來說相對于剛性模板來說, , 變形模板使自己發(fā)生變形以變形模板使自己發(fā)生變形以匹配到顯