李 青，潘振寬，魏偉波，宋田田

(青島大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，山東 青島 266071)

1 引言

變分法[1]是研究泛函的極大值或極小值問(wèn)題的一種方法，在圖像的變分模型下，可以把圖像處理的問(wèn)題轉(zhuǎn)化成求解變分的問(wèn)題，對(duì)圖像的處理效率高且效果好。圖像分割是一項(xiàng)重要的圖像分析和處理技術(shù)，在醫(yī)學(xué)圖像分析、智能交通管理、遙感圖像處理等領(lǐng)域得到了廣泛的應(yīng)用。圖像分割的重點(diǎn)在于分割目標(biāo)值的速度和精度，很多方法存在著計(jì)算效率低、分割精度不高、魯棒性差的問(wèn)題。結(jié)合變分偏微分方程方法利用數(shù)值計(jì)算方法高效的優(yōu)勢(shì)，在解決圖像問(wèn)題時(shí)可以快速地處理圖像的幾何特征，這類數(shù)學(xué)方法也易于擴(kuò)展到多個(gè)模型中。

基于變分模型的方法利用圖像的區(qū)域、邊界等信息，廣泛應(yīng)用于圖像分割的領(lǐng)域中。近年來(lái)，活動(dòng)輪廓模型(Active contour model， ACM)[2]在圖像分割領(lǐng)域中受到極大的關(guān)注。M-S(Mumford-Shah)模型[3]是一個(gè)基于能量泛函的圖像分割模型，由于模型中含有不同的維度，在數(shù)值求解過(guò)程中存在一定的難度，因此出現(xiàn)了很多近似M-S模型的簡(jiǎn)化模型，例如Chan-Vese模型[4]。Chan-Vese模型是多相圖像分割[5]的基礎(chǔ)，這類模型無(wú)需用梯度定義邊界，大大降低了M-S模型的復(fù)雜度，提高了分割的效率。文獻(xiàn)[4]中Chan和Vese等人提出了基于變分水平集方法的Chan-Vese模型，文獻(xiàn)[6]中Bresson等人提出了一種凸松弛[7]方法解決Chan-Vese模型中的兩階段和多階段分割問(wèn)題。分段常值的水平集方法求解需要凸松弛、閾值化以及水平集函數(shù)的等式約束，求解困難在于總變差TV項(xiàng)的處理。

TV模型[8]是變分模型求解的基礎(chǔ)，對(duì)于求解TV模型經(jīng)典的計(jì)算方法有交替方向乘子法(Alternation Direction Method of Multipliers， ADMM)[9-10]、分裂Bregman方法(Split-Bregman Method，SBM)[11]、對(duì)偶方法(Dual Method， DM)[12-13]。這些方法均可用于Chan-Vese模型的求解，文獻(xiàn)[14]和[15]中對(duì)于Chan-Vese模型的求解方法進(jìn)行了改進(jìn)，提出了多種基于水平集函數(shù)的變分方法， 由于水平集方法涉及的因素較多，存在很多計(jì)算效率低的問(wèn)題。標(biāo)記函數(shù)無(wú)需過(guò)多的約束，避免了方程病態(tài)的問(wèn)題。

隨著分割模型和求解算法的不斷提出與改進(jìn)， 提高模型的計(jì)算速度成為這一領(lǐng)域的熱點(diǎn)問(wèn)題。FISTA(Fast Iterative Shrinkage-Thresholding Algorithm)[16]算法適用于迭代過(guò)程的加速。CP(Chambolle-Pock)[17]算法運(yùn)用對(duì)偶方法快速地解決了凸優(yōu)化問(wèn)題。FISTA和CP兩種算法在迭代過(guò)程中都能加速使其結(jié)果達(dá)到時(shí)間復(fù)雜度為O(1/k2)的收斂速度。

本文的研究方法依賴于一個(gè)凸松弛法求解基于全變差的能量最小化的問(wèn)題，其基本思想是基于離散的二值標(biāo)記函數(shù)，將兩相Chan-Vese分割模型轉(zhuǎn)化為凸優(yōu)化模型，引用投影方法進(jìn)行約束，結(jié)合FISTA和CP算法，設(shè)計(jì)了相應(yīng)的快速計(jì)算方法FADMM(Fast Alternation Direction Method of Multipliers)和ACPDM(Acceleration Chambolle-Pock of Dual Method)，通過(guò)數(shù)值實(shí)驗(yàn)與傳統(tǒng)的計(jì)算方法進(jìn)行收斂性分析，驗(yàn)證了改進(jìn)后的計(jì)算方法在保證分割效果的基礎(chǔ)上，顯著提高模型的收斂速度，同時(shí)減少算法迭代次數(shù)和時(shí)間。

2 快速算法的研究基礎(chǔ)

Chan-Vese模型[4]在M-S模型的基礎(chǔ)上，去除了面積項(xiàng)，保留了長(zhǎng)度項(xiàng)，長(zhǎng)度項(xiàng)表示閉合曲線的長(zhǎng)度。它的優(yōu)點(diǎn)是不依賴于圖像的梯度，可以靈活選擇初始曲線的輪廓，基于圖像的灰度信息自動(dòng)檢測(cè)分割目標(biāo)的輪廓。

2.1 基于二值標(biāo)記函數(shù)的Chan-Vese模型

對(duì)于一幅原始標(biāo)量圖像f(x)∈Ω?R2，兩相Chan-Vese模型的能量泛函表示為

(1)

(1)式將原圖像分成了兩個(gè)區(qū)域Ω1和Ω2，Ω=Ω1∪Ω2，Ω1∩Ω2=?。u=(u1，u2)分別表示圖像在每個(gè)區(qū)域的均值。

根據(jù)演化曲線Γ構(gòu)造水平集函數(shù)φ，結(jié)合變分水平集方法和Heaviside函數(shù)的余面積公式，式(1)中的長(zhǎng)度項(xiàng)的積分可表示為下式所示

(2)

其中，H(φ)為Heaviside函數(shù)，δ(φ)為Dirac函數(shù)，δ(φ)表示為H(φ)在分布意義上的導(dǎo)數(shù)。

基于變分水平集的Chan-Vese模型可表示為

(3)

根據(jù)H(φ)的二值性，H(φ)∈{0，1}，用H(φ)將圖像劃分為兩類區(qū)域，一類標(biāo)記0，另一類標(biāo)記1，采用離散的二值標(biāo)記函數(shù)取代水平集函數(shù)，φ(x)∈{0，1}，其變分模型可轉(zhuǎn)化為下式

(4)

2.2 快速迭代收縮閾值算法

快速迭代收縮閾值算法(Fast Iterative Shrinkage-Thresholding Algorithm，F(xiàn)ISTA)[16]是Beck和Teboulle提出的一種利用梯度投影快速地求解最優(yōu)化的方法，解決凸函數(shù)問(wèn)題。ISTA(Iterative Shrinkage-Thresholding Algorithm)算法的思想是基于梯度下降法[18]，但由于梯度下降法求解的是局部最優(yōu)，受初值影響較大，所以在ISTA算法的基礎(chǔ)上，采用文獻(xiàn)[19]的Nesterov加速技術(shù)，達(dá)到計(jì)算量減少和迭代時(shí)間加速的目的。FISTA在沒(méi)有增加計(jì)算量的情況下，提高了收斂速度，達(dá)到了Ο(1/k2)的收斂結(jié)果。

2.3 快速迭代收縮閾值算法

CP(Chambolle-Pock)[17]算法是一階原對(duì)偶算法，適用于多種約束和非約束的優(yōu)化模型，算法不要求模型的光滑程度。在原始目標(biāo)或?qū)ε寄繕?biāo)為一致凸的情況下，可以實(shí)現(xiàn)Ο(1/k2)的收斂。文獻(xiàn)[20]中基于CP算法提出了一種計(jì)算凸正則項(xiàng)變分模型的算法框架，此算法對(duì)模型的數(shù)據(jù)項(xiàng)沒(méi)有要求。利用梯度下降法可將凸正則項(xiàng)的變分問(wèn)題的最小化問(wèn)題簡(jiǎn)單化。

3 基于標(biāo)記函數(shù)的改進(jìn)算法

3.1 Chan-Vese模型的FADMM方法

(5)

在交替迭代優(yōu)化過(guò)程中，可以得到參數(shù)u1，u2的以下估計(jì)公式

(6)

(7)

(8)

由變分方法可得到關(guān)于u的以下Euler-Lagrange方程以及涉及方程的邊界條件

(9)

此算法選擇了簡(jiǎn)單的有限差分，進(jìn)而提高計(jì)算效率。結(jié)合Gauss-Seidel迭代以及(9)式中的Euler-Lagrange方程可得到φk+1的演化方程

(10)

通過(guò)FISTA算法快速優(yōu)化求解過(guò)程，引入加速變量t，以下是有關(guān)t的迭代公式

(11)

將(11)式對(duì)φ和λ的求解進(jìn)行加速迭代處理

(12)

最后，對(duì)結(jié)果φ閾值化為最優(yōu)解

(13)

3.2 Chan-Vese模型的ACPDM方法

(14)

參數(shù)u1，u2的估計(jì)公式如(6)式所示。當(dāng)u1，u2估計(jì)后，(14)式可轉(zhuǎn)化為以下優(yōu)化形式

(15)

(16)

(17)

(18)

有關(guān)φ的求解結(jié)果為以下梯度降的方程

(19)

根據(jù)CP算法和以下加速因子進(jìn)行更快速的迭代求解

(20)

σk+1=σk/?k

(21)

在求解φ的過(guò)程中，有關(guān)τ的加速公式為

τk+1=?kτk

(22)

結(jié)合式(20)，按照下式更新φ

φk+1=φk+?k(φk+1-φk)

(23)

通過(guò)對(duì)上述式子進(jìn)行一系列交替優(yōu)化，可求得φ的解。最后將φ進(jìn)行如式(13)的閾值化處理。

4 數(shù)值實(shí)驗(yàn)

本實(shí)驗(yàn)將針對(duì)Chan-Vese模型的求解方法，對(duì)本文所提出的FADMM和ACPDM方法進(jìn)行數(shù)值驗(yàn)證，并與ADMM和DM方法進(jìn)行比較。實(shí)驗(yàn)環(huán)境：CPU為Intel(R) Core(TM)i7-8550U，內(nèi)存8G，操作系統(tǒng)為Windows 10，軟件平臺(tái)為Matlab2016b。

圖1選取了5幅不同的圖像分別使用ADMM和改進(jìn)的方法進(jìn)行分割的結(jié)果對(duì)比。第一排是一幅合成的幾何圖形圖像，第二排是由多個(gè)硬幣經(jīng)過(guò)處理的圖像，第三排是BSDS300數(shù)據(jù)集中一幅經(jīng)過(guò)處理的飛機(jī)圖像，第四排是一幅復(fù)雜的馬的圖像，第五排是BSDS300數(shù)據(jù)集中一幅經(jīng)過(guò)處理的鳥(niǎo)圖像。第一列是原始圖像，第二列是對(duì)5幅圖像的相同的初始化。分別為不同圖像使用ADMM和FADMM分割的結(jié)果。從(c)和(d)的分割效果圖中，視覺(jué)評(píng)價(jià)兩種分割效果一致，第三排和第五排(d)圖分割效果優(yōu)于(c)方法分割的結(jié)果，可見(jiàn)FADMM的方法在保持幾何形狀方面輪廓線與目標(biāo)的邊界緊貼性較好。表1是實(shí)驗(yàn)過(guò)程中所涉及的參數(shù)，F(xiàn)ADMM涉及的參數(shù)針對(duì)不同的圖像變化較小，可以得出改進(jìn)后的方法穩(wěn)定性高，模型的魯棒性強(qiáng)。表2是以上圖像分別利用ADMM和FADMM所得到的迭代次數(shù)和CPU運(yùn)行總時(shí)間的對(duì)比，迭代次數(shù)和CPU占用內(nèi)存的時(shí)間提升了約60%-90%，可見(jiàn)FADMM在這兩種評(píng)價(jià)標(biāo)準(zhǔn)中，明顯比ADMM的效率高。

圖1 不同圖像不同方法的分割結(jié)果

表1 實(shí)驗(yàn)中涉及的參數(shù)

表2 迭代次數(shù)和計(jì)算時(shí)間對(duì)比

圖2是5幅不同的圖像使用對(duì)偶方法和加速后的對(duì)偶方法分割結(jié)果的比較。第一排是一幅大腦局部腦干的圖像，第二排是一幅楓葉圖像，第三排是一幅手掌的圖像，第四幅和第五幅是兩幅不同的大腦圖像。實(shí)驗(yàn)中所涉及的輔助參數(shù)設(shè)置為σ=0.01，τ=0.01，η=0.7。

圖2 不同圖像不同方法的分割結(jié)果

在(c)(d)的結(jié)果中，從整體視覺(jué)效果來(lái)看，前三幅圖像DM和ACPDM分割結(jié)果相似，且都能達(dá)到很好的分割效果，從圖像的部分細(xì)節(jié)來(lái)看，比較兩種方法在兩幅不同的大腦圖像中，第四排大腦1圖的左上部分以及下面的部分，ACPDM輪廓線緊貼分割的目標(biāo)邊緣。第五排的大腦2圖DM方法出現(xiàn)了欠分割的現(xiàn)象。表3是兩種方法實(shí)驗(yàn)涉及的參數(shù)，ACPDM方法的相同參數(shù)適用于多組圖像，穩(wěn)定性強(qiáng)。計(jì)算結(jié)果如表4所示，不論是迭代次數(shù)還是CPU的計(jì)算時(shí)間，ACPDM都比DM的計(jì)算效率高，說(shuō)明根據(jù)CP算法和加速因子加速后的對(duì)偶方法明顯具有優(yōu)越性。

表3 實(shí)驗(yàn)中涉及的參數(shù)

表4 迭代次數(shù)和計(jì)算時(shí)間對(duì)比

圖3是兩組對(duì)比實(shí)驗(yàn)中，楓葉圖像在不同的分割方法中的能量泛函的變化。由于收斂條件的設(shè)置，能量值呈下降趨勢(shì)且最終大于零。從圖3可以看出，F(xiàn)ADMM和ACPDM較傳統(tǒng)方法，其迭代曲線更快地趨于穩(wěn)定狀態(tài)。圖3(a)中FADMM的能量曲線下降較快，在第四步達(dá)到收斂。圖3(b)中ACPDM方法在前三步的迭代過(guò)程中的能量值比DM方法能量下降的快，同時(shí)快速的穩(wěn)定下來(lái)，達(dá)到收斂狀態(tài)，且從實(shí)驗(yàn)的視覺(jué)分析中，分割精度提高。從以上整理的信息中，可以明顯看出改進(jìn)方法計(jì)算效率的提升。

圖3 不同方法對(duì)楓葉圖像的分割能量

為了進(jìn)一步驗(yàn)證本文提出的兩種新方法改進(jìn)的效果，將兩種新方法進(jìn)行比較，分別得出每一種方法的特點(diǎn)及優(yōu)越性。圖4和圖5是馬和大腦圖像通過(guò)本文提出的兩種新的分割方法分割出的結(jié)果將部分區(qū)域放大后的效果。通過(guò)圖4的(a)和(b)可以看出FADMM和ACPDM的分割效果相似，都可以解決傳統(tǒng)方法無(wú)法清晰分割出馬眼睛的問(wèn)題。證明了兩種新方法不僅可以使效率提升，還能精確分割出局部的邊界。圖5的(a)和(b)可以準(zhǔn)確看出輪廓線貼合分割目標(biāo)邊緣的情況，整體區(qū)域分割明顯，但由于圖像局部信息強(qiáng)度不均勻的問(wèn)題，ACPDM方法在處理圖像內(nèi)部出現(xiàn)欠分割的現(xiàn)象，相比較這一方面FADMM在分割準(zhǔn)確性上更具有優(yōu)越性。表5是兩種新方法在分割同一幅圖像的迭代次數(shù)和CPU計(jì)算時(shí)間的對(duì)比，ACPDM耗時(shí)較少，在分割的速度上更具有優(yōu)越性?？傮w來(lái)說(shuō)，兩種新方法與傳統(tǒng)的分割方法相比，分割精確度和時(shí)間效率明顯提升。

圖4 馬圖像兩種新方法的分割結(jié)果

圖5 大腦圖像兩種新方法的分割結(jié)果

表5 迭代次數(shù)和計(jì)算時(shí)間對(duì)比

5 結(jié)束語(yǔ)

本文綜合離散的二值標(biāo)記函數(shù)，將Chan-Vese模型轉(zhuǎn)化為凸優(yōu)化模型，引用投影方法進(jìn)行約束，結(jié)合FISTA算法和CP算法，設(shè)計(jì)出了FADMM和ACPDM算法，并通過(guò)數(shù)值對(duì)比實(shí)驗(yàn)分別驗(yàn)證了兩種方法加速的效果。其結(jié)果是加快了分割的計(jì)算效率，減少了CPU的運(yùn)行時(shí)間，同時(shí)得到了更準(zhǔn)確的分割結(jié)果。針對(duì)實(shí)驗(yàn)中發(fā)現(xiàn)的FADMM方法和ACPDM方法分割同一幅圖像時(shí)，雖然迭代次數(shù)減少，但是ACPDM方法對(duì)于一些復(fù)雜圖像的邊緣位置欠分割的問(wèn)題需要進(jìn)一步的改進(jìn)。在本文的工作基礎(chǔ)上，此類模型的快速分割方法可推廣到多相圖像以及曲面圖像的分割問(wèn)題中，為快速算法運(yùn)用到多種分割模型中，對(duì)于不同特征的圖像進(jìn)行分割，提高分割的準(zhǔn)確性和效率奠定了良好的基礎(chǔ)。