圖割方法綜述

林 強，董 平，林嘉宇

（國防科技大學電子科學與工程學院，長沙410073）

·微機軟件·

圖割方法綜述

林 強，董 平，林嘉宇

（國防科技大學電子科學與工程學院，長沙410073）

介紹了近年來圖像分割方法及圖割的研究進展。首先將現有的多種類型圖像分割方法歸結為五類典型方法，并分析各自的特性；接著詳細介紹圖割的概念和圖割的三種分割方法，每種方法的應用現狀和特性；最后指出了圖割的一些研究方向。

圖割；交互式；能量函數；分水嶺

1 引 言

圖像分割是將圖像分割成不同的有類似顏色、強度或紋理的區域［1］。圖像分割作為預處理步驟在計算機視覺、目標識別、跟蹤和圖像分析等領域起著顯著作用。通常，圖像分割分成五類：第一類是基于閾值的分割方法。它是利用圖像的灰度直方圖信息得到分割閾值，將圖像分成目標和背景，從而實現對圖像的分割。閾值法包括單閾值分割［2］、多閾值分割［3］和可變閾值分割。基于閾值的方法實現簡單，算法也比較簡單，特別針對目標和背景差異比較大的圖像。缺點是不容易找到合適的閾值，容易受到噪聲的影響，難以處理多個目標的情況。最常用的閾值算法有最小誤差法［4］、最大類間方差法［5］、模糊集法［6］、最大熵分割算法［7］等。

第二類是基于邊緣的分割方法。該方法假定不同區域的像素值是不同的，通過特征的不連續來檢測區域邊緣，由此實現區域分割。這些不連續通常用第一階或第二階導數法來檢測，如Laplace算法［8］。而基于梯度的Sobel［1］、Roberts和Prewitt算法比較容易實現，并且可以粗略檢測輪廓外形，但它們和Laplace算法一樣，對圖像的噪聲很敏感。由此，引入LOG算法，通過高斯濾波器平滑圖像，然后利用Laplace算子降低噪聲影響。這些算法都有一個缺點，不能夠得到連續完整的邊緣，因此需要進一步對邊緣進行修正。常用的邊緣修正的方法有相位編組法、啟發式連接和層次記號編組法等。

第三類是基于區域的分割方法。區域分割方法利用局部空間信息進行分割，將具有相似特征的像素集合起來構成區域，區域分割法分為區域生長和區域分裂合并［1］。區域生長算法是在每個區域中找一個或多個種子像素點作為生長的起點，然后相鄰像素根據預定義準則來分組，直至沒有可以歸并的點為止。區域分裂合并算法先將圖像劃分成一系列小區域，然后按照某種準則進行分裂或合并區域。因此區域分裂合并算法的研究重點是對分裂和合并的準則設計。基于區域的分割方法可以有效消除噪聲干擾，算法上具有較強的魯棒性，但分割速度較慢。

第四類是基于分水嶺的分割方法［9］。該方法把圖像看作拓撲面，把像素值看作高度。圖像區域的最低值定義為集水區，兩個相鄰的集水區之間的最大值稱為脊線，即分水嶺，基于分水嶺的分割算法就是在圖像中找分水嶺。該算法適用于目標對應為集水區，邊界對應為分水嶺的梯度圖像。缺點是容易受到噪聲和不規則梯度的影響，有時還會存在過度分割的問題。通常通過標記控制方法來減少過度分割。

第五類是基于能量的分割。該方法需要建立一個客觀的能量函數，當圖像按預期結果分割時函數達到極小值，由此將圖像分割問題轉化為能量最小化問題。常見算法有Live wire［10］、活動輪廓［11］、水平集［12］和圖割［13］等。對于Live wire，種子必須位于目標的邊界，最小化能量函數得到曲線最優解。基于活動輪廓的圖像分割模型是一個動態的二維或高維閉合曲線模型。它在模型內力和外力的共同作用下向目標邊界運動，最終到達平衡位置時即收斂到目標邊緣，得到目標的分割結果。基于水平集的方法也是先給出初始曲線，讓曲線按照某種規則演變，使能量函數得到極小值。這兩種方法只利用邊界信息且對初始曲線非常敏感，運算時間比較大，且不易得到全局最優結果。對于圖割分割，能量函數的構造是基于區域和邊界信息，將圖像分割問題轉換為能量函數的優化問題，通過合適的能量函數建立相應的網絡圖，通過最大流/最小割算法求解網絡圖最小割，實現能量的全局最優化，從而獲取圖像分割的結果。文中，首先介紹圖割分割的概念，然后介紹圖割分割的一些方法。

2 圖割分割

在本節中，將介紹圖割的概念以及如何建立圖割分割的圖像對應的無向圖。

2.1 圖割概念

設一個無向圖G＝＜V，E＞，V是圖中兩種不同類型節點的集合，定義V＝｛s，t｝∪P，P表示對應圖像像素的點集，s和t表示兩個特殊的頂點或稱為終端，通常一個稱為源點s，代表目標，一個稱為匯點t，代表背景。這種圖形也被稱為S－T圖。

在圖中，也有兩種類型的邊，n－links和tlinks，n－links連接圖像內相鄰的像素p、q，t－links連接像素和終端，每個像素有兩條t－links，｛p，s｝和｛p，t｝。每條邊都被賦予一個非負權重We，也被稱為代價。圖G的一個割C是邊集E的一個子集，將圖G的兩個終端分離（即兩個終端之間沒有邊連接），而對于C的任一子集，均不能將兩個終端分離。割C的代價（記作｜C｜）定義為組成割C的所有邊的權重總和，表示如下：

最小割就是圖G中所有割代價最小的割，它根據L.Ford and D.Fulkerson［16］提出的網絡流理論，通過尋求網絡圖的最大流而得到。文獻［17］證實，該最小割相當于最大流，而這個最小割正是要求解的能量函數的全局最優值。因此，該圖節點被分為兩個互不相交的子集S和T，s∈S、t∈T且S∪T＝V。兩個子集對應圖像的目標和背景。

2.2 圖割分割

圖像分割可以視為像素標記問題。目標（s節點）的標簽設置為1，背景（t節點）的標簽設置為0，這個過程可以通過最小化能量函數實現。為了使分割合理，分割應該在目標和背景之間的邊界內。考慮一個數據集合（像素）P和用一個集合L表示的鄰域系統L＝｛l1，l2，...，li，...，lp｝，p是圖像像素的數量，li∈｛0，1｝。向量L定義一個分割，該分割的能量函數為以下方程，它可以在S－T圖中用最小割來最小化［13］：

其中，R（L）表示包括區域分割信息的區域項，B（L）表示約束邊界分割的邊界項，μ是區域項和邊界項之間的相對因子。區域項R（L）定義如下：

Rp（lp）是像素p到目標和背景的處罰，可以通過比較像素p與目標和背景強度的直方圖獲得。t－links的權重定義如下：

從上式看到，當Pr（Ip｜′obj′）大于Pr（Ip｜′bkg′）時，Rp（1）小于Rp（0），因此，當所有的像素正確分成兩個子集時，區域項減小到最低程度。邊界項B（L）定義如下：

其中，p、q是相鄰像素，δ（lp，lq）定義如下：

當相鄰像素具有相同的標簽時，處罰為0。B＜p，q＞定義如下：

σ看作是圖像的噪聲，Ip和Iq表示像素p、q的強度值，‖p－q‖是像素p與q的歐式距離。Yuri Boykov和Vladimir Kolmogorov［17］發現能量函數的極小值可以通過最大流最小割計算，把能量最小問題轉化為圖割問題。

根據能量優化的觀點求解最小圖割，是目前圖割的主要求解方法。該方法需要根據圖像的特征信息，建立合適的能量函數，然后根據能量函數，建立圖論中的網絡圖，通過對網絡圖采用最大流/最小割算法，獲得分割結果。從理論上講，基于圖割的能量函數最小化方法，可以提供能量函數的全局最小化。因此對特定領域里一些有爭議的問題，可利用基于圖割的能量最小化方法，得到準確的解決方式，以期得到更好的分割結果。

3 圖割算法分類

在本節中，我們將圖割基礎技術分為三類：第一類是基于加速的圖割，旨在改善以圖割為基礎的方法的速度；第二類是基于交互式的圖割，將用戶的交互融入到分割中，從而改善分割結果；第三類是基于形狀先驗的圖割，將目標之前的形狀納入考慮范圍，使分割更為合理。

3.1 基于加速的圖割

按照慣例，圖像中每個像素都被看作是圖的一個節點，隨著圖像分辨率的增加，圖像越來越大，導致圖形的計算加大，速度變慢。為了加快圖割算法的計算，人們研究相應的方法。V.Vineet和P.J.Narayanan［18］建議應用基于CUDA分割的GPU硬件加速，相對于串行計算，該方法采用具有良好性能的并行計算達到加速目的，但效果不是很好。另外一種常用的方法是在圖的重建過程中減少圖的節點。在大多數情況下，目標比較集中，只占據圖像的一個小區域，由此可以只考慮分割覆蓋目標的相對較小的一部分，使圖像像素減少，節點也相應減少，該部分可以由用戶輸入或通過一些匹配算法進行［15］。此外，當兩個相鄰像素強度非常相似時，在圖中的權重也非常大，這意味著這兩個像素不會分開，換句話說，可以把這兩個像素看作是一個像素，以此類推。這種由許多相似的像素點組合在一起，將它們作為一個整體來替代原有像素點，這個整體稱之為超像素，這是集群的一種應用方法。生成超像素的算法主要分為兩類：基于圖論的方法和基于梯度上升的方法。基于圖論的分割方法的本質就是移除特定的邊，將圖劃分為若干子圖從而實現分割；基于梯度上升的分割方法是指先獲得一個不精確的粗略聚類，在后面每一次的迭代過程中，利用梯度上升的方法去改進在上一次迭代的聚類結果，直到最后收斂為止。在圖割中生成超像素最常用的算法是分水嶺方法［17］。在分水嶺算法的基礎上，把相似強度的小區域歸為一個集群，把這些集群作為圖割新圖的點，分水嶺的計算過程是一個迭代標注過程。該水域重新分割后，每個集群的平均強度作為新的像素點值（超點）。因此，t－links的權重可以通過比較超點與目標背景直方圖的強度值來設置，與（4）（5）類似，而n－links的權重可以通過下面的等式計算［17］：

其中，gradij（i）是集群i平均梯度值，j是其相鄰集群。此外，還可以將兩種方法結合，也即分水嶺不需要在整個圖像，只需要在圖像的某些部分應用就可以了。在文獻［15］中，只有邊界附近區域是基于分水嶺的圖割；馬秀麗等［17］基于分水嶺算法都使圖的頂點數大大減少，取得了較好的實時性。分水嶺算法的優點是可獲得微弱邊緣的良好響應，精度較好速度快，可以保證封閉連續邊緣。但是由于圖像噪聲及細節信息等影響，該算法常常會產生過分割的現象。基于加速的圖割特別是基于分水嶺的圖割廣泛應用于醫療影像、工業圖像、自然圖像等不同種類［18－20］。

3.2 基于交互式的圖割

對大多數圖像而言，完全自動分割是很困難的，特別是對目標精度要求比較高的圖像，進行交互式分割是不可避免的。基于交互式的圖割首先選擇簡單的區域或者單一的種子節點，其次是迭代的種子節點。在［15］里，使用邊界框選定目標區域，邊界外部區域看作背景，邊界框的中心當作目標。在［13］中，迭代的交互式圖割得到了應用。當結果不完美時，更多的種子節點被添加，直到分割到滿意的目標。迭代交互式分割在目標的周邊有較好的魯棒性。通常，交互式分割的圖形權重可以從表1得到，圖表示為G＝＜V，E＞，其中V＝P∪｛S，T｝［13］。

當一點分為目標，這點與S節點的權重就比較高，而與T節點的權重則為0，若該點為背景，則相反。在迭代的交互式分割中，邊的權重會動態改變，一輪圖割過后，一些新的點選定為目標或背景，權重會按上表的方式更新，而后圖割再次運行。新選定的節點權重如表2所示。

表1 交互式分割圖形權重表

表2 迭代后圖形權重表

當新的點選為目標或背景，新的權重不會改變先前的最優分割，這意味著可以用基于先前的最大流獲得最優分割，這種方法用在大部分的交互式迭代算法中，但是分割效率不是很好。

3.3 基于形狀先驗的圖割

由于噪聲或目標被遮擋、污染，邊緣擴散等影響，傳統的圖割僅僅考慮區域和邊緣的信息，不容易得到理想的分割結果，基于交互式的圖割可以適當減少這類程度的問題，但影響分割效率。此時要想得到更好的分割結果，一個比較好的辦法是在分割過程中融入形狀先驗知識。如何將形狀先驗信息轉化為能量函數，從而提高分割效果，許多研究者做了大量工作。Slabaugh［21］等提出了一種基于橢圓形狀與圖割的分割技術，該方法用橢圓表示形狀先驗，并將其添加到能量函數的區域項中，對含有噪聲、遮擋物的圖像有較好的分割結果，但對高度不同的圖像具有很大限制。Nhat Vu［22］等定義了離散形狀的形狀先驗，并將其通過邊緣權值合并到圖中，該方法的形狀模板比較單一，對和形狀模板有差異的目標無法得到較好的分割效果。Veksler［23］采用星形先驗信息，沒有局限于具體形狀，可部分解決多目標問題，但不能區分目標。Wang［24］等提出了自適應形狀先驗方法，主要思想是目標的邊緣信息越少，越需要更強的形狀先驗信息，但該方法只適用于灰度圖像等。在大多數情況下，將形狀先驗項添加到能量函數中，通常定義如下方程：

Eshape是形狀先驗項，目的是使目標邊界的像素變小而遠離目標邊界的像素變大。有兩種能量形式表示形狀先驗，第一是選擇逼近目標的中心點像素為參考點，設置該點像素值較高而其他點的值根據該像素點與中心像素點的距離逐步變小，在目標內部點的像素值較高在背景區域值較低。由于目標中心值比模板其他位置相對較大，可將該模板的值與區域項結合。因此（10）式可改變如下：

另一種先驗信息能量形式也是采用距離比較，但設置目標邊界區域的值為零，靠近目標邊界區域的值比較小，而其他值比較大，這種形狀信息的能量被納入到邊界項中，表示如下：

因此，形狀模板的建立是很重要的，許多預分割目標采用訓練集來建立形狀先驗模板。此外，訓練集的排列也將影響模板與圖像的匹配，進而得到改進的能量模型。

4 總結與展望

在文中，簡要介紹了圖像分割方法與圖割的優勢，還詳細介紹了圖割的概念，而后將基于圖割的眾多分割方法分為三類：基于加速的圖割、基于交互式的圖割和基于形狀先驗的圖割。這種分類有助于研究者理清研究方向，而且這些圖割方法往往相互組合應用以提高分割效果。

圖像分割是計算機視覺研究中的一個難以解決的問題。國內外學者進行了廣泛而深入的研究，提出了各種分割方法，但至今尚無比較完整的理論體系，沒有普遍的適用性。基于圖割的圖像分割，是目前圖像分割領域一個新的研究熱點，因其具有獨特的優勢，得到了很多研究者的青睞。然而這一種新的圖像分割方式，還有大量問題有待研究和解決，例如如何克服現有圖割方法的不足、如何擴展圖割方法的應用范圍以及如何將其他一些經典方法融入圖割當中等。與此同時，將多種圖割方法綜合運用，得到具有較強適應性和快速高效的分割方法也是今后的一個研究重點。總而言之，圖像分割方法正朝著更快速、更精確的方向發展，將不斷完善圖像分割的理論體系，取得新的突破和創新。

［1］ Gonzalez R C，Woods R E.Digital Imaging Processing［M］.Prentice Hall：New York，NY，USA，2002.

［2］ Bernsen J.Dynamic thresholding of gray—level images［J］.InProc 81CPR，1986：1251－1255.

［3］ SBoukaharouba，JM Rebordao，R L Wendel.An amplitude segmentation method based on the distribution of an image.Computer Vision［J］.Graphics and Image Processing，1985，29：47－59.

［4］ Chow C K，Kaneko.Automatic boundary detection of left ventricle from cineangiograms［J］.Compat Biomed Res，1972（5）：388－410.

［5］ Nobuyuki Otsu.A threshold selection method from gray level histogram［J］.IEEE Trans on System，Man and Cybemetics，1979，9（1）：62－66.

［6］ Pal S K，King R A，Hashim A.A Automatic grey level thresholding through index of fuzziness and entropy［J］.Patt ern Recognit ion Letters，1983，1（3）：141－146.

［7］ Kapur JN，Sahoo P K，Wong A K C.A new method for gray level picture thresholding using the entropy of the histogram［J］.Computer Vision，Graphics and Image Processing，1985，29（3）：273－285.

［8］ S Raut，M Raghuvanshi，R Dharaskar，A Raut.Image Segmentation－A State－of－Art Survey for Prediction［J］.ICACC，2009：420－424.

［9］ S Naz，H Majeed，H Irshad.Image segmentation using fuzzy clustering：A survey［J］.International conference on emerging technologies，2010：181－186.

［10］ A X Falcao，J K Udupa，F K Miyazawa.An ultra－fast user－steered image segmentation paradigm：live wire on the fly［J］.IEEE trans on Medical Imaging，2002，19（1）：55－62.

［11］ G Sundaramoorthi，A Yezzi，A C Mennucci.Coarseto－Fine Segmentation and Tracking Using Sobolev Active Contours［J］.IEEE trans on Pattern Analysis and Machine Intelligence，2008，30（5）：851－864.

［12］ R M Willett，R D Nowak.Minimax Optimal Level－Set Estimation［J］.IEEE trans on Image Processing，2007，16（12）：2965－2979.

［13］ Y B Yuri，G F Lea.Graph Cuts and Efficient N－D Image Segmentation［J］.Intenational Journal of Computer Vision，2006，70（2）：109－131.

［14］ Ford L，Fulkerson D.Flow s in Netw or ks［M］.New Jersey.Princeton Univer sity Press，1962.

［15］ Y Boykov，V Kolmogorov.An experimental comparison of mincut/max－flow algorrithms for energyminimization in vision［J］.IEEE trans on PAMI，2004，26（9）：1124－1137.

［16］ V Vineet，P J Narayanan.CUDA cuts：Fast graph cuts on the GPU［C］.IEEE conference on CVPRW，2008：1－8.

［17］ 馬秀麗，焦李成.基于分水嶺－譜聚類的SAR圖像分割［J］.紅外與毫米波學報，2008，27（6）：452－456.

［18］ Z Yu，M Xu，Z Gao.Biomedical image segmentation via constrained graph cuts and presegmentation［C］.International conference of the IEEE on EMBC，2011：5714－5717.

［19］ XWu，W Xu，L Li，G Shao，JZhang.An Interactive Segmentation Method Using Graph Cuts for Mamographic Masses［C］.International conference on iCBBE，2011：1－4.

［20］ X Wu，Y Wang.Interactive Forreground/Background Segmentation Based on Graph Cut［C］.Congress on Image and Signal processing，2008：692－696.

［21］ Slabaugh G，Unal G.inInt.Graph cuts segmentation using an elliptical shape prior［C］.inIntConf.on Image Processing，2005：1222－1225.

［22］ Nhat V，Manjunath B.Shape prior segmentation ofmuttiple objects with graph cuts［C］.In proc.IEEE conference on computer vision and pattern recognition，2008：1－8.

［23］ Veksler O.Star shape prior for graph－cut image segmentation［J］.Procedings of the 10th European Conference on Com puter Vision［C］.Mar seille，France：Springer，2008：454－467.

［24］ Wang H，Zhang H.Adaptive shape prior in graph cut image segmentation［J］.Pattern Recognition，2012（11）：1－6.

A Survey on Graph Cut Techniques

Lin Qiang，Dong Ping，Lin Jiayu
（School of Electronic Science and Engineer，National University Defense Technology，Changsha 410073，China）

The image segmentationmethods and the research progress of graph cut in recent years are introduced in this paper.At first，image segmentation methods are classified into five typical types，and their characteristics are analyzed.Secondly，the concept of graph cut and three categories of graph cut，and applications and characteristics of each category are described in details.Finally，some directions of graph cut is presented.

Graph cut；Interactive；Energy function；Watershed

10.3969/j.issn.1002－2279.2015.01.011

TP391

A

1002－2279（2015）01－0035－05

林強（1982－），男，福建福州人，工程碩士，主研方向：圖形圖像處理。

2014－08－11