Superpixel Segmentation

Presentation on theme: "Superpixel Segmentation"— Presentation transcript:

1 Superpixel Segmentation
2/25/2019 赵海伟 戴嘉伦 王如晨 CVBIOUC,Ocean University of China 指导教师：郑海永 3/23/2015

2 Superpixel Segmentation
2/25/2019 Introduction Superpixel History 基于图论的超像素分割方法 Normalized cuts Graph-based segmentation 基于梯度上升的超像素分割方法 Mean shift 算法 TurboPixels SLIC Experimental comparision 3/23/2015

3 Introduction Image segmentation Threshold segmentation
2/25/2019 Image segmentation Threshold segmentation Edge segmentation Morphologic segmentation 基于像素级的传统分割算法 1. 像素并不是视觉感知的着重点！ 2. 图像的分辨率不断增大，许多基于像素级的传统分割算法花费的时间越来越长，如何才能减少分割的数据运算量成为图像分割的难题之一！ 3/23/2015

4 Introduction Superpixel
2/25/2019 Superpixel 人类视觉感知到的图像信息并不是从某一个孤立的像素点得到的，而是从由大量像素点组合而成的区域得到的，孤立的单一像素点并没有具体的实际意义，只有许多像素点组合在一起才对人类的视觉感知有意义。 3/23/2015

5 Introduction Superpixel
2/25/2019 Superpixel 超像素，是指具有相似纹理、颜色、亮度等特征的相邻像素构成的图像块。这些图像块大都没有破坏图像的边界信息，而且还保留了对图像进行进一步分割的有效信息。 3/23/2015

6 Introduction Superpixel Segmentation
2/25/2019 Superpixel Segmentation 使用了超像素后可以有效地减少图像局部信息冗余，使图像处理的复杂度和运算量大大降低，目前被广泛地应用于计算机视觉领域中，并且常作为图像分割和模式识别的初始阶段。 3/23/2015

7 Introduction History of Superpixel Segmentation
2/25/2019 History of Superpixel Segmentation Ren 等人于2003年最早提出了超像素这一概念。 Felzenszwalb 等人于2004 年提出了一种基于图的超像素 分割方法。主要是一种“小而合并”的思想。 Levinshtein 等人于2009年采用了一种基于几何流的水平 集方法，能快速地产生超像素。 Achanta等人于2012年在TPAMI发表论文SLIC。 Learning a classification model for segmentation.IEEE 2003, Ren et. al. Efficient graph-based image segmentation.IJCV,2004, Pedro F et. al. Fast superpixels using geometric flows. IEEE Alex Levinshtein et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

8 Introduction 基于图论的超像素分割方法 基于梯度上升的超像素分割方法 Normalized cuts
2/25/2019 基于图论的超像素分割方法 Normalized cuts Graph-based segmentation 基于梯度上升的超像素分割方法 Mean shift 算法 TurboPixels SLIC 2009 年Levinshtein等人采用了一种基于几何流的水平集方法，能快速地产生超像素。该方法来源于早期计算机视觉领域中的曲线演化技术。通过膨胀初始化种子点， 并结合曲率演化模型和背景区域的骨架化过程， 将图像分割为网格状的超像素。 SLIC 是Simple Linear Iterative Clustering的缩写，最早由Achanta于2010 年6 月在洛桑联邦理工学院的一次技术报告中提出。2012年经整理、完善后发表在TPAMI上。 Learning a classification model for segmentation.IEEE 2003, Ren et. al. Efficient graph-based image segmentation.IJCV,2004, Pedro F et. al. Fast superpixels using geometric flows. IEEE Alex Levinshtein et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

9 SLIC SLIC- Simple Linear Iterative Clustering
2/25/2019 SLIC- Simple Linear Iterative Clustering Slic superpixels.Technical report,2010,Achanta,et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

10 动态聚类法——C-均值法 2/25/2019 Cluster 根据待分类的模式属性或特征相似程度进行分类，相似的模式归为一类，不相似对的模式分划到不同类中，将待分类的模式集分成若干个互不重叠的子集。 定义适当的准则函数，运用有关的数学工具，或利用有关统计的概念和原理进行分类。 3/23/2015

11 动态聚类法——C-均值法 ⒈ 条件及约定 设待分类的模式特征矢量集为： 类的数目C是事先取定的。 ⒉ 算法思想
2/25/2019 ⒈ 条件及约定 设待分类的模式特征矢量集为： 类的数目C是事先取定的。 ⒉ 算法思想 该方法取定C个类别和选取 C个初始聚类中心，按最小距离原则将各模式分配到 C类中的某一类，之后不断地计算类心和调整各模式的类别，最终使各模式到其判属类别中心的距离平方之和最小。 3/23/2015

12 聚类中心发生变化（E ≤threshold）
动态聚类法——C-均值法 2/25/2019 3.动态聚类框图 初始化聚类中心 相似性度量 True 聚类中心发生变化（E ≤threshold） 输出最终聚类结果 False 确定新的聚类中心 3/23/2015

13 动态聚类法——C-均值法 4.算法原理步骤 ⑴ 任选C个模式特征矢量作为初始聚类中心： , 令 。
2/25/2019 4.算法原理步骤 ⑴ 任选C个模式特征矢量作为初始聚类中心： , 令 。 ⑵ 将待分类的模式特征矢量集 中的模式逐个按最小距离原则分划给C类中的某一类，即: 如果 则 , 式中 表示 和 的中心 的距离，上角标 表示迭代次数。于是产生新聚类 。 3/23/2015

14 动态聚类法——C-均值法 4.算法原理步骤 (3) 计算重新分类后的各类心 式中 为类 中所含模式的个数。
2/25/2019 4.算法原理步骤 (3) 计算重新分类后的各类心 式中 为类 中所含模式的个数。 (4) 如果 ,则结束,否则 ,转至(2)。 3/23/2015

15 到哪个聚类中心的距离最小，这个点就属于哪一类
动态聚类法——C-均值法 2/25/2019 选取K个初始聚类中心 计算每一个点到K个聚类中心的距离 True 到哪个聚类中心的距离最小，这个点就属于哪一类 聚类中心发生变化 输出最终聚类结果 False 更新聚类中心为该类中所有样本的均值向量 3/23/2015

16 Segmentation of [1] using SLIC
2/25/2019 Original Image Ground True SLIC 是Simple Linear Iterative Clustering 的缩写，最早由Achanta [3] 于2010 年6 月在洛桑联邦理工学院的一次技术报告中提出。2012 年经整理、完善后发表在TPAMI 上[4]。其中“Linear”体现在算法复杂度O(N) 与图像中像素个数N 是线性关系，“Clustering” 是采用k-均值聚类。 Segmentation of [1] using SLIC Multi-Class Segmentation with Relative Location Prior , S. Gould, et. al. Slic superpixels.Technical report,2010,Achanta,et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

17 C-均值法与SLIC 算法搜索区域的区别 2/25/2019 SLIC 优化了距离计算的数目：传统的k-均值方法中每个聚类中心 的搜索范围是整幅图像，要计算该聚类中心与图像中所有像素 点之间的距离，而SLIC 算法只在与预设的超像素尺寸成比例的一 个区域内搜索。 SLIC 算法在计算聚类中心与像素点之间的距离时同时结合了颜色 和空间位置两方面的信息来表征其相似度，这样可以起到控制 超像素尺寸和紧密度的作用。 SLIC 是一种使用简单和易于理解的方法，是对传统的k-均值超像素分割方法的改进。 3/23/2015

18 SLIC——步骤 该算法只有一个参数k，即所需生成的近似同样大 小的超像素的个数。 a）初始化聚类中心。 b）相似度衡量。
2/25/2019 该算法只有一个参数k，即所需生成的近似同样大 小的超像素的个数。 a）初始化聚类中心。 b）相似度衡量。 c）确定新的聚类中心。 重复b）和c）直至最后收敛（E ≤threshold）。 初始化聚类中心 True 聚类中心发生变化 False 输出最终聚类结果 相似性度量 确定新的聚类中心 3/23/2015

19 SLIC——步骤 2/25/2019 (a) 初始化聚类中心： 假设一幅彩色图像有N 个像素点，预分割为k 个相同尺 寸的超像素，那么首先要将该彩色图像转换为CIELAB 颜 色空间和XY 坐标下的5 维特征向量，然后将图像均分为 k个网格，网格边长为 ，k 个初始聚类中心 为每个网格内色阶值最低的像素。 对图像中的每一个像素点j，令其与最近的聚类中心i的 距离d(ij) 的初始值为正无穷。 色阶表示的是图像亮度强弱的数值。 3/23/2015

20 SLIC——步骤 2/25/2019 (b) 相似度衡量： 对于每个聚类中心i，逐一计算其2S*2S 邻域内各像素j 与该类中心点的距离D，若D < d(ij)，选取最小的D所属 的类别i，将j暂时归为该类i，并且将d(ij) 赋值为D，其 中： 3/23/2015

21 SLIC——步骤 (c) 确定新的聚类中心： (d) 输出最终聚类结果：
2/25/2019 (c) 确定新的聚类中心： 当每个像素都被归类到其最近的聚类中心后，新的聚类中心为该 类中所有像素的[l,a,b,x,y]T 向量的平均值。 为了避免聚类中心落在边界上，以及对后续的聚类过程造成干扰， 需要将聚类中心在以3*3 的邻域内打乱，将聚类中心移到邻域内梯 度最小的地方（图像灰度值变化最缓慢的地方）。 计算残差E（新的聚类中心与之前聚类中心的L1范数）。 (d) 输出最终聚类结果： 重复(b) 和(c) 直至最后收敛（E≤threshold）。 3/23/2015

22 SLIC——算法 j=1 E≤ threshold End 将N个像素点的图像均分为K份，网格边长为S
2/25/2019 j=1 E≤ threshold End 将N个像素点的图像均分为K份，网格边长为S 计算残差E(新的聚类中心与之前聚类中心的L1范数) 初始化K个聚类中心为每个网格内色阶值最低的像素点 将聚类中心移到3*3邻域内梯度值最小位置 计算新的聚类中心为该类中所有像素向量的平均值 对于图像中像素点j令其与最近的聚类中心i的距离d(ij)为正无穷 True j<N False j=j+1 对于每个聚类中心计算2S*2S邻域内各像素j与该类中心点i的距离D D<d(ij) False True 选取最小的D所属的类别i使j∈i且d(ij)=D 3/23/2015

23 SLIC——实验 EM Image GS04 TP09 QS09 SLIC
2/25/2019 EM Image GS04 TP09 QS09 SLIC Slic superpixels.Technical report,2010,Achanta,et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

24 SLIC——实验 2/25/2019 (a) (b) Plot of the under-segmentation error w.r.t. number of superpixels. Plot of the boundary recall w.r.t. number of superpixels. Slic superpixels.Technical report,2010,Achanta,et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

25 SLIC——实验 2/25/2019 (a) (b) (a) Plot of the time taken for 10 iterations of k-means (GKM) versus our algorithm for dierent number of superpixels on input images of size (b) Plot of the segmentation time taken (in seconds) versus image size in pixels. Slic superpixels.Technical report,2010,Achanta,et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

26 SLIC——应用 SLIC supervoxels computed for a video sequence:
2/25/2019 SLIC supervoxels computed for a video sequence: Slic superpixels.Technical report,2010,Achanta,et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

27 SLIC——应用 2/25/2019 SLIC applied to segment mitochondria from 2D and 3D EM images of neural tissue： (a) SLIC superpixels from an EM slice. (b) The segmentation result from another method. (c) SLIC supervoxels on a 1024*1024*600 volume. (d)Mitochondria extracted using another method. Slic superpixels.Technical report,2010,Achanta,et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

28 Experimental comparision
2/25/2019 Graph-based segmentation、Ncut、Mean shift、 TurboPixels、SLIC 方法的实验效果： Graph-based Ncut Mean shift TurboPixels SLIC 是否可控制超像素的数目 否 是 运行时间（327 *400 像素） 1.470s 78.188s 1.377s 9.493s 0.314s Learning a classification model for segmentation.IEEE 2003, Ren et. al. Efficient graph-based image segmentation.IJCV,2004, Pedro F et. al. Fast superpixels using geometric flows. IEEE Alex Levinshtein et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

29 Experimental comparison
2/25/2019 Graph-based segmentation： Input image sigma = 0.3, k = 350, min = 1200 Learning a classification model for segmentation.IEEE 2003, Ren et. al. Efficient graph-based image segmentation.IJCV,2004, Pedro F et. al. Fast superpixels using geometric flows. IEEE Alex Levinshtein et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

30 Experimental comparison
2/25/2019 Ncut： Input image Nsp = 200 Learning a classification model for segmentation.IEEE 2003, Ren et. al. Efficient graph-based image segmentation.IJCV,2004, Pedro F et. al. Fast superpixels using geometric flows. IEEE Alex Levinshtein et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

31 Experimental comparison
2/25/2019 Mean shift： Input image ratio = 0.5, kernelsize = 2, maxdist = 10 Learning a classification model for segmentation.IEEE 2003, Ren et. al. Efficient graph-based image segmentation.IJCV,2004, Pedro F et. al. Fast superpixels using geometric flows. IEEE Alex Levinshtein et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

32 Experimental comparison
2/25/2019 TurboPixels： Input image Nsp = 200 Learning a classification model for segmentation.IEEE 2003, Ren et. al. Efficient graph-based image segmentation.IJCV,2004, Pedro F et. al. Fast superpixels using geometric flows. IEEE Alex Levinshtein et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

33 Experimental comparison
2/25/2019 SLIC ： Input image regionSize = 10, regularizer = 10 Learning a classification model for segmentation.IEEE 2003, Ren et. al. Efficient graph-based image segmentation.IJCV,2004, Pedro F et. al. Fast superpixels using geometric flows. IEEE Alex Levinshtein et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

34 Experimental comparison
2/25/2019 Input image Graph-based segmentation Ncut Mean shift TurboPixels SLIC Learning a classification model for segmentation.IEEE 2003, Ren et. al. Efficient graph-based image segmentation.IJCV,2004, Pedro F et. al. Fast superpixels using geometric flows. IEEE Alex Levinshtein et .al. Slic superpixels compared to state-of-the-art superpixel methods. TPAMI,2012, Achanta,et .al. 3/23/2015

35 Superpixel Segmentation
Thank you for your attention! Q&A