安 超，李磊民，黃玉清

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

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

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

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

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

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

0 引言

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

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

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

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

1 SLIC簡(jiǎn)介

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

設(shè)：

(1)

則：

(2)

(3)

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

算法流程如下。

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

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

④計(jì)算新的聚類中心點(diǎn)。

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

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

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

2 GrabCut算法簡(jiǎn)介

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

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

(4)

(5)

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

算法原理圖如圖1所示。

圖1 算法原理圖

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

GrabCut算法步驟如下。

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

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

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

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

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

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

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

圖2 交互信息獲取示意圖

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

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

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

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

圖3 像素搜索范圍比較圖

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

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

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

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

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

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

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

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

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

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

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

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

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

①GMM標(biāo)號(hào);

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

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

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

(5)輸出分割圖像。

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

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

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

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

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

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

(6)

分割正確率和分割時(shí)間對(duì)比如表1所示。

表1 分割正確率與分割時(shí)間對(duì)比

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

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

5 結(jié)束語(yǔ)

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

[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ì)算機(jī)工程與設(shè)計(jì),2012(4):1477-1481.

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

[7] 周良芬,何建農(nóng).基于GrabCut改進(jìn)的圖像分割算法[J].計(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ì)算機(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ī)器視覺(jué)等方向的研究。E-mail827130596@qq.com。

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