宋 琳, 高滿屯, 王三民, 王淑俠

（西北工業(yè)大學(xué)機(jī)電學(xué)院，陜西 西安 710072）

融合區(qū)域和測地線的活動輪廓模型與圖割相結(jié)合的自然圖像分割

宋 琳, 高滿屯, 王三民, 王淑俠

（西北工業(yè)大學(xué)機(jī)電學(xué)院，陜西 西安 710072）

針對活動輪廓模型利用水平集函數(shù)演化來分割圖像時，只能分割灰度均勻的圖像問題以及容易陷入能量泛函局部極小值的缺點，提出一種新的圖像分割模型。模型將區(qū)域中的局部和全局信息融合的活動輪廓模型與邊界模型相結(jié)合，然后利用圖切割進(jìn)行優(yōu)化。實驗表明，該方法對初始曲線不敏感，能分割灰度不均的自然圖像，避免陷入局部極小，并能有效提高圖像分割的速度和精度。

圖像分割；活動輪廓；水平集方法；圖割

圖像分割是常用的圖像預(yù)處理方法，其目的是將圖像簡化表示為具有類似屬性的、有意義的、以及和空間相關(guān)的區(qū)域，如對象或背景相一致部分[1]。通常將人們對圖像中感興趣的部分稱為目標(biāo)或前景，其他部分稱為背景[2]。圖像分割主要應(yīng)用于軍事、天文、醫(yī)學(xué)、交通等領(lǐng)域。在過去的幾十年中，國內(nèi)外對于圖像的分割方法進(jìn)行了廣泛研究，提出了許多種圖像分割方法。

由Malladi等[3]和Caselles等[4]各自提出的幾何活動輪廓模型，由于具有能夠自動處理邊界曲線拓?fù)浣Y(jié)構(gòu)的合并與斷裂、計算穩(wěn)定、計算結(jié)果精度高的特點，所以受到越來越多的學(xué)者關(guān)注。活動輪廓模型可分為基于邊界的模型和基于區(qū)域的模型。基于邊界的活動輪廓模型是依靠邊緣檢測，利用圖像的梯度信息構(gòu)造邊界函數(shù)，用邊界的局部信息來驅(qū)使曲線演化，因此存在對初始曲線位置敏感、易產(chǎn)生邊緣泄漏等問題。測地線的活動輪廓模型就是基于邊界的活動輪廓模型。

基于區(qū)域的活動輪廓模型相對于邊界模型具有許多優(yōu)點，其是直接利用活動輪廓內(nèi)部和外部的全部信息，對噪聲不敏感，降低了曲線演化對初始曲線的依賴性，而且對于弱邊界和無邊界的圖像能獲得較好地分割結(jié)果。Chan和Vese[5]提出的無邊緣活動輪廓（簡稱C-V模型）是一種基于區(qū)域的活動輪廓模型，是利用活動輪廓內(nèi)部區(qū)域和外部區(qū)域的全部信息，具有分割結(jié)果對初始輪廓位置和大小不敏感、計算簡單的優(yōu)點，但是該模型要求圖像的目標(biāo)和背景之間的平均灰度相差較大，并且各自的灰度值變化不大。在實際的自然圖像中目標(biāo)和背景的情況復(fù)雜，噪聲干擾大，往往存在灰度不均勻現(xiàn)象，針對這種情況Li等[6-7]提出局部二值擬合(local binary fitting, LBF)模型和可變區(qū)域擬合能量模型(region scalable fitting, RSF)、以及結(jié)合全局和局部信息的改進(jìn)活動輪廓模型[8-10]來分割灰度不均的圖像，對灰度不均勻圖像取得了較好地分割結(jié)果，但存在依賴于演化曲線的大小和初始位置、對噪聲敏感的缺點。

水平集將曲線演化問題轉(zhuǎn)化為偏微分方程數(shù)值求解問題，具有很強(qiáng)地處理拓?fù)浣Y(jié)構(gòu)變化的能力，但計算復(fù)雜度較高[11]。以上這些模型都是基于偏微分方程求解活動輪廓水平集模型的數(shù)值方法，其還存在以下2個缺點：①利用梯度下降的方法來解決連續(xù)問題的優(yōu)化，容易陷于能量泛函的局部最??；②圖像分割的效果依賴于迭代的次數(shù)，隨著迭代次數(shù)的增加，輪廓線越靠近邊界，耗時增加且計算量增大。

圖論是以圖為研究對象的數(shù)學(xué)的一個分支，基于圖論進(jìn)行圖像分割的方法是一種較新的圖像分割方法。其是將網(wǎng)絡(luò)圖與圖像相結(jié)合，基于能量最小化進(jìn)行目標(biāo)分割的交互式方法。圖割優(yōu)化[12]方法作為一種優(yōu)化工具，利用合適的能量函數(shù)框架，將區(qū)域?qū)傩院瓦吘壭畔⒂袡C(jī)地結(jié)合，具有全局最優(yōu)、分割結(jié)果的強(qiáng)魯棒性，執(zhí)行效率高等優(yōu)點，廣泛地應(yīng)用到了圖像分割領(lǐng)域中。El-Zehiry等[13-14]將圖割應(yīng)用到兩相Mumford-Shah模型中，結(jié)果表明用圖割求最小化能量函數(shù)值結(jié)果比梯度下降法要有效和穩(wěn)定。

本文提出新的輪廓模型，融合了區(qū)域和邊界活動輪廓模型的優(yōu)點，并將其與圖割優(yōu)化方法相結(jié)合，用圖割算法作為高效的能量函數(shù)最優(yōu)化算法來取代水平集演化方法，不需要設(shè)置許多參數(shù)就能對灰度不均勻的自然圖像進(jìn)行分割，避免陷入局部極小，降低了分割結(jié)果對初始化的依賴性，并且能夠有效地提高圖像分割的速度和精度。

1 相關(guān)背景

1.1 區(qū)域活動輪廓模型

C-V模型通過極小化的能量泛函來實現(xiàn)分割：

其中，u(x)是待分割的圖像；C是演化曲線，in(C)和out(C)分別表示曲線的內(nèi)部和外部；c1和c2分別為圖像u(x)在區(qū)域in(C)和out(C)的灰度平均值，μ≥0，λ1，λ2為正的常數(shù)，通常取λ1=λ2=1。這樣，最優(yōu)化圖像分割問題就轉(zhuǎn)化為求能量函數(shù)ECV(c1,c2,C)的最小值問題。利用水平集方法解決這個最小值問題，用水平集函數(shù)φ(x)來代替未知曲線C，得到如式(2)所示的用水平集函數(shù)表示式(1)的參數(shù)化能量泛函：

H(φ)是Heaviside函數(shù)。δ (φ)=H′(φ)，δ(φ)是Dirac函數(shù)。

固定c1和c2，通過梯度下降法，可導(dǎo)出控制水平集演化的偏微分方程：

在迭代過程中c1和c2的值可用水平集函數(shù)φ表示為式(5)和式(6)：

對于每個水平集函數(shù)φ，常數(shù)c1和c2分別是圖像在演化曲線內(nèi)外的平均灰度值，是一種全局信息，沒有包含圖像的局部信息，對于灰度不均勻的自然圖像進(jìn)行分割用c1和c2來近似演化曲線內(nèi)外的灰度值就會產(chǎn)生較大的誤差，從而不會得到很好地分割結(jié)果。在設(shè)置參數(shù)時，如果ε太大，δε(z)雖然能夠獲得全局最小的趨勢，但是最終輪廓線位置不太精確。如果ε太小，δε(z)的值就接近于0，其影響范圍就小，能量函數(shù)就容易陷入局部極小。如果初始曲線離目標(biāo)比較遠(yuǎn)，目標(biāo)就不容易被分割出來，為了獲得好的結(jié)果，初始曲線的位置就很重要。

因此，在使用C-V進(jìn)行分割圖像時，不能很好分割灰度不均的自然圖像，同時受初始曲線位置和噪聲的影響大，存在陷入局部極小的缺點，且計算量大，限制了模型的應(yīng)用能力。

1.2 圖割

圖割(graph cuts)是以圖論為理論基礎(chǔ)，根據(jù)能量最小化模型構(gòu)造能量函數(shù)，從而將視覺問題轉(zhuǎn)化為能量函數(shù)最小化問題；根據(jù)圖像構(gòu)造網(wǎng)絡(luò)，使能量與網(wǎng)絡(luò)的割相對應(yīng)，從而將能量最小化問題轉(zhuǎn)化為網(wǎng)絡(luò)最小割問題。

圖論中圖的一個割是將圖中的頂點利用最大流/最小割定理區(qū)分成不同的兩個類（子集）。由Ford和Fulkerson[15]在1962年證明的最大流/最小割定理是指：在任何網(wǎng)絡(luò)圖中，最大流的值等于最小切割的容量，通過計算最大流即可獲得最小割，從而獲得全局最優(yōu)的二元標(biāo)號。根據(jù)最大流/最小割定理，將網(wǎng)絡(luò)最小割問題轉(zhuǎn)化為最大流問題；通過求解最大流問題，求得圖的最小割，從而獲得視覺問題的解。圖像分割問題就可以看作是將圖像元素點劃分成不同類的問題。

將圖像映射為帶權(quán)的無向圖，用G=(V, L)表示，V為圖中節(jié)點的集合，L為圖中連接節(jié)點各邊的集合。通常，一般的節(jié)點對應(yīng)于像素點，v∈V，圖1中還包含兩個特殊節(jié)點，s稱為源點，t稱為匯點，則V={v1, v2,…, vn, s, t}。L={e}是各邊的集合，每條從源點出發(fā)的邊或匯集到匯點的邊都被稱為t-link。連接除源點和匯點以外的其他節(jié)點的邊被稱為n-link。如圖1(a)所示，一個簡單的3×3二維網(wǎng)絡(luò)，其節(jié)點 v對應(yīng)于圖像的像素，wij表示節(jié)點 vi和vj間的權(quán)，其大小反映節(jié)點之間的相似性。無向圖G中的一個割將節(jié)點集合V劃分成兩個相鄰的子集S和T，s∈S，t∈T如圖1(b)所示。

圖1 3×3二維圖切割

2 本文模型

2.1 改進(jìn)的活動輪廓模型

由于C-V模型在實際應(yīng)用中存在一個很大問題，就是無法分割灰度不均的圖像也就是異質(zhì)目標(biāo)，因此，在分割復(fù)雜的自然圖像時，處理過程易受噪聲影響，造成冗余輪廓，不能得到很好地分割結(jié)果。

在本文提出的融合區(qū)域和邊界的能量函數(shù)模型(region based Chan-vese, RBCV)中，根據(jù)LBF[6]模型和LRCV(local region-based Chan-vese)[10]模型，將C-V模型中用兩個單一的常數(shù)c1和c2來描述輪廓區(qū)域內(nèi)外的灰度均值，替換為用c1(x)和c2(x)兩個函數(shù)來描述輪廓內(nèi)外區(qū)域的灰度，這樣可將輪廓區(qū)域內(nèi)的局部與全局信息結(jié)合；為了使輪廓曲線具有較好地邊緣捕獲能力，將測地線主動輪廓長度加入到模型最后一項[16]。

其中，y為x的鄰域，對于一點x∈R2的灰度值可以用u(y)的加權(quán)均值來近似，因此，c1(x)和c2(x)值的大小與x鄰域內(nèi)所有點的灰度值u(y)有關(guān)。由于Kσ的特性，c1(x)和c2(x)受u(y)的影響與y和x之間的距離有關(guān)，當(dāng)y離x比較近時，影響較大；當(dāng)y離x比較遠(yuǎn)時，u(y)就接近于0，影響較小。在算法的迭代過程中采用高斯核函數(shù)(Kσ(x))：

為了抑制圖像噪聲的影響，在迭代過程中采用高斯濾波減少冗余輪廓。

2.2 圖割優(yōu)化

對于許多處理的圖像模型來講，能量函數(shù)都是非凸性，存在局部極小，如果在最小化過程中采用梯度下降法，就容易陷入局部極小值[17]。本文采用文獻(xiàn)[14]中提到的圖割方法求解能量函數(shù)最小值以獲得圖像分割結(jié)果。

對于每一個像素點p∈Ω，定義一個二值變量xp，則：

對于p鄰域內(nèi)任意一點r，c1和c2可寫成如下離散形式：

Boykov和Kolmogorov[18]提出圖割測度(cut metric)的概念，認(rèn)為網(wǎng)絡(luò)圖上的一個割是封閉曲線，曲線長度近似為一個割，可以用Cauchy Crofton公式[19]近似為：

其中，δ為網(wǎng)絡(luò)圖的網(wǎng)格單位長度，nk是曲線C與第K組邊線交點的總個數(shù)，ek是兩個節(jié)點的最短長度矢量，ωk是邊ek的權(quán)值，則：

本文在近似計算曲線的長度時，使用8鄰域系統(tǒng)N8，如圖2所示，Δ θk為ek相鄰兩邊的夾角。

圖 2 8鄰域系統(tǒng)N8

曲線C的長度∫s d離散化為：

最終能量函數(shù)的離散形式可以表達(dá)為：

為了構(gòu)造一個圖G=(V, L)，圖像中每一像素點被認(rèn)為是一個節(jié)點。對于每一個節(jié)點有兩個連接源點和匯點的t-links，即(s, p)、(p, t)，各自的權(quán)值定義為wsp和wpt，兩個相鄰節(jié)點的連接為n-link，權(quán)值為wpq，則：

2.3 算法實現(xiàn)

算法步驟如下：

(1) 確定初始曲線位置，在圖像任意位置繪制初始曲線C，將圖像劃分成曲線內(nèi)部區(qū)域Ω1和外部區(qū)域Ω2；初始化xp，在曲線外部標(biāo)記為0，在曲線內(nèi)部標(biāo)記為1；

(2) 依據(jù)式(12)、(13)計算c1(p)和c2(p)；

(3) 構(gòu)造圖G，對于每一個像素點p∈Ω，添加Svp的權(quán)值為wsp，邊vpT的權(quán)值wpt；

對于p的8領(lǐng)域系統(tǒng)中的每一點q用式(21)計算wpq；并添加邊vpvq的權(quán)值為wpq；

(4) 用最大流最小割算法計算圖G的最小割并得到圖像的二值標(biāo)記結(jié)果{xp|xp∈{0,1}, p=1,…, N}；

(5) 重復(fù)步驟(2)～(4)，直到能量函數(shù)值達(dá)到最小。

3 實驗結(jié)果與分析

為了驗證本文模型的可行性和有效性，對大量自然圖像進(jìn)行分割實驗。實驗平臺為Intel Pentium CPU G 640 2.80 GHz、2.80 GHz，內(nèi)存為2 GB的PC機(jī)，編程環(huán)境為Malab R2013和Microsoft Visual Studio 2010，并且使用了OpenCV圖像處理函數(shù)庫。模型參數(shù)設(shè)置為：λ1=λ2=1，μ=1 500，β=0.03。

3.1 分割結(jié)果對初始曲線位置和大小不敏感

圖3中，第一行有3種不同初始曲線位置，第二行是對應(yīng)的分割結(jié)果。圖4中，第一行有3種不同初始曲線大小，第二行是對應(yīng)的分割結(jié)果。根據(jù)圖3和圖4中所示結(jié)果，當(dāng)改變初始曲線位置和大小，對分割結(jié)果的影響不大。

圖 3 各種初始位置及分割結(jié)果

圖 4 各種初始曲線大小分割結(jié)果

根據(jù)圖5(a)、(b)所示的能量函數(shù)值曲線可以看出，3種不同位置和大小的初始曲線，用本文所提出的方法分割時能量函數(shù)值均在前兩次迭代后明顯降低，五次迭代后的變化較小，十次迭代以后基本就能達(dá)到能量函數(shù)值最小。

圖 5 不同初始曲線位置及大小的能量函數(shù)值

從以上分析可知，初始曲線的位置以及大小對分割結(jié)果影響不大，所以這種分割方法對初始曲線的位置以及大小不敏感。

3.2 縮短運行時間

表1分別用RBCV模型和C-V模型分割圖6的自然圖像所需時間。可以看出，用本文模型進(jìn)行圖像分割時，雖然每次迭代的時間比C-V模型的時間要長，但分割所需時間和迭代次數(shù)要少。

表1 RBCV模型與C-V模型分割圖像迭代次數(shù)和CPU時間比較

3.3 分割結(jié)果的有效性

圖6(a)用RBCV模型分割圖像，依次為初始曲線位置、1、2、7、10、12次迭代的分割圖像。圖6(b)用C-V模型分割圖像，依次為初始曲線位置、10、20、500、2 000、5 000次迭代的分割圖像。從分割結(jié)果看C-V模型將馬身上的反光部分都標(biāo)記為背景，將草中的陰影部分標(biāo)記為前景，冗余輪廓較多，從而沒有得到目標(biāo)的正確輪廓。RBCV模型分割結(jié)果冗余輪廓較少（僅在馬的頸部和鼻子上標(biāo)記出冗余輪廓，且標(biāo)記的面積均小于C-V模型分割結(jié)果的標(biāo)記面積），因此，RBCV模型分割的目標(biāo)輪廓比較清晰、準(zhǔn)確。

對Berkeley數(shù)據(jù)庫提供的多幅自然圖像進(jìn)行分割，將結(jié)果與C-V模型和RBCV模型得到的結(jié)果進(jìn)行比較與分析，如圖7所示。

圖 6 RBCV模型和C-V模型的分割結(jié)果

圖 7 自然圖像的分割結(jié)果比較

從分割結(jié)果可以看出，C-V模型對于灰度不均的自然圖像進(jìn)行分割，受噪聲影響比較大，容易陷入局部極小，造成冗余輪廓，難以得到準(zhǔn)確結(jié)果；RBCV模型分割自然圖像，盡管分割結(jié)果中還存在局部冗余輪廓，但分割結(jié)果受噪聲影響比較小，避免陷入局部極小值，能夠提供較光滑準(zhǔn)確的目標(biāo)邊界。

4 結(jié) 束 語

本文提出了一種將改進(jìn)的活動輪廓模型與圖割相結(jié)合的圖像分割方法，不但能有效分割灰度不均的自然圖像，而且利用圖割算法可大幅度提高圖像分割速度，減少分割時間，同時避免陷入局部極小。本文模型的缺點是只能分割單一目標(biāo)，且目標(biāo)輪廓中還存在局部冗余輪廓，而自然圖像中往往包含多個目標(biāo)，下一步的研究方向?qū)⒈疚哪Ｐ拖蚨嗄繕?biāo)圖像的分割擴(kuò)展，同時進(jìn)一步減少目標(biāo)的冗余輪廓，提高分割的正確性和精度。

[1] Mignotte M. MDS-based segmentation model for the fusion of contour and texture cues in natural images [J]. Computer Vision and Image Understanding, 2012, 116(9): 981-990.

[2] 孫海鵬, 余偉巍, 席 平. 基于Level Set 的交互式快速分割算法[J]. 工程圖學(xué)學(xué)報, 2011, 32(3): 45-51.

[3] Malladi R, Sethian J A, Venmuri B C. Shape modeling with front propagation: a level set approach [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17(2): 158-174.

[4] Caselles V, Kimmel R, Sapiro G. Geodesic active contours [J]. International Journal of Computer Vision, 1997, 22(1): 61-79.

[5] Chan T F, Vese L A. Active contours without edges [J]. IEEE Transactions on Image Processing, 2001, 10(2): 266-277.

[6] Li Chunming, Kao C Y, Gore J C, et al. Implicit active contours driven by local binary fitting energy [C]//IEEE Conference on Computer Vision and Pattern Recognition. Minneapolis, USA, 2007: 1-7.

[7] Li Chunming, Kao Chiuyen, Gore J, et al. Minimization of region-scalable fitting energy for image segmentation [J]. IEEE Transactions on Image Processing, 2008, 17(10): 1940-1949.

[8] Zhang Kaihua, Zhang Lei, Song Huihui, et al. Active contours with selective local or global segmentation: a new formulation and level set method [J]. Image and Vision Computing, 2010, 28(4): 668-676.

[9] Wang Xiaofeng, Huang Deshuang, Xu Huan. An efficient local Chan-Vese model for image segmentation [J]. Pattern Recognition, 2010, 43(3): 603-618.

[10] Liu Shigang, Peng Yali. A local region-based Chan-Vese model for image segmentation [J]. Pattern Recognition, 2012, 45(3): 2769-2799.

[11] 田 元, 王 乘, 管 濤. 基于FCM 和圖割的交互式圖像分割方法[J]. 工程圖學(xué)學(xué)報, 2010, 31(2): 123-127.

[12] Boykov Y Y, Jolly M P. Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images [C]//IEEE Conference on Computer Vision. Vancouver, Canada, 2001, 105-112.

[13] El-Zehiry N, Xu S, Sahoo P, et al. Graph cut optimization for the Mumford-Shah model [C]//The Seventh IASTED International Conference on Visualization, Imaging and Image Processing. Anaheim, CA, USA, 2007: 182-187.

[14] El-Zehiry N, Sahoo P, Elmaghraby A. Combinatorial optimization of the piecewise constant Mumford-Shah functional with application to scalar/vector valued and volumetric image segmentation [J]. Image and Vision Computing, 2011, 29(6): 365-381.

[15] Ford L R, Fulkerson D R. Flows in networks [J]. American Institute of Physics, 1963, 13: 54.

[16] Tao Wenbing, Tai XueCheng. Multiple piecewise constant with geodesic active contours (MPC-GAC) framework for interactive image segmentation using graph cut optimization [J] Image and Vision Computing, 2011, 29(3): 499-508.

[17] Brown E S, Chan T F, Bresson X. Completely convex formulation of the Chan-Vese image segmentation model [J]. International Journal of Computer Vision, 2012, 98(1): 103-121.

[18] Boykov Y, Kolmogorov V. Computing geodesics and minimal surfaces via graph cuts [C]//IEEE International Conference on Computer Vision. Nice, France, 2003: 26-33.

[19] Kolmogorov V, Boykov Y. What metrics can be approximated by geo-cuts, or global optimization of length/area and flux [C]//Proceedings of the Tenth IEEE International Conference on Computer Vision. Cambridge, UK, 2005: 564-571.

Combining Region-Based Model with Geodesic Active Contour for Nature Image Segmentation Using Graph Cut Optimization

Song Lin, Gao Mantun, Wang Sanmin, Wang Shuxia
(School of Mechanical Engineering, Northwestern Polytechnical University, Xi′an Shaanxi 710072, China)

As the active contour model segments images using level set formulation, such formulation results in very slow algorithms that get easily stuck in local solutions and only segment image with intensity homogeneity. In this paper, a new model combining region-based with geodesic active contours is proposed for image segmentation. The new energy functional can be iteratively minimized by graph cut algorithms with high computational efficiency compared with the level set framework. Experiment results show that the proposed model can effectively and efficiently segment images with intensity inhomogeneity. The method is less sensitive to the location of initial contour and can also avoid local minima solutions.

image segmentation; active contours; level set method; graph cut

TP 391

A

2095-302X(2015)05-0756-07

2014-12-11；定稿日期：2015-04-16

國家自然科學(xué)基金資助項目(51105310)

宋 琳(1975-)，女，河北任縣人，講師，博士研究生。主要研究方向為計算機(jī)視覺和模式識別。E-mail：songlin03@sina.com