李淑玲

LI Shuling

重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，重慶 401331

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

1 引言

圖像分割是圖像處理的基礎(chǔ)，水平集方法作為一種有效的分割方法被廣泛地應(yīng)用于圖像分割領(lǐng)域[1]?；谒郊椒ǎ珻han和Vese提出了Chan-Vese模型，簡(jiǎn)稱為CV模型[2]，這是近年來被大量研究的一種典型的區(qū)域型幾何活動(dòng)輪廓模型，并且成功應(yīng)用于眾多領(lǐng)域的圖像分割問題。

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

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

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

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

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

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

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

其中ε是參數(shù)。

因?yàn)閺较蚧c(diǎn)插值法生成的近似函數(shù)是全局光滑的，所以令[12-14]γ=0，λ1=λ2=1，從而

3 徑向基點(diǎn)插值法

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

將Ω用N個(gè)節(jié)點(diǎn)xj(j=1,2,…,N)離散。對(duì)任意x∈Ω，點(diǎn)x的影響域定義為：

其中h是影響域?(x)的半徑。用表示?()x內(nèi)的節(jié)點(diǎn)的編號(hào)。

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

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

即

其中。由于R對(duì)稱，所以當(dāng)徑向基函數(shù)嚴(yán)格正定時(shí)，R可逆，此時(shí)方程組（6）有唯一解。本文選取，其中β是正常數(shù)。

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

其中

4 圖像分割模型的數(shù)值解法

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

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

令上式在所有N個(gè)節(jié)點(diǎn)xj成立，可得：

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

因?yàn)樾魏瘮?shù) Φi(x)具有Delta性質(zhì)[15]，即 Φi(xj)=，所以由式（11）可得：

即

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

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

其中tk=tk-1+τ，t0=0，τ＞0是時(shí)間步長(zhǎng)。根據(jù)式（2），計(jì)算式（14）的初始條件為：

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

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

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

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

（2）將圖像區(qū)域用節(jié)點(diǎn) x1，x2，…，xN離散，由式（8）計(jì)算Φi(x) ，i=1,2,…,N 。

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

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

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

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

（7）由式（7）計(jì)算圖像區(qū)域內(nèi)的水平集函數(shù)，確定目標(biāo)圖像的輪廓曲線，輸出分割結(jié)果。

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

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

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

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

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

表1 五種算法在不同初始輪廓時(shí)的分割結(jié)果

表2 表1中分割的計(jì)算時(shí)間 s

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

表3 表1中分割的DSC和RSE

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

表4 五種算法對(duì)不同圖像在沒有初始輪廓時(shí)的分割結(jié)果

表5 表4中分割的計(jì)算時(shí)間s

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

6 結(jié)束語

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

表6 本文算法和文獻(xiàn)[14]的算法對(duì)5幅真實(shí)圖像在沒有初始輪廓時(shí)的分割結(jié)果

參考文獻(xiàn)：

[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]顧鵬程，黃福珍.基于改進(jìn)Chan-Vese模型的電力設(shè)備紅外圖像分割[J].計(jì)算機(jī)工程與應(yīng)用，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]張?chǎng)?，王小鵬，李志強(qiáng)，等.分水嶺優(yōu)化的C-V模型腦腫瘤圖像分割[J].計(jì)算機(jī)工程與應(yīng)用，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]屈健健，應(yīng)時(shí)輝，彭亞新.Chan-Vese模型的共輒梯度算法[J].應(yīng)用數(shù)學(xué)和計(jì)算數(shù)學(xué)學(xué)報(bào)，2013，27（4）：469-477.

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

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

[12]Gelas A，Bernard O，F(xiàn)riboulet 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]李淑玲，李小林.全局正定徑向基函數(shù)在圖像分割中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，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.