基于區(qū)域的活動(dòng)輪廓圖像分割模型的變步長(zhǎng)優(yōu)化算法

鄭漢翔，王美清

(福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州　350116)

基于區(qū)域的活動(dòng)輪廓圖像分割模型的變步長(zhǎng)優(yōu)化算法

鄭漢翔，王美清

(福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州350116)

摘要：基于偏微分方程圖像分割的活動(dòng)輪廓模型，基本思想是將圖像分割歸結(jié)為最小化一個(gè)封閉曲線的能量泛函, 圖像分割問題實(shí)質(zhì)上是一個(gè)無約束最優(yōu)化問題. 傳統(tǒng)最小化算法的數(shù)值實(shí)現(xiàn)過程中采用固定時(shí)間步長(zhǎng)的方法, 時(shí)間步長(zhǎng)選取較大，迭代過程容易出現(xiàn)震蕩現(xiàn)象影響分割結(jié)果，而時(shí)間步長(zhǎng)選取較小，又會(huì)減慢收斂速度. 利用Wolfe-Powell線搜索方法，提出了一種變時(shí)間步長(zhǎng)的優(yōu)化算法，在迭代過程中根據(jù)搜索方向自動(dòng)調(diào)整時(shí)間步長(zhǎng)大小，有效克服了固定時(shí)間步長(zhǎng)出現(xiàn)的震蕩現(xiàn)象和收斂速度慢的問題.

關(guān)鍵詞：圖像分割； 非精確線搜索； 活動(dòng)輪廓； 時(shí)間步長(zhǎng)

0引言

圖像分割是圖像處理和計(jì)算機(jī)視覺的基本問題之一，其目的是把感興趣的對(duì)象從給定圖像中分離出來. 基于活動(dòng)輪廓模型圖像分割是當(dāng)前的一個(gè)熱門研究課題，特別是基于區(qū)域的活動(dòng)輪廓模型，由于它的魯棒性以及能很好地結(jié)合圖像信息而被廣泛應(yīng)用. 活動(dòng)輪廓模型(或Snake模型)是由Kass等[1]首先提出的，其基本思想是將圖像分割問題歸結(jié)為最小化一個(gè)封閉曲線的能量泛函[2]. Chan等[3]提出的CV模型是應(yīng)用最廣泛的一種基于區(qū)域的圖像分割模型，該模型利用活動(dòng)輪廓內(nèi)部和外部的灰度均值近似分割圖像，對(duì)同質(zhì)圖像可以得到很好的分割結(jié)果. Li等[4]提出了LBF模型克服了CV模型不能處理非同質(zhì)圖像的缺點(diǎn)，該模型利用圖像的局部信息控制輪廓曲線演化，能有效地克服灰度不均現(xiàn)象.

梯度下降法是求解活動(dòng)輪廓模型能量最小化問題最簡(jiǎn)單直接的算法，圖像處理中的傳統(tǒng)方案是通過計(jì)算負(fù)梯度方向作為能量下降方向，并且以固定的時(shí)間步長(zhǎng)迭代求解. 但是在迭代過程中，如果時(shí)間步長(zhǎng)選取過小，將會(huì)影響收斂速度； 如果時(shí)間步長(zhǎng)選取過大，求解過程會(huì)出現(xiàn)震蕩現(xiàn)象影響分割結(jié)果. 因此，近年來許多學(xué)者針對(duì)活動(dòng)輪廓圖像分割模型提出了新的求解算法. 如Goldstein等[5]采用了分裂Bregman迭代算法求解凸化的CV模型，另外還有Newton 方法和Quai-Newton法[6]等. Bregman迭代出自泛函分析的概念，該算法要求所求模型必須為凸模型； 在數(shù)值優(yōu)化中，Newton法比梯度下降法擁有更快的收斂速度，但Newton法計(jì)算與存儲(chǔ)Hessian矩陣的開銷很大，并且當(dāng)Hessian矩陣奇異時(shí)牛頓方向不存在或者不是函數(shù)的下降方向； Quai-Newton法雖然不需要計(jì)算Hessian，但是Quai-Newton法在儲(chǔ)存矩陣以及通過求解線性方程組來計(jì)算搜索方向上，在圖像處理中開銷依然很大.

針對(duì)傳統(tǒng)活動(dòng)輪廓迭代格式中選取固定時(shí)間步長(zhǎng)的問題，應(yīng)用Wolfe-Powell非精確線搜索準(zhǔn)則提出一種變步長(zhǎng)算法. 在迭代求解過程中，根據(jù)求得的下降方向自動(dòng)調(diào)節(jié)時(shí)間步長(zhǎng)，提高收斂速度的同時(shí)克服了震蕩現(xiàn)象. 實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法的有效性.

1基于區(qū)域活動(dòng)輪廓分割模型

1.1CV模型

CV模型[3]假設(shè)分割圖像I為分片常數(shù)圖像，通過最小化如下由水平集表示的能量泛函來實(shí)現(xiàn)分割：

(1)

其中： λ1，λ2，μ∈R+； Ω?R2表示圖像區(qū)域； φ(x):Ω→R表示水平集函數(shù)； c1和c2分別表示演化曲線內(nèi)部和外部的灰度平均值.

(2)

式中:H(·)和δ(·)分別表示Heaviside函數(shù)和Dirac函數(shù)，參考文獻(xiàn)[3]，取正則化的Heaviside函數(shù)Hε(·)和δε(·)：

CV模型利用圖像全局信息，因此對(duì)初始曲線不敏感且對(duì)噪聲具有魯棒性. 但由于假設(shè)待分割圖像為分片常數(shù)圖像，因此無法處理灰度分布不均的非同質(zhì)圖像.

1.2LBF模型

為了分割非同質(zhì)圖像，LBF模型[4]通過引入核函數(shù)定義了一個(gè)局部二值擬合水平集能量泛函：

(3)

其中： η1，η2，ν，μ∈R+； H(·)和δ(·)分別表示Heaviside函數(shù)和Dirac函數(shù)； Kσ為高斯核函數(shù)； f1(x)和f2(x)為圖像在x點(diǎn)的局部擬合值.

(4)

LBF模型的后兩項(xiàng)為長(zhǎng)度項(xiàng)和避免重新初始化的正則化項(xiàng).

在LBF模型中,f1(x)和f2(x)利用了圖像的局部信息，因此能夠很好地處理灰度分布不均的非同質(zhì)圖像. 但是由于未涉及全局信息，該模型對(duì)初始輪廓和噪聲沒有魯棒性. 實(shí)驗(yàn)結(jié)果還表明, LBF模型對(duì)時(shí)間步長(zhǎng)極其敏感.

1.3傳統(tǒng)求解方案

對(duì)CV模型(1)和LBF模型(3)分別用變分法獲得梯度公式：

(5)

(6)

再利用下列迭代格式更新水平集函數(shù)：

(7)

在最小化活動(dòng)輪廓模型的迭代過程中，由式(5)和(2)交替更新φ和c1、c2來求解CV模型，由式(6)和(4)交替更新φ和f1、f2來求解LBF模型. 數(shù)值實(shí)現(xiàn)過程中涉及時(shí)間步長(zhǎng)Δt的選取，傳統(tǒng)的求解方法一般通過多次實(shí)驗(yàn)選取固定的時(shí)間步長(zhǎng)Δt. 為了避免分割結(jié)果產(chǎn)生震蕩現(xiàn)象，往往取Δt為一較小的值，因此傳統(tǒng)方法收斂速度比較慢.

2變步長(zhǎng)優(yōu)化算法

2.1Wolfe-Powell線搜索

在上述的求解過程中，只能通過多次實(shí)驗(yàn)手動(dòng)選取時(shí)間步長(zhǎng)，并且在迭代過程中時(shí)間步長(zhǎng)是固定的，不會(huì)根據(jù)搜索方向的變化而變化. 實(shí)驗(yàn)結(jié)果表明過大的時(shí)間步長(zhǎng)會(huì)產(chǎn)生震蕩現(xiàn)象影響分割結(jié)果，因此為了保證分割結(jié)果，往往只能選擇較小的時(shí)間步長(zhǎng)，但這將會(huì)增加迭代次數(shù)影響收斂速度.

(8)

(9)

由于準(zhǔn)則(8)和(9)有可能把步長(zhǎng)因子的極小值排除在可接受區(qū)間之外，后來Wolfe、 Powell等又給出了更為簡(jiǎn)單的條件代替(9)式，詳見：

(10)

其中：c2∈(c1，1). 有時(shí)也用另一種條件更強(qiáng)的不等式：

(11)

來代替不等式(10). 聯(lián)合式(8)和(10)或式(8)和(11)即是著名的Wolfe-Powell準(zhǔn)則[7-8].

由于Armijo-Goldstein準(zhǔn)則和Wolfe-Powell準(zhǔn)則均具有良好的收斂性質(zhì)和不錯(cuò)的數(shù)值表現(xiàn)，至今仍在許多數(shù)值計(jì)算和工程中廣泛采用[9].

利用Wolfe-Powell準(zhǔn)則確定式(7)中的時(shí)間步長(zhǎng)Δt，具體算法如下：

算法1Wolfe-Powell線搜索算法

Step1: 給定xk，設(shè)c1=0.000 1，c2=0.9，β=0.8，Δt=1;

Step2: 根據(jù)公式(5)或者(6)計(jì)算能量泛函的梯度▽?duì)誇(xk)，并且設(shè)搜索方向?yàn)樨?fù)梯度方向d=-▽?duì)誇(φk)，若F(xk+Δtd)≤F(xk)+c1Δt▽?duì)誇(xk)Td，轉(zhuǎn)入Step3，否則轉(zhuǎn)入Step4；

Step3:Δt=Δt/β，若F(xk+Δtd)>F(xk)+c1Δt▽?duì)誇(xk)Td，停止； 否則轉(zhuǎn)入Step2；

Step4:Δt=Δt·β，若▽?duì)誇(xk+Δtd)Td

2.2變步長(zhǎng)優(yōu)化算法

利用Wolfe-Powell線搜索算法，提出了能量最小化問題的變步長(zhǎng)優(yōu)化算法. 首先根據(jù)式(5)或(6)確定能量泛函的負(fù)梯度方向?yàn)樗阉鞣较騞k=-▽?duì)誇(φk)，然后由算法1確定時(shí)間步長(zhǎng)Δt； 將dk和Δt代入公式(7)更新水平集函數(shù)φk. 重復(fù)使用上述過程直至相鄰兩次水平集函數(shù)滿足停止標(biāo)準(zhǔn). 用相鄰兩次迭代產(chǎn)生的水平集函數(shù)的近似程度作為停止標(biāo)準(zhǔn).

具體算法如下：

算法2變步長(zhǎng)優(yōu)化算法

Step1: 給定初始輪廓曲線φ0，給定迭代停止標(biāo)準(zhǔn)δ；

Step2: 計(jì)算搜索方向dk=-▽?duì)誇(φk)；

Step3: 由算法1確定時(shí)間步長(zhǎng)Δt，利用式(7)更新φk；

該算法跟蹤曲線演化過程中的梯度方向，動(dòng)態(tài)地調(diào)節(jié)時(shí)間步長(zhǎng)，有效避免了手動(dòng)選取步長(zhǎng)導(dǎo)致的震蕩現(xiàn)象和收斂速度慢的問題.

2.3方法可行性分析

圖1　時(shí)間步長(zhǎng)選取示意圖Fig.1　Diagram for the choosing of time step

將F定義為以Δt為自變量的函數(shù)，xk，dk均為常量. 則圖1中實(shí)線表示函數(shù)F(xk+Δtdk)，點(diǎn)劃線表示函數(shù)F(xk)+c1Δt▽F(xk)Tdk，虛線表示斜率為c2▽F(xk)Tdk且與函數(shù)F(xk+Δtdk)相切的直線.Wolfe-Powell準(zhǔn)則(8)式保證Δtb，所以算法選取的時(shí)間步長(zhǎng)Δt的可接受區(qū)間被限制在[b，a]，其中包括極小值點(diǎn)c. 因此經(jīng)過迭代可以收斂到極小值點(diǎn). 而傳統(tǒng)方法選取固定的時(shí)間步長(zhǎng)，如果選取過大的時(shí)間步長(zhǎng)，函數(shù)F(xk+Δtdk)將越過極小值點(diǎn)，并且在極小值點(diǎn)附近徘徊，這將造成震蕩現(xiàn)象而無法收斂，所以必須選取較小的時(shí)間步長(zhǎng)才能保證函數(shù)充分接近極小值點(diǎn)，這樣又導(dǎo)致收斂速度緩慢.

在算法實(shí)現(xiàn)過程中，將Wolfe-Powell線搜索的最大循環(huán)次數(shù)限制為常數(shù)40，因此變步長(zhǎng)算法的時(shí)間復(fù)雜度為T(N)=O(N)+O(c·N)=O(N)，與傳統(tǒng)的梯度下降法一致. 但是傳統(tǒng)算法迭代過程選取的時(shí)間步長(zhǎng)近似于可接受區(qū)間里的最小值，因此每次分割都接近算法的最壞情況，而變步長(zhǎng)算法選取可接受區(qū)間內(nèi)的最大步長(zhǎng)，避免了最壞情況的發(fā)生.

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

3.1CV模型

圖2、 3均為對(duì)CV模型分別應(yīng)用傳統(tǒng)求解方法和變步長(zhǎng)算法獲得的實(shí)驗(yàn)結(jié)果. 圖2(a)、 3(a)是原始圖像和初始輪廓線; 圖2(b)、 3(b)為傳統(tǒng)方法求解結(jié)果，迭代次數(shù)分別為132次和142次，迭代時(shí)間分別為1.41 s和2.06 s； 圖2(c)、 3(c)是采用變步長(zhǎng)方法求解結(jié)果，迭代過程自動(dòng)選取時(shí)間步長(zhǎng)，迭代次數(shù)分別為71次和68次，迭代時(shí)間分別為0.98 s和1.47 s. 從實(shí)驗(yàn)結(jié)果可以看出，變步長(zhǎng)方法在保證分割結(jié)果的同時(shí)減少迭代次數(shù)，加快了迭代收斂速度. CV模型對(duì)時(shí)間步長(zhǎng)大小相對(duì)不敏感，所以變步長(zhǎng)方法在CV模型中主要起自動(dòng)選取時(shí)間步長(zhǎng)以及加速收斂的作用.

圖2　同質(zhì)圖像的CV模型分割結(jié)果Fig.2　Segmentation result of CV model for homogeneous image

圖3　帶噪聲幾何圖形的CV模型分割結(jié)果Fig.3　　　　Segmentation result of CV model for geometric 　　　figure with noise

3.2LBF模型

圖4是對(duì)LBF模型分別用傳統(tǒng)迭代方法和變步長(zhǎng)方法的分割結(jié)果. 圖4(a)～(c)是利用傳統(tǒng)迭代方法求解LBF模型在不同時(shí)間步長(zhǎng)下的分割結(jié)果. 可以看出在傳統(tǒng)迭代方法中，時(shí)間步長(zhǎng)的微小變化會(huì)嚴(yán)重影響LBF模型的分割結(jié)果和迭代次數(shù)，即LBF模型是對(duì)時(shí)間步長(zhǎng)較為敏感的一種模型. 圖4(d)為變步長(zhǎng)方法的迭代結(jié)果，變(時(shí)間)步長(zhǎng)方法避免了LBF模型對(duì)時(shí)間步長(zhǎng)的敏感性.

圖4　LBF模型的分割結(jié)果Fig.4　Segmentation result of LBF model

圖5　LBF模型能量變化曲線　　　Fig.5 Energy curve of LBF model

圖5是LBF模型的能量變化曲線，橫坐標(biāo)表示迭代次數(shù)，縱坐標(biāo)表示函數(shù)能量. 其中紅色實(shí)線為變步長(zhǎng)方法的能量下降曲線，藍(lán)色點(diǎn)線、 黑色點(diǎn)劃線、 綠色虛線代表用傳統(tǒng)迭代方法分別取Δt=0.15、 0.20、 0.25時(shí)的能量下降曲線.

當(dāng)時(shí)間步長(zhǎng)為0.20時(shí)，能量泛函最小化過程出現(xiàn)震蕩現(xiàn)象，從圖4(b)中可以看出分割結(jié)果受到影響，同時(shí)震蕩現(xiàn)象使得停止標(biāo)準(zhǔn)失效，而當(dāng)時(shí)間步長(zhǎng)大于0.20時(shí)，能量泛函沒有收斂到最小，對(duì)應(yīng)圖4(c)則無法分割. 通過反復(fù)實(shí)驗(yàn)發(fā)現(xiàn)傳統(tǒng)方法選取時(shí)間步長(zhǎng)為0.15時(shí)達(dá)到最佳的分割結(jié)果，迭代次數(shù)為275次，用時(shí)3.38 s (見圖4(a)). 而采用變步長(zhǎng)方法自動(dòng)選取時(shí)間步長(zhǎng)，得到最佳分割結(jié)果的同時(shí)，加快收斂速度，迭代次數(shù)僅為109次，用時(shí)2.26s (見圖4(d)).

4結(jié)論

在傳統(tǒng)活動(dòng)輪廓模型數(shù)值最優(yōu)化算法的基礎(chǔ)上，提出一種變時(shí)間步長(zhǎng)算法. 該算法根據(jù)每次迭代求得的搜索方向自動(dòng)調(diào)節(jié)時(shí)間步長(zhǎng). 實(shí)驗(yàn)結(jié)果表明，該方法克服了傳統(tǒng)方法選取較大時(shí)間步長(zhǎng)時(shí)出現(xiàn)的震蕩現(xiàn)象，同時(shí)減少了迭代次數(shù)，加速了算法收斂.

參考文獻(xiàn)：

[1] KASS M，WITKIN A，TERZOPOULOS D. Snakes: active contour models[J]. International Journal of Computer Vision，1988，1(4): 321-331.

[2] MUMFORD D，SHAH J. Optimal approximation by piece-wise smooths functions and associated variational problems[J]. Communications on Pure and Applied Mathematics，1989，42(5): 677- 685.

[3] CHAN T F，VESE L A. Active contours without edges[J]. Image Processing，IEEE Transactions on，2001，10(2): 266-277.

[4] LI C，KAO C Y，GORE J C，etal. Implicit active contours driven by local binary fitting energy[C]//Computer Vision and Pattern Recognition. Minneapolis: IEEE Conference Publications，2007: 1-7.

[5] GOLDSTEIN T，BRESSON X，OSHER S. Geometric applications of the split Bregman method: segmentation and surface reconstruction[J]. Journal of Scientific Computing，2010，45(1/2/3): 272-293

[6] CHAN T F，ESEDOGLU S，NIKOLOVA M. Algorithms for finding global minimizers of image segmentation and denoising models[J]. SIAM Journal on Applied Mathematics，2006，66(5): 1 632-1 648.

[7] BOYD S P，VANDENBERGHE L. Convex optimization[M]. Cambridge: Cambridge University Press，2004.

[8] 黃紅選，韓繼業(yè). 數(shù)學(xué)規(guī)劃[M]. 北京： 清華大學(xué)出版社，2006.

[9] 朱訓(xùn)芝，唐煥文. 一種新的無約束優(yōu)化線搜索算法[J]. 運(yùn)籌與管理，2005，14(5): 18-23.

(責(zé)任編輯： 洪江星)

A variable step-size optimization algorithm based on active contour model

ZHENG Hanxiang，WANG Meiqing

(College of Mathematics and Computer Science，F(xiàn)uzhou University，F(xiàn)uzhou，F(xiàn)ujian 350116，China)

Abstract:The basic idea of PDE-based image segmentation based on the active contour model is to minimize the energy functional on a closed curve. Thus, the image segmentation problem is in essence an unconstrained optimization problem. The traditional minimization uses, a fix time step which may produce some problems. The large time step may lead to the oscillation of energy functional, while the small time step will slow down the convergence speed. A variable step-size method is proposed by using the Wolfe-Powell line search method. Our method will adjust time step at each iteration according to the search direction which effectively overcome the oscillation of energy functional and the defect on convergence speed.

Keywords:image segmentation; inexact line search; active contour; time step

DOI:10.7631/issn.1000-2243.2016.03.0419

文章編號(hào)：1000-2243(2016)03-0419-05

收稿日期:2014-01-17

通訊作者:王美清(1967-), 教授，主要從事圖像處理技術(shù)、 視頻壓縮算法、 數(shù)值算法方面研究，mqwang@fzu.edu.cn

基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(11071270)

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)識(shí)碼：A