一種改進(jìn)的基于SLIC的自適應(yīng)GrabCut算法

安 超，李磊民，黃玉清

(1.西南科技大學(xué)信息工程學(xué)院，四川 綿陽 621000；2.西南科技大學(xué)國防科技學(xué)院，四川 綿陽 621000)

一種改進(jìn)的基于SLIC的自適應(yīng)GrabCut算法

安 超1，李磊民2，黃玉清1

(1.西南科技大學(xué)信息工程學(xué)院，四川 綿陽621000；2.西南科技大學(xué)國防科技學(xué)院，四川 綿陽621000)

圖像分割是對圖像進(jìn)行分析的關(guān)鍵步驟，是圖像識別和計算機(jī)視覺至關(guān)重要的預(yù)處理過程，也是計算機(jī)視覺的基礎(chǔ)技術(shù)之一。計算復(fù)雜度是判斷圖像分割算法好壞的重要標(biāo)準(zhǔn)，降低算法復(fù)雜度是當(dāng)前圖像分割領(lǐng)域的主要任務(wù)之一。針對GrabCut算法計算復(fù)雜度高、耗時長等缺點，提出了一種改進(jìn)的基于簡單線性迭代聚類(SLIC)的自適應(yīng)GrabCut算法。通過激光雷達(dá)獲取用戶交互信息，采用閾值法得到包含目標(biāo)的外截矩形框，并將其設(shè)為感興趣區(qū)域，然后采用SLIC算法對感興趣區(qū)域作預(yù)處理，最終構(gòu)建精簡的GraphCut網(wǎng)絡(luò)圖并進(jìn)行圖像分割。試驗結(jié)果證明，該算法縮小了SLIC預(yù)處理的圖像區(qū)域，減少了圖的節(jié)點數(shù)，降低了錯誤率，提高了目標(biāo)邊緣信息提取的精確度。

圖像分割； 簡單線性迭代聚類； 超像素； GrabCut算法； 激光雷達(dá)； 自適應(yīng)； 分割精度

0 引言

圖像分割是指將圖像中具有特殊意義的不同區(qū)域劃分開來。前景分割算法是將用戶感興趣的區(qū)域提取出來。如今，該算法的應(yīng)用領(lǐng)域十分廣泛，在計算機(jī)視覺和圖像工程等學(xué)科都發(fā)揮著重要的作用。

2001年，Boykov等[1]將GraphCut理論應(yīng)用于灰度圖像前景提取領(lǐng)域，實現(xiàn)圖像自動分割。Blake等[2]使用高斯混合模型對顏色空間進(jìn)行建模,得到較好的彩色圖像分割效果。2004年，Rother等[3]提出GrabCut算法，減小了用戶交互量。但高斯混合模型增加了算法的復(fù)雜度和運行時間。

針對算法耗時的缺陷，文獻(xiàn)[4]采用分水嶺算法對圖像進(jìn)行預(yù)分割，提高分割效率。文獻(xiàn)[5]通過壓縮圖像、降低圖像分辨率來提高運算速率。文獻(xiàn)[6]采用感興趣區(qū)域(regionofinterest,ROI)提高算法的準(zhǔn)確率。周良芬等[7]采用多尺度分水嶺平滑去噪,提高了分割精度。

針對GrabCut的缺陷，本文提出一種運用激光雷達(dá)獲取交互信息，并利用簡單線性迭代聚類(simplelineariterativecluster,SLIC)算法進(jìn)行預(yù)處理的自適應(yīng)的GrabCut分割算法。

1 SLIC簡介

假設(shè)第K個超像素中心為cj=[lj,aj,bj,xj,yj]T,點ci=[li,ai,bi,xi,yi]T到cj的距離ds的計算公式推導(dǎo)如下。

設(shè)：

(1)

則：

(2)

(3)

式中：dlab和dxy分別為像素點之間的顏色距離和空間距離；m為控制超像素緊密度的平衡參數(shù)(默認(rèn)為10)，其值越大，聚類越緊湊。

算法流程如下。

②在種子點n×n鄰域內(nèi)計算像素點的梯度值(n=3)，將種子點移到梯度值最小的地方。

③對于每個種子點，在它的2S×2S的鄰近區(qū)域計算距離，求取距離最小值作為該像素點的聚類中心。

④計算新的聚類中心點。

⑤計算殘留率E，如果E小于給定的閾值，則算法收斂。

⑥重復(fù)③～⑤，直至算法收斂。

⑦增強(qiáng)區(qū)域連通性。

2 GrabCut算法簡介

GrabCut算法是Rother等[3]基于GraphCut算法提出的，它將1幅圖像映射成1個無項網(wǎng)絡(luò)圖，并建立標(biāo)記的能量函數(shù)；然后采用最大流/最小割算法對網(wǎng)絡(luò)圖進(jìn)行分割，以得到能量函數(shù)的最小值，達(dá)到分割的目的。GrabCut用來分割的能量函數(shù)如下：

E(α,k,θ,z)=U(α,k,θ,z)+V(α,z)

(4)

(5)

式中:E為能量函數(shù)；U為數(shù)據(jù)項；V為平滑項。

算法原理圖如圖1所示。

圖1 算法原理圖

首先，將1幅給定的原圖像轉(zhuǎn)化為具有2個端點的加權(quán)圖G=(V,E)。其中，V為圖像像素點和端點的集合，E為像素點連線邊的集合。原圖像如圖1(a)所示，f1為前景標(biāo)記點，b1為背景標(biāo)記點。通過K-Means聚類得到圖像紋理特征的類別，然后使用GMM統(tǒng)計參數(shù)得到如圖1(b)所示的加權(quán)圖模型。得到加權(quán)圖后,通過Boykov[8-9]提出的最大流/最小割進(jìn)行全局分割，得到如圖1(c)所示的分割圖像。再經(jīng)過全局S-T最小割運算得到能量函數(shù)的最小解，得到如圖1(d)所示的分割結(jié)果。

GrabCut算法步驟如下。

(1)用戶在原始圖像上用1個矩形框選出可能的目標(biāo)，框外為背景區(qū)域(TB),框內(nèi)為未知區(qū)域(TU)。

(2)根據(jù)標(biāo)定的前景和背景區(qū)域初始化高斯混合模型(Gaussian mixture model,GMM)參數(shù)，對框內(nèi)區(qū)域迭代，直至收斂。

(3)重復(fù)步驟(2)直到收斂。

3 改進(jìn)的基于SLIC的自適應(yīng)GrabCut算法

3.1完成標(biāo)定的激光雷達(dá)識別目標(biāo)

由于GrabCut需要用戶交互來完成矩形框的選定，本文采用32線激光雷達(dá)和電荷耦合器件(charge coupled device,CCD)攝像頭聯(lián)合標(biāo)定建立映射關(guān)系，進(jìn)而完成用戶交互，實現(xiàn)對目標(biāo)的框選。交互信息獲取過程為：首先獲取雷達(dá)掃描障礙物的波形圖，然后將激光雷達(dá)和CCD圖像獲取的信息進(jìn)行融合，得到交互信息。

交互信息獲取示意圖如圖2所示。

圖2 交互信息獲取示意圖

圖2中：I為1幅RGB圖像，深色區(qū)域為檢測到的障礙物。激光雷達(dá)的作用就是檢測到障礙物并返回(x1,y1)和(x2,y2)2個坐標(biāo)點，進(jìn)而得到GrabCut算法交互所需的矩形框，精確定位目標(biāo)所在區(qū)域，從而完成GrabCut算法的自適應(yīng)交互。

3.2SLIC構(gòu)建超像素圖

通過上述激光雷達(dá)得到包含目標(biāo)的矩形框，將其設(shè)為感興趣區(qū)域，并采用SLIC算法對其進(jìn)行預(yù)處理。將圖像預(yù)分割成塊狀圖，通過聚類減少像素點。SLIC聚類每個超像素種子點的方法和標(biāo)準(zhǔn)的K-Means聚類算法不同。標(biāo)準(zhǔn)的K-Means算法是在整張圖中搜索像素點，而SLIC只是在以種子點為中心的2S×2S區(qū)域內(nèi)搜索，提高了算法的運算速度。最終，采用鄰近合并的方法來消除比較小的超像素，提高連通性。

像素搜索范圍比較如圖3所示。

圖3 像素搜索范圍比較圖

3.3GrabCut算法實現(xiàn)圖像分割

在文獻(xiàn)[10]中，胡志立等采用SLIC算法對圖像進(jìn)行預(yù)處理，然后運用GrabCut進(jìn)行分割，大大縮短了算法的運行時間，取得了良好的效果。

針對傳統(tǒng)GrabCut存在的耗時較長、運算復(fù)雜等缺陷，本文利用高斯混合模型(Gaussianmixturemodel,GMM)來取代直方圖描述背景和前景像素的分布，并采用迭代估計法替代一次最小化估計，使能量函數(shù)達(dá)到最小，提高分割速度和精度。

(1)初始化GMM參數(shù)。

分別對前景和背景進(jìn)行高斯混合模型建模，利用K-Means對前景和背景分別進(jìn)行特征聚類,得到某個像素屬于前景或背景的概率D(x)、均值μ(α,k)、協(xié)方差∑(α,k)、權(quán)重π(α,k)。

(2)迭代估計GMM參數(shù)。

①為每個超像素分配GMM中的高斯分量，將加權(quán)概率最大的高斯分量設(shè)為它的GMM高斯標(biāo)簽。這樣，每個高斯分量都有一些超像素作為樣本。通過這些像素樣本的超像素值，可以估計出各個高斯分量的均值和協(xié)方差。該高斯分量的權(quán)重可以通過屬于該高斯分量的超像素個數(shù)與總的超像素個數(shù)的比值得到。

②通過超像素之間的鄰近關(guān)系構(gòu)造網(wǎng)絡(luò)圖，并采用最大流/最小割算法進(jìn)行分割。

3.4算法實現(xiàn)步驟

算法的實現(xiàn)步驟如下。

(1)讀入彩色圖像，通過激光雷達(dá)在輸出圖像上標(biāo)出1個包含目標(biāo)的矩形框。將矩形框設(shè)為感興趣區(qū)域。

(2)利用SLIC算法對感興趣區(qū)域圖像進(jìn)行預(yù)處理，輸出塊編碼及塊邊界的索引圖。

(4)迭代估計GMM參數(shù)：

①GMM標(biāo)號;

②學(xué)習(xí)GMM參數(shù);

③根據(jù)分塊之間的鄰近關(guān)系構(gòu)建網(wǎng)絡(luò)圖，并進(jìn)行最小割分割;

④重復(fù)步驟①～③，直到算法收斂。

(5)輸出分割圖像。

4 試驗結(jié)果與分析

本文的試驗平臺包括：64位Windows7,MATLABR2014b,MicrosoftVisualStudio2013,計算機(jī)配置有2.4GHz的Intel雙核CPU4GB內(nèi)存。對于每幅圖像，由激光雷達(dá)先設(shè)置1個選中目標(biāo)區(qū)域的矩形框，并用SLIC算法對其預(yù)處理，最后用GrabCut算法進(jìn)行分割。將分割結(jié)果分別與GrabCut算法、分水嶺算法分割結(jié)果進(jìn)行比較。本次試驗選取具有代表性的圖像，分別為cats.jpg、bear.jpg、horse.jpg。

對圖像進(jìn)行用不同超像素數(shù)目進(jìn)行預(yù)處理,由超像素處理結(jié)果可知，設(shè)定的超像素數(shù)量越大，聚類效果越好。但是在數(shù)量增加的同時，也會增加算法的復(fù)雜度，影響運行效率。通過試驗測試可知，當(dāng)超像素數(shù)量設(shè)為500時，已經(jīng)取得較好的聚類效果。所以，本算法中的超像素數(shù)目為500。

通過選擇簡單背景和復(fù)雜背景兩種類別的圖像進(jìn)行試驗。由試驗結(jié)果可知，對于背景復(fù)雜的圖片，GrabCut算法和分水嶺算法都不能產(chǎn)生較好的分割效果,對簡單背景分割精度和耗時方面都不是很理想。本文算法對背景復(fù)雜的貓頭和熊的后半部分進(jìn)行分割的效果比較好，邊緣信息更光滑。對背景單一的Horse圖片也能產(chǎn)生較好的邊緣分割效果。

綜上分析，在復(fù)雜背景和單一背景下，本算法和GrabCut算法分割精度基本一致。另外，分水嶺算法對前景像素的標(biāo)記要求比較高，造成分塊區(qū)域內(nèi)一致性不夠強(qiáng)，對背景復(fù)雜的區(qū)域分割效果比較差，所以分割精度和分割邊緣光滑度均不如本算法。

本文對算法的精度進(jìn)行了評估。將分割正確率R作為分割精度的度量標(biāo)準(zhǔn)，定義如下：

(6)

分割正確率和分割時間對比如表1所示。

表1 分割正確率與分割時間對比

從表1可以看出,本文算法正確率顯著提高。對于Horse圖像，由于前景和背景差別較大，所以分割正確率比較高；對Bear圖像，由于背景比較復(fù)雜，分割正確率比較低。由分割時間可以看出，圖片越大，分割時間越長。由此可以看出，本算法在背景和前景差別比較大的時候分割效果比較好。

綜上所述，本算法較原算法在速度上有了提高，比分水嶺算法的分割時間更短、精度更高。從時間和正確率分析，本文算法提取目標(biāo)更加準(zhǔn)確、省時，并且在背景復(fù)雜的情況下也能產(chǎn)生較好的分割效果，分割的邊緣更加細(xì)致、光滑。

5 結(jié)束語

針對GrabCut算法分割耗時問題，在SLIC超像素處理的基礎(chǔ)上，本文提出了一種改進(jìn)的基于SLIC的GrabCut算法，既可以保證GrabCut算法的精度，又能提高運行速率。通過激光雷達(dá)對目標(biāo)進(jìn)行定位，用矩形框框選出目標(biāo)，減小了圖像處理時前景像素搜索區(qū)域。把矩形框設(shè)定為感興趣區(qū)域并用SLIC進(jìn)行超像素處理成塊狀圖，用每個塊中RGB均值像素代替整個塊中的每個像素，減少了超像素處理的像素點和后期GMM高斯混合模型迭代的復(fù)雜度，從而減少了整個算法的運行時間。試驗結(jié)果表明，與原算法相比，本算法在分割時間上有較大的提升。

[1]BOYKOVY,JOLLYMP.InteractivegraphcutsforoptimalboundaryandregionsegmentationofobjectsinN-Dimages[C]//IEEEInternationalConferenceonComputerVision,2001:105-112.

[2]BLAKEA,ROTHERC,BROWNM,etal.InteractiveimagesegmentationusinganadaptiveGMMRFmodel[C]//EuropeanConferenceonComputerVision-eccv,2004.

[3]ROTHERC,KOLMOGOROVV,BLAKEA."GrabCut":interactiveforegroundextractionusingiteratedgraphcuts[J].AcmTransactionsonGraphics,2004,23(3):307-312.

[4]LIY，SUNJ，TANGCK，etal.Lazysnapping[J].ACMTransactionsonGraphics，2004，23(3)：303-308.

[5] 丁紅,張曉峰.基于快速收斂Grabcut的目標(biāo)提取算法[J].計算機(jī)工程與設(shè)計,2012(4):1477-1481.

[6] 徐秋平,郭敏,王亞榮.基于分水嶺變換和圖割的彩色圖像快速分割[J].計算機(jī)工程,2009(19):210-212.

[7] 周良芬,何建農(nóng).基于GrabCut改進(jìn)的圖像分割算法[J].計算機(jī)應(yīng)用,2013,33(1):49-52.

[8]BOYKOVY,VEKSLERO,ZABIHR.Fasterapproximateenergyminimizationviagraphcuts[J].IEEETransactiononPatternAnalysisandMachineIntelligence,2001,23(11):1-18.

[9]BOYKOVY,KOLMOGOROVV.Anexperimentalcomparisonofmin-cut/max-flowalgorithmsforenergyminimizationinvision[J].IEEETransationonPatternAnalysisandMachineIntelligence,2004,26(9):1124-1137.

[10]胡志立,郭敏.基于SLIC的改進(jìn)GrabCut彩色圖像快速分割[J].計算機(jī)工程與應(yīng)用,2016(2):186-190.

AnImprovedAdaptiveGrabCutAlgorithmBasedonSLIC

AN Chao1,LI Leimin2,HUANG Yuqing1

(1.School of Information Engineering,Southwest University of Science and Technology,Mianyang621000,China;2.School of National Defence Science and Technology,Southwest University of Science and Technology,Mianyang621000,China)

Image segmentation is a key step in the analysis and understanding of images.It is the critical preprocessing procedure of image recognition and computer vision,and also one of the basic technologies of computer vision.Computational complexity is an important criterion for judging if an image segmentation algorithm is good or not,so reducing the complexity of the algorithm is one of the main tasks in the field of image segmentation.Aiming at the shortcomings of GrabCut algorithm,such as high complexity and long time consuming,an improved adaptive GrabCut algorithm based on simple linear iterative clustering (SLIC) is proposed.The laser radar obtains the user interaction information,uses the threshold method to get the outer cut rectangular frame containing the targets,and sets it into the region of interest.Then the SLIC algorithm is used to preprocess the region of interest.Finally,a concise GraphCut network diagram is built and the image segmentation process is conducted.The test results show that the proposed algorithm reduces the size of the image region of SLIC preprocessing and reduces the number of nodes in the graph,thus the error rate is reduced and the precision of extraction of target edge information is improved.

Image segment； Simple linear iterative cluster(SLIC); Ultra pixel； GrabCut algorithm; Laser radar; Self-adaption; Segmentation accuracy

TH7；TP39

10.16086/j.cnki.issn1000-0380.201710005

修改稿收到日期:2017-04-11

安超(1990—)，男，在讀碩士研究生，主要從事圖像分割、機(jī)器視覺等方向的研究。E-mail827130596@qq.com。

李磊民(通信作者)，男，碩士，教授，主要從事機(jī)器視覺、圖像恢復(fù)等方向的研究。E-mail:228660169@qq.com。