一种改进的基于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。