陳　杏　李　軍

(1.西安工業(yè)大學(xué)電子信息工程學(xué)院　西安　710021)(2.西安工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院　西安　710021)

?

基于圖論的分割算法研究綜述*

陳杏1李軍2

(1.西安工業(yè)大學(xué)電子信息工程學(xué)院西安710021)(2.西安工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院西安710021)

圖像分割是計(jì)算機(jī)視覺領(lǐng)域中的經(jīng)典問題之一,基于圖論的分割算法因其良好的時間性能與分割效果成為眾研究者新的關(guān)注點(diǎn)。論文在對圖像分割算法綜述的基礎(chǔ)上,重點(diǎn)介紹了基于圖論的分割算法并且通過實(shí)際仿真分別從時間性能與分割效果上對Grab Cut與One Cut算法進(jìn)行了比較。最后對當(dāng)前該領(lǐng)域存在的問題與發(fā)展方向進(jìn)行了總結(jié)。

圖像分割; 能量優(yōu)化; 迭代最小化; 最優(yōu)二元分割

Class NumberTP391.41

1　引言

所謂圖像分割指的是根據(jù)灰度、顏色、紋理和形狀等特征把圖像劃分成若干互不交迭的區(qū)域,并使這些特征在同一區(qū)域內(nèi)呈現(xiàn)出相似性,而在不同區(qū)域間呈現(xiàn)出明顯的差異性[1]。圖像分割不僅是由圖像處理到圖像分析的關(guān)鍵步驟,而且是計(jì)算機(jī)視覺的一種基本技術(shù)。若想實(shí)現(xiàn)目標(biāo)特征提取與參數(shù)測量,圖像分割是其必須經(jīng)歷的步驟,也使得更深層次的圖像分析和理解成為可能。針對圖像分割領(lǐng)域的研究已經(jīng)出現(xiàn)了很多算法,但是近些年來,基于圖論的圖像分割已經(jīng)成為該領(lǐng)域研究的熱點(diǎn)與方向?；趫D論的圖像分割算法將圖像分割映射為加權(quán)圖的形式,其像素及其顏色、灰度等特征信息分別代表圖中的頂點(diǎn)及其屬性,像素之間的鄰接關(guān)系對應(yīng)于圖的邊集,邊的權(quán)重顯示出對應(yīng)像素的差異度。

圖像處理技術(shù)不僅在諸多領(lǐng)域扮演著舉足輕重地角色,而且圖像分割是圖像進(jìn)行處理的鍵環(huán)節(jié)之一及基于圖論的圖像分割理論的前沿性,使針對該類圖像分割技術(shù)的研究具有較大的價(jià)值與應(yīng)用前景。

2　圖像分割方法概述

針對圖像分割技術(shù)的研究已經(jīng)經(jīng)歷了很長時間,伴隨著計(jì)算機(jī)技術(shù)與機(jī)器視覺的不斷發(fā)展,圖像處理技術(shù)越來越受到國內(nèi)外研究者及各行各業(yè)的重視。其中,針對圖像分割領(lǐng)域中的算法研究也是層出不窮,但至今仍然找不到一個適用于所有類型圖像的分割方法,而對于圖像分割算法的依據(jù)也是不唯一。本節(jié)將對當(dāng)前主流的圖像分割算法的進(jìn)行歸納與總結(jié),如圖1所示為圖像分割算法分類示意圖。

圖1　圖像分割算法分類示意圖

2.1基于閾值的分割算法

基于閾值的分割[2～4]是通過單個或多個閾值將圖像的灰度直方圖分成幾類,認(rèn)為圖像中灰度值在同一灰度級別的像素屬于同一物體。閾值分割法先確定適當(dāng)?shù)姆指铋撝?然后將圖像中所有像素的灰度級與該閾值進(jìn)行比較,從而可對區(qū)域進(jìn)行劃分,達(dá)到圖像分割的目的?；陂撝档姆指钏惴ㄖ饕譃槿N：基于點(diǎn)、區(qū)域的全局及局部與多閾值方法。

2.2基于邊緣的分割算法

基于邊緣的圖像分割[5～7]是基于目標(biāo)對象的邊緣灰度變化較大的特點(diǎn),利用邊緣檢測的方法將目標(biāo)對象所屬區(qū)域進(jìn)行提取的分割方法。由于該方法是利用圖像區(qū)域間的不同性質(zhì)對區(qū)域進(jìn)行劃分處理,通常不僅會產(chǎn)生目標(biāo)對象邊緣的斷點(diǎn)現(xiàn)象,而且可能產(chǎn)生錯誤的邊緣。按照處理順序可以將邊緣分割技術(shù)分為串行與并行邊緣檢測。

2.3基于區(qū)域的分割算法[8]

基于區(qū)域的分割算法是按照相似性準(zhǔn)則對圖像進(jìn)行劃分,其方法可歸納為區(qū)域生長法、分裂合并法等幾種類型。

1) 區(qū)域生長法

區(qū)域生長法是根據(jù)同一物體區(qū)域內(nèi)像素的相似性對像素進(jìn)行聚集的方法,從初始區(qū)域開始,將相同屬性的相鄰像素或區(qū)域歸并于當(dāng)前區(qū)域從而達(dá)到區(qū)域逐步擴(kuò)散的目的,直至該圖像中不存在可以進(jìn)行歸并的像素點(diǎn)或區(qū)域。

2) 分裂合并法

分裂合并法首先將圖像分成若干互不相交的區(qū)域,然后按照相關(guān)規(guī)則對區(qū)域進(jìn)行分裂或合并從而實(shí)現(xiàn)分割目的,該方法適用于灰度圖像與紋理圖像分割。

2.4基于圖論的分割算法

基于圖論的分割算法將圖的最小割問題應(yīng)用于圖像分割領(lǐng)域。該算法首先將圖像映射為帶權(quán)無向圖G=〈V,E〉,圖中每個節(jié)點(diǎn)N∈V對應(yīng)于圖像中的每個像素,每條邊∈E連接著一對相鄰的像素,邊的權(quán)值表示了相鄰像素之間非負(fù)相似度(灰度、顏色或紋理)。對圖像一個分割S相當(dāng)于一次剪切處理,每個被分割的區(qū)域C∈S與圖中一個子圖相對應(yīng)。基于圖論的分割方法的實(shí)質(zhì)是移除特定的邊,將圖劃分為若干子圖從而達(dá)到分割的目的。目前所了解基于圖論的方法有Graph Cut、Grab Cut和One Cut等。

2.5基于能量泛函的分割算法

基于能量泛函的分割算法是指活動輪廓模型(Active Contour Model)及在其基礎(chǔ)上衍生出的相關(guān)算法,其基本思想是將目標(biāo)對象的邊緣用連續(xù)曲線進(jìn)行表達(dá),并定義一個能量泛函使得其自變量包括邊緣曲線,因此分割過程就轉(zhuǎn)變?yōu)榍蠼饽芰糠汉淖钚≈颠^程。按照模型中曲線表達(dá)形式的不同,活動輪廓模型可以分為兩大類：參數(shù)活動輪廓模型(Parametric Active Contour model)和幾何活動輪廓模型(Geometric Active Contour Model)。

3　基于圖論的分割算法

在上文針對圖像分割算法分類介紹的基礎(chǔ),本節(jié)就基于圖論的分割算法展開詳細(xì)的介紹。依據(jù)其算法發(fā)展的歷程,分別就Graph Cut、Grab Cut與One Cut算法原理進(jìn)行深層次地理解與探討。

3.1Graph Cut算法[9]

在圖像處理與機(jī)器視覺中,很多問題最后都是匯聚于解決一個最小化能量函數(shù)的問題。由于該問題需要在一個相當(dāng)高維數(shù)空間求解一個非凸函數(shù)的最小化,以致在此問題的最優(yōu)化上顯的較為困難。Graph Cuts方法可對一類具有某種特定形式的能量函數(shù)得到快速而有效地最優(yōu)解,導(dǎo)致該方法受到越來越多的關(guān)注。20世紀(jì)90年代末Boykov等將該技術(shù)應(yīng)用于圖像分割領(lǐng)域,并提出了該算法。

3.1.1S-T圖像映射結(jié)構(gòu)

首先用一個無向圖G=〈V,E〉表示要分割的圖像,V和E分別是頂點(diǎn)(vertex)和邊(edge)的集合。如圖2所示為圖像轉(zhuǎn)換成圖結(jié)構(gòu)后對應(yīng)的S-T圖,圖中每個頂點(diǎn)對應(yīng)于圖像中每個像素,在此基礎(chǔ)上還另外增加了頂點(diǎn)S與T。S-T圖中存在兩種類型的邊,實(shí)線表示兩個鄰域頂點(diǎn)相連形成的邊(n-links),虛線表示每個頂點(diǎn)與S和T相連形成的邊(t-links)。在前后景分割中,S一般表示前景目標(biāo),T一般表示背景。若邊集合中的所有邊斷開將會導(dǎo)致“S”與“T”圖的分開,故將其稱為“割”。若一個割的過程中其對應(yīng)邊的所有權(quán)值之和最小,就將其稱為最小割。

圖2　S-T圖

3.1.2最小割S-T圖

由Boykov和Kolmogorov發(fā)明的最大流(Max-Flow)/最小割(Min-Cut)算法可以達(dá)到S-T圖的最小割目的。最小割可以將圖的頂點(diǎn)劃分為兩個沒有交集的集合S與T,其中s∈S,t∈T和S∪T=V。此時S與T分別代表了前景和背景的像素集,同時意味著圖像分割過程的結(jié)束。

假設(shè)整幅圖像的標(biāo)簽label為L= {l1,l2,…,lp},其中l(wèi)i為0(背景)或者1(目標(biāo))。那假設(shè)圖像的分割為L時,圖像的能量可以表示為

E(L)=aR(L)+B(L)

R(L)為區(qū)域項(xiàng),B(L)為邊界項(xiàng)。a為區(qū)域項(xiàng)與邊界項(xiàng)之間的影響因子,決定了二者對能量的影響程度。E(L)為能量函數(shù),圖割的目標(biāo)就是優(yōu)化該能量函數(shù)并使其值最小化。區(qū)域項(xiàng)(t-links)中邊的權(quán)值計(jì)算公式為

Rp(lp)能量項(xiàng)的權(quán)重可以通過將像素p的灰度與給定目標(biāo)和背景的灰度直方圖進(jìn)行比較而獲得,即像素p屬于標(biāo)簽lp的概率,所以t-links的權(quán)值如下：

Rp(1)=-lnPr(lp|′obj′)

Rp(0)=-lnPr(lp|′bkg′)

邊界項(xiàng)：n-links中每條邊權(quán)值如下：

其中

p和q為相鄰像素,邊界項(xiàng)體現(xiàn)分割L的邊界屬性,B〈p,q〉表示像素p與q之間不連續(xù)的程度。

在確定了每條邊的權(quán)重后,可以通過mincut算法對圖像進(jìn)行最小割處理,這些邊的斷開既實(shí)現(xiàn)了對目標(biāo)與背景的分離,又實(shí)現(xiàn)了能量的最小化。

3.2GrabCut算法[10]

GrabCut算法是在GraphCut算法的基礎(chǔ)上進(jìn)行改進(jìn)而產(chǎn)生的一種新的圖像分割算法。該算法利用圖像中的紋理與邊界信息,只需用戶少量的交互操作就可以得到較為滿意的分割結(jié)果。若目標(biāo)與背景之間的色差較大將會影響分割的效果。

GrabCut在GraphCut算法的基礎(chǔ)上做出的改進(jìn)工作可以歸納為以下幾點(diǎn)：

1)GraphCut中目標(biāo)與背景的模型采用灰度直方圖,而GrabCut將其改為RGB三通道的混合高斯模型(GMM);

2)GraphCut中能量最小化是一次性達(dá)到,而GrabCut采用交互迭代的方式對其進(jìn)行分割估計(jì)與模型參數(shù)的學(xué)習(xí);

3)GraphCut需要用戶指定目標(biāo)與背景的一些種子像素點(diǎn),而GrabCut只需提供背景區(qū)域的像素集。若需要分割的結(jié)果更加精確,可以在初次分割的基礎(chǔ)上提供一些確定的種子像素點(diǎn),在運(yùn)行該算法即可。

3.2.1顏色空間模型

GrabCut對圖像采用RGB顏色空間,分別用一個k割高斯分量的全協(xié)方差混合高斯模型(GMM)對目標(biāo)及背景進(jìn)行模型的建立。在該過程中衍生出向量K= {k1,…,kn,…,kN},其中kn是第n個像素對應(yīng)的高斯分量,kn∈{1,…,K},則可以將整個圖像的Gibbs能量定義為

結(jié)合高斯模型,其中U的定義為

參數(shù)β由圖像對比度決定,如果圖像對比度較低,像素m和n的差‖zm-zn‖比較小,此時需乘一個較大的β放大這種差別;如果圖像對比度較高,像素m和n的差‖zm-zn‖比較大,那么此時需乘以一個較小的β縮小這種差別。這樣就使得V項(xiàng)在對比度高或低的情況下均可正常工作,此時可以對該圖進(jìn)行分割操作了。

3.2.2初始化

迭代能量最小化分割算法的初始化過程如下:

1) 通過用戶框選目標(biāo)來得到初始的trimapT,可將框外像素視為背景像素TB,而框內(nèi)像素TU可視為目標(biāo)的可能像素;

2) 初始化TB內(nèi)的每一像素n的標(biāo)簽αn=0;初始化TU內(nèi)的每個像素n的標(biāo)簽αn=1;

3) 經(jīng)過上述過程,可以得到目標(biāo)與背景的一些像素。通過這些像素可進(jìn)行目標(biāo)和背景GMM的估計(jì)。首先通過k-mean算法將目標(biāo)和背景的像素聚類為K類,其次通過RGB值估計(jì)參數(shù)均值和協(xié)方差,最后通過該高斯分量中的像素?cái)?shù)目與像素總數(shù)的比值確定高斯分量的權(quán)值。

3.2.3迭代最小化

迭代最小化的算法過程如下:

4) 重復(fù)1)和3),直至收斂;

5) 采用bordermatting對分割的邊界進(jìn)行平滑等等后期處理。

3.3OneCut算法[11]

Tang等在GrabCut算法的基礎(chǔ)上提出了OneCut圖像分割算法,GrabCut算法通過迭代的圖切割來達(dá)到預(yù)期的圖像分割目的,而OneCut算法是通過一次圖切割便可以得到預(yù)期的結(jié)果,并在時間和分割效果上均優(yōu)于GrabCut算法。

OneCut算法使用快速全局最優(yōu)二元分割技術(shù),明確了最小化目標(biāo)、背景顏色分布之間的表觀重疊,其一次圖切割最小化能量函數(shù)表達(dá)式如下：

其中,R?Ω表示包圍盒對應(yīng)的二元碼,S?Ω是一個分割段,ls={sp|p∈Ω}是S?Ω的特征函數(shù)。第一項(xiàng)與第二項(xiàng)分別表示包圍盒R的一個標(biāo)準(zhǔn)膨脹與表觀重疊懲罰項(xiàng);最后一項(xiàng)是對比敏感平滑項(xiàng),其展開式為

|?S|=∑wpq|sp-sq|

Nn指n(I)元素個數(shù),n(I)的值表示圖像I中相鄰像素對集合

β′是一個全局參數(shù),經(jīng)實(shí)驗(yàn)得出β′=0.9,λ=9。

用戶根據(jù)特定圖像提供一個其感興趣的目標(biāo)矩形包圍盒,矩形包圍盒外面的像素使用硬性約束分配為背景,又可以將分割能量函數(shù)簡化為以下形式：

由于One Cut算法對矩形框比較敏感,則需要用戶繪制的矩形框要完全覆蓋目標(biāo),并且盡可能小。該方法使用了少量的輔助節(jié)點(diǎn)實(shí)現(xiàn)了高效率的圖像分割,與Grab Cut算法相比,對于復(fù)雜圖像來說該算法依然具備很好的分割效果與時間性能。

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

通過前面針對圖論的圖像分割算法的詳細(xì)介紹,本節(jié)就Grab Cut與One Cut圖像分割算法進(jìn)行分割效果與算法性能的分析。

4.1Grab Cut與One Cut實(shí)驗(yàn)結(jié)果

在充分理解Grab Cut與One Cut的算法原理基礎(chǔ)上,分別對這兩個分割算法做了分割效果的實(shí)驗(yàn),其圖像分割結(jié)果分別如圖3、4所示。

圖3　Grab Cut圖像分割結(jié)果

圖4　One Cut圖像分割結(jié)果

由圖3,4比較可知,雖然從分割結(jié)果上來說,它們均達(dá)到了較好的效果,但是從交互方式上來看,One Cut算法更具優(yōu)勢。

4.2Grab Cut與One Cut時間性能分析

本文針對Grab Cut與One Cut時間性能做了具體而實(shí)際地分析工作,它們的時間性能情況如圖5中所示。

針對One Cut每一次分割過程中,取其時間消耗值,樣本數(shù)為10。通過對Grab Cut遞增其迭代次數(shù)得到其時間消耗值,迭代次數(shù)由1逐漸增至10。由圖中可知,Grab Cut隨著迭代次數(shù)的增加,其時間消耗越大;One Cut各個樣本的時間變化不大,時間消耗始終在100ms上下浮動。

圖5　Grab Cut與One Cut算法時間性能對比圖

通過實(shí)驗(yàn)與分析可知,在相同分割效果的前提下,One Cut在交互及時間性能上均是優(yōu)于Grab Cut圖像分割算法。

5　結(jié)語

本文在描述圖像分割算法的基礎(chǔ)上,重點(diǎn)針對基于圖論的分割算法進(jìn)行算法原理進(jìn)行詳細(xì)闡述,并對Grab Cut與One Cut算法進(jìn)行分割效果及時間性能上的實(shí)驗(yàn)分析。雖然在分割效果上滿足要求,但是由于分割過程中對交互的依賴性過大,達(dá)不到圖像分割的自動化與實(shí)時性的目標(biāo),而且在該類方法是基于圖像像素為對象展開方法的研究工作,若圖像中像素過多將會導(dǎo)致計(jì)算量過大。所以在保證分割效果的前提下,算法效率的提高將是圖像分割算法在未來的發(fā)展過程中很長時間內(nèi)亟待解決的課題。

[1] Abadi D J, Carney D, Cetintemel U, et al. Aurora:A New Model and Architecture for Data Stream Management[J]. VLDB Journal,2003,12(2):120-139.

[2] Noma A, Graciano A B V, Consularo L, et al. A new algorithm for interactive structural image segmentation[J]. The Computing Research Repository,2008(1):4-6.

[3] 武紅玉.閾值分割算法在圖像處理中的應(yīng)用[J].科技信息,2012(27):201-202.

WU Yuhong. Application of threshold segmentation algorithm in image processing[J]. Science and Technology Information,2012(27):201-202.

[4] Han S Q, Wang L. The review of threshold methods in image segmentation[J]. System Engineering and Electronics,2002,4(6):91-102.

[5] Mortensen E. Interactive segmentation with intelligent scissors[J]. Graphical Models and Image Processing,1998,60(5):349-384.

[6] Falcao A X, Udupa J K, Miyazawa F K. An ultra-fast user-steered image segmentation paradigm: livewire on the fly[J]. IEEE Transaction on Medical Imaging,2000,19(1):55-62.

[7] De Miranda P A V, Falcāo A X, Udupa J K. Synergistic arc-weight estimation for interactive image segmentation using graphs[J]. Computer Vision and Image Understanding,2010,114(1):85-99.

[8] 舒添慧,胥布工,胡戰(zhàn)虎.基于區(qū)域生長法的醫(yī)學(xué)圖像分割[J].微計(jì)算機(jī)信息,2008,24(6-3):284-285.

SHU Tianhui, XU Bugong, HU Zhanhu. Medical image segmentation based on region growing method[J]. Microcomputer information,2008,24(6-3):284-285.

[9] Yuri Boykov M. P. Jolly. Interactive graph cuts for optimal boundary region Segmentation of objects in N-D images[C]//Proceedings of ICCV,2001:106-110.

[10] Carsten Rother, Vladimir Kologorov, Andrew Blake. “GrabCut”—Interactive foreground extraction using iterated graph cuts[J]. In ACM Transactions on Graphics (SIGGRAPH),August 2004:3-10.

[11] TANG M, GORELICK L, VEKSLER O, et al. GrabCut in One Cut[C]//International Conference on Computer Vision, Sydney: IEEE,2013:1769-1776.

Summary of Segmentation Algorithm Based on Graph Theory

CHEN Xing1LI Jun2

(1.School of Electronic Information Engineering, Xi’an Technological University, Xi’an710021) (2.School of Computer Science and Engineering, Xi’an Technological University, Xi’an710021)

In the field of computer vision,image segmentation is one of the classical problems. Because of its good time performance and segmentation results,the segmentation algorithm based on graph theory has become a new focus for the researchers. On the basis of the summary of image segmentation algorithm,this paper focuses on the segmentation algorithm based on graph theory and compares the Grab Cut and One Cut algorithms from the time performance and the segmentation results. Finally,the existing problems and the development direction of this field are summarized.

image segmentation, energy optimization, iterative minimization, optimal two partition

2016年4月8日,

2016年5月28日

陳杏,女,碩士研究生,研究方向：計(jì)算機(jī)視覺。李軍,男,碩士研究生,研究方向：智能計(jì)算與機(jī)器視覺。

TP391.41

10.3969/j.issn.1672-9722.2016.10.038