基于局部圖劃分的多相活動輪廓圖像分割模型

孔丁科 汪國昭

(浙江大學數學系計算機圖像圖形研究所 杭州 310027)

1 引言

基于曲線演化理論[1]與水平集方法[2]的幾何活動輪廓模型是為解決計算機視覺與模式識別領域廣泛存在的圖像分割問題而提出的，目前，在理論及應用方面的研究正方興未艾[3?8]。幾何活動輪廓模型實現圖像分割的基本思想是：將演化曲線(活動輪廓)隱含地表示為更高維曲面(稱為水平集函數)的零水平集，水平集函數在演化方程(由圖像信息定義的能量泛函變分得之)控制下進行演化，直至圖像的目標邊界。這種演化有許多優點：(1)曲線演化過程始終處于固定格網，因此數值實現較為簡單；(2)能夠自動處理邊界拓撲變化(如合并、斷裂等)；(3)提供光滑、閉合的高精度分割曲線，利于后續圖像處理工作(如目標識別、形狀分析等)。

幾何活動輪廓模型基本可分為：邊界模型[3]和區域模型[4?8]。邊界模型是以邊界局部信息驅使曲線演化，存在對初始曲線敏感、易邊緣泄漏等問題。相對而言，區域模型直接利用活動輪廓內部和外部的全部信息，具有較好的抑噪性和邊界處理能力，而且降低了曲線演化對初始曲線的依賴性，因此能獲得較好的分割結果。

目前，常見的區域模型有分段常數模型[4,5]，分段光滑模型[6]，統計模型[7,8]等。近來，Sumengen等[9,10]結合圖劃分和幾何活動輪廓模型的優點，提出了基于成對相似性的圖劃分活動輪廓 (Graph Partitioning Active Contours，GPAC) 模型。與傳統區域模型不同，GPAC模型以活動輪廓內外像素點的成對相似性作為連接權函數并定義能量泛函，同時，應用基于梯度下降法的水平集函數演化，最終獲得全局優化的圖像分割結果。然而，GPAC模型存在明顯不足：(1)連接權函數僅與光譜信息相關，因此，對離散及低對比度模糊圖像難有較好的邊界定位結果；(2)圖像成對相似性計算量較大，數值實現效率不甚理想[11]。

針對GPAC模型的上述缺陷，本文提出了基于局部圖劃分的多相活動輪廓(Localized Graph-cut based Multiphase Active Contours，LGMAC)圖像分割模型。與原模型的不同之處：(1)以結合空間距離和圖像梯度的測地核函數[12]定義連接權函數，在測度像素點相似度的同時，有效保留潛在邊界信息；(2)以測地核函數的帶寬約束，實現水平集演化的窄帶加速效果；(3)優化圖劃分能量泛函定義，以適應模型的多目標擴展。

2 GPAC模型

基于圖劃分(Graph Partitioning Method，GPM)的圖像分割技術一直以來是圖像分割領域的有效工具[13]，其基本思想是：將圖像映射為帶權無向圖，把像素點視作節點，利用最小割集準則得到圖像的最佳分割。GPM方法本質上是將圖像分割問題轉化為最優化問題，而最小割集準則在連續域下可用能量泛函等價表示，因此，Sumengen等[9]利用幾何活動輪廓模型模擬最優劃分問題，提出了基于成對相似性的圖劃分活動輪廓模型。

令G=G (V, E)是圖像I的帶權無向圖(其中V是節點，E是節點間的邊)，則圖G被劃分為A，B兩部分(且A∪B=V，A∩B=?)的代價函數可表示為

其中w(p, q)是節點p, q之間的連接權(相似性)函數，在連續域下，用能量函數等價表示為

其中C是閉曲線，而Ri(C)和Ro(C)分別是閉曲線的內部和外部區域。由此，GPAC模型融合最優劃分和活動輪廓模型，用梯度下降法求解上式能量的最小化問題，經變分有GPAC模型的曲線演化方程[9]：

其中t是曲線演化的時間參數，c是活動輪廓C上的點，而N是其外法向。從演化方程可知，對任意c∈C，F(c)是該點與活動輪廓內部和外部的相似度比較：當F(c)＞0時，活動輪廓擴張；反之，當F(c)＜0時，活動輪廓收縮，而當且僅當c位于目標邊界時演化停止。

相對于基于區域相似性的傳統區域模型而言，GPAC模型采用自由度更高的像素級相似性比較，使得模型更易融合和擴展，而且，模型通過GPM全局最優化策略，以達到最佳的分割結果。下面分析GPAC模型的不足之處。

首先，僅以像素點的光譜信息(如灰度等)定義連接權函數，而與空間分布無關，使得模型對不同局部結構但光譜信息相似的像素點不存在區分度，因此，僅適用于高對比度的均質圖像，而對光譜信息復雜、邊界模糊的離散及低對比度圖像(如自然、遙感圖像等)難有較好的分割結果。

其次，圖像成對相似性的計算量極大，使得模型在處理較大圖像分割時，存在明顯的局限性。文獻[9]對GPAC模型進行了分塊加速，但數值實現效率仍不理想[11]；而文獻[10]提出了基于過分割的加速方法，極大提高了數值實現效率，但過分割質量很大程度上決定了圖像的分割精度。

3 LGMAC模型

在GPAC模型中，連接權函數與空間分布無關，這使得模型對圖像局部結構缺乏區分度和自適應性，從而無法較好地表征局部結構，造成潛在邊界信息易在演化過程中被忽略。為解決這一問題，本文引入測地核函數[12]定義模型的連接權函數，它滿足以下特性：(1)能夠根據圖像局部結構自適應地選取鄰域采樣點，在有效表征局部結構的同時，實現了水平集演化的窄帶加速效果；(2)能夠在有效測度像素點相似性的同時，較完整地保留潛在邊界信息，從而提高模型的弱邊界處理能力。同時，為更好地處理多目標圖像，本文將分割模型進行了多相水平集擴展。

3.1 基于測地核函數的連接權

定義1 對定義域為???2的圖像I:?→?m(m≥1是光譜空間維數)求導，可得圖像方向對比度矩陣而對比度變化率可由矩陣M的特征向量表示，其極值λ±=定義圖像梯度gλ+=

其中g是圖像梯度，定義路徑?=?p→q的測地時間為

由定義可知，測地時間與空間距離與圖像梯度均相關。一般來講，圖像梯度越大(潛在邊界)，或空間距離越大，則路徑的測地時間越長。由此可以給出基于測地時間的測地核函數定義[12]。

由連接權函數定義可知：在相同的光譜差值情況下，若空間距離或圖像梯度越小，則相似性越大；反之，相似性越小，如處于潛在邊界兩側的鄰近點對，雖然距離小，但梯度大，因此Kσ小，則點對相似性小。因此，基于測地核函數的連接權函數能自適應地表征和區分圖像局部結構，較好地保留潛在邊界信息，同時，能夠通過核帶寬的約束，實現模型的快速窄帶演化：在數值實現中,當空間距離時，Kσ(p, q)趨于零，因此，活動輪廓可看成在±3σ范圍內做窄帶水平集演化，從而極大地降低了演化過程的計算量。

3.2 多相活動輪廓模型

為方便模型的多目標擴展，首先對連續域下的能量泛函進行優化。令

其中A∪B=?，A∩B=?，而w(p, q)是式(7)定義的相似性函數(下同)。

定理1 令

則能量泛函E'與GPAC能量泛函E等價。

證明

兩式相加，則有

但由于diss(A,?)+diss(B,?)=diss(?, ?)與圖劃分無關，可忽略。因此，式(10)等價于2E=diss(A,A)+diss(B, B)。證畢

下面給出本文多相活動輪廓模型的外部能量泛函定義：

其中N=2k是目標區域個數。由定義可知，最優化過程即是最小化各目標區域內的圖像點相異性。Vese等[6]針對分段常數和分段光滑的圖像提出了用k個水平集函數劃分N=2k個子區域的多相分割模型：用φ={φ1, φ2,…,φk}表示水平集函數的集合，A1,表示分割區域，則對于第(1,2,,2k)i i=…個區域，自然數i的二進制數可表示為(其中由此可定義區域iA的特征函數

其中H是一維Heaviside函數，在數值實現時，本文采用與文獻[4,6]一致的正則化Heaviside函數及相應的Dirac函數：

結合活動輪廓長度約束項，LGMAC能量泛函可表示為

由ELGMAC(φ)通過變分[6]得到如下水平集函數的演化方程：

4 實驗分析

本文用LGMAC模型對Berkeley數據庫[15]的多幅自然圖像(具有形態各異的目標邊界)進行分割實驗，并將結果與GPAC模型[9]和NCUT模型[16]的分割結果進行定量比較，分析和驗證LGMAC模型的以下特點：(1)目標邊界獲取能力；(2)窄帶加速效果；(3)多相分割的有效性。實驗參數的取值：ε=1.0，σ=6.0，λ=0.1×2552，時間步長Δt=0.2。實驗平臺為具有Intel Core2 1.66G CPU，1.5G RAM的微機。

實驗1 目標邊界獲取能力 圖1是一副自然圖像的2相分割結果和比較，該圖像由于暗紋理等影響存在一定程度的模糊邊界。圖1(b)是GPAC模型的分割結果，圖1(c)是本文LGMAC模型的2相分割結果，而圖1(d)是GPAC和LGMAC模型局部分割結果的比較。從對比結果可知，LGMAC模型不僅能精確定位出高對比度目標邊界，而且在弱邊界處理上也較GPAC模型更為出色。

圖1 自然圖像LGMAC2相分割示例

通過分割質量的定量比較，進一步驗證LGMAC模型的邊界獲取能力：本文選取Berkeley數據庫內適合2相分割的64副自然圖像進行GPAC和LGMAC分割實驗，并計算其查全率Recall(R)、查準率Precision(P)和F-Measure(F)。表1是上述分割實驗的平均P，R和F值，圖2選取了一組自然圖像的分割結果：其中第1行是原始圖像，第2行是人工分割結果，第3，4行分別是GPAC和LGMAC模型的多相分割結果。由實驗及分析結果可知，LGMAC模型的R，P及F值均不同程度高于GPAC模型，這得益于LGMAC模型的局部弱邊界處理能力，因此LGMAC模型的整體分割質量相對較優。

表1 分割精確度分析

實驗2 窄帶加速效果 本文通過分析GPAC模型和LGMAC模型的數據訪問次數來計算算法復雜度：在GPAC模型的數值實現中，數據的訪問次數為ann，a為平均迭代次數，n是圖像點個數；而本文LGMAC的窄帶演化實現為bk2m，b為基于窄帶加速的水平集迭代次數，k=6σ是窄帶寬度，而m?n是演化曲線上圖像點的個數。表2給出了圖2分割實驗的平均運算量測定，可以看出：LGMAC模型不僅每次迭代的計算時間明顯小于GPAC模型，同時迭代次數也略小于GPAC模型，因此，LGMAC模型的實現效率優于GPAC模型。

表2 圖2實驗平均運算量測定

實驗3 多相分割的有效性 圖3給出了LGMAC模型2相(k=1)，4相(k=2)及16相(k=4)的分割示例。由實驗結果可以看出，本文模型可以實現多目標分割且分割結果較為理想：隨著相數增加，LGMAC模型能較好地細分目標子區域，而整體均質區域(如黑色背景)仍能比較完整地維持形狀而未被過分割。

圖2 LGMAC和GPAC模型2相分割結果

圖3 自然圖像LGMAC多相分割示例

通過與NCUT模型的定量分析比較，進一步驗證LGMAC多相分割的有效性：自然圖像分別通過NCUT模型和LGMAC模型進行多相分割，分割結果與人工分割結果做比較，并計算各模型的分割精度F值。圖4是一組自然圖像的實驗結果，其中第1行是原始圖像，第2行是人工分割結果，第3，4行分別是NCUT模型(采樣鄰域18×18)和LGMAC模型的多相分割結果，同時F值標記在結果圖下。實驗結果可知，LGMAC模型分割結果的F值比NCUT模型高出21%～37%，NCUT模型的分割結果存在較大程度的過分割，弱邊界處理也不甚理想，而LGMAC模型能同時保留大尺度均質目標和小尺度細節，且邊界定位基本準確。

5 結束語

本文提出了一種基于局部圖劃分的多相活動輪廓(LGMAC)圖像分割模型：以測地核函數定義連接權函數，在測度像素點相似性的同時，能有效表征和區分圖像局部結構，從而較完整地保留潛在邊界信息；同時，通過核帶寬的約束，實現模型的快速窄帶水平集演化。此外，LGMAC模型還實現了復雜場景下的多目標分割。而融合更多圖像特征定義連接權函數[13]，進一步提高LGMAC模型的分割精度，將是本文后續工作的主要內容。

圖4 LGMAC和NCUT模型多相分割結果

[1] Kass M, Witkin A, and Terzopoulos D. Snakes: Active contour models [J]. International Journal of Computer Vision,1988, 1(4): 321-331.

[2] Osher S and Sethian J A. Fronts propagating with curvaturedependent speed: Algorithms based on Hamilton-Jacobi formulation [J]. Journal of Computational Physics, 1988,79(1): 12-49.

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

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

[5] Yan N L, Lee H K, and Yip A M. A multiresolution stochastic level set method for Mumford–Shah image segmentation [J].IEEE Transactions on Image Processing, 2008, 17(12):2289-2300.

[6] Vese L and Chan T F. A multiphase level set framework for image segmentation using the Mumford and Shah model [J].International Journal of Computer Vision, 2002, 50(3):271-293.

[7] Paragios N and Deriche R. Geodesic Active Regions: A new framework to deal with frame partition problems in computer vision [J]. Journal of Visual Communication and Image Representation, 2002, 13(1-2): 249-268.

[8] 曹宗杰, 閔銳, 龐伶俐, 等. 基于統計模型的變分水平集SAR圖像分割方法[J]. 電子與信息學報, 2008, 30(12): 2862-2866.Cao Zong-jie, Min Rui, and Pang Ling-li, et al.. A variational level set SAR image segmentation approach based on statistical model [J]. Journal of Electronics & Information Technology, 2008, 30(12): 2862-2866.

[9] Sumengen B and Manjunath B S. Graph Partitioning Active Contours (GPAC) for image segmentation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2006, 28(4): 509-521.

[10] Bertelli L, Sumengen B, and Manjunath B S, et al.. A variational framework for multiregion pairwisesimilarity-based image segmentation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(8):1400-1414.

[11] Yuan X, Situ N, and Zouridakis G. A narrow band graph partitioning method for skin lesion segmentation [J]. Patten Recognition, 2009, 42(6): 1017-1028.

[12] Grazzini J and Soille P. Edge-preserving smoothing using a similarity measure in adaptive geodesic neighbourhoods [J].Patten Recognition, 2009, 42(10): 2306-2316.

[13] 劉佳, 王宏琦. 一種基于圖割的交互式圖像分割方法[J]. 電子與信息學報, 2008, 30(8): 1973-1976.Liu Jia and Wang Hong-qi. A graph-cuts based interactive image segmentation method [J]. Journal of Electronics &Information Technology, 2008, 30(8): 1973-1976.

[14] Scheunders P. A multivalued image wavelet representation based on multiscale fundamental forms [J]. IEEE Transactions on Image Processing, 2002, 11(5): 568-575.

[15] Martin D, Fowlkes C, and Tal D, et al.. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[C]. Proceedings 8th International Conference on Computer Vision, Vancouver, Canada, 2001: 416-423.

[16] Shi J and Malik J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.