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

牛文斐，汪西莉

陜西師范大學 計算機科學學院，西安 710062

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

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

1 基于圖割的圖像分割

1.1 圖割理論

圖割是一種基于圖論的組合優化方法，它將一幅圖像映射成一個網絡圖，其中像素點對應圖中的節點，相鄰像素點之間的關系對應圖中節點之間邊，并建立關于標號的能量函數，割的容量對應能量函數。運用最大流/最小割算法對網絡圖進行切割，得到網絡圖的最小割，即對應于待分割的目標邊界。

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

（1）構造能量函數，從而將分割問題轉化為能量函數最小化問題，該能量函數反映了圖像分割結果的好壞。

（2）根據圖像構造s-t網絡圖，這個圖將能量函數視為其中邊的集合，使能量與網絡圖的割相對應，從而將能量最小化問題轉化為求網絡圖最小割問題。

（3）根據最大流/最小割定理，將網絡圖最小割問題轉化為最大流問題。

（4）求得網絡圖的最大流，即對應著圖的最小割，從而得到能量函數的全局最優解，最終得到圖像分割結果[4]。

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

其中，數據項Edata(f)用來衡量像素p所分配的標號fp與觀察到的數據不一致性；光滑項Esmooth(f)用于約束鄰接像素間具有一致視差，它體現了區域內部的連續性和邊界的不連續性。不同的能量函數對應網絡圖中的邊所賦權值的方法是不同的，但能量函數最終是解決標號問題的。運用圖割算法求解能得到該能量函數的全局最優解。

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

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

2.1 形狀先驗模型

首先定義形狀先驗能量，根據文獻[8]中提到的運用Chan和Zhu[9]提出的形狀距離的描述形式，將形狀先驗能量通過終端邊緣權值合并到圖中。該方法中的形狀距離是對稱的，而且遵循了三角不等式，其使用的形狀模板是和待分割目標相同的二值形狀模板。

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

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

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

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

2.2 模板仿射變換

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

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

2.3 本文方法

2.3.1 算法設計

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

算法流程為：

步驟1首先選取一幅彩色圖像，對圖像構造s-t網絡圖，建立關于此標號的能量函數EA(f)，根據定義好的能量函數，確定圖的邊緣之間的權值。

步驟2在該網絡圖上運用最大流/最小割算法求得圖的最大流，即對應著最小割，從而得到初始的圖像分割結果。

步驟3在上述算法的基礎上，結合添加形狀先驗的思想，定義形狀先驗能量，在能量函數中添加形狀項，構成新的能量函數E(f)，然后把這些形狀能量通過終端邊緣權值合并到圖中。

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

2.3.2 能量函數的定義

算法步驟1和步驟3是建立關于標號的能量函數，本文選擇的能量函數形式為：

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

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

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

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

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

3 實驗結果與分析

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

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

圖1 horse320.jpg加入高斯噪聲分割結果

圖2 horse125.jpg加入高斯噪聲分割結果

圖3 horse321.jpg加入高斯噪聲分割結果

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

圖4 horse002.jpg加入遮擋物分割結果

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

圖5 horse097.jpg含遮擋物分割結果

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

圖7的圖像分割使用的模板是尺度縮放后的模板（a），和分割得到的標記圖不相同，則使用上述匹配思想進行模板匹配，在此基礎上加入形狀先驗，得到結果如圖所示。圖8和圖9使用的先驗模板分別是平移以后和旋轉以后的模板。

圖6 horse099.jpg含陰影遮擋分割結果

圖7 horse129.jpg的圖像分割結果

圖8 horse008.jpg的圖像分割結果

圖9 horse182.jpg的圖像分割結果

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

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

4 結束語

傳統的圖割方法對簡單圖像的分割可以得到良好的效果，但是對于含有噪聲、遮擋物等的復雜的圖像，它的分割效果不能令人滿意，有的圖像目標分割不完整，有的圖像分割結果包含雜質或陰影等部分。本文提出的基于形狀先驗和圖割的圖像分割算法，比傳統的圖割方法分割精度高，特別是對上述提到的復雜圖像也能得到良好的分割結果，為圖割融合先驗知識提供了一種思路。文中選用一個形狀先驗模板，對一些特定的目標分割具有局限性，只能分割和該形狀先驗模板一樣或仿射不同的目標，對于和形狀模版有非剛性變形的目標分割則不適用。針對該局限性，可以考慮采用多個形狀先驗模板，以適應局部和全局變形。

[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，Fulkerson D.Flows in networks[M].Princeton，New Jersey：Princeton University Press，1962.

[4]楊建功，汪西莉.一種結合圖割與雙水平集的圖像分割方法[J].計算機工程與應用，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.