結合形狀先驗的圖割目標分割方法

張微

（寶雞文理學院 陜西 寶雞 721016）

圖像分割是計算機視覺與圖像處理領域非常重要的研究內容，是圖像理解與分析的基礎，在圖像工程中有著極其關鍵的地位。圖像分割的方法有很多，其中，基于能量最小化的方法在過去30年受到了研究者們的廣泛關注[1]。圖割[2]（Graph cuts）算法是能量最小化方法中常見的一種，在圖像分割中的應用也越來越多[3-4]，一類常見的應用是利用Graph cuts算法將感興趣的目標從背景中分離出來，以實現對圖像中感興趣目標的分割。Graph cuts算法可以在全局最優的框架下進行分割，能夠保證能量的全局最優解，不僅利用圖像的像素灰度信息，還考慮了區域邊緣信息，得到了較好的分割結果[1]。

傳統的Graph cuts算法僅依賴圖像的底層顏色信息，對于簡單圖像分割效果良好，但當待分割目標與背景顏色信息相似或背景復雜時，以及目標邊緣有陰影或是圖像包含噪聲的情況下，并不能得到較好地處理，圖像目標的準確分割變得很困難[5]。通常情況下，待分割目標的形狀可以是已知的，若能夠將這類先驗信息加入到Graph cuts中，則會增加分割方法的魯棒性。

文中以圖割算法為基礎，給出了一種形狀先驗的定義，然后將其轉化為能量函數的形式，定義了完整的能量函數，最后對其進行能量最小化，得到目標分割結果。形狀對于仿射變換具有不變性，使得方法更為靈活，易于應對不同的情形。實驗結果表明，形狀先驗信息增加了對目標邊界的有效約束，使得目標能夠正確的分割，提高了算法的精確度。

1 Graph cuts圖像分割理論

1.1 Graph cuts

在討論graph cuts之前，這里先給出圖的定義。假設圖G=（V，E）是一個有向帶權圖，由節點V和有向邊E的集合組成，每一條邊有一個非負的權值。節點V的集合中包含兩種不同類型的節點：由圖像像素集合P組成的鄰域節點，以及兩個特殊的端點稱為終端：源點s與匯點t。在鄰域系統中，若q∈Np，即q是p的鄰域像素，則像素p與像素q相連接。相鄰像素節點p與q通過邊帶有權值Wpq的邊epq相連接。除此之外，像素p與終端s與t分別通過帶有權值Wsp和Wpt的邊 esp和 ept相連。 這里在圖 G中，若 epq∈E，則 eqp∈E，權值Wpq=Wqp，且所有的像素p∈P都與終端s與t相連。

割集C?E是邊的一個子集，若將C從圖G中移除，則節點V被分為兩個不連接的集合S與T=V-S，且s∈S，t∈T。割集C的代價是所有邊上權值之和。最小割的割集代價也是最小的，可以通過最大流/最小割算法在線性時間內獲得[6]。

1.2 基于圖割的圖像分割模型

將目標/背景分割問題也可以認為是一個二元標記問題，即圖像中的每一個像素都可以從標記集合L={0，1}中分配一個標記，其中0和1分別表示背景和目標。

P表示圖像中所有像素的集合，N表示集合P上的鄰域系統，它可以是4-階鄰域系統或8-階鄰域系統。fp∈L表示分配給像素p的標記，f={fp|p∈P}是所有可能分配的標記的集合。圖像分割的能量函數通常以如下形式給出：

在式（1）中，由于第一項加入了區域約束，因此又稱為區域項或數據項，具體而言，它衡量像素p適合目標或是背景模型的程度。Dp（fp）是給像素p分配標記fp的懲罰。給像素p分配標記fp的可能性越大，數據項Dp（fp）的值也就越小。目標/背景模型可以是事先已知的，或是通過手工標記的種子節點來建模，文中采用高斯混合模型。為確保種子節點能夠正確的分割，對于任何目標種子節點 p，可以設 Dp（0）=∞，而對于背景種子節點 p，設 Dp（1）=∞。

由于式（1）中第二項加入了邊界約束，也將其稱為邊界項。分割邊界通常出現在標記不同的相鄰像素間。邊界項Vpq（fp，fq）是給相鄰像素分配標記fp和fq的懲罰。由于大多數相鄰像素都會有相同的標記，因此若相鄰像素的標記相同，則不添加任何懲罰，反之，若相鄰像素的標記不同，則加入懲罰項。一般地，Vpq（ fp，fq）=wpq·I（ fp≠fq），其中當 fp≠fq時，I（·）為 1，否則為0。wpq可以定義為如下形式：

其中Ip表示像素p的顏色特征，σ是對相機噪聲的估計值[2]。

式（1）中的參數λ≥0用來權衡數據項和邊界項的相對重要性。較小的值使得數據項更為重要。

2 結合形狀先驗的Graph cuts目標分割

2.1 形狀先驗的引入

形狀先驗可以定義如下：

其中參數α是形狀先驗項的權值，用來權衡形狀先驗的相對重要性。dist（·）表示歐式距離變換，C*表示估計得到的形狀先驗輪廓。dist（p，C*）通過距離變換計算像素點p到形狀先驗輪廓C*的歐式距離。

形狀先驗能量函數定義為二階勢函數的形式：

其中當 fp≠fq時，I（·）為 1，否則為 0。

可以看出，該能量項可以使目標分割邊界向理想的形狀模版輪廓邊緣趨近。根據[7]，該能量函數可以通過[8]中的最大流/最小割算法實現最小化，得到最終分割結果。

形狀先驗的引入可以有效地約束待分割目標的邊界，使分割結果向與形狀相似處收斂，利用圖像的已有信息指導目標分割過程，能夠在一定程度上改善分割結果。

2.2 形狀模版及其仿射變化

由于待分割目標與形狀模版在位置、尺度及旋轉角度上會有不同，在計算形狀先驗之前，形狀模版通常需要與待分割目標進行對齊。這里采用尺度不變特征變換方法[9]（Scale Invariant Feature Transform，SIFT）和隨機抽樣一致方法[10]（RANdom SAmple Consensus，RANSAC）相結合的方式，實現待分割圖像目標與形狀模版之間的對齊，整個過程可以自動地進行。

具體過程如下：先利用SITF方法提取形狀模版與分割圖像間的特征點對；再采用RANSAC方法除去特征點對中錯誤的匹配，并且利用其余的匹配點對計算仿射變換參數；通過以上估計得到的參數對形狀模版進行逆變換，得到對齊后的形狀模版。

形狀對齊過程對于形狀先驗的引入至關重要，形狀對齊的準確性直接影響到目標分割的結果。SIFT算法和RANSAC算法相結合，可以有效地實現待分割目標與形狀模版間的對齊，并且對于包含噪聲的情形，也能進行較好地應對。

2.3 能量函數的定義

在考慮加入形狀先驗之后，新的能量函數變為如下的形式：

其中，勢函數Vpq在1.2小節中已給出定義，形狀先驗約束項在VSpq式（4）中定義。根據文獻[7]，若包含兩個隨機變量的二元函數 g 滿足 g（0，0）+g（1，1）≤g（1，0）g（0，1）這一條件時，則稱該函數是sub-modular，當所有的二階勢函數都是sub-modular時，式（6）中定義的能量函數可以通過graph cuts算法進行優化。可以很明顯地看出，二階勢函數Vpq和VSpq都滿足這一條件，可以通過graph cuts算法得到全局最優解。

3 算法流程

文中算法可以描述如下：

1）對于待分割圖像，根據式（1），分別計算能量函數Dp（ fp）和 Vpq（ fp，fq）；

2）采用 graph cuts算法對僅包含 Dp（ fp）和 Vpq（ fp，fq）的能量函數進行最小化，從而得到初始分割結果f；

3）將形狀模版與得到的初始分割結果進行對齊，然后計算形狀先驗能量 VSpq（fp，fq），得到新的能量函數，如式（6）；

4）用graph cuts算法對新能量函數進行最小化，得到加入形狀先驗后的目標分割結果fnew。

4 實驗結果與分析

文中算法程序采用Matlab編寫，其中核心部分由C++語言實現，編程環境為Matlab R2010b。選擇標準圖像庫Berkeley Segmentation Dataset[11]中的圖像進行實驗，并分別用傳統圖割算法和本文算法對圖像進行分割。在實驗中，將參數σ設為相鄰像素間顏色特征差異的均值，這樣對于不同的圖像該參數的值也會有差異。參數α的設為1，參數λ的值固定為5。圖1中給出了實驗中所用到的形狀模版，可以看出，該模版與待分割目標之間包含了不同的仿射變換，如尺度、平移變換，以及同時包含尺度、旋轉、平移變換的情形，增加了用形狀先驗進行目標分割的難度。

圖1 實驗中用到的形狀模版Fig.1 The shape templates used in the experiment

圖2 中給出了用傳統圖割算法得到的分割結果以及本文算法得到的分割結果，并將它們進行對比。將圖2（a）中的原始圖像依次編號為（1）~（4），其中紅色和藍色標記分別表示對目標和背景的初始化。（b）表示傳統圖割算法得到的分割結果，（c）是實驗中用到的形狀先驗，該先驗信息已通過2.2小節中的方法實現與待分割目標的對齊。（d）是使用形狀先驗信息后得到的分割結果。可以很明顯地看出，當加入形狀先驗信息之后，分割結果有了非常明顯的改善。形狀先驗在這里起到了不可替代的作用。

圖2 分割結果對比Fig.2 The comparison of segmentation results

圖像（1）~（3）都包含了較為復雜的背景，且目標與背景的顏色信息十分相似，使得不采用任何先驗信息得到正確的分割結果較為困難，而形狀先驗的加入很好地改善了這一問題。當加入形狀先驗之后，圖像目標被準確的分割出來，去除了背景中雜亂的部分，也使待分割目標內部更加完整，并且形狀對齊可以適應待分割目標與形狀模版間較大的仿射不同，得到了較好的分割結果。圖像（4）中添加了均值為0，方差為0.01的高斯噪聲。從結果中可以看出，形狀先驗的引入同樣可以有效地應對圖像噪聲、陰影帶來的影響，得到了完整的目標分割結果。

表1中給出了兩種算法的性能比較，包括分割錯誤率以及運行時間上的對比。從表1可以看出，形狀先驗的加入使得分割錯誤率顯著下降，得到的分割效果良好，并且沒有引起運行時間的大量增加。以上實驗數據表明本文算法的有效性，對于圖像背景復雜、目標背景顏色信息相似、陰影、噪聲問題能夠得到較好地應對，形狀先驗信息起到了十分重要的作用，有助于分割錯誤率的降低，能夠準確完整地將圖像目標分割出來。

表1 算法性能比較Tab.1 The comparison of algorithm performance

5 結 論

文中提出一種結合形狀先驗的圖割目標分割方法，將形狀先驗引入圖割框架中，并將其轉化為勢函數，加入到能量函數中，通過能量最小化得到最終分割結果。相比于傳統圖割方法，該方法可以有效改善噪聲、陰影、復雜背景等因素對分割結果帶來的不利影響，分割效果良好。實驗結果表明形狀先驗信息在目標分割過程中起到了不可替代的作用。

文中選用的是單一形狀模版，對于包含相似形狀的目標，以及形狀的局部或全局變化并不能進行較好地處理，下一步將針對該局限性，基于多個形狀模版定義形狀先驗，以適應于更復雜的情形。

[1]劉松濤，殷福亮.基于圖割的圖像分割方法及其新進展[J]. 自動化學報，2012，38（6）:911-922.LIU Song-tao，YIN Fu-liang.The basic principle and its new advances of image segmentation methods based on graph cuts[J].Acta Automatica Sinica，2012，38（6）:911-922.

[2]Boykov Y Y，Jolly M P.Interactive graph cuts for optimal boundary®ion segmentation of objects in ND images[C]//Computer Vision，2001.ICCV 2001.Proceedings.Eighth IEEE International Conference on.IEEE，2001（1）:105-112.

[3]Vu N，Manjunath B S.Shape prior segmentation of multiple objects with graph cuts[C]//Computer Vision and Pattern Recognition，2008.CVPR 2008.IEEE Conference on.IEEE，2008:1-8.

[4]Veksler O.Star shape prior for graph-cut image segmentation[M]//Computer Vision-ECCV 2008.Springer Berlin Heidelberg，2008:454-467.

[5]張微.基于概率圖模型的圖像分類研究[D].西安：陜西師范大學，2013.

[6]Ford D R，Fulkerson D R.Flows in networks[M].Princeton university press，2010.

[7]Kolmogorov V，Zabin R.What energy functions can be minimized via graph cuts?[J].Pattern Analysis and Machine Intelligence， IEEE Transactions on，2004，26（2）:147-159.

[8]Boykov Y，Kolmogorov V.An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（9）:1124-1137.

[9]Comaniciu D，Meer P.Mean shift:A robust approach toward featurespaceanalysis[J].IEEETransactionson Pattern Analysis and Machine Intelligence，2002，24（5）:603-619.

[10]Fischler M A，Bolles R C.Random sample consensus:a paradigm for model fitting with applications to image analysis and automated cartography[J].Communications of the ACM，1981，24（6）:381-395.

[11]Martin D，Fowlkes C，Tal D，et al.A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[C]//Computer Vision， 2001.ICCV 2001.Proceedings.Eighth IEEE International Conference on.IEEE，2001 （2）:416-423.