張微

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

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

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

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

1 Graph cuts圖像分割理論

1.1 Graph cuts

在討論graph cuts之前，這里先給出圖的定義。假設(shè)圖G=（V，E）是一個(gè)有向帶權(quán)圖，由節(jié)點(diǎn)V和有向邊E的集合組成，每一條邊有一個(gè)非負(fù)的權(quán)值。節(jié)點(diǎn)V的集合中包含兩種不同類型的節(jié)點(diǎn)：由圖像像素集合P組成的鄰域節(jié)點(diǎn)，以及兩個(gè)特殊的端點(diǎn)稱為終端：源點(diǎn)s與匯點(diǎn)t。在鄰域系統(tǒng)中，若q∈Np，即q是p的鄰域像素，則像素p與像素q相連接。相鄰像素節(jié)點(diǎn)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是邊的一個(gè)子集，若將C從圖G中移除，則節(jié)點(diǎn)V被分為兩個(gè)不連接的集合S與T=V-S，且s∈S，t∈T。割集C的代價(jià)是所有邊上權(quán)值之和。最小割的割集代價(jià)也是最小的，可以通過最大流/最小割算法在線性時(shí)間內(nèi)獲得[6]。

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

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

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

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

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

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

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

2 結(jié)合形狀先驗(yàn)的Graph cuts目標(biāo)分割

2.1 形狀先驗(yàn)的引入

形狀先驗(yàn)可以定義如下：

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

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

其中當(dāng) fp≠fq時(shí)，I（·）為 1，否則為 0。

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

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

2.2 形狀模版及其仿射變化

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

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

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

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

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

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

3 算法流程

文中算法可以描述如下：

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

圖1 實(shí)驗(yàn)中用到的形狀模版Fig.1 The shape templates used in the experiment

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

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

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

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

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

5 結(jié) 論

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

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

[1]劉松濤，殷福亮.基于圖割的圖像分割方法及其新進(jìn)展[J]. 自動(dòng)化學(xué)報(bào)，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.