張微

（寶雞文理學(xué)院 陜西 寶雞 721016）

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

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

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

1 Graph cuts圖像分割理論

1.1 Graph cuts

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

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

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

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

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

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

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

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

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

2 結(jié)合形狀先驗的Graph cuts目標分割

2.1 形狀先驗的引入

形狀先驗可以定義如下：

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

形狀先驗?zāi)芰亢瘮?shù)定義為二階勢函數(shù)的形式：

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

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

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

2.2 形狀模版及其仿射變化

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

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

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

2.3 能量函數(shù)的定義

在考慮加入形狀先驗之后，新的能量函數(shù)變?yōu)槿缦碌男问剑?/p>

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

3 算法流程

文中算法可以描述如下：

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

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

3）將形狀模版與得到的初始分割結(jié)果進行對齊，然后計算形狀先驗?zāi)芰?VSpq（fp，fq），得到新的能量函數(shù)，如式（6）；

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

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

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

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

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

圖2 分割結(jié)果對比Fig.2 The comparison of segmentation results

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

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

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

5 結(jié) 論

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

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

[1]劉松濤，殷福亮.基于圖割的圖像分割方法及其新進展[J]. 自動化學(xué)報，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].西安：陜西師范大學(xué)，2013.

[6]Ford D R，F(xiàn)ulkerson 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，F(xiàn)owlkes 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.