凸松弛Chan-Vese模型的快速分割方法

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

(青島大學計算機科學技術學院，山東 青島 266071)

1 引言

變分法[1]是研究泛函的極大值或極小值問題的一種方法，在圖像的變分模型下，可以把圖像處理的問題轉化成求解變分的問題，對圖像的處理效率高且效果好。圖像分割是一項重要的圖像分析和處理技術，在醫學圖像分析、智能交通管理、遙感圖像處理等領域得到了廣泛的應用。圖像分割的重點在于分割目標值的速度和精度，很多方法存在著計算效率低、分割精度不高、魯棒性差的問題。結合變分偏微分方程方法利用數值計算方法高效的優勢，在解決圖像問題時可以快速地處理圖像的幾何特征，這類數學方法也易于擴展到多個模型中。

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

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

隨著分割模型和求解算法的不斷提出與改進， 提高模型的計算速度成為這一領域的熱點問題。FISTA(Fast Iterative Shrinkage-Thresholding Algorithm)[16]算法適用于迭代過程的加速。CP(Chambolle-Pock)[17]算法運用對偶方法快速地解決了凸優化問題。FISTA和CP兩種算法在迭代過程中都能加速使其結果達到時間復雜度為O(1/k2)的收斂速度。

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

2 快速算法的研究基礎

Chan-Vese模型[4]在M-S模型的基礎上，去除了面積項，保留了長度項，長度項表示閉合曲線的長度。它的優點是不依賴于圖像的梯度，可以靈活選擇初始曲線的輪廓，基于圖像的灰度信息自動檢測分割目標的輪廓。

2.1 基于二值標記函數的Chan-Vese模型

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

(1)

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

根據演化曲線Γ構造水平集函數φ，結合變分水平集方法和Heaviside函數的余面積公式，式(1)中的長度項的積分可表示為下式所示

(2)

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

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

(3)

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

(4)

2.2 快速迭代收縮閾值算法

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

2.3 快速迭代收縮閾值算法

CP(Chambolle-Pock)[17]算法是一階原對偶算法，適用于多種約束和非約束的優化模型，算法不要求模型的光滑程度。在原始目標或對偶目標為一致凸的情況下，可以實現Ο(1/k2)的收斂。文獻[20]中基于CP算法提出了一種計算凸正則項變分模型的算法框架，此算法對模型的數據項沒有要求。利用梯度下降法可將凸正則項的變分問題的最小化問題簡單化。

3 基于標記函數的改進算法

3.1 Chan-Vese模型的FADMM方法

(5)

在交替迭代優化過程中，可以得到參數u1，u2的以下估計公式

(6)

(7)

(8)

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

(9)

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

(10)

通過FISTA算法快速優化求解過程，引入加速變量t，以下是有關t的迭代公式

(11)

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

(12)

最后，對結果φ閾值化為最優解

(13)

3.2 Chan-Vese模型的ACPDM方法

(14)

參數u1，u2的估計公式如(6)式所示。當u1，u2估計后，(14)式可轉化為以下優化形式

(15)

(16)

(17)

(18)

有關φ的求解結果為以下梯度降的方程

(19)

根據CP算法和以下加速因子進行更快速的迭代求解

(20)

σk+1=σk/?k

(21)

在求解φ的過程中，有關τ的加速公式為

τk+1=?kτk

(22)

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

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

(23)

通過對上述式子進行一系列交替優化，可求得φ的解。最后將φ進行如式(13)的閾值化處理。

4 數值實驗

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

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

圖1 不同圖像不同方法的分割結果

表1 實驗中涉及的參數

表2 迭代次數和計算時間對比

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

圖2 不同圖像不同方法的分割結果

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

表3 實驗中涉及的參數

表4 迭代次數和計算時間對比

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

圖3 不同方法對楓葉圖像的分割能量

為了進一步驗證本文提出的兩種新方法改進的效果，將兩種新方法進行比較，分別得出每一種方法的特點及優越性。圖4和圖5是馬和大腦圖像通過本文提出的兩種新的分割方法分割出的結果將部分區域放大后的效果。通過圖4的(a)和(b)可以看出FADMM和ACPDM的分割效果相似，都可以解決傳統方法無法清晰分割出馬眼睛的問題。證明了兩種新方法不僅可以使效率提升，還能精確分割出局部的邊界。圖5的(a)和(b)可以準確看出輪廓線貼合分割目標邊緣的情況，整體區域分割明顯，但由于圖像局部信息強度不均勻的問題，ACPDM方法在處理圖像內部出現欠分割的現象，相比較這一方面FADMM在分割準確性上更具有優越性。表5是兩種新方法在分割同一幅圖像的迭代次數和CPU計算時間的對比，ACPDM耗時較少，在分割的速度上更具有優越性。總體來說，兩種新方法與傳統的分割方法相比，分割精確度和時間效率明顯提升。

圖4 馬圖像兩種新方法的分割結果

圖5 大腦圖像兩種新方法的分割結果

表5 迭代次數和計算時間對比

5 結束語

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