基于形狀先驗和圖割的彩色圖像分割

牛文斐，汪西莉

陜西師范大學(xué) 計算機科學(xué)學(xué)院，西安 710062

圖像分割是利用圖像的某些特性，如灰度、顏色、紋理、形狀等信息將圖像劃分成若干個獨立的有意義的連續(xù)區(qū)域或?qū)ο螅诿總€區(qū)域內(nèi)部具有同質(zhì)的特性。圖像的分割結(jié)果直接影響到后期的圖像分析理解。利用圖割理論進行圖像分割是近年來基于能量最小化框架的一個研究熱點。該理論的新穎之處在于它的全局最優(yōu)求解能力及結(jié)合多種知識的統(tǒng)一圖像分割框架。1989年，Greig等人[1]為了驗證模擬退火算法解決全局優(yōu)化問題的不足，首次將圖割理論引入計算機視覺領(lǐng)域。2001年，Boykov和Jolly[2]首次提出了基于圖割的圖像分割方法Interactive Graph Cuts，它有著獲取全局最優(yōu)解以及融合多種先驗知識的能力，奠定了運用圖割理論進行圖像分割的基本架構(gòu)。

傳統(tǒng)的圖割方法對簡單圖像的分割是成功的，但是對于含有噪聲或遮擋物的復(fù)雜圖像的分割效果并不好。針對該缺陷，本文提出以圖割算法為基礎(chǔ)，增加形狀先驗知識，運用形狀先驗信息和組合圖割優(yōu)化的方法進行圖像分割，可以有效改善這些問題。

1 基于圖割的圖像分割

1.1 圖割理論

圖割是一種基于圖論的組合優(yōu)化方法，它將一幅圖像映射成一個網(wǎng)絡(luò)圖，其中像素點對應(yīng)圖中的節(jié)點，相鄰像素點之間的關(guān)系對應(yīng)圖中節(jié)點之間邊，并建立關(guān)于標(biāo)號的能量函數(shù)，割的容量對應(yīng)能量函數(shù)。運用最大流/最小割算法對網(wǎng)絡(luò)圖進行切割，得到網(wǎng)絡(luò)圖的最小割，即對應(yīng)于待分割的目標(biāo)邊界。

1.2 圖割方法解決圖像分割的一般框架

（1）構(gòu)造能量函數(shù)，從而將分割問題轉(zhuǎn)化為能量函數(shù)最小化問題，該能量函數(shù)反映了圖像分割結(jié)果的好壞。

（2）根據(jù)圖像構(gòu)造s-t網(wǎng)絡(luò)圖，這個圖將能量函數(shù)視為其中邊的集合，使能量與網(wǎng)絡(luò)圖的割相對應(yīng)，從而將能量最小化問題轉(zhuǎn)化為求網(wǎng)絡(luò)圖最小割問題。

（3）根據(jù)最大流/最小割定理，將網(wǎng)絡(luò)圖最小割問題轉(zhuǎn)化為最大流問題。

（4）求得網(wǎng)絡(luò)圖的最大流，即對應(yīng)著圖的最小割，從而得到能量函數(shù)的全局最優(yōu)解，最終得到圖像分割結(jié)果[4]。

圖割理論的核心思想是構(gòu)造一個能量函數(shù)，能量函數(shù)一般由兩項組成[5]：

其中，數(shù)據(jù)項Edata(f)用來衡量像素p所分配的標(biāo)號fp與觀察到的數(shù)據(jù)不一致性；光滑項Esmooth(f)用于約束鄰接像素間具有一致視差，它體現(xiàn)了區(qū)域內(nèi)部的連續(xù)性和邊界的不連續(xù)性。不同的能量函數(shù)對應(yīng)網(wǎng)絡(luò)圖中的邊所賦權(quán)值的方法是不同的，但能量函數(shù)最終是解決標(biāo)號問題的。運用圖割算法求解能得到該能量函數(shù)的全局最優(yōu)解。

2 基于形狀先驗和圖割的圖像分割

傳統(tǒng)圖割方法可以獲取全局最優(yōu)解或者是帶有很強特征的局部最優(yōu)解，但是對含有噪聲或遮擋物等復(fù)雜圖像，算法會受圖像中噪聲、遮擋等的影響，分割得到的目標(biāo)不完整或者包含一些雜質(zhì)。而目前提出的很多在已有算法中加入形狀先驗的思想，使算法包含更多約束信息，限制了感興趣區(qū)域的搜尋空間，從而更好地分割出完整目標(biāo)。如Slabaugh[6]等提出了基于橢圓形狀先驗和圖割的圖像分割方法；Veksler[7]提出一種融合星形形狀先驗到圖割算法中的圖像分割方法。引入形狀先驗的思想，關(guān)鍵要考慮如何將形狀先驗懲罰添加到傳統(tǒng)圖割算法中，從而進行有效的分割。形狀先驗?zāi)０蹇梢赃x用一個簡單的模板，也可以選用多個形狀先驗?zāi)０宓挠?xùn)練集，后者更為靈活，適用于變形的形狀，但計算是復(fù)雜而耗時的。因此本文在圖割算法的基礎(chǔ)上，加入了簡單的形狀先驗知識，有效提高了圖割的分割精度，使圖割方法更具有魯棒性。若給定形狀先驗?zāi)０迮c待分割目標(biāo)存在平移、旋轉(zhuǎn)、尺度縮放等剛性變換，則運用（Scale Invariant Feature Transform，SIFT）算法進行特征匹配，通過仿射變換將給定模板與分割目標(biāo)進行對齊，解決形狀先驗?zāi)０迮c待分割目標(biāo)存在的仿射不同，使該算法更靈活。

2.1 形狀先驗?zāi)Ｐ?/h3>

首先定義形狀先驗?zāi)芰?，根?jù)文獻[8]中提到的運用Chan和Zhu[9]提出的形狀距離的描述形式，將形狀先驗?zāi)芰客ㄟ^終端邊緣權(quán)值合并到圖中。該方法中的形狀距離是對稱的，而且遵循了三角不等式，其使用的形狀模板是和待分割目標(biāo)相同的二值形狀模板。

對于給定的一個形狀模板φ0，定義二值標(biāo)簽f的能量：

由上述思想可以得到，形狀先驗懲罰為：

其中f表示未含形狀先驗得到的分類標(biāo)記，φ0表示已知的二值形狀模板。

加入形狀懲罰的思想：如果分類得到的標(biāo)記模板和已知形狀的二值模板在某點的標(biāo)記不一致，如p點的標(biāo)記fp=0，而模板=1，或p點的標(biāo)記fp=1，而模板=0，則表示分割有誤，需要加入形狀懲罰1；如果分割得到的標(biāo)記模板和已知二值模板的像素點的標(biāo)記一致，則形狀懲罰為0，即不需要加入任何懲罰。

2.2 模板仿射變換

如果給定的二值形狀模板和分類得到的標(biāo)記模板不完全相同，存在平移、旋轉(zhuǎn)、尺度縮放等差異，則需要將兩個形狀通過仿射變換進行配準(zhǔn)。通過仿射變換實現(xiàn)圖像配準(zhǔn)有多種方法，比如歸一化算法[10]、梯度下降法[11]等，但歸一化算法是根據(jù)圖像矩來求解的，對于含有陰影等雜質(zhì)的模板處理效果不好，往往得不到正確的形式；梯度下降法求解容易陷入局部最優(yōu)，找不到最優(yōu)解。本文運用SIFT特征匹配算法[12]，SIFT由Lowe于1999年提出，2004年完善總結(jié)，其匹配能力較強，可以處理兩幅圖像之間發(fā)生平移、旋轉(zhuǎn)、尺度縮放等情況下的匹配問題。SIFT算法是一種提取局部特征的算法，在尺度空間尋找極值點，提取位置、尺度、旋轉(zhuǎn)不變量。極值點是一些十分突出的點，比如角點、邊緣點、暗區(qū)域的亮點以及亮區(qū)域的暗點，如果兩幅圖像中有相同的景物，那么使用某種方法分別提取各自的穩(wěn)定點，則這些點之間會有相互對應(yīng)的匹配點。

根據(jù)正確匹配的特征點，運用仿射變換公式求得變換參數(shù)，從而使兩幅圖像正確匹配。

2.3 本文方法

2.3.1 算法設(shè)計

本文算法的思想：首先建立關(guān)于標(biāo)號的能量函數(shù)EA(f)，利用圖割方法最小化該能量函數(shù)求得最優(yōu)解，從而得到初始分割結(jié)果。在此基礎(chǔ)上，運用上述提到的添加形狀先驗的思想，在能量函數(shù)中添加形狀項，構(gòu)成新的能量函數(shù)，通過終端邊緣權(quán)值將形狀懲罰合并到圖中，運用圖割算法求得最終分割結(jié)果。

算法流程為：

步驟1首先選取一幅彩色圖像，對圖像構(gòu)造s-t網(wǎng)絡(luò)圖，建立關(guān)于此標(biāo)號的能量函數(shù)EA(f)，根據(jù)定義好的能量函數(shù)，確定圖的邊緣之間的權(quán)值。

步驟2在該網(wǎng)絡(luò)圖上運用最大流/最小割算法求得圖的最大流，即對應(yīng)著最小割，從而得到初始的圖像分割結(jié)果。

步驟3在上述算法的基礎(chǔ)上，結(jié)合添加形狀先驗的思想，定義形狀先驗?zāi)芰浚谀芰亢瘮?shù)中添加形狀項，構(gòu)成新的能量函數(shù)E(f)，然后把這些形狀能量通過終端邊緣權(quán)值合并到圖中。

步驟4運用圖割方法進行分割，得到加入形狀以后的圖像分割結(jié)果。

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

算法步驟1和步驟3是建立關(guān)于標(biāo)號的能量函數(shù)，本文選擇的能量函數(shù)形式為：

該能量函數(shù)包括兩項：第一項是基于圖像信息的能量項；第二項是形狀能量項。算法步驟1中建立的是基于圖像的能量函數(shù)，對應(yīng)式（4）的第一項，這一項是基于圖像信息的，包含數(shù)據(jù)項和平滑項；算法步驟3建立的能量函數(shù)如式（4）所示，包括兩項。

能量函數(shù)中第一項E(A)采用文獻[2]定義的形式：

其中R(A)是數(shù)據(jù)項，B(A)是平滑項；系數(shù)λ≥0表示了區(qū)域項R(A)和邊界項B(A)的相對重要性。數(shù)據(jù)項和平滑項的定義如下：

式（6）中R(A)表示像素p屬于背景或者目標(biāo)的概率的代價。式（9）中系數(shù)B{p，q}≥0表示像素p和q之間的不相似性的代價，δ(Ap，Aq)表示像素點標(biāo)號的值，式（11）中Ip和Iq表示像素點的值。算法中，數(shù)據(jù)項選用高斯模型來建模，采用K均值算法。將圖像像素點聚為兩類，得到樣本的標(biāo)記并計算每類的均值和協(xié)方差，從而估計得到參數(shù)進行建模。

能量函數(shù)中第二項形狀項ES(f)采用2.1節(jié)描述來定義。如果給定的形狀模板經(jīng)過了仿射變換，則采用2.2節(jié)的思想來定義。

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

運用上述方法對彩色圖像進行分割。程序用Matlab編寫，其核心部分由C++語言實現(xiàn)，編程環(huán)境為Matlab 2009b和VC2008。選用標(biāo)準(zhǔn)圖像庫Weizmann Horse Database（msri.org/people/members/eranb/）中 的 圖 像 進行實驗，該數(shù)據(jù)庫中馬的顏色、大小、形態(tài)各異，而且背景也十分復(fù)雜，有些與馬的顏色很接近，不同圖像中的目標(biāo)之間、背景之間也有著明顯的差異。本文分別用傳統(tǒng)圖割算法和添加形狀先驗后的算法對圖像進行分割，兩種方法的能量函數(shù)定義的參數(shù)λ均設(shè)置為43。

圖1（a）是一幅加入均值為0，方差為0.01的高斯噪聲后的彩色圖像，使用傳統(tǒng)圖割方法時得到初始分割結(jié)果如圖1（b）；添加形狀先驗?zāi)芰亢?，使用圖割方法得到分割結(jié)果和標(biāo)記如圖1（c）。從圖中可以看到，分割效果得到了優(yōu)化，錯誤率明顯降低。圖2和圖3是加入和上圖相同大小的噪聲后得到的圖像分割結(jié)果。從這三個圖像的分割結(jié)果圖來看，加入形狀先驗后的圖割算法，對含有噪聲的圖像具有更強的魯棒性，得到了更完整的目標(biāo)分割。

圖1 horse320.jpg加入高斯噪聲分割結(jié)果

圖2 horse125.jpg加入高斯噪聲分割結(jié)果

圖3 horse321.jpg加入高斯噪聲分割結(jié)果

圖4（a）是一幅在原圖上添加一部分遮擋物后得到的彩色圖像；使用傳統(tǒng)圖割方法得到初始分割結(jié)果如圖4（b）。從結(jié)果圖中可以看到，遮擋物部分沒有得到有效分割，仍然屬于一個整體被錯分給了目標(biāo)部分。添加形狀先驗?zāi)芰亢?，使用圖割方法得到分割結(jié)果和標(biāo)記如圖4（c）。從圖中可以看到，遮擋物部分得到了正確分割，目標(biāo)部分分割更加完整，分割效果得到了優(yōu)化，錯誤率明顯降低。

圖4 horse002.jpg加入遮擋物分割結(jié)果

圖5（a）是一幅彩色圖像。該圖像本身就含有遮擋物，圖中人坐在馬上，人的上部分身體屬于背景，下部分身體屬于目標(biāo)，人為遮擋物。使用傳統(tǒng)圖割方法得到初始分割結(jié)果如圖5（b）。從圖中可以看出，人的部分沒有得到正確分割，目標(biāo)分割不完整。添加形狀先驗?zāi)芰亢?，使用圖割方法得到分割結(jié)果和標(biāo)記如圖5（c）。從圖中可以看到，錯誤部分得到了很大改善，分割效果得到了優(yōu)化。

圖5 horse097.jpg含遮擋物分割結(jié)果

圖6（a）為一幅彩色圖像。圖中人和馬都有影子，含有陰影遮擋。首先使用傳統(tǒng)圖割方法得到初始分割結(jié)果如圖6（b）。從結(jié)果圖中看出，陰影部分均還存在，沒有得到正確分割。在上述圖割算法中添加形狀先驗懲罰后，得到分割結(jié)果如圖6（c）。從圖中可以看到，陰影部分得到正確分割，分割結(jié)果得到了優(yōu)化。

圖7的圖像分割使用的模板是尺度縮放后的模板（a），和分割得到的標(biāo)記圖不相同，則使用上述匹配思想進行模板匹配，在此基礎(chǔ)上加入形狀先驗，得到結(jié)果如圖所示。圖8和圖9使用的先驗?zāi)０宸謩e是平移以后和旋轉(zhuǎn)以后的模板。

圖6 horse099.jpg含陰影遮擋分割結(jié)果

圖7 horse129.jpg的圖像分割結(jié)果

圖8 horse008.jpg的圖像分割結(jié)果

圖9 horse182.jpg的圖像分割結(jié)果

從表1看出，添加形狀先驗后的錯誤率大幅度下降，圖像分割效果良好，而耗時會增加，主要是由于增加形狀懲罰部分引起的，因為形狀懲罰是按圖像的像素點加進去的，所以需要逐個像素點來判斷，但是并沒有增加太多的時間復(fù)雜度。實驗數(shù)據(jù)進一步表明了本文算法的有效性和分割效率，表明了本文算法針對含噪、有遮擋或陰影的復(fù)雜圖像可以較完整地分割出目標(biāo)，取得了較好的結(jié)果。

表1 未含形狀信息和包含形狀信息的分割錯誤率和算法運行時間比較

4 結(jié)束語

傳統(tǒng)的圖割方法對簡單圖像的分割可以得到良好的效果，但是對于含有噪聲、遮擋物等的復(fù)雜的圖像，它的分割效果不能令人滿意，有的圖像目標(biāo)分割不完整，有的圖像分割結(jié)果包含雜質(zhì)或陰影等部分。本文提出的基于形狀先驗和圖割的圖像分割算法，比傳統(tǒng)的圖割方法分割精度高，特別是對上述提到的復(fù)雜圖像也能得到良好的分割結(jié)果，為圖割融合先驗知識提供了一種思路。文中選用一個形狀先驗?zāi)０?，對一些特定的目?biāo)分割具有局限性，只能分割和該形狀先驗?zāi)０逡粯踊蚍律洳煌哪繕?biāo)，對于和形狀模版有非剛性變形的目標(biāo)分割則不適用。針對該局限性，可以考慮采用多個形狀先驗?zāi)０?，以適應(yīng)局部和全局變形。

[1]Greig D，Porteous B，Seheult A.Exact maximum a posteriori estimation for binary image[J].Journal of the Royal Statistical Society：Series B，1989，51（2）：271-279.

[2]Boykov Y Y，Jolly M P.Interactive graph cuts for optimal boundary®ion segmentation of objects in N-D images[C]//Proceedings of Internation Conference on Computer Vision，July 2001.

[3]Ford L，F(xiàn)ulkerson D.Flows in networks[M].Princeton，New Jersey：Princeton University Press，1962.

[4]楊建功，汪西莉.一種結(jié)合圖割與雙水平集的圖像分割方法[J].計算機工程與應(yīng)用，2012，48（3）：195-197.

[5]Boykov Y，Veksler O，Zabih R.Fast approximate energy minimization via graph cuts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23（11）：1222-1239.

[6]Slabaugh G，Unal G.Graph cuts segmentation using an elliptical shape prior[C]//Proceedings of International Conference on Image Processing，2005：1222-1225.

[7]Veksler O.Star shape prior for graph-cut image segmentation[C]//Proceedigns of ECCV 2008，2008，5304：454-467.

[8]Vu N，Manjunath B S.Shape prior segmentation of multiple objects with graph cuts[C]//Proceedings of CVPR 2008，24-26 June，2008.

[9]Chan T，Zhu W.Level set based shape prior segmentation[C]//Proceedings of CVPR 2005，June 2005，2005：1164-1170.

[10]Pei S C，Lin C N.Imagenormalization for pattern recognition[J].Image and Vision Computing，1995，13（10）.

[11]Paragios N，Rousson M，Ramesh V.Non-rigidregistration using distancefunctions[J].Computer Vision and Image Understanding，2003，89（2/3）：142-165.

[12]Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.