林 強，董 平，林嘉宇

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

·微機軟件·

圖割方法綜述

林 強，董 平，林嘉宇

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

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

圖割；交互式；能量函數(shù)；分水嶺

1 引 言

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

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

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

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

第五類是基于能量的分割。該方法需要建立一個客觀的能量函數(shù)，當(dāng)圖像按預(yù)期結(jié)果分割時函數(shù)達到極小值，由此將圖像分割問題轉(zhuǎn)化為能量最小化問題。常見算法有Live wire［10］、活動輪廓［11］、水平集［12］和圖割［13］等。對于Live wire，種子必須位于目標(biāo)的邊界，最小化能量函數(shù)得到曲線最優(yōu)解?；诨顒虞喞膱D像分割模型是一個動態(tài)的二維或高維閉合曲線模型。它在模型內(nèi)力和外力的共同作用下向目標(biāo)邊界運動，最終到達平衡位置時即收斂到目標(biāo)邊緣，得到目標(biāo)的分割結(jié)果?；谒郊姆椒ㄒ彩窍冉o出初始曲線，讓曲線按照某種規(guī)則演變，使能量函數(shù)得到極小值。這兩種方法只利用邊界信息且對初始曲線非常敏感，運算時間比較大，且不易得到全局最優(yōu)結(jié)果。對于圖割分割，能量函數(shù)的構(gòu)造是基于區(qū)域和邊界信息，將圖像分割問題轉(zhuǎn)換為能量函數(shù)的優(yōu)化問題，通過合適的能量函數(shù)建立相應(yīng)的網(wǎng)絡(luò)圖，通過最大流/最小割算法求解網(wǎng)絡(luò)圖最小割，實現(xiàn)能量的全局最優(yōu)化，從而獲取圖像分割的結(jié)果。文中，首先介紹圖割分割的概念，然后介紹圖割分割的一些方法。

2 圖割分割

在本節(jié)中，將介紹圖割的概念以及如何建立圖割分割的圖像對應(yīng)的無向圖。

2.1 圖割概念

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

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

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

2.2 圖割分割

圖像分割可以視為像素標(biāo)記問題。目標(biāo)（s節(jié)點）的標(biāo)簽設(shè)置為1，背景（t節(jié)點）的標(biāo)簽設(shè)置為0，這個過程可以通過最小化能量函數(shù)實現(xiàn)。為了使分割合理，分割應(yīng)該在目標(biāo)和背景之間的邊界內(nèi)?？紤]一個數(shù)據(jù)集合（像素）P和用一個集合L表示的鄰域系統(tǒng)L＝｛l1，l2，...，li，...，lp｝，p是圖像像素的數(shù)量，li∈｛0，1｝。向量L定義一個分割，該分割的能量函數(shù)為以下方程，它可以在S－T圖中用最小割來最小化［13］：

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

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

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

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

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

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

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

3 圖割算法分類

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

3.1 基于加速的圖割

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

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

3.2 基于交互式的圖割

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

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

表1 交互式分割圖形權(quán)重表

表2 迭代后圖形權(quán)重表

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

3.3 基于形狀先驗的圖割

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

Eshape是形狀先驗項，目的是使目標(biāo)邊界的像素變小而遠(yuǎn)離目標(biāo)邊界的像素變大。有兩種能量形式表示形狀先驗，第一是選擇逼近目標(biāo)的中心點像素為參考點，設(shè)置該點像素值較高而其他點的值根據(jù)該像素點與中心像素點的距離逐步變小，在目標(biāo)內(nèi)部點的像素值較高在背景區(qū)域值較低。由于目標(biāo)中心值比模板其他位置相對較大，可將該模板的值與區(qū)域項結(jié)合。因此（10）式可改變?nèi)缦拢?/p>

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

因此，形狀模板的建立是很重要的，許多預(yù)分割目標(biāo)采用訓(xùn)練集來建立形狀先驗?zāi)０濉４送?，?xùn)練集的排列也將影響模板與圖像的匹配，進而得到改進的能量模型。

4 總結(jié)與展望

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

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

［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(xiàn) 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，F(xiàn)ulkerson 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］.紅外與毫米波學(xué)報，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，F(xiàn)rance：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