一種改進的圖割目標(biāo)分割算法

湯依婷，韓彥芳

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

?

一種改進的圖割目標(biāo)分割算法

湯依婷，韓彥芳

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

為了減少圖像目標(biāo)在分割過程中受到噪聲、復(fù)雜背景等因素的影響，將圖像的多特征信息引入到圖割算法中，提出了一種結(jié)合圖像的多特征信息圖割目標(biāo)分割方法。該方法先選取像素點的多種圖像特征組成特征向量，并對已做好標(biāo)記的目標(biāo)和背景種子點的特征向量分別進行FCM聚類，然后分別計算各像素點與這兩類種子點的各聚類中心的最短歐式距離，并據(jù)此信息完成對能量函數(shù)的構(gòu)造，最終運用最大流/最小割的方法得到圖像分割的結(jié)果。其與傳統(tǒng)圖割算法相比，分割結(jié)果有了明顯改善。實驗結(jié)果表明，該算法具有有效性。

圖割；圖像分割；特征向量；FCM聚類；最大流最小割

TANG Yiting, HAN Yanfang

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology,Shanghai 200093, China)

圖像分割是由圖像處理到圖像分析的關(guān)鍵步驟。只有在圖像分割的基礎(chǔ)上才能對目標(biāo)進行特征提取和參數(shù)測量，使得更高層的圖像分析和理解成為可能。因此，對圖像分割方法的研究具有重要意義。經(jīng)典算法有閾值法[1]、區(qū)域合并[2]、基于邊緣檢測[3]、分水嶺算法[4]和聚類分析[5]等，這些算法在不同領(lǐng)域得到了廣泛應(yīng)用。而圖割(Graph Cuts)算法可在全局最優(yōu)的框架下進行分割，能確保能量的全局最優(yōu)解，因而得到廣泛關(guān)注。

傳統(tǒng)Graph Cuts算法僅依賴圖像的灰度信息構(gòu)造能量函數(shù)。對于簡單圖像分割效果良好，但當(dāng)背景較為復(fù)雜，且與目標(biāo)灰度較為接近時，圖像目標(biāo)的準(zhǔn)確分割變得困難。故本文在傳統(tǒng)Graph cuts算法的基礎(chǔ)上，提出一種依賴圖像多特征信息構(gòu)造能量函數(shù)的圖割方法。待分割的目標(biāo)與背景總會在某一種或多種圖像性質(zhì)上存在差異，綜合考慮多種因素，增加多特征的信息，可實現(xiàn)目標(biāo)的正確分割，提高算法精確度。

1 Graph Cuts圖像分割理論

1.1 圖割理論

圖割法是利用圖論中的最小割算法求能量函數(shù)全局最優(yōu)解的算法。利用圖割來解決圖像分割問題的步驟如下。

1.1.1 構(gòu)造圖結(jié)構(gòu)

將圖像轉(zhuǎn)變成圖結(jié)構(gòu)，構(gòu)造的圖為G=(V,E)，V和E分別代表圖的節(jié)點和邊的集合，每一條邊均有一個非負的權(quán)值。V中包括兩類節(jié)點：(1)由圖像像素集合P組成的領(lǐng)域節(jié)點；(2)兩個特殊的端點稱為終端：源點s與匯點t，分別對應(yīng)圖像中的目標(biāo)種子點和背景種子點。E中也包括兩類：1)相鄰像素節(jié)點p和q之間帶有權(quán)值Wpq的邊epq,其中q∈Np，通常q為p點的4領(lǐng)域或8領(lǐng)域；2)像素p與s和t之間帶有權(quán)值Wsp和Wpt的邊esp和邊ept(p∈P)。一幅二維圖像及其構(gòu)造圖，如圖1(a)和圖1(b)所示。

1.1.2 構(gòu)造能量函數(shù)

用一組像素集合I表示一幅圖像，領(lǐng)域系統(tǒng)N用以表示I中兩個像素{p,q}的相互關(guān)系，向量A=(A1,A2,…,A|I|)描述了I中各像素的屬性狀態(tài)，Ai={′obj′,′bkg′},Ai是一個二元值，代表像素i屬于目標(biāo)或背景。在通過向量A來構(gòu)造能量函數(shù)時，需考慮各個像素自身的情況以及像素間的相互聯(lián)系。因此，Boykov給出了能量函數(shù)的定義為[6]

E(A)=λ·R(A)+B(A)

(1)

其中

(2)

(3)

式中，B(A)表示平滑項能量，為相鄰像素之間的能量；R(A)表示數(shù)據(jù)項能量，為各個像素自身情況在能量函數(shù)中的體現(xiàn)。

1.1.3 最大流/最小割

利用該算法求解能量函數(shù)全局最小值得到的就是對圖像的分割結(jié)果，如圖1(c)和圖1(d)所示。

圖1 圖和圖割

1.2 最大流/最小割

最大流/最小割分割法通過計算圖的最大流求得圖最小割的值，從而使能量函數(shù)最優(yōu)化，得到最優(yōu)解。本文采用的是利用兩棵動態(tài)搜索樹的方法計算最大流/最小割的算法[7]。

根據(jù)網(wǎng)絡(luò)流的理論[8]和由L.Ford and D.Fulkerson提出的定理[9]可知，在s-t網(wǎng)絡(luò)中，可行流的最大值等于割的容量最小值。因此，網(wǎng)絡(luò)圖的最小割與最大流可相互轉(zhuǎn)化來得到，故圖的最小割可通過計算圖的最大流得到。

搜索樹算法的基本思想是：分別以源點s和匯點t來構(gòu)造搜索樹S和T，通過生長樹S和T來尋找增廣路徑?？煞殖梢韵?個步驟：

步驟1 尋找增廣路徑(Growth Stage)；

步驟2 處理增廣路徑(Augmentation Stage)；

步驟3 組合深林成樹(Adoption Stage)；

步驟4 若步驟1中尋找不到增廣路徑，則找到最小割，算法退出；否則，繼續(xù)執(zhí)行步驟1～步驟3。

由上述算法思想可找到一條從源點s到匯點t的增廣路徑，如圖2所示。與源點和匯點均不相連的點被歸為背景區(qū)域。

圖2 從源點s到匯點t的一條路徑

2 基于多特征的圖割分割算法

2.1 算法原理

2.1.1 限制條件

為使圖像分割結(jié)果能達到預(yù)期的目的，適當(dāng)?shù)南拗菩詶l件必不可少?；趫D割的分割方法可看做是一類交互式圖像分割方式，故人機交互的標(biāo)示就是一種簡單而有效的限制性條件。在文中的限制條件即為人在圖像上對目標(biāo)和背景所做的標(biāo)示。

2.1.2 特征信息選取與融合

對于圖像特征信息的選取，本文主要從像素灰度和梯度兩方面考慮。對于一幅灰度圖像I，本文選取6個特征組成其特征向量，即Vp=(a1,a2,a3,a4,a5,a6)。其中，a1代表像素p的灰度；a2代表像素p為中心的8領(lǐng)域內(nèi)的灰度類方差；a3代表像素p灰度值的橫向梯度；a4代表像素p灰度值的縱向梯度；a5代表了像素p所在的行信息；a6代表像素p所在的列信息

圖3 8領(lǐng)域像素塊

(4)

(5)

a3=(|Ip-I4|+|Ip-I5|)/2

(6)

a4=(|Ip-I2|+|Ip-I7|)/2

(7)

a5=m,m為像素點所在的行

(8)

a6=n,n為像素點所在的列

(9)

以單個像素作為基本處理單元，在選定若干個有效的圖像特征后，每一個像素均對應(yīng)一個特征向量。首先對特征向量進行FCM聚類[10]，每個聚類中心對應(yīng)的向量代表了一組典型的圖像特征。在聚類后，每一個像素均對應(yīng)一個聚類類型，以k代表其屬于第k類。

在本文算法中，針對上文標(biāo)示的目標(biāo)和背景種子像素分別用FCM聚類分為k類，則可知目標(biāo)像素和背景像素所可能具有的k類典型特征向量，為下文構(gòu)造能量函數(shù)做準(zhǔn)備。為減小計算量，此處k取10。

2.1.3 構(gòu)造能量函數(shù)

構(gòu)造能量函數(shù)是圖割算法最為重要的部分，能量函數(shù)構(gòu)造的優(yōu)劣將直接影響到分割結(jié)果。能量函數(shù)表達式如下所示

E(A)=λ·R(A)+B(A)=

(10)

其中，第一項為數(shù)據(jù)項能量，Rp(Ap=′obj′)反映了像素p屬于目標(biāo)的可能性，若像素p屬于目標(biāo)的可能性越大，則Rp(Ap=′obj′)的取值就越小，反之亦然。同理，有Rp(Ap=′bkg′)。而這一可能性如何度量，則是構(gòu)造能量函數(shù)的關(guān)鍵。

定義Dist(p,′obj′)和Dist(p,′bkg′)分別代表像素點p與目標(biāo)和背景的距離。由上文已計算出分別代表目標(biāo)和背景的k類典型特征向量，分別計算像素點p的特征向量與代表目標(biāo)的k類特征向量和代表背景的k類特征向量的歐式距離，并取其中的最小值作為Dist(p,′obj′)和Dist(p,′bkg′)的值，設(shè)p的特征向量可表示為 (n個特征)，目標(biāo)的特征向量可表示為αoi={Bi1,βi2,…,βin} (n個特征，第i類特征向量，1≤i≤k)；同理得背景的特征向量可表示為： (n個特征，第i類特征向量， )。計算公式如式(11)和式(12)所示。

(11)

(12)

Dist(p′obj′)和Dist(p,′bkg′)也可理解為此像素屬于目標(biāo)或背景的可能性。此時數(shù)據(jù)項可表示為

(13)

其中

(14)

由Dist(p,Ap)定義可知，Dist(p,Ap)是一個非負數(shù)，ε1和ε2均為正常數(shù)，是保證Pr(p|Ap)∈(0,1)，且應(yīng)盡可能減小其對Pr(p|Ap)取值的影響。

第二項B(A)是平滑項，其大小反映的是兩個相鄰像素之間的相似性，兩個像素越相似，其值越大。定義Bp,q為

(15)

其中

Rq(′obj′))2+(Rp(′bkg′)-Rq(′bkg′))2)

(16)

2.2 算法總結(jié)

算法分為4步：

步驟1 人機交互，選取目標(biāo)和背景的種子像素;

步驟2 將彩色圖像變?yōu)榛叶葓D像，計算種子像素的特征向量，并分別對目標(biāo)種子像素和背景種子像素進行FCM聚類，各分為10類;

步驟3 由文中介紹的構(gòu)造能量函數(shù)的方法構(gòu)造能量函數(shù);

步驟4 采用最大流/最小割的搜索樹算法實現(xiàn)圖像的分割。

3 實驗與分析

文中算法程序采用Matlab編寫，其中核心部分由C++語言實現(xiàn)，編程環(huán)境為Matlab 2014，選擇標(biāo)準(zhǔn)圖像庫Berkeley Segmentation Dataset中的圖像進行實驗。并分別用傳統(tǒng)的圖割算法和本文的圖割算法對圖像進行分割，分割結(jié)果如圖4～圖6所示，其中交互圖像中十字點為目標(biāo)種子點，圓圈為背景種子點。

圖4 分割結(jié)果示意圖

圖5 分割結(jié)果示意圖

圖6 分割結(jié)果示意圖

以上幾幅圖像均包括較為復(fù)雜的背景，通過本算法和傳統(tǒng)算法的分割結(jié)果比較可看出，本算法優(yōu)于傳統(tǒng)算法，加入了多特征的向量構(gòu)造能量函數(shù)，使分割結(jié)果有了明顯改善，去除了背景中大部分雜亂部分，且邊緣細節(jié)的捕捉能力也更好，驗證了本算法的有效性。

4 結(jié)束語

本文介紹了一種基于多種特征構(gòu)造能量函數(shù)的圖割算法。本算法通過FCM聚類來融合多個圖像特征，分別計算目標(biāo)和背景的k類特征向量，計算各個像素點和種子像素點的最短歐式距離得到數(shù)據(jù)項函數(shù)，然后利用相鄰像素點間的灰度信息構(gòu)造平滑項函數(shù)，最終通過最大流/最小割中的搜索樹算法得到圖像分割結(jié)果。相比于傳統(tǒng)圖割方法，該方法在背景較為復(fù)雜的情況下，對于目標(biāo)區(qū)域的分割依然效果良好。實驗結(jié)果表明，加入多特征構(gòu)造能量函數(shù)方法在分割過程中起到了一定的作用。

[1] Joe H. Bivariate threshold methods for extremes[J].Journal of the Royal Statistical Society, 1992,54(1):171-183.

[2] Richard N,Frank N.Statistical region merging[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2004, 26(11):1452-1458.

[3] Catté F,Coll T. Image selective smoothing and edge detection by nonlinear diffusion:II[J].Siam Journal on Numerical Analysis,1992,29(3):845-866.

[4] Vincent L, Soille P. Watersheds in digital spaces: an efficient algorithm based on immersion simulations[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1991,13(6):583-598.

[5] Arifin A Z, Asano A. Image Segmentation by histogram thresholding using hierarchical cluster analysis[J]. Pattern Recognition Letters,2006,27(13):1515-1521.

[6] Boykov Y Y,Jolly M P.Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images[C].UT,USA:ICCV Proceedings,Eighth IEEE International Conference on Computer Vision, IEEE,2001.

[7] Yuri B,Vladimir K.An Experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2004,26(9):1124-1137.

[8] 田豐,張運清.圖與網(wǎng)絡(luò)流理論[M].2版.北京:科學(xué)出版社,2015.

[9] Ford L R,Fulkerson D R.Flows in networks[J].Princeton University Press Princeton N J,2010,18(4):157-172.

[10] Bezdek J C,Ehrlich R,Full W.FCM: The fuzzy c-means clustering algorithm[J].Computers & Geosciences, 1984, 10(84):191-203.

[11] Xu N,Ahuja N, Bansal R. Object segmentation using graph cuts based active contours[C].Hongkong:IEEE Conference on Computer Vision & Pattern Recognition,2003.

An Improved Algorithm of Graph Cut Segmentation

A combination of multiple image feature information and graph cut algorithm is proposed for segmenting target by introducing multiple feature image information into the graph cut algorithm to reduce the negative influence on the target image of noise, complex background and other factors in the segmentation process. First, multiple image features are selected to compose the feature vectors, and the feature vectors of labeled target and background seed points are clustered by FCM. Second, the shortest distance of each pixel to the cluster center of each seed point of the two types is calculated, according to which the energy function is constructed. Finally, the maximum flow minimum cut method is used to get the results of image segmentation. Experimental results show that the proposed algorithm significantly improves the segmentation results over the traditional graph cut algorithm.

graph cut; image segmentation; feature vector; FCM clustering; max-flow min-cut

2016- 01- 04

湯依婷(1993-)，女，碩士研究生。研究方向：數(shù)字圖像處理與計算機視覺。韓彥芳(1974-)，女，博士，講師。研究方向：圖像處理和模式識別。

10.16180/j.cnki.issn1007-7820.2016.10.013

TP391.41

A

1007-7820(2016)10-043-04