一種改進的基于SLIC的自適應GrabCut算法

安 超，李磊民，黃玉清

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

一種改進的基于SLIC的自適應GrabCut算法

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

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

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

圖像分割； 簡單線性迭代聚類； 超像素； GrabCut算法； 激光雷達； 自適應； 分割精度

0 引言

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

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

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

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

1 SLIC簡介

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

設：

(1)

則：

(2)

(3)

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

算法流程如下。

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

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

④計算新的聚類中心點。

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

⑥重復③～⑤，直至算法收斂。

⑦增強區域連通性。

2 GrabCut算法簡介

GrabCut算法是Rother等[3]基于GraphCut算法提出的，它將1幅圖像映射成1個無項網絡圖，并建立標記的能量函數；然后采用最大流/最小割算法對網絡圖進行分割，以得到能量函數的最小值，達到分割的目的。GrabCut用來分割的能量函數如下：

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

(4)

(5)

式中:E為能量函數；U為數據項；V為平滑項。

算法原理圖如圖1所示。

圖1 算法原理圖

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

GrabCut算法步驟如下。

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

(2)根據標定的前景和背景區域初始化高斯混合模型(Gaussian mixture model,GMM)參數，對框內區域迭代，直至收斂。

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

3 改進的基于SLIC的自適應GrabCut算法

3.1完成標定的激光雷達識別目標

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

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

圖2 交互信息獲取示意圖

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

3.2SLIC構建超像素圖

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

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

圖3 像素搜索范圍比較圖

3.3GrabCut算法實現圖像分割

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

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

(1)初始化GMM參數。

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

(2)迭代估計GMM參數。

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

②通過超像素之間的鄰近關系構造網絡圖，并采用最大流/最小割算法進行分割。

3.4算法實現步驟

算法的實現步驟如下。

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

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

(4)迭代估計GMM參數：

①GMM標號;

②學習GMM參數;

③根據分塊之間的鄰近關系構建網絡圖，并進行最小割分割;

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

(5)輸出分割圖像。

4 試驗結果與分析

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

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

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

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

本文對算法的精度進行了評估。將分割正確率R作為分割精度的度量標準，定義如下：

(6)

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

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

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

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

5 結束語

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

[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的目標提取算法[J].計算機工程與設計,2012(4):1477-1481.

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

[7] 周良芬,何建農.基于GrabCut改進的圖像分割算法[J].計算機應用,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的改進GrabCut彩色圖像快速分割[J].計算機工程與應用,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—)，男，在讀碩士研究生，主要從事圖像分割、機器視覺等方向的研究。E-mail827130596@qq.com。

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