基于SLIC超像素的Grab Cut算法改进

1 .基于 SLIC 超像素的 Grab Cut 算法改进 作者：董茜、颜凯、孙婷婷、张思远 主讲人：董茜 

2 .研究背景 Research Background 图像识别 图像分割就是把图像分成若干个特定的、具有 独特性质的区域并提出感兴趣目标的技术和过 图像搜索 程。它是由图像处理到图像分析的关键步骤。 图像分析 应用领域相当广 人脸识别 车牌识别 图片检索 视频分析 

3 .研究背景 Research Background 超像素算法主要是将图像中的像素在感知上划 分为一个个原子区域，用这些原子区域将图像 分割成一个个超像素快，这些超像素块中的所 有像素具有特征相似的特点。用它们来代替原 有无意义的像素点，可以大大降低图像的运算 速度和分割准确率。 摄录像设备高速发展，单幅图像像素越来越高 NC 算法 GS 算法 SL 算法 基于图论 超像素算法分类 TP 算法 QS 算法 WS 算法 基于梯度上升法 GCa 、 GCb 算 SLIC 算 法 法 

4 .研究背景 GrubCut 算 法 Research Background 中级处理 SLIC 算 分割 表示与描述 法 预处理 识别与 结果 知识库 问题 解释 图像获取 低级处理 高级处理 图像分析系统基本构成 

5 .研究内容 Research Content SLIC 算法 SLIC （简单线性、迭代聚类）算法是 K-means 算法的改进算法 ，它在由 CIELAB 色彩空间中的 L,a,b 值和 x,y 坐标像素所构成的五维 空间中执行一个局部的像素点聚合。一种新的距离度量能够实现超像 素形状的紧凑、有规则，并能够无缝隙的包含灰度及彩色图像。 SLIC 实现起来比较简单 , 容易在实践中应用——唯一的参数指定所需超像素 点的数量。 SLIC 是一种通过利用像素的颜色相似度和图像片面空间对 像素进行聚类，从而有效的生成紧凑的几乎统一化的超像素的分割方 法。 SLIC 分割方法使用简单，只需给定需要得到的超像素的数量即可 ，且运行速度快，只需要线性的运行时间和存储空间。 SLIC 分割方法 生成的超像素具有较好的紧凑性和边界贴合度，超像素大小一致且形 状均匀。 形状较均匀 边界附着率较高 速度最快 

6 .研究内容 Research Content K-means 算法过程 ① 随机在图中取 K （这里 K=2 ）个种子点。 ② 然后对图中的所有点求到这 K 个种子点的距离，假如点 Pi 离种子点 Si 最近，那么 Pi 属于 Si 点群。（图中，我们可以看到 A ， B 属于上面 的种子点， C ， D ， E 属于下面中部的种子点） ③ 接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的 第 3 步） ④ 然后重复第 2 和第 3 步，直到种子点没有移动，一般迭代十次即可 。 

7 .研究内容 Research Content SLIC 算法过程 ① 初始化种子点（聚类中心）：按照设定的超像素个数，在图像内均 匀的分配种子点。 图片总共有 N 个像素点，预分割为 K 个相同尺寸的 超像素，每个超像素的大小为 N/K ，相邻种子店的距离（步长）近似 S  N /k 为 ② 在种子点的 3*3 邻域内重新选择种子点，计算该邻域内所有像素点 的梯度最小的地方，避免种子点落在噪声点上。 ③ 在每个种子点周围的邻域内为每个像素点分配类标签： SLIC 的搜索 范围限制为 2S*2S, 从而加速算法收敛。 

8 . 研究内容 Research Content 01 SLIC 02 Grab Cut Grab Cut 算法 预处理生成超像素 通过交互式方法进行分割 Grab Cut 算法是 一种交互式图像分割算法。它在 Graph Cut 算法上做 了改进。 Graph Cuts 交互式图像分割算法，结合使用了颜色与边界这两类 信息。但该算法只能分割灰度图像 , 且用户交互繁琐。 Grab Cut 有如下改 进： ① Grab Cut 使用迭代方式来求解最小值 , 而不是一次性求出 , 增加了 精确性 ; ② Grab Cut 使用了不完全标记法 , 在用户侧只需要一个方框将对象主 体框进去即可完成分割 , 大大简化了用户的操作 ; ③ Grab Cut 使用了高斯混合模型取代灰度直方图 , 实现了彩色图像的 分割。 

9 . 算法改进 Algorithm Improvement 改进 SLIC 算法 问题描述： SLIC 超像素是使用随机方式选取聚类中心 , 随意性很 高 , 若选取的点都落在同一处时 , 可能会增加算法的迭代次数、造成大 量的冗余、得到的超像素个数较少、大小形状不规则等情况。 改进前：随机选取超像 改进后：均匀分布的超像素聚类中心 改进方法：在选取 k 个超像素后 , 首先 , 将整幅图像分割成 a 个大 素 小相同的区域 , 在每个区域中随机选择 b 个点当做超像素的中心 , 记作 SLIC （ a,b ）。根据经验一般 b 的取值为 [1,2] 。根据 b 的取值来得到 a 的取值。假设 a=20, 图像的分辨率为 400*300 ，那么每个区域的大小 为 20*15 。取每个区域的中心点作为超像素的聚类中心。 算法优点：修改了算法的搜索空间，进一步减少迭代次数和重复像 素的计算个数。 

10 . 算法改进 Algorithm Improvement 改进 Grab Cut 算法 问题描述： Grab Cut 算法虽然经过迭代可以有效提高分割结果的精确性 , 但 是算法的效率低下。 改进思路：由于在分割过程中 , Grab Cut 是对区域内所有像素点进行采样来构 建高斯混合模型 , 最后通过最小化能量方程的方式进行图像分割。但是若仅仅对像 超像素分割图 素进行抽样采样又会影响算法的分割效果。为了提高 Grab Cut 算法的运算效率 , 减少采样量是一个可行的办法 , 但为了保证高斯混合模型的完整性 , 无法对所有像 素点进行抽样 , 因此可以使用多个像素聚类而成的超像素的方法。 具体方法：可以将取超像素中所有像素的平均特征值 , 以该平均值表示该超像 素的特征 , 作为加权图中的一个节点。由于超像素是多个具有相同或类似像素点的 聚类 , 为了有效地提升算法效率 , 只在每一个超像素中随机采样 n 个像素 , 以这 n 由超像素建立加权图 个像素的平均特征值作为加权图中的节点即可。 

11 .实验验证 Experimental Verification 分辨率 189*286 原图 自动分割 交互信息 迭代一次 迭代二次 迭代三次 迭代四次 迭代五次 

12 .实验验证 Experimental Verification 分辨率 1024*726 原图 交互信息 迭代一次 迭代二次 迭代三次 

13 .实验验证 Experimental Verification 使用算法 项目 自动分割 传统 Grab Cut 改进后的 Grab Cut 图片分辨率 189*286 1024*726 189*286 1024*726 189*286 1024*726 用户是否编 ✕ ✕ ✓ ✓ ✓ ✓ 辑 迭代次数 5 3 5 3 5 3 使用时间 7826.7 11832.4 14313.6 40275.2 4074.8 9378.3 (ms) 实验证明：结合 SLIC 超像素算法和 Grab Cut 算法的基础上提出的基于改进 SLIC 超像素的 Grab Cut 算法 , 保 留了传统 Grab Cut 的精确性 , 并且迭代次数较少 , 运行时间较短。在一定程度上提升了传统 Grab Cut 算法的运行效 率。 

14 .谢谢 appletung@uestc.edu.cn