袁恒東

(南京理工大學 計算機科學與工程學院,江蘇 南京 210094)

基于標簽傳遞圖割的圖像分割算法

袁恒東

(南京理工大學 計算機科學與工程學院,江蘇 南京 210094)

基于圖割的交互式圖像分割方法實現(xiàn)了基于用戶感興趣區(qū)域的圖像前景和背景分割，在計算機視覺和圖像處理領域受到了眾多研究者的關注。傳統(tǒng)圖割算法往往是基于圖像局部特征進行分割，其收斂速度以及圖像結構描述能力具有一定的局限性。為了進一步提高分割精度，提出一種基于標簽傳遞圖割的交互式圖像分割算法。首先通過引入三層超像素層構造圖模型，實現(xiàn)高層信息的計算。通過多層超像素層，既能抑制過分割，也可以通過不同參數(shù)的超像素來增加算法的魯棒性，提升算法穩(wěn)定性能。然后結合高次信息，采用已標記樣本特征指導未標記樣本的標簽分配，進行標簽傳遞，利用較少標記樣本對未標記樣本進行聚類，從而提高了學習精度。最后使用最大流/最小割算法求解最終的分割結果。在MSRC和Berkeley數(shù)據(jù)集上進行的分割實驗表明，基于標簽傳遞和圖割的圖像分割算法是有效的。

交互式圖像分割；圖割；超像素；標簽傳遞

0 引 言

目前，圖像分割方法主要有基于區(qū)域的分割方法和基于邊緣的分割方法?；趨^(qū)域的分割方法是將區(qū)域作為處理對象，根據(jù)灰度、紋理等將目標分割出來，如高斯混合模型(GMM)，通過圖像的特征進行聚類，該類方法易出現(xiàn)過分割現(xiàn)象，無法保證全局最優(yōu)?；谶吘壍姆指罘椒ㄖ饕罁?jù)物體邊緣的鄰域灰度值不連續(xù)、階越的特性，此類方法依賴初始標記的輪廓線，對初始標記較敏感，易出現(xiàn)局部極值。由BOYKOV等[1]提出的Graph cuts模型，是目前研究和應用最為廣泛的交互式圖像分割方法之一。該方法在分割過程中將圖像的區(qū)域信息和邊界信息同時引入，先利用圖像建圖，再求圖的最小割，基于圖割的圖像分割方法可以得到較好的分割效果。

傳統(tǒng)的Graph cuts方法基于統(tǒng)計直方圖，根據(jù)交互的標記信息獲得每個像素屬于前、背景的概率，但由于直方圖的限制，該類方法對低對比度和復雜背景的圖像進行分割時往往不能獲得滿意的結果，并且對交互信息的數(shù)量有很大的依賴。后來，ROTHER等[2]利用高斯混合模型代替直方圖，提出了Grabcut方法。該方法使用方框圈出前景和背景進行交互，通過迭代更新高斯混合模型中的各項參數(shù)來獲得更優(yōu)結果，然而因為使用了迭代求解模式，使得內(nèi)存開銷、運算速度和計算復雜度都受到了很大影響。

基于上述分析，文中提出了一種基于標簽傳遞圖割的交互式分割方法。在構圖時，加入多層超像素，通過超像素增加高次信息，使用多層來降低超像素對圖像分割結果的誤分，防止過分割，并且通過不同參數(shù)的超像素層結合，提高了算法對不同圖像分割的魯棒性。再通過每個節(jié)點迭代傳遞它的標記信息到近鄰，直到全局穩(wěn)定，結合了局部信息和非局部信息，代替GMM來獲得每個像素隸屬于前、背景的概率，減少計算時的迭代時間，提升了算法運算速度。

1 基于圖割的圖像分割算法

給定一個標簽集合F，一個圖像的像素集合P，圖像分割可以看成像素標記(pixel labeling)問題，即給圖像中的每個像素點p∈P分配一個標fp∈F。圖像分割看成二值標記問題，即F={0,1}，其中1代表前景標簽，0代表背景標簽[3]。圖像分割即為從圖像像素集合P到標簽集合F進行映射，表示為f={fp|fp∈F}。根據(jù)使用者設定的前景種子點和背景點限定的邊緣和區(qū)域的性質(zhì)，設計出相對應的能量函數(shù)E(f)。能量函數(shù)E(f)中一般包括兩部分：平滑約束部分和區(qū)域約束部分，即E(f)=Esmooth(f)+Eregion(f)，常常把基于圖割的交互式圖像分割方法的能量函數(shù)表達為：

E(f)=R(f)+λ·B(f)=Er(f)+λ·Eb(f)

(1)

其中，Er為區(qū)域項，強調(diào)數(shù)據(jù)的一致性；Eb為邊界項，強調(diào)平滑性[4]；λ為調(diào)節(jié)參數(shù)。

根據(jù)原圖構建無向圖G=(V,E),V代表節(jié)點，E代表邊緣。圖割在無向圖G的基礎上增加了“源”節(jié)點S和“匯”節(jié)點T，分別表示前景終點和背景終點。點集V由各像素點以及S、T構成，邊集E包括兩部分，一部分是每兩個相鄰節(jié)點的連接邊n-links(圖1右實線)，另一部分是普通節(jié)點和終端節(jié)點的連接邊t-links(圖1右虛線)。

圖1 Graph Cuts模型

然后使用最大流/最小割算法求解圖的最小割集[5]。割是割集中所有邊的權重之和，若一個割中的邊權值之和為最小，即最小割，就是圖割的結果。由BOYKOV和KOLMOGOROV提出的max-flow/min-cut算法[6]就可以用來獲得S-T圖的最小割。

由于將多種區(qū)域信息與邊界信息進行了有效結合，基于圖割的圖像分割方法的效果要好于只有一種信息進行指導時分割所產(chǎn)生的效果，具有全局最優(yōu)、數(shù)值魯棒性強等顯著優(yōu)點。傳統(tǒng)的基于圖割的圖像分割算法使用像素點間的相似性表征局部信息，再通過求得的相似性進行圖像分割；而目前基于圖像非局部信息的改進算法往往是結合區(qū)域或者全局信息，利用計算圖像中非局部的特征信息，但是仍然存在一定的不足之處：分割算法在使用GMM時采用EM算法，需要迭代收斂，較復雜，時間消耗大;在復雜背景和低對比的圖像中，由于分割信息單一，算法往往出現(xiàn)誤分割；對于局部信息，獨立的像素點間易受到噪聲、極值點等的影響，所以在表征其相似性關系時難度較大，從而影響分割，得到錯誤的分割結果。

2 文中算法

一般圖像分割方法在分割過程中只考慮圖像的像素信息或局部信息，但在超像素的指導下，結合非局部信息可作為一個重要特征來提升圖像的分割質(zhì)量。

2.1 超像素層權重構造

超像素是指具有某些相似特征的相鄰像素構成的不規(guī)則像素塊。它利用像素之間特征的相似性將像素分類，用少量的超像素代替大量的像素表達圖片特征，很大程度上降低了圖像處理的復雜度[7-8]。文中采用SLIC(Simple Linear Iterative Cluster)算法生成超像素[9]。SLIC算法產(chǎn)生的超像素緊湊整齊，鄰域特征易表達，且設置的參數(shù)較少。

由于一些區(qū)域可能由于噪聲和參數(shù)值而僅在一個過分割中與真實對象邊界不一致，所以通過不同參數(shù)得到多個分割來減少關于區(qū)域形狀的不確定性。通過將SLIC算法的分割種子點設為400、800、1 600個，使用SLIC分割得到三層超像素層，將每個超像素層中超像素和像素層中像素點連接，從而建立結合了像素層和多重超像素層的圖模型，如圖2所示。其中，左邊是圖像右邊是圖模型，圖像由下往上分別是原圖和使用了三種不同參數(shù)得到的分割圖像，右半邊展示了文中算法模型的構造和連接方式。

圖2 結合多重超像素的圖模型

從圖2中可以看出，圖模型建立完成后圖中的邊有三種，分別是像素層中像素點之間的連接邊lx、超像素層中超像素之間的連接邊ly和像素點和超像素間的連接邊lxy。對于層節(jié)點間的相似性w由歐氏距離計算得到，所以圖的鄰接矩陣W即為：

(2)

其中，Wxx是像素層內(nèi)的像素點之間的相似性；Wxy,Wyx是像素層內(nèi)的像素點與超像素層內(nèi)的超像素點之間的相似性；Wyy是超像素層內(nèi)的超像素點之間的相似性。

由于像素層內(nèi)的像素點之間的相似性、超像素層內(nèi)的超像素點之間的相似性較高，在計算邊的權重時，加入?yún)?shù)α，對于鄰接矩陣W，將一般的公式改為：

(3)

2.2 結合標簽傳遞的圖割算法

利用局部和全局一致性[10]的學習方法進行標簽傳遞，降低了對標記點數(shù)量的依懶性，減少了迭代時間和算法的復雜度，提高了圖像的利用率和分割精度。標簽傳遞的核心是對每個點進行反復迭代，傳遞它的標簽信息到它的近鄰，直到所有樣本標簽達到穩(wěn)定。

ZHOU等[10]對算法的收斂性進行了計算和證明，標注概率F收斂到一個等式：

F*=(I-βS)-1Y

(4)

其中，F(xiàn)*是一個定值，因此它是該迭代算法的固定唯一解，提供了一種無需迭代直接解決問題的方法,節(jié)省了計算的時空消耗。

具體的算法步驟如下：

(1)使用SLIC進行預分割，得到三種不同個數(shù)的超像素層。

(2)像素層和三層超像素層連接，構造圖模型。

由步驟(2)建立的模型計算相似度矩陣，相似度由式(5)得到，再根據(jù)式(3)得到鄰接矩陣W。

(5)

(4)使用式(4)計算每個像素點標簽的概率，即文中算法的能量函數(shù)為：

E(f)=(I-βS)-1Y+λ·Eb(f)

(6)

(5)使用最大流/最小割優(yōu)化能量函數(shù)，求得能量函數(shù)的最小值，也就可得到相同代價的圖的割集。

最后在圖中去掉割集的所有邊，圖將會被分割成互不相交的兩部分。文中算法通過結合超像素這個高層語義進行權重計算，并且結合局部和全局的一致性進行標簽預分配，使得圖割算法能夠利用全局和高次信息，提高算法的分割精度。

3 實驗結果分析與比較

為了進行算法有效性以及正確性的評估，選擇了MSRC和Berkeley公共圖片庫作為實驗的圖像數(shù)據(jù)集。采用圖像的錯誤率來評價分割結果，分割錯誤率定義為錯分類像素點的數(shù)目與所有未分類像素點數(shù)目的比值，其中未分類像素點不包括前、背景的種子點。通過對測試數(shù)據(jù)集中的50幅測試圖像分割后取平均錯誤率來評價分割結果，在兩個測試圖像庫中做了定量評估。

3.1 參數(shù)設置

算法中式(3)的參數(shù)α和式(6)的參數(shù)β由多組對比實驗得到合適的實驗值，分別為0.12和0.77。圖3是α、β取值過程中的平均分割錯誤率。三層超像素的K值分別為400、800、1 600。由于文中算法是先確定β值的，所以從圖3可以看到，對應的分割錯誤率比較高。確定策略是β從0到1變化，通過數(shù)據(jù)比較可知，當β為0.77時，分割的錯誤率最小，分割的效果最佳。同樣，通過固定其他參數(shù)，α值在0到1變化時在50幅測試集上的分割錯誤率表明，當α值為0.12時，分割的錯誤率最小，分割的效果最佳。

圖3 不同α、β取值時的分割錯誤率

3.2 實驗結果分析

將文中算法與傳統(tǒng)圖割算法(GC)、隨機游走算法[11](RW)和無參高階學習算法[12](NPHO)進行比較。文中算法的分割結果如圖4所示，圖中是20幅Berkeley圖像和30幅MSRC圖像分割后的結果。

圖4 文中算法的分割結果

圖5為每幅圖像的分割錯誤率，從中可以看出文中算法的錯誤率基本都是最低，證明了基于超像素和標簽傳遞的圖割算法的可行性。

圖5 分割錯誤率對比

表1給出了50幅測試圖的平均分割錯誤率。根據(jù)具體實驗結果可以發(fā)現(xiàn)，文中算法的分割錯誤率最低，表明該算法的分割效果較好。

表1 數(shù)據(jù)集中多個算法的平均分割錯誤率

4 結束語

文中算法結合了超像素和標簽傳遞，通過在圖割算法中加入超像素層，在構圖計算權重時考慮到高次信息，再使用標簽傳遞算法，讓每個節(jié)點反復迭代傳遞它的標記信息到它的近鄰，直到所有樣本的標記達到穩(wěn)定。最后通過多種分割方法的實驗比較和定量的分割錯誤率分析證明了該算法的可行性和有效性。雖然文中算法繼承了半監(jiān)督學習的優(yōu)點，提高了圖像分割的效果，但對于交互信息極少和前背景部分較多融合、對比度低的圖像的分割效果不是特別好；另外，使用矩陣存儲節(jié)點間的相似度，所占用內(nèi)存空間較大，對于高分辨率圖像的數(shù)據(jù)處理較慢，這些問題還需要在今后的研究中繼續(xù)進行解決。

[1] BOYKOV Y,JOLLY M P.Interactive graph cuts for optimal boundary & region segmentation of objects in ND images[C]//Eighth IEEE international conference on computer vision.[s.l.]:IEEE,2001:105-112.

[2] ROTHER C,KOLMOGOROV V,BLAKE A."GrabCut":interactive foreground extraction using iterated graph cuts[J].ACM Transactions on Graphics,2004,23(3):309-314.

[3] GREIGD M,PORTEOUS B T,SEHEULT A H.Exact maximum a posteriori estimation for binary images[J].Journal of the Royal Statistical Society,1989,51(2):271-279.

[4] BOYKOV Y,VEKSLER O,ZABIH R.Markov random fields with efficient approximations[C]//Proceedings of IEEE conference on computer vision and pattern recognition.[s.l.]:IEEE,1998:648-655.

[5] 劉松濤,殷福亮.基于圖割的圖像分割方法及其新進展[J].自動化學報,2012,38(6):911-922.

[6] BOYKOV Y,KOLMOGOROV V.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.

[7] 王春瑤,陳俊周,李 煒.超像素分割算法研究綜述[J].計算機應用研究,2014,31(1):6-12.

[8] 韓守東,趙 勇,陶文兵,等.基于高斯超像素的快速Graph Cuts圖像分割方法[J].自動化學報,2011,37(1):11-20.

[9] ACHANTA R,SHAJI A,SMITH K,et al.SLIC superpixels[R].[s.l.]:[s.n.],2010.

[10] ZHOU D,BOUSQUET O,LAL T N,et al.Learning with local and global consistency[C]//Proceedings of the 16th international conference on neural information processing systems.Whistler,British Columbia,Canada:MIT Press，2004:321-328.

[11] GRADY L.Random walks for image segmentation[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2006,28(11):1768-1783.

[12] KIM T H,LEE K M,SANG U L.Nonparametric higher-order learning for interactive segmentation[C]//Proceedings of international conference of computer vision and pattern recognition.Seoul,South Korea:IEEE,2010:3201-3208.

AnImageSegmentationAlgorithmBasedonLabelPropagationGraphCut

YUAN Heng-dong

(School of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094,China)

The interactive image segmentation algorithm based on graph cut segments the foreground and background in the image based on the region of interest of the users,and has

the attention of many researchers in the field of computer vision and image processing.Traditional image segmentation algorithm is usually based on local features of image,which is limited to its convergence speed and description of image structure.In order to further improve the segmentation accuracy,an interactive image segmentation algorithm based on label propagation and graph cut is proposed.Firstly,a three-layer super-pixel layer structure graph model is introduced to consider the high-level information,which can further improve its robustness and stability.Then,the label propagation technology is utilized to cluster the unlabeled samples with limited labeled samples and improve the segmentation accuracy by combining the local and high-order information.Finally,the maximum flow/minimum cut algorithm is used to achieve the final segmentation result.Experiments on MSRC and Berkeley datasets demonstrate the effectiveness of the proposed algorithm comparing with state-of-the-art methods.

interactive image segmentation;graph cut;super pixels;label propagation

TP301.6

A

1673-629X(2017)12-0035-04

10.3969/j.issn.1673-629X.2017.12.008

2016-12-30

2017-05-03 < class="emphasis_bold">網(wǎng)絡出版時間

時間：2017-09-27

國家自然科學基金資助項目(61401209)；江蘇省自然科學基金青年基金項目(BK20140790)；中國博士后科學基金(2014T70525,2013M531364)

袁恒東(1992-)，男，碩士研究生，研究方向為圖像分割。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170927.0958.044.html