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

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

（西北工業大學機電學院，陜西 西安 710072）

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

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

（西北工業大學機電學院，陜西 西安 710072）

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

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

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

由Malladi等[3]和Caselles等[4]各自提出的幾何活動輪廓模型，由于具有能夠自動處理邊界曲線拓撲結構的合并與斷裂、計算穩定、計算結果精度高的特點，所以受到越來越多的學者關注。活動輪廓模型可分為基于邊界的模型和基于區域的模型?；谶吔绲幕顒虞喞Ｐ褪且揽窟吘墮z測，利用圖像的梯度信息構造邊界函數，用邊界的局部信息來驅使曲線演化，因此存在對初始曲線位置敏感、易產生邊緣泄漏等問題。測地線的活動輪廓模型就是基于邊界的活動輪廓模型。

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

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

圖論是以圖為研究對象的數學的一個分支，基于圖論進行圖像分割的方法是一種較新的圖像分割方法。其是將網絡圖與圖像相結合，基于能量最小化進行目標分割的交互式方法。圖割優化[12]方法作為一種優化工具，利用合適的能量函數框架，將區域屬性和邊緣信息有機地結合，具有全局最優、分割結果的強魯棒性，執行效率高等優點，廣泛地應用到了圖像分割領域中。El-Zehiry等[13-14]將圖割應用到兩相Mumford-Shah模型中，結果表明用圖割求最小化能量函數值結果比梯度下降法要有效和穩定。

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

1 相關背景

1.1 區域活動輪廓模型

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

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

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

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

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

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

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

1.2 圖割

圖割(graph cuts)是以圖論為理論基礎，根據能量最小化模型構造能量函數，從而將視覺問題轉化為能量函數最小化問題；根據圖像構造網絡，使能量與網絡的割相對應，從而將能量最小化問題轉化為網絡最小割問題。

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

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

圖1 3×3二維圖切割

2 本文模型

2.1 改進的活動輪廓模型

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

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

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

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

2.2 圖割優化

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

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

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

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

其中，δ為網絡圖的網格單位長度，nk是曲線C與第K組邊線交點的總個數，ek是兩個節點的最短長度矢量，ωk是邊ek的權值，則：

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

圖 2 8鄰域系統N8

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

最終能量函數的離散形式可以表達為：

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

2.3 算法實現

算法步驟如下：

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

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

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

對于p的8領域系統中的每一點q用式(21)計算wpq；并添加邊vpvq的權值為wpq；

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

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

3 實驗結果與分析

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

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

圖3中，第一行有3種不同初始曲線位置，第二行是對應的分割結果。圖4中，第一行有3種不同初始曲線大小，第二行是對應的分割結果。根據圖3和圖4中所示結果，當改變初始曲線位置和大小，對分割結果的影響不大。

圖 3 各種初始位置及分割結果

圖 4 各種初始曲線大小分割結果

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

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

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

3.2 縮短運行時間

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

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

3.3 分割結果的有效性

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

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

圖 6 RBCV模型和C-V模型的分割結果

圖 7 自然圖像的分割結果比較

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

4 結 束 語

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

[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]. 工程圖學學報, 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]. 工程圖學學報, 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

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

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