基于徑向基點插值的Chan-Vese模型圖像分割算法

李淑玲

LI Shuling

重慶師范大學 數學科學學院，重慶 401331

School of Mathematical Sciences,Chongqing Normal University,Chongqing 401331,China

1 引言

圖像分割是圖像處理的基礎，水平集方法作為一種有效的分割方法被廣泛地應用于圖像分割領域[1]。基于水平集方法，Chan和Vese提出了Chan-Vese模型，簡稱為CV模型[2]，這是近年來被大量研究的一種典型的區域型幾何活動輪廓模型，并且成功應用于眾多領域的圖像分割問題。

CV模型中涉及依賴于時間的非線性偏微分方程，通常用迎風有限差分法等計算方法數值求解。這些算法雖然得到了廣泛應用，但是演化速度常常較慢，計算效率低下，主要原因是：（1）算法計算量大，耗時較多；（2）演化結果嚴重依賴于水平集初始輪廓的形狀、大小和位置，不同的初始輪廓可能導致不同甚至錯誤的分割結果；（3）為了保證演化過程的穩定性，需要定期使用耗時的算法來重新初始化水平集函數；（4）缺乏明確的演化終止條件，設置固定演化次數的做法不夠高效。因此，如何高效地數值求解CV模型在水平集圖像分割領域里十分重要。為此，很多學者對CV模型進行了改進和完善，比如文獻[3-4]提出的改進CV模型解決了演化結果嚴重依賴于初始輪廓的缺陷，文獻[5-7]提出的改進CV模型避免了重新初始化過程，文獻[8-10]分別利用多重網格法、共軛梯度法和兩點步長梯度法提高了CV模型的演化速率，但是這些文獻中的CV模型仍然使用有限差分法離散求解，導致計算量偏大。

徑向基函數被廣泛應用于數值求解微分方程初邊值問題[11]，具有各向同性和形式簡單等特征，分為緊支徑向基函數和全局徑向基函數兩種。由于徑向基函數插值的光滑性較高，用徑向基函數求解CV模型時不需要重新初始化水平集函數，并且分割結果幾乎不受水平集初始輪廓的影響，因此計算速度明顯快于基于有限差分格式的算法[12-14]。文獻[12]用緊支徑向基函數求解了CV模型。緊支徑向基函數形成的插值矩陣稀疏，相應方程組的求解時間較少，但是插值精度較低，所以文獻[12]中的方法演化時間仍然較長。文獻[13-14]用全局徑向基函數求解了CV模型。全局徑向基函數插值精度較高，但形成的插值矩陣稠密，且容易病態甚至奇異，導致相應方程組的求解時間較多，因此相比文獻[12]中的緊支徑向基函數方法，文獻[13-14]中的全局徑向基函數方法的演化時間只降低了20%左右。

徑向基點插值法[15]是一種融入了緊支域概念的全局徑向基函數方法。為了克服文獻[13-14]中插值矩陣稠密且病態的不足，同時為了進一步提高文獻[12-14]中算法的演化速度，本文將借助徑向基點插值法建立求解CV模型的高效數值算法。該算法保留了文獻[12]中緊支徑向基函數方法和文獻[13-14]中全局徑向基函數方法的優點，既具有明確的演化終止條件，又具有較高的插值精度和演化速度，因此對水平集初始輪廓不敏感，無需重新初始化水平集函數。另外，由于徑向基點插值法是一種無網格方法，所以本文算法只需要節點，不需要網格單元。實驗表明，本文算法大幅度降低了文獻[12-14]中算法的演化分割時間。

2 圖像分割Chan-Vese（CV）模型

圖像分割的CV模型可表示為[1-2，5-6]：

其中x是圖像區域Ω中的空間變量，t是時間變量，φ(x,t)是水平集函數，φ0(x)表示水平集初始輪廓，V(x,φ(x,t))是如下速度函數：

式（3）中，γ≥0、λ1＞0和 λ2＞0都是權重系數，I()x表示圖像灰度。

其中ε是參數。

因為徑向基點插值法生成的近似函數是全局光滑的，所以令[12-14]γ=0，λ1=λ2=1，從而

3 徑向基點插值法

文獻[12]和文獻[13-14]分別用緊支徑向基函數和全局徑向基函數逼近水平集函數，但這兩種徑向基函數固有的缺點致使分割演化速度較慢，為此本文采用徑向基點插值法逼近水平集函數。

將Ω用N個節點xj(j=1,2,…,N)離散。對任意x∈Ω，點x的影響域定義為：

其中h是影響域?(x)的半徑。用表示?()x內的節點的編號。

函數φ(x,t)在?(x)上的徑向基點插值為[15]：

其中ai(t)是僅依賴于時間t的未知量，ri(x)是徑向基函數，rT(x)=[r1(x),r2(x),…,rn(x)]，a(t)=[a1(t),a2(t),…,an(t)]T。令式（5）在?(x)內的所有節點xsj處滿足，可得：

即

其中。由于R對稱，所以當徑向基函數嚴格正定時，R可逆，此時方程組（6）有唯一解。本文選取，其中β是正常數。

由式（6）解出未知向量a(t) ，再代入式（5）可得：

其中

4 圖像分割模型的數值解法

在傳統水平集方法中，常常利用有限差分法和重新初始化算法求解式（1）和式（2）組成的偏微分方程初值問題，具有較高復雜度和較大計算量。文獻[12-14]中的徑向基函數圖像分割算法雖然克服了傳統水平集方法中的一些缺點，但算法計算量還可進一步降低。本文通過用徑向基點插值法逼近水平集函數，將式（1）和式（2）轉化為常微分方程組初值問題，然后設計具有終止條件的Euler法求解。

把式（7）代入式（1）可得：

令上式在所有N個節點xj成立，可得：

類似于文獻[13-14]中的算法，為了克服水平集函數的駐點延緩演化速度的不足，可將式（10）中的替換為其規范化形式則式（10）變成：

因為形函數 Φi(x)具有Delta性質[15]，即 Φi(xj)=，所以由式（11）可得：

即

其中φ(t)是由式（9）給出的未知向量。

用向前Euler法離散式（12）可得：

其中tk=tk-1+τ，t0=0，τ＞0是時間步長。根據式（2），計算式（14）的初始條件為：

圖像分割的主要任務是找出目標圖像的輪廓曲線。由于φ(x,t)與任一非零實數的乘積不改變φ(x,t)=0的x值（即輪廓曲線的位置），因此為了給出明確的演化終止條件，可在每次計算式（14）之后將φ(tk)規范化，即令，此時可設置演化終止條件為[12-14]：

迭代計算式（14）終止之后得到φ(tk) ，此即為式（9）中向量φ(t)的近似值，然后可由式（7）計算區域Ω內任一點x處的水平集函數φ(x,t)，最后由φ(x ,t)=0確定目標圖像的輪廓曲線。

因此，本文圖像分割算法的主要步驟如下：

（1）輸入需要分割的圖像，選取參數ε和β、時間步長τ，令t0=0，k=1。

（2）將圖像區域用節點 x1，x2，…，xN離散，由式（8）計算Φi(x) ，i=1,2,…,N 。

（3）初始化水平集函數得φ0(x)i，i=1,2,…,N ，再由式（15）得

（4）令tk=tk-1+τ，由式（4）計算i=1,2,…,N ，再由式（13）得

（5）由式（14）計算φ(tk)，令

（6）檢驗式（16），如果不成立則令k=k+1并返回步驟（4），否則停止迭代并轉向步驟（7）。

（7）由式（7）計算圖像區域內的水平集函數，確定目標圖像的輪廓曲線，輸出分割結果。

因為用徑向基點插值法生成的近似函數是全局光滑的[15]，所以類似于文獻[12-14]中的算法，本文算法能避免重新初始化過程和克服輪廓初始化問題。其次，由于建立了明確的演化終止條件，本文算法不需要事先設置演化次數。再次，由于使用徑向基點插值法，本文算法比文獻[12-14]中的算法演化速度更快。

5 實驗結果

使用本文算法、文獻[2]的有限差分算法、文獻[12]的緊支徑向基函數算法以及文獻[13-14]的全局徑向基函數算法分割一些圖像，比較計算時間和分割精確性。實驗參數選取如下：對本文和文獻[12-14]的算法，ε=1，β=8，τ=1；對文獻[2]的算法，ν=0，μ=0.5×2552，λ1=λ2=1，τ=0.1，每迭代10次對水平集函數重新初始化1次，迭代最大次數為5 000。實驗軟件為Matlab7.0.1，硬件環境為Intel?Core? i7-6500U CPU@2.50 GHz，8.00 GB內存。

表1給出了在不同初始輪廓曲線時分割表1（a3）中圖像的結果。對于本文和文獻[12-14]的算法，不管初始輪廓曲線在何處（表1（a1，a2）），甚至缺乏初始輪廓（表1（a3））時，這四種算法都能正確分割。對于文獻[2]的算法，當目標被初始輪廓包圍時才能分割正確（表1（f1）），否則分割錯誤（表1（f2，f3））。

表2給出了表1中分割需要的計算時間。文獻[12-14]中算法所需時間約為本文算法的25～35倍，而文獻[2]中算法所需時間更多，所以本文算法所需時間非常小，具有很高的演化速度。

表1 五種算法在不同初始輪廓時的分割結果

表2 表1中分割的計算時間 s

表3給出了表1中分割的Dice相似性系數(DSC)和錯誤分割率(RSE)[13]。DSC越接近1，同時RSE越接近0，分割精度越高。表3中的數據表明本文算法和文獻[12-14]中算法都具有較高的分割精度，而文獻[2]中算法的精度要差一些。

表3 表1中分割的DSC和RSE

表4給出了在沒有初始輪廓時本文算法和文獻[2，12-14]中算法分割表4（a1）～（a5）中圖像的結果。本文和文獻[12-14]的算法都能正確分割，但文獻[2]的算法無法正確分割。表5給出了表4中分割需要的計算時間，本文算法所需時間比文獻[12-14]中的算法少很多。

表4 五種算法對不同圖像在沒有初始輪廓時的分割結果

表5 表4中分割的計算時間s

表6第一行給出了5幅真實圖像，表6第二行和第三行表明本文算法和文獻[14]的算法在沒有初始輪廓時都能正確地分割這些圖像。在實驗中發現文獻[12]和文獻[13]的算法也能正確分割這5幅真實圖像，但本文算法所需時間比文獻[12-14]中的算法少很多。

6 結束語

針對水平集CV模型演化耗時的缺點，本文提出了一種高效數值求解CV模型的圖像分割算法。該算法通過利用徑向基點插值法逼近水平集函數，將CV模型轉化為常微分方程組初值問題，然后用具有迭代終止條件的向前Euler方法求解。相比基于有限差分格式的算法，本文算法無需復雜費時的重新初始化過程，對水平集初始輪廓不敏感，也不需要事先設置演化次數，從而降低了算法的復雜度和計算量，實驗表明本文算法分割效果更好，并且演化速度快很多。相比基于緊支徑向基函數和全局徑向基函數的算法，實驗表明分割效果幾乎相同，但本文算法計算時間明顯少很多，演化速度快了25～35倍。

表6 本文算法和文獻[14]的算法對5幅真實圖像在沒有初始輪廓時的分割結果

參考文獻：

[1]Tsai R，Osher S.Level set methods and their applications in image science[J].Comm Math Sci，2003，1：623-656.

[2]Chan T，Vese L.Active contours without edges[J].IEEE Trans on Image Process，2001，10：266-277.

[3]顧鵬程，黃福珍.基于改進Chan-Vese模型的電力設備紅外圖像分割[J].計算機工程與應用，2017，53（10）：193-196.

[4]Abdelsamea M M，Gnecco G，Gaber M M.A SOM-based Chan-Vese model for unsupervised image segmentation[J].Soft Comput，2017，21：2047-2067.

[5]Li C，Xu C，Gui C，et al.Distance regularized level set evolution and its application to image segmentation[J].IEEE Trans on Image Process，2010，19：3243-3254.

[6]Zhang K H，Zhang L，Song H H，et al.Re-initialization free level set evolution via reaction diffusion[J].IEEE Trans on Image Process，2013，22：258-271.

[7]張雯，王小鵬，李志強，等.分水嶺優化的C-V模型腦腫瘤圖像分割[J].計算機工程與應用，2017，53（5）：176-180.

[8]Badshah N，Chen K.Multigrid method for the Chan-Vese model in variational segmentation[J].Commun Comput Phys，2008，4：294-316.

[9]屈健健，應時輝，彭亞新.Chan-Vese模型的共輒梯度算法[J].應用數學和計算數學學報，2013，27（4）：469-477.

[10]彭亞新，陳颯颯，沈超敏，等.求解圖像分割CV模型的BB算法[J].運籌學學報，2014，18（3）：79-87.

[11]陳文，傅卓佳，魏星.科學與工程計算中的徑向基函數方法[M].北京：科學出版社，2014.

[12]Gelas A，Bernard O，Friboulet D，et al.Compactly supported radial basis functions based collocation method for level-set evolution[J].IEEE Trans on Image Process，2007，16：1873-1887.

[13]李淑玲，李小林.全局正定徑向基函數在圖像分割中的應用[J].計算機工程與應用，2014，50（6）：139-143.

[14]Li S L，Li X L.Radial basis functions and level set method for image segmentation using partial differential equation[J].Appl Math Comput，2016，286：29-40.

[15]Liu G R.Mesh-free methods：Moving beyond the finite element method[M].Boca Raton：CRC Press，2009.