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

陳　杏　李　軍

(1.西安工業大學電子信息工程學院　西安　710021)(2.西安工業大學計算機科學與工程學院　西安　710021)

?

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

陳杏1李軍2

(1.西安工業大學電子信息工程學院西安710021)(2.西安工業大學計算機科學與工程學院西安710021)

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

圖像分割; 能量優化; 迭代最小化; 最優二元分割

Class NumberTP391.41

1　引言

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

圖像處理技術不僅在諸多領域扮演著舉足輕重地角色,而且圖像分割是圖像進行處理的鍵環節之一及基于圖論的圖像分割理論的前沿性,使針對該類圖像分割技術的研究具有較大的價值與應用前景。

2　圖像分割方法概述

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

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

2.1基于閾值的分割算法

基于閾值的分割[2～4]是通過單個或多個閾值將圖像的灰度直方圖分成幾類,認為圖像中灰度值在同一灰度級別的像素屬于同一物體。閾值分割法先確定適當的分割閾值,然后將圖像中所有像素的灰度級與該閾值進行比較,從而可對區域進行劃分,達到圖像分割的目的。基于閾值的分割算法主要分為三種：基于點、區域的全局及局部與多閾值方法。

2.2基于邊緣的分割算法

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

2.3基于區域的分割算法[8]

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

1) 區域生長法

區域生長法是根據同一物體區域內像素的相似性對像素進行聚集的方法,從初始區域開始,將相同屬性的相鄰像素或區域歸并于當前區域從而達到區域逐步擴散的目的,直至該圖像中不存在可以進行歸并的像素點或區域。

2) 分裂合并法

分裂合并法首先將圖像分成若干互不相交的區域,然后按照相關規則對區域進行分裂或合并從而實現分割目的,該方法適用于灰度圖像與紋理圖像分割。

2.4基于圖論的分割算法

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

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

基于能量泛函的分割算法是指活動輪廓模型(Active Contour Model)及在其基礎上衍生出的相關算法,其基本思想是將目標對象的邊緣用連續曲線進行表達,并定義一個能量泛函使得其自變量包括邊緣曲線,因此分割過程就轉變為求解能量泛函的最小值過程。按照模型中曲線表達形式的不同,活動輪廓模型可以分為兩大類：參數活動輪廓模型(Parametric Active Contour model)和幾何活動輪廓模型(Geometric Active Contour Model)。

3　基于圖論的分割算法

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

3.1Graph Cut算法[9]

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

3.1.1S-T圖像映射結構

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

圖2　S-T圖

3.1.2最小割S-T圖

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

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

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

R(L)為區域項,B(L)為邊界項。a為區域項與邊界項之間的影響因子,決定了二者對能量的影響程度。E(L)為能量函數,圖割的目標就是優化該能量函數并使其值最小化。區域項(t-links)中邊的權值計算公式為

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

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

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

邊界項：n-links中每條邊權值如下：

其中

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

在確定了每條邊的權重后,可以通過mincut算法對圖像進行最小割處理,這些邊的斷開既實現了對目標與背景的分離,又實現了能量的最小化。

3.2GrabCut算法[10]

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

GrabCut在GraphCut算法的基礎上做出的改進工作可以歸納為以下幾點：

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

2)GraphCut中能量最小化是一次性達到,而GrabCut采用交互迭代的方式對其進行分割估計與模型參數的學習;

3)GraphCut需要用戶指定目標與背景的一些種子像素點,而GrabCut只需提供背景區域的像素集。若需要分割的結果更加精確,可以在初次分割的基礎上提供一些確定的種子像素點,在運行該算法即可。

3.2.1顏色空間模型

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

結合高斯模型,其中U的定義為

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

3.2.2初始化

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

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

2) 初始化TB內的每一像素n的標簽αn=0;初始化TU內的每個像素n的標簽αn=1;

3) 經過上述過程,可以得到目標與背景的一些像素。通過這些像素可進行目標和背景GMM的估計。首先通過k-mean算法將目標和背景的像素聚類為K類,其次通過RGB值估計參數均值和協方差,最后通過該高斯分量中的像素數目與像素總數的比值確定高斯分量的權值。

3.2.3迭代最小化

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

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

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

3.3OneCut算法[11]

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

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

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

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

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

β′是一個全局參數,經實驗得出β′=0.9,λ=9。

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

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

4　實驗結果與分析

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

4.1Grab Cut與One Cut實驗結果

在充分理解Grab Cut與One Cut的算法原理基礎上,分別對這兩個分割算法做了分割效果的實驗,其圖像分割結果分別如圖3、4所示。

圖3　Grab Cut圖像分割結果

圖4　One Cut圖像分割結果

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

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

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

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

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

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

5　結語

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

[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] 武紅玉.閾值分割算法在圖像處理中的應用[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] 舒添慧,胥布工,胡戰虎.基于區域生長法的醫學圖像分割[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日

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

TP391.41

10.3969/j.issn.1672-9722.2016.10.038