精华内容
下载资源
问答
  • SLIC超像素算法

    千次阅读 2020-03-08 11:12:31
    文章目录一、前言二、现有的超像素算法2.1 基于图的算法2.2 基于梯度上升的方法三、SLIC超像素3.1 算法详解3.2 距离测量2.3 后处理2.4 时间复杂度 一、前言 源码下载:https://www.epfl.ch/labs/ivrl/superpixels/ ...

    一、前言

    官网:https://www.epfl.ch/labs/ivrl/superpixels/
    超像素是把一张图片中具有相似特征的像素进行聚类,形成一个更具有代表性的大“像素”。这个新的像素可以作为其他图像处理算法的基本单位,可以减低图像的维度和异常像素点。为了解现有方法的优点和缺点,我们比较了目前最好的五种超像素算法,比较的指标为图像边界的粘附性,算法速度,存储效率,以及它们对分割性能的影响。

    这介绍简单的线性迭代聚类(SLIC)超像素算法,它采用k均值聚类方法高效地生成超像素。尽管它很简单,但SLIC较以前的算法可以更好地获取边界,同时,它具有更快的速度,更高的内存效率,并且能提高分割性能,也可以直接扩展到超体元生成。
    关键词-超像素,分割,聚类,k均值。

    目前常用的超像素分割算法有SLIC、SEEDS和LSC。
    在这里插入图片描述
    超像素算法将像素组合成感知有意义的原子区域( atomic regions),其可以用于替换像素网格的刚性结构。它们捕获图像冗余,提供计算图像特征的方便原语( primitive ),并且大大降低了后续图像处理任务的复杂性。
    如果超像素用于构建具有更规则的晶格的图形,虽然很难定义指标来判断算法的优劣性,但我们相信以下属性通常是可取的:

    1. 超像素应当良好地粘附到图像边界。
    2. 当作为预处理步骤用于降低的计算复杂度时,超像素应当快速计算,存储 器效率高且易于使用。
    3. 当用于分割目的时,超像素应当增加速度并提高结果的质量。

    下表提供了超像素方法进行了研究方法的定性和定量总结,速度,连接图,相对性能。
    在这里插入图片描述

    二、现有的超像素算法

    2.1 基于图的算法

    基于图形的超像素生成方法将每个像素视为图中的节点。两个节点之间的边权重与相邻像素之间的相似性成比例。超像素通过最小化图中定义的成本函数来创建。

    NC05-归一化切割算法[23]递归地使用轮廓和纹理线索分割图像中的所有像素的图形,从而全局性地最小化在分割边界处的边缘定义的成本函数。它产生非常规则,视觉上令人愉快的超像素。然而,NC05的边界粘附相对较差,并且它是方法中最慢的(特别是对于大图像),尽管试图加速的算法存在[5]。NC05具有[15]的复杂度 O(N32)O(N^{\frac{3}{2}}),其中N是像素的数量。

    GS04-Felzenszwalb和Huttenlocher[8]提出了一种替代的基于图形的方法,已被应用于生成超像素。它将像素作为图的节点,使得每个超像素是组成像素的最小生成树。GS04在实践中很好地粘附到图像边界,但是产生具有非常不规则的尺寸和形状的超像素。它的复杂度是 O(NlogN)O(N\log N),在实践中速度很快。然而,它不提供对超像素的量或其紧凑性的明确控制。

    SL08-Mooreetal提出了一种通过确定将图像分割成更小的垂直或水平区域的最佳路径或接缝来生成符合网格的超像素的方法[21]。使用类似于SeamCarving[1]的图切割方法找到最佳路径。尽管作者给出的复杂的是O(N32logN)O(N^{\frac{3}{2}}\log N),但这并不考虑预先计算的边界图,这强烈影响输出的质量和速度。

    GCa10和GCb10-[26],Veksleretal。使用类似于[14]的纹理合成工作的全局优化方法。通过将重叠的图像块拼接在一起来获得超像素,使得每个像素仅属于重叠区域中的一个。这个方法有两个变种,一个用于生成紧凑超像素(GCa10),一个用于恒定强度超像素(GCb10)。

    2.2 基于梯度上升的方法

    从粗略的像素初始聚类开始,梯度上升法迭代地修改聚类,直到满足一些收敛标准以形成超像素。

    MS02-In[4]中,平均偏移,用于定位密度函数的局部最大值的迭代模式寻找过程被应用于图像的颜色或强度特征空间中的第一模式。会聚到相同模式的像素定义超像素。MS02是一种较旧的方法,产生不均匀尺寸的不规则形状的超像素。它是复杂度O(N2)O(N^2),使其相对较慢,并且不提供对超像素的量,尺寸或紧密度的直接控制。

    QS08-快速移位[25]也使用模式查找分割方案。它使用medoid移位过程初始化分割。然后将特征空间中的搜索点移动到最近的邻居,从而增加Parzen密度估计。虽然它具有相对良好的边界粘附,但是QS08的运行速度相当缓慢,具有复杂度O(dN2)O(dN^2)(d是一个小常数[25])。而且QS08不允许对超像素的大小或数量的显式控制。以前的作品使用QS08对象定位[9]和运动分割[2]。

    WS91-分水岭方法[28]从局部最小值开始执行梯度上升以产生分水岭,和分离集水盆地的线条。所得到的超像素在尺寸和形状上通常是高度不规则的,并且不表现出良好的边界粘附。[28]的方法相对较快(具有 O(NlogN)O(N\log N) 的复杂度),但不提供对超像素量或其紧凑性的控制。

    TP09-Turbopixel方法使用基于水平集的几何流动逐渐扩大一组种子位置[15]。几何流依赖于局部图像梯度,目的是在图像平面上规则地分布超像素。与WS91不同,TP09超像素被约束为具有均匀的尺寸,紧凑性和边界粘附。TP09依赖于不同复杂度的算法,但在实践中,如作者所声称的,具有大约 O(N)O(N) 的复杂度[15],是所检查的最慢的算法之一,并且表现出相对较差的边界粘附。

    三、SLIC超像素

    我们提出一种新的生成超像素的方法,比现有方法更快,更高的记忆效率,展示了目前最优的边界依从性,并提高了分割算法的性能。简单线性迭代聚类(SLIC)采用K均值算法生成超像素,相较与其他算法具有两个重要的区别:
    1)通过将搜索空间限制为与超像素大小成比例的区域,显着地减少了优化中的距离计算的数量。这降低了像素数N的线性复杂度,并且与超像素k的数量无关。
    2)加权距离度量组合颜色和空间接近度,同时提供对超像素的尺寸和紧凑性的控制。
    SLIC类似于[30]中描述的用于深度估计的预处理步骤的方法,其没有在超像素方向进行研究。

    3.1 算法详解

    SLIC使用简单易懂。默认情况下,算法的唯一参数是k,其含义是大小大致相等的超像素的个数。对于CIELAB色彩空间中的彩色图像,聚类过程从初始化步骤开始,其中k个初始聚类中心 Ci=[li,ai,bi,xi,yi,]TC_i = [l_i,a_i,b_i,x_i,y_i,]^T 在间隔S个像素的规则网格上采样。为了产生大致相等大小的超像素,网格间隔为 S=NkS =\sqrt{\frac{N}{k}}。将中心移动到与3×3邻域中的最低梯度位置相对应的种子位置。这样做是为了避免将超像素定位在边缘上,并且减少用噪声像素接种超像素的机会。
    接下来,在分配步骤中,每个像素i与搜索区域与其位置重叠的最近聚类中心相关联,如图2所示。这是加速我们的算法的关键,因为限制搜索区域的大小显着地减少了距离计算的数量,并且导致相对于常规kmeans聚类的显着的速度优势,其中每个像素必须与所有聚类中心比较。这只能通过引入距离测量D来实现,该距离测量D确定每个像素的最近聚类中心,如第III-B节中所讨论的。由于超像素的预期空间范围是近似尺寸S×S的区域,因此在超像素中心周围的区域2S×2S中进行类似像素的搜索。
    在这里插入图片描述
    图.2:减少超像素搜索区域。SLIC的复杂性在图像O(N)中的像素数目中是线性的,而常规的k均值算法是O(kNI),其中I是迭代次数。这在分配步骤中提供了每个聚类中心的搜索空间。
    (a)在常规k均值算法中,从每个聚类中心到图像中的每个像素计算距离。
    (b)SLIC仅计算从每个聚类中心到2S×2S区域内的像素的距离。注意,期望的超像素大小仅为S×S,由较小的正方形表示。这种方法不仅减少了距离计算,而且使得SLIC的复杂性与超像素的数量无关。

    一旦每个像素已经与最近的聚类中心相关联,更新步骤将聚类中心调整为属于该聚类的所有像素的平均向量 [l,a,b,x,y]T[l,a,b,x,y]^T。L2范数用于计算新聚类中心位置和先前聚类中心位置之间的残差误差E.分配和更新步骤可以迭代重复,直到错误收敛,但我们发现10次迭代足够大多数图像,并报告本文中使用此标准的所有结果。最后,后处理步骤通过将不相交像素重新分配给附近的超像素来实施连通性。算法1中总结了整个算法。
    在这里插入图片描述

    3.2 距离测量

    SLIC超像素对应于labxy颜色空间中的簇,这里提出了定义距离D的问题。D在算法1中的计算像素i和聚类中心CkC_k之间的距离,像素颜色在CIELAB颜色空间 [l a b]T中表示,其取值范围是已知的,另一方面,像素的位置 [x,y]T的取值范围随着图像的尺寸变化而变化。

    简单定义D为labxy空间中的五维欧式距离将导致不同超像素大小的聚类行为的不一致性。对于大的超像素,空间距离超过颜色接近度,给出比空间接近度比颜色更多的相对重要性。这产生不良好的粘附到图像边界的紧凑超像素。对于较小的超像素,则相反。

    为了将两个距离组合成单个测量,有必要通过它们在簇内的各自的最大距离 NsN_sNcN_c 来标准化颜色接近度和空间接近度。D为:
    dc=(ljli)2+(ajai)2+(bjbi)2ds=(xjxi)2+(yjyi)2D=(dcNc)2+(dsNs)2(1) \begin{aligned} d_c&=\sqrt{(l_j-l_i)^2 +(a_j-a_i)^2 +(b_j-b_i)^2 } \\ d_s&=\sqrt{(x_j-x_i)^2 +(y_j-y_i)^2 } \\ D'&=\sqrt{\left ( \frac{d_c}{N_c} \right )^2 + \left ( \frac{d_s}{N_s} \right )^2 } \end{aligned} \tag1

    给定群集内预期的最大空间距离对应于采样间隔,Ns=S=NKN_s = S =\sqrt{\frac{N}{K}}。确定最大的颜色距离 NcN_c 不是那么简单。因为颜色距离可以从簇到簇和图像到图像显著不同。这个问题可以通过将NcN_c固定为常数 m来避免,1变为:
    D=(dcm)2+(dsS)2(2)D' = \sqrt{\left ( \frac{d_c}{m} \right )^2 + \left ( \frac{d_s}{S} \right )^2} \tag2
    这简化了我们在实践中使用的距离测量
    D=dc2+(dsS)2m2(3)D = \sqrt{d_c^2 + \left ( \frac{d_s}{S} \right )^2m^2} \tag3
    通过以这种方式定义D,m还允许我们权衡颜色相似性和空间邻近度之间的想读重要性。当m大时,空间邻近性更重要,并且所得到的超像素更紧凑(即它们具有更低的面积周长比),当m小时,所得到的超像素更紧密的粘附到图像边界,但是具有较小的规则尺寸和形状。当使用CIELAB色彩空间时,m可以在 [1,40] 的范围内。

    式(3)设置dc=(ljli)d_c = \sqrt{(l_j-l_i)} 适用于灰度图像,它可以扩展到处理3D 超像素,深度维度到空间邻近项方程:
    ds=(xixj)2+(yiyj)+(zixzj)2d_s=\sqrt{(x_i-x_j)^2 +(y_i-y_j) +(z_i-xz_j)^2 }

    在这里插入图片描述
    图3:为视频序列计算的SLIC超体元。(顶部)短波的短视频序列所产生的帧。(左下)包含视频的卷。最后一帧出现在卷的顶部。(右下)视频的超像素分割。为便于显示,具有橙色聚类中心的超体素被去除。

    3.3 后处理

    像一些其他超像素算法[8],SLIC没有明确强制连接。在聚类过程结束时,可能保留不属于与其聚类中心相同的连接分量的一些“孤立”像素。为了对此进行校正,使用连通分量算法向这些像素分配最近聚类中心的标签。

    3.4 时间复杂度

    通过在聚类过程中的定位搜索,SLIC避免执行行数千个冗余距离计算。在实践中,像素落在小于8个聚类中心附近,这意味着SLIC是 O(N) 复杂度。相比之下,经典K均值算法的频繁上限是O(kN) ,时间复杂度O(kNI),其中I是收敛的迭代次数。虽然使用了像素长度随机抽样,局部簇交换以及通过设置上限和下限来降低K均值复杂度的方案。SLIC是专门针对超像素聚类的问题,它的时间复杂度在像素数量上是线性的,与K无关。

    生物医学应用
    许多流行的基于图形的分割方法,例如图切割[3]变得越来越昂贵,因为更多的节点被添加到图中,这在实践中会对图像大小产生限制。 对于一些应用,例如从电子显微照片(EM)的线粒体分割,这种情况下图像的尺寸是很大的,但是此时不能降低分辨率。 在这种情况下,在像素网格上定义的图形上的分割将是棘手的。 在[18],SLIC超像素显着降低图的复杂性,使分割易处理。 来自[18]的分段线粒体显示在 图3(a)和(b)。在[19],这种方法扩展到3D图像堆栈,其中可以包含数十亿的体素。 只有最节俭的算法可以在这样大量的数据上操作,而不需要以某种方式减小图的大小。 SLIC超体元将存储器要求和复杂性降低超过三个数量级,并且与常规立方体相比显着增加性能,如 图3(c) - (e)所示。
    在这里插入图片描述
    SLIC应用于来自神经组织的2D和3D EM图像的线粒体。
    (a)来自EM切片的SLIC超像素。
    (b)来自[18]的方法的分割结果。
    (c)1024×1024×600体积的SLIC超体元。
    (d)使用[19]中描述的方法提取的线粒体。
    (e)比较SLIC超体元与相似尺寸的立方体在(c)中体积的分割性能。

    四、Python-OpenCV示例

    retval = cv.ximgproc.createSuperpixelSLIC( image[, algorithm[, region_size[, ruler]]] )

    其中各个参数意义如下:
        image :输入图像
        algorithm:选择要使用的算法变体:SLIC、SLICO(默认)和MSLIC三种可选
        region_size:平均超像素大小,默认10
        ruler:超像素平滑度,默认10

    import cv2
    
    img = cv2.imread("./cat.png")
    
    #初始化slic项,超像素平均尺寸20(默认为10),平滑因子20
    slic = cv2.ximgproc.createSuperpixelSLIC(img,region_size=20,ruler = 20.0)
    slic.iterate(10)                                    #迭代次数,越大效果越好
    mask_slic = slic.getLabelContourMask()              #获取Mask,超像素边缘Mask==1
    label_slic = slic.getLabels()                       #获取超像素标签
    number_slic = slic.getNumberOfSuperpixels()         #获取超像素数目
    mask_inv_slic = cv2.bitwise_not(mask_slic)
    img_slic = cv2.bitwise_and(img,img,mask =  mask_inv_slic)  #在原图上绘制超像素边界
    cv2.imshow("img_slic",img_slic)
    cv2.waitKey(0)
    cv2.destroyAllWindows()
    

    在这里插入图片描述
    python-opencv:https://blog.csdn.net/qq_40268412/article/details/103915197
    C++源码:https://blog.csdn.net/zhj_matlab/article/details/52986700
    C++源码:https://github.com/csjy309450/SLIC-Superpixels

    展开全文
  • SLIC与目前最优超像素算法的比较

    万次阅读 2017-08-14 22:32:29
    SLIC与目前最优超像素算法的比较 Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine S¨usstrunk 摘要 近年来,计算机视觉应用越来越依赖超像素,但并不总是清楚什么是...

    SLIC与目前最优超像素算法的比较

    Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine S¨usstrunk

    摘要

    近年来,计算机视觉应用越来越依赖超像素,但并不总是清楚什么是良好的超像素算法。为了解现有方法的优点和缺点,我们比较了目前最好的五种超像素算法,比较的指标为图像边界的粘附性,算法速度,存储效率,以及它们对分割性能的影响。然后我们介绍一种新的超像素算法,简单的线性迭代聚类(SLIC),它采用k均值聚类方法高效地生成超像素。尽管它很简单,但SLIC较以前的算法可以更好地获取边界,同时,它具有更快的速度,更高的内存效率,并且能提高分割性能,也可以直接扩展到超体元生成。 
    关键词-超像素,分割,聚类,k均值。 
    这里写图片描述 
    图.1:使用SLIC分割成尺寸(大约)为64,256和1024的超像素。

    I.引言

    超像素算法将像素组合成感知有意义的原子区域( atomic regions),其可以用于替换像素网格的刚性结构。它们捕获图像冗余,提供计算图像特征的方便原语( primitive ),并且大大降低了后续图像处理任务的复杂性。它们已经成为许多计算机视觉算法的关键构建块,如PASCAL VOC挑战中的多类对象分割[9],[29],[11],深度估计[30],分割[16],身体模型估计[22]和对象定位[9]。 
    目前存在许多产生超像素的方法,每种具有其自身的优点和缺点,可更好地适合于特定应用。例如,如果遵守图像边界是至关重要的,[8]的基于图的方法可能是一个理想的选择。然而,如果超像素用于构建具有更规则的晶格的图形(lattice),[23]可能是更好的选择。虽然很难定义指标来判断算法的优劣性,但我们相信以下属性通常是可取的: 
    1)超像素应当良好地粘附到图像边界。 
    2)当作为预处理步骤用于降低的计算复杂度时,超像素应当快速计算,存储 器效率高且易于使用。 
    3)当用于分割目的时,超像素应当增加速度并提高结果的质量。 
    因此,我们对五个最先进的超像素方法进行了比较[8],[23],[26],[25],[15],评估他们的速度,连接图像边界的能力还有分割性能。我们还提供这些和其他超像素方法的定性分析。我们的结论是,现有的方法不能在所有方面都令人满意。 
    为了解决这个问题,我们提出了一种新的超像素算法:简单线性迭代聚类(SLIC),它采用kmeans聚类以类似于[30]的方式生成超像素。虽然非常简单,但是SLIC在Berkeley基准[20]上产生显示出对图像边界的最好效果,并且在PASCAL[7]和MSRC[24]数据集上进行分割时优于现有方法。此外,它比现有方法更快,更高的存储效率。除了这些可量化的好处,SLIC还易于使用,更为的紧凑,其生成的超像素数量也更灵活,还可直接扩展到更高的维度,并且是免费使用的(意思是代码是开源的)。

    II.现有的超像素生成算法

    用于生成超像素的算法可以大致分类为基于图或梯度上升的方法。下面,我们回顾每个类别常见的超像素方法,包括一些最初设计不是为了生成超像素的算法。表I提供了所研究方法的定性和定量总结,包括其相对性能。 
    这里写图片描述
    表I:现有超像素算法的总结。 超像素法粘附到边界的性能可以在伯克利数据集[20]中进行评估,其可以根据两个标准度量进行排名:欠分割误差和边界回忆(对于〜500超像素)。 我们还展示了使用具有2GB RAM的Intel双核2.26 GHz处理器分段图像所需的平均时间,以及使用[11]中描述的方法在MSRC数据集上获得的类平均分割精度。 粗体条目表示每个类别的最佳性能。 还提供了指定超像素的量,控制其紧凑性以及生成超体素的能力。

    A.基于图的算法

    基于图形的超像素生成方法将每个像素视为图中的节点。两个节点之间的边权重与相邻像素之间的相似性成比例。超像素通过最小化图中定义的成本函数来创建。 
    NC05-归一化切割算法[23]递归地使用轮廓和纹理线索分割图像中的所有像素的图形,从而全局性地最小化在分割边界处的边缘定义的成本函数。它产生非常规则,视觉上令人愉快的超像素。然而,NC05的边界粘附相对较差,并且它是方法中最慢的(特别是对于大图像),尽管试图加速的算法存在[5]。NC05具有[15]的复杂度这里写图片描述,其中N是像素的数量。 
    GS04-Felzenszwalb和Huttenlocher[8]提出了一种替代的基于图形的方法,已被应用于生成超像素。它将像素作为图的节点,使得每个超像素是组成像素的最小生成树。GS04在实践中很好地粘附到图像边界,但是产生具有非常不规则的尺寸和形状的超像素。它的复杂度是这里写图片描述,在实践中速度很快。然而,它不提供对超像素的量或其紧凑性的明确控制。 
    SL08-Mooreetal提出了一种通过确定将图像分割成更小的垂直或水平区域的最佳路径或接缝来生成符合网格的超像素的方法[21]。使用类似于SeamCarving[1]的图切割方法找到最佳路径。尽管作者给出的复杂的是这里写图片描述,但这并不考虑预先计算的边界图,这强烈影响输出的质量和速度。 
    GCa10和GCb10-[26],Veksleretal。使用类似于[14]的纹理合成工作的全局优化方法。通过将重叠的图像块拼接在一起来获得超像素,使得每个像素仅属于重叠区域中的一个。这个方法有两个变种,一个用于生成紧凑超像素(GCa10),一个用于恒定强度超像素(GCb10)。

    B.基于梯度上升的方法

    从粗略的像素初始聚类开始,梯度上升法迭代地修改聚类,直到满足一些收敛标准以形成超像素。 
    MS02-In[4]中,平均偏移,用于定位密度函数的局部最大值的迭代模式寻找过程被应用于图像的颜色或强度特征空间中的第一模式。会聚到相同模式的像素定义超像素。MS02是一种较旧的方法,产生不均匀尺寸的不规则形状的超像素。它是复杂度这里写图片描述,使其相对较慢,并且不提供对超像素的量,尺寸或紧密度的直接控制。 
    QS08-快速移位[25]也使用模式查找分割方案。它使用medoid移位过程初始化分割。然后将特征空间中的搜索点移动到最近的邻居,从而增加Parzen密度估计。虽然它具有相对良好的边界粘附,但是QS08的运行速度相当缓慢,具有复杂度这里写图片描述(d是一个小常数[25])。而且QS08不允许对超像素的大小或数量的显式控制。以前的作品使用QS08对象定位[9]和运动分割[2]。 
    WS91-分水岭方法[28]从局部最小值开始执行梯度上升以产生分水岭,和分离集水盆地的线条。所得到的超像素在尺寸和形状上通常是高度不规则的,并且不表现出良好的边界粘附。[28]的方法相对较快(具有这里写图片描述的复杂度),但不提供对超像素量或其紧凑性的控制。 
    TP09-Turbopixel方法使用基于水平集的几何流动逐渐扩大一组种子位置[15]。几何流依赖于局部图像梯度,目的是在图像平面上规则地分布超像素。与WS91不同,TP09超像素被约束为具有均匀的尺寸,紧凑性和边界粘附。TP09依赖于不同复杂度的算法,但在实践中,如作者所声称的,具有大约这里写图片描述的复杂度[15],是所检查的最慢的算法之一,并且表现出相对较差的边界粘附。

    III.SLIC超像素

    我们提出一种新的生成超像素的方法,比现有方法更快,更高的记忆效率,展示了目前最优的边界依从性,并提高了分割算法的性能。简单线性迭代聚类(SLIC)采用K均值算法生成超像素,相较与其他算法具有两个重要的区别: 
    1)通过将搜索空间限制为与超像素大小成比例的区域,显着地减少了优化中的距离计算的数量。这降低了像素数N的线性复杂度,并且与超像素k的数量无关。 
    2)加权距离度量组合颜色和空间接近度,同时提供对超像素的尺寸和紧凑性的控制。 
    SLIC类似于[30]中描述的用于深度估计的预处理步骤的方法,其没有在超像素方向进行研究。

    A.算法

    SLIC使用简单易懂。默认情况下,算法的唯一参数是k,其含义是大小大致相等的超像素的个数。对于CIELAB色彩空间中的彩色图像,聚类过程从初始化步骤开始,其中k个初始聚类中心这里写图片描述在间隔S个像素的规则网格上采样。为了产生大致相等大小的超像素,网格间隔为这里写图片描述。将中心移动到与3×3邻域中的最低梯度位置相对应的种子位置。这样做是为了避免将超像素定位在边缘上,并且减少用噪声像素接种超像素的机会。 
    接下来,在分配步骤中,每个像素i与搜索区域与其位置重叠的最近聚类中心相关联,如图2所示。这是加速我们的算法的关键,因为限制搜索区域的大小显着地减少了距离计算的数量,并且导致相对于常规kmeans聚类的显着的速度优势,其中每个像素必须与所有聚类中心比较。这只能通过引入距离测量D来实现,该距离测量D确定每个像素的最近聚类中心,如第III-B节中所讨论的。由于超像素的预期空间范围是近似尺寸S×S的区域,因此在超像素中心周围的区域2S×2S中进行类似像素的搜索。 
    这里写图片描述 
    图.2:减少超像素搜索区域。SLIC的复杂性在图像O(N)中的像素数目中是线性的,而常规的k均值算法是O(kNI),其中I是迭代次数。这在分配步骤中提供了每个聚类中心的搜索空间。(a)在常规k均值算法中,从每个聚类中心到图像中的每个像素计算距离。(b)SLIC仅计算从每个聚类中心到2S×2S区域内的像素的距离。注意,期望的超像素大小仅为S×S,由较小的正方形表示。这种方法不仅减少了距离计算,而且使得SLIC的复杂性与超像素的数量无关。 
    一旦每个像素已经与最近的聚类中心相关联,更新步骤将聚类中心调整为属于该聚类的所有像素的平均向量这里写图片描述。L2范数用于计算新聚类中心位置和先前聚类中心位置之间的残差误差E.分配和更新步骤可以迭代重复,直到错误收敛,但我们发现10次迭代足够大多数图像,并报告本文中使用此标准的所有结果。最后,后处理步骤通过将不相交像素重新分配给附近的超像素来实施连通性。算法1中总结了整个算法。 
    这里写图片描述 
    这里写图片描述 
    这里写图片描述

    B.距离测量

    这里写图片描述
    这里写图片描述
    这里写图片描述
    这里写图片描述 
    图3:为视频序列计算的SLIC超体元。(顶部)短波的短视频序列所产生的帧。(左下)包含视频的卷。最后一帧出现在卷的顶部。(右下)视频的超像素分割。为便于显示,具有橙色聚类中心的超体素被去除

    C.后处理

    像一些其他超像素算法[8],SLIC没有明确强制连接。在聚类过程结束时,可能保留不属于与其聚类中心相同的连接分量的一些“孤立”像素。为了对此进行校正,使用连通分量算法向这些像素分配最近聚类中心的标签。

    D.复杂度

    这里写图片描述

    IV.与现有技术的比较

    V.生物医学应用

    许多流行的基于图形的分割方法,例如图切割[3]变得越来越昂贵,因为更多的节点被添加到图中,这在实践中会对图像大小产生限制。 对于一些应用,例如从电子显微照片(EM)的线粒体分割,这种情况下图像的尺寸是很大的,但是此时不能降低分辨率。 在这种情况下,在像素网格上定义的图形上的分割将是棘手的。 在[18],SLIC超像素显着降低图的复杂性,使分割易处理。 来自[18]的分段线粒体显示在 图3(a)和(b)。在[19],这种方法扩展到3D图像堆栈,其中可以包含数十亿的体素。 只有最节俭的算法可以在这样大量的数据上操作,而不需要以某种方式减小图的大小。 SLIC超体元将存储器要求和复杂性降低超过三个数量级,并且与常规立方体相比显着增加性能,如 图3(c) - (e)所示。 
    这里写图片描述 
    图3:SLIC应用于来自神经组织的2D和3D EM图像的线粒体。 (a)来自EM切片的SLIC超像素。 (b)来自[18]的方法的分割结果。 (c)1024×1024×600体积的SLIC超体元。 (d)使用[19]中描述的方法提取的线粒体。 (e)比较SLIC超体元与相似尺寸的立方体在(c)中体积的分割性能。

    VI.结论

    超像素已经成为视觉社区的重要工具,在本文中,我们为读者提供了对现代超像素技术性能的深入分析。我们以边界粘附性,分割速度和作为分割框架中预处理步骤时的性能为指标,比较了目前最好的五个超像素算法。此外,我们提出了一种基于kmeans聚类生成超像素的新方法,SLIC已被证明在几乎每个方面都优于现有的超像素方法。 
    虽然我们的实验是彻底的,但是有一个警告。某些超像素方法,即GC10和TP09,不考虑颜色信息,而其他方法考虑。这可能会对其性能产生不利影响。

    参考文献

    [1] Shai Avidan and Ariel Shamir. Seam carving for content-aware image resizing. ACM Transactions on Graphics (SIGGRAPH), 26(3), 2007. 
    [2] A. Ayvaci and S. Soatto. Motion segmentation with occlusions on the superpixel graph. In Workshop on Dynamical Vision, Kyoto, Japan, October 2009. 
    [3] Y. Boykov and M. Jolly. Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images. In International Conference on Computer Vision (ICCV), 2001. 
    [4] D. Comaniciu and P. Meer. Mean shift: a robust approach toward feature space analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(5):603–619, May 2002. 
    [5] T. Cour, F. Benezit, and J. Shi. Spectral segmentation with multiscale graph decomposition. In IEEE Computer Vision and Pattern Recognition (CVPR) 2005, 2005. 
    [6] Charles Elkan. Using the triangle inequality to accelerate k-means. International Conference on Machine Learning, 2003. 
    [7] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman. The PASCAL Visual Object Classes Challenge. International Journal of Computer Vision (IJCV), 88(2):303–338, June 2010. 
    [8] Pedro Felzenszwalb and Daniel Huttenlocher. Efficient graph-based image segmentation. International Journal of Computer Vision (IJCV), 59(2):167–181, September 2004. 
    [9] B. Fulkerson, A. Vedaldi, and S. Soatto. Class segmentation and object localization with superpixel neighborhoods. In International Conference on Computer Vision (ICCV), 2009. 
    [10] J.M. Gonfaus, X. Boix, J. Weijer, A. Bagdanov, J. Serrat, and J. Gonzalez. Harmony Potentials for Joint Classification and Segmentation. In Computer Vision and Pattern Recognition (CVPR), 2010. 
    [11] Stephen Gould, Jim Rodgers, David Cohen, Gal Elidan, and Daphne Koller. Multi-class segmentation with relative location prior. International Journal of Computer Vision (IJCV), 80(3):300–316, 2008. 
    [12] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Eighteenth annual symposium on Computational geometry, pages 10–18, 2002. 
    [13] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. A simple linear time (1+e)-approximation algorithm for k-means clustering in any dimensions. Annual IEEE Symposium on Foundations of Computer Science, 0:454–462, 2004. 
    [14] Vivek Kwatra, Arno Schodl, Irfan Essa, Greg Turk, and Aaron Bobick. Graphcut textures: Image and video synthesis using graph cuts. ACM Transactions on Graphics, SIGGRAPH 2003, 22(3):277–286, July 2003. 
    [15] A. Levinshtein, A. Stere, K. Kutulakos, D. Fleet, S. Dickinson, and K. Siddiqi. Turbopixels: Fast superpixels using geometric flows. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 2009. 
    [16] Yin Li, Jian Sun, Chi-Keung Tang, and Heung-Yeung Shum. Lazy snapping. ACM Transactions on Graphics (SIGGRAPH), 23(3):303– 308, 2004 
    [17] Stuart P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, IT-28(2):129–137, 1982. 
    [18] A. Lucchi, K. Smith, R. Achanta, V. Lepetit, and P. Fua. A fully automated approach to segmentation of irregularly shaped cellular structures in em images. International Conference on Medical Image Computing and Computer Assisted Intervention, 2010. 
    [19] Aur´elien Lucchi, Kevin Smith, Radhakrishna Achanta, Graham Knott, and Pascal Fua. Supervoxel-Based Segmentation of Mitochondria in EM Image Stacks with Learned Shape Features. IEEE Transactions on Medical Imaging, 30(11), 2011. 
    [20] D. Martin, C. Fowlkes, D. Tal, and J. Malik. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In IEEE International Conference on Computer Vision (ICCV), July 2001. 
    [21] Alastair Moore, Simon Prince, Jonathan Warrell, Umar Mohammed, and Graham Jones. Superpixel Lattices. IEEE Computer Vision and Pattern Recognition (CVPR), 2008. 
    [22] Greg Mori. Guiding model search using segmentation. In IEEE International Conference on Computer Vision (ICCV), 2005. 
    [23] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 22(8):888–905, Aug 2000. 
    [24] J. Shotton, J. Winn, C. Rother, and A. Criminisi. TextonBoost for Image Understanding: Multi-Class Object Recognition and Segmentation by Jointly Modeling Texture, Layout, and Context. International Journal of Computer Vision (IJCV), 81(1), January 2009. 
    [25] A. Vedaldi and S. Soatto. Quick shift and kernel methods for mode seeking. In European Conference on Computer Vision (ECCV), 2008. 
    [26] O. Veksler, Y. Boykov, and P. Mehrani. Superpixels and supervoxels in an energy optimization framework. In European Conference on Computer Vision (ECCV), 2010. 
    [27] O. Verevka and J.W. Buchanan. Local k-means algorithm for color image quantization. Graphics Interface, pages 128–135, 1995. 
    [28] Luc Vincent and Pierre Soille. Watersheds in digital spaces: An efficient algorithm based on immersion simulations. IEEE Transactions on Pattern Analalysis and Machine Intelligence, 13(6):583–598, 1991. 
    [29] Y. Yang, S. Hallman, D. Ramanan, and C. Fawlkes. Layered Object DetectionforMulti-ClassSegmentation. InComputer Visionand Pattern Recognition (CVPR), 2010. 
    [30] C. L. Zitnick and S. B. Kang. Stereo for image-based rendering using image over-segmentation. International Journal of Computer Vision (IJCV), 75:49–65, October 2007.

    文章下载:https://infoscience.epfl.ch/record/177415/files/Superpixel_PAMI2011-2.pdf 
    源码地址:http://ivrl.epfl.ch/research/superpixels

    原帖 :http://blog.csdn.net/zhj_matlab/article/details/52986700


    展开全文
  • 像素算法

    万次阅读 2018-09-13 17:57:11
    在这篇博客里,主要讲解两点:点定位(Point localization)以及边缘定位(Edge localization),均是亚像素级定位精度。当然还有其他定位方法,这里仅针对亮点和边缘两种情形分别进行精确定位。   1. 为何需要进行亚...

    在这篇博客里,主要讲解两点:点定位(Point localization)以及边缘定位(Edge localization),均是亚像素级定位精度。当然还有其他定位方法,这里仅针对亮点和边缘两种情形分别进行精确定位。

     

    1. 为何需要进行亚像素定位?

    >数字图像通常是被离散化成像素形式;

    >每个像素对应一个整数坐标位置;

    >整数坐标位置对于很多应用然而并不精确,比如跟踪、相机标定、图像配准、图像拼接以及三维重构;

    >为达到有些应用的精确性,需要精确到浮点坐标位置;

    所以会涉及到亚像素定位问题。亚像素定位就是计算特征所在图像中的真实位置,而真实位置有时候并不在像素所在整数坐标位置上,而是在像素的内部。

     

    2. 基本思想

    >设计一个特征模型以便进行定位,通常使用数学模型来描述图像的特征,数学模型也不一定就完全能表达图像的特征,至少能接近,否则设计的模型欠妥;

    >使用常用算法进行定位,初定位精度一般达到整数坐标位置即可,通常初定位的精度要保证至少在精确位置附近,否则偏离较远,算法计算可能也会实效;

    >反复迭代使用匹配模型进行精确定位,检测图像特征位置,使特征位置精度达到亚像素级别,迭代的目的通常是优化模型参数;

    注意,大多数亚像素定位算法需要对特征所在的位置有一个良好的估计,否则会将图像上的噪声位置误认为期望的特征位置。

     

    3. 点定位

    首先,点在图像里是如何呈现的?如下图所示:

    >一个“点”通常会占用多个像素;

    >一个“点”通常也不具有强边缘性质,其边缘通常是光滑的、模糊的;

     

    那么我们当然不能以一个像素区域作为“点”的位置,应该以一个坐标点来标记这个“点”的位置,通常计算点区域的中心位置 或者 点区域的最亮位置所对应的坐标, 那么如何去计算该点的位置呢?

     

    结合上图所示,点的灰度分布特征是不是跟二维高斯模型很相似?中心处最亮,离中心距离越远会随之变暗。所以这里的图像特征,我们用高斯模型进行描述。

    利用高斯模型,我们可以构建点的最终模型函数M,如下:

    说明下,这个模型比单独的高斯模型更适合表达图像特征,如果仅仅用高斯模型,那么离中心越远,图像亮度越小,但图像的亮度的最小程度也就是四周的暗区域,这些暗区域的灰度强度值并不为0,而是A。

    上述表达式中的各个参数解释如下:

    >M:代表对应像素位置上的强烈程度

    >(x,y):图像中某个像素位置

    >A:背景的强烈程度,比如上面的黑色区域

    >B:亮区域中的强烈程度的峰值

    >(u,v):亮区域中的峰值所在的位置

    >sigma:高斯模型方差

    上面左边表达式可以简化为:,其中表示图像的像素位置;是点的模型参数,当模型参数已知,那么图像特征已被定位,也就是高斯模型的中心位置(u,v),该坐标位置是浮点型的,也即是亚像素别级的。

    针对图像中存在"点"情形,如果模型,即对应像素位置的强度与模型函数M估计出来的强度相同,那么我们认为用该模型匹配点区域的像素值是完美的,该模型是适合描述该区域的特征。事实上,在点区域里,保证不了左右两等式相等,我们只求左右两等式尽量逼近,那么如何获取一个良好的匹配模型呢,也即如何求解出模型的最佳参数呢?基本都是通过残差进行分析,如:

    ,其中W相当于一个窗口或者是一个模板,所以W窗口移动到点附近哪个位置是最合适的?在进行残差计算前,首先使用一个简单算法粗定位一个位置,将窗口中心移动至该位置上,再进行残差计算。我们的目的是最小化误差,即可获取亚像素位置坐标(u,v)。 亚像素定位方法可以直接对误差函数的每一个参数进行偏导求取,也可以使用梯度下降法进行求解,最终得到模型的相关参数(这里极有可能得到的解是局部最优解)。当然求解的方法很多,最好使用的方法能解出全局最优解,这样解的模型才是最优的。

     

    4. 边缘定位

    边缘定位算法跟点定位算法相似。 下面是一幅带有边缘的图像:

     

    这里着重讲解下边缘模型的推导:

     

    其中,是原始图像坐标系;是定义的边缘的局部坐标系。

    对于单位跃阶边缘,我们可以定义如下:

    因此,对于一个理想的二维跃阶边缘,以为坐标系,那么沿着轴方向有:

    这里我们可以假设一个模型来对实际边缘进行模拟,实际边缘其实是模糊的,没有跃阶现象,那么我们可以认为实际边缘是由一个二维的跃阶边缘与一个一维的高斯函数进行卷积形成的:

    其中在图像坐标系中的位置为(u,v).

    所以,需要定位的亚像素位置应该是理想中的二维跃阶边缘位置,在真实边缘图像中,该位置应该是从暗到亮转变过程中,导数发生最大变化所对应的位置。

    此时我们结合上面坐标系图示,可以得到边缘点在局部坐标系和图像坐标系位置转换关系

    我们最终建立的边缘模型可以表示为:

    其中是模型参数向量。

    求解参数,仍是使用误差函数分析,使误差函数最小化,此处的W是一窗口或者模板

    可以使用梯度下降法优化残差函数,求取,最终获得(u,v),也即是定位得到的边缘亚像素位置,边缘方向是垂直于theta角的。

     

    当然,亚像素定位算法很多,视图像的具体特征而定,欢迎讨论留言。

    展开全文
  • SLIC与目前最优超像素算法的比较 Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine S¨usstrunk 摘要 近年来,计算机视觉应用越来越依赖超像素,但并不总是清楚什么是...

    SLIC与目前最优超像素算法的比较

    Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine S¨usstrunk

    摘要

    近年来,计算机视觉应用越来越依赖超像素,但并不总是清楚什么是良好的超像素算法。为了解现有方法的优点和缺点,我们比较了目前最好的五种超像素算法,比较的指标为图像边界的粘附性,算法速度,存储效率,以及它们对分割性能的影响。然后我们介绍一种新的超像素算法,简单的线性迭代聚类(SLIC),它采用k均值聚类方法高效地生成超像素。尽管它很简单,但SLIC较以前的算法可以更好地获取边界,同时,它具有更快的速度,更高的内存效率,并且能提高分割性能,也可以直接扩展到超体元生成。 
    关键词-超像素,分割,聚类,k均值。 
    这里写图片描述 
    图.1:使用SLIC分割成尺寸(大约)为64,256和1024的超像素。

    I.引言

    超像素算法将像素组合成感知有意义的原子区域( atomic regions),其可以用于替换像素网格的刚性结构。它们捕获图像冗余,提供计算图像特征的方便原语( primitive ),并且大大降低了后续图像处理任务的复杂性。它们已经成为许多计算机视觉算法的关键构建块,如PASCAL VOC挑战中的多类对象分割[9],[29],[11],深度估计[30],分割[16],身体模型估计[22]和对象定位[9]。 
    目前存在许多产生超像素的方法,每种具有其自身的优点和缺点,可更好地适合于特定应用。例如,如果遵守图像边界是至关重要的,[8]的基于图的方法可能是一个理想的选择。然而,如果超像素用于构建具有更规则的晶格的图形(lattice),[23]可能是更好的选择。虽然很难定义指标来判断算法的优劣性,但我们相信以下属性通常是可取的: 
    1)超像素应当良好地粘附到图像边界。 
    2)当作为预处理步骤用于降低的计算复杂度时,超像素应当快速计算,存储 器效率高且易于使用。 
    3)当用于分割目的时,超像素应当增加速度并提高结果的质量。 
    因此,我们对五个最先进的超像素方法进行了比较[8],[23],[26],[25],[15],评估他们的速度,连接图像边界的能力还有分割性能。我们还提供这些和其他超像素方法的定性分析。我们的结论是,现有的方法不能在所有方面都令人满意。 
    为了解决这个问题,我们提出了一种新的超像素算法:简单线性迭代聚类(SLIC),它采用kmeans聚类以类似于[30]的方式生成超像素。虽然非常简单,但是SLIC在Berkeley基准[20]上产生显示出对图像边界的最好效果,并且在PASCAL[7]和MSRC[24]数据集上进行分割时优于现有方法。此外,它比现有方法更快,更高的存储效率。除了这些可量化的好处,SLIC还易于使用,更为的紧凑,其生成的超像素数量也更灵活,还可直接扩展到更高的维度,并且是免费使用的(意思是代码是开源的)。

    II.现有的超像素生成算法

    用于生成超像素的算法可以大致分类为基于图或梯度上升的方法。下面,我们回顾每个类别常见的超像素方法,包括一些最初设计不是为了生成超像素的算法。表I提供了所研究方法的定性和定量总结,包括其相对性能。 
    这里写图片描述
    表I:现有超像素算法的总结。 超像素法粘附到边界的性能可以在伯克利数据集[20]中进行评估,其可以根据两个标准度量进行排名:欠分割误差和边界回忆(对于〜500超像素)。 我们还展示了使用具有2GB RAM的Intel双核2.26 GHz处理器分段图像所需的平均时间,以及使用[11]中描述的方法在MSRC数据集上获得的类平均分割精度。 粗体条目表示每个类别的最佳性能。 还提供了指定超像素的量,控制其紧凑性以及生成超体素的能力。

    A.基于图的算法

    基于图形的超像素生成方法将每个像素视为图中的节点。两个节点之间的边权重与相邻像素之间的相似性成比例。超像素通过最小化图中定义的成本函数来创建。 
    NC05-归一化切割算法[23]递归地使用轮廓和纹理线索分割图像中的所有像素的图形,从而全局性地最小化在分割边界处的边缘定义的成本函数。它产生非常规则,视觉上令人愉快的超像素。然而,NC05的边界粘附相对较差,并且它是方法中最慢的(特别是对于大图像),尽管试图加速的算法存在[5]。NC05具有[15]的复杂度这里写图片描述,其中N是像素的数量。 
    GS04-Felzenszwalb和Huttenlocher[8]提出了一种替代的基于图形的方法,已被应用于生成超像素。它将像素作为图的节点,使得每个超像素是组成像素的最小生成树。GS04在实践中很好地粘附到图像边界,但是产生具有非常不规则的尺寸和形状的超像素。它的复杂度是这里写图片描述,在实践中速度很快。然而,它不提供对超像素的量或其紧凑性的明确控制。 
    SL08-Mooreetal提出了一种通过确定将图像分割成更小的垂直或水平区域的最佳路径或接缝来生成符合网格的超像素的方法[21]。使用类似于SeamCarving[1]的图切割方法找到最佳路径。尽管作者给出的复杂的是这里写图片描述,但这并不考虑预先计算的边界图,这强烈影响输出的质量和速度。 
    GCa10和GCb10-[26],Veksleretal。使用类似于[14]的纹理合成工作的全局优化方法。通过将重叠的图像块拼接在一起来获得超像素,使得每个像素仅属于重叠区域中的一个。这个方法有两个变种,一个用于生成紧凑超像素(GCa10),一个用于恒定强度超像素(GCb10)。

    B.基于梯度上升的方法

    从粗略的像素初始聚类开始,梯度上升法迭代地修改聚类,直到满足一些收敛标准以形成超像素。 
    MS02-In[4]中,平均偏移,用于定位密度函数的局部最大值的迭代模式寻找过程被应用于图像的颜色或强度特征空间中的第一模式。会聚到相同模式的像素定义超像素。MS02是一种较旧的方法,产生不均匀尺寸的不规则形状的超像素。它是复杂度这里写图片描述,使其相对较慢,并且不提供对超像素的量,尺寸或紧密度的直接控制。 
    QS08-快速移位[25]也使用模式查找分割方案。它使用medoid移位过程初始化分割。然后将特征空间中的搜索点移动到最近的邻居,从而增加Parzen密度估计。虽然它具有相对良好的边界粘附,但是QS08的运行速度相当缓慢,具有复杂度这里写图片描述(d是一个小常数[25])。而且QS08不允许对超像素的大小或数量的显式控制。以前的作品使用QS08对象定位[9]和运动分割[2]。 
    WS91-分水岭方法[28]从局部最小值开始执行梯度上升以产生分水岭,和分离集水盆地的线条。所得到的超像素在尺寸和形状上通常是高度不规则的,并且不表现出良好的边界粘附。[28]的方法相对较快(具有这里写图片描述的复杂度),但不提供对超像素量或其紧凑性的控制。 
    TP09-Turbopixel方法使用基于水平集的几何流动逐渐扩大一组种子位置[15]。几何流依赖于局部图像梯度,目的是在图像平面上规则地分布超像素。与WS91不同,TP09超像素被约束为具有均匀的尺寸,紧凑性和边界粘附。TP09依赖于不同复杂度的算法,但在实践中,如作者所声称的,具有大约这里写图片描述的复杂度[15],是所检查的最慢的算法之一,并且表现出相对较差的边界粘附。

    III.SLIC超像素

    我们提出一种新的生成超像素的方法,比现有方法更快,更高的记忆效率,展示了目前最优的边界依从性,并提高了分割算法的性能。简单线性迭代聚类(SLIC)采用K均值算法生成超像素,相较与其他算法具有两个重要的区别: 
    1)通过将搜索空间限制为与超像素大小成比例的区域,显着地减少了优化中的距离计算的数量。这降低了像素数N的线性复杂度,并且与超像素k的数量无关。 
    2)加权距离度量组合颜色和空间接近度,同时提供对超像素的尺寸和紧凑性的控制。 
    SLIC类似于[30]中描述的用于深度估计的预处理步骤的方法,其没有在超像素方向进行研究。

    A.算法

    SLIC使用简单易懂。默认情况下,算法的唯一参数是k,其含义是大小大致相等的超像素的个数。对于CIELAB色彩空间中的彩色图像,聚类过程从初始化步骤开始,其中k个初始聚类中心这里写图片描述在间隔S个像素的规则网格上采样。为了产生大致相等大小的超像素,网格间隔为这里写图片描述。将中心移动到与3×3邻域中的最低梯度位置相对应的种子位置。这样做是为了避免将超像素定位在边缘上,并且减少用噪声像素接种超像素的机会。 
    接下来,在分配步骤中,每个像素i与搜索区域与其位置重叠的最近聚类中心相关联,如图2所示。这是加速我们的算法的关键,因为限制搜索区域的大小显着地减少了距离计算的数量,并且导致相对于常规kmeans聚类的显着的速度优势,其中每个像素必须与所有聚类中心比较。这只能通过引入距离测量D来实现,该距离测量D确定每个像素的最近聚类中心,如第III-B节中所讨论的。由于超像素的预期空间范围是近似尺寸S×S的区域,因此在超像素中心周围的区域2S×2S中进行类似像素的搜索。 
    这里写图片描述 
    图.2:减少超像素搜索区域。SLIC的复杂性在图像O(N)中的像素数目中是线性的,而常规的k均值算法是O(kNI),其中I是迭代次数。这在分配步骤中提供了每个聚类中心的搜索空间。(a)在常规k均值算法中,从每个聚类中心到图像中的每个像素计算距离。(b)SLIC仅计算从每个聚类中心到2S×2S区域内的像素的距离。注意,期望的超像素大小仅为S×S,由较小的正方形表示。这种方法不仅减少了距离计算,而且使得SLIC的复杂性与超像素的数量无关。 
    一旦每个像素已经与最近的聚类中心相关联,更新步骤将聚类中心调整为属于该聚类的所有像素的平均向量这里写图片描述。L2范数用于计算新聚类中心位置和先前聚类中心位置之间的残差误差E.分配和更新步骤可以迭代重复,直到错误收敛,但我们发现10次迭代足够大多数图像,并报告本文中使用此标准的所有结果。最后,后处理步骤通过将不相交像素重新分配给附近的超像素来实施连通性。算法1中总结了整个算法。 
    这里写图片描述 
    这里写图片描述 
    这里写图片描述

    B.距离测量

    这里写图片描述 
    这里写图片描述 
    这里写图片描述 
    这里写图片描述 
    图3:为视频序列计算的SLIC超体元。(顶部)短波的短视频序列所产生的帧。(左下)包含视频的卷。最后一帧出现在卷的顶部。(右下)视频的超像素分割。为便于显示,具有橙色聚类中心的超体素被去除

    C.后处理

    像一些其他超像素算法[8],SLIC没有明确强制连接。在聚类过程结束时,可能保留不属于与其聚类中心相同的连接分量的一些“孤立”像素。为了对此进行校正,使用连通分量算法向这些像素分配最近聚类中心的标签。

    D.复杂度

    这里写图片描述

    IV.与现有技术的比较

    V.生物医学应用

    许多流行的基于图形的分割方法,例如图切割[3]变得越来越昂贵,因为更多的节点被添加到图中,这在实践中会对图像大小产生限制。 对于一些应用,例如从电子显微照片(EM)的线粒体分割,这种情况下图像的尺寸是很大的,但是此时不能降低分辨率。 在这种情况下,在像素网格上定义的图形上的分割将是棘手的。 在[18],SLIC超像素显着降低图的复杂性,使分割易处理。 来自[18]的分段线粒体显示在 图3(a)和(b)。在[19],这种方法扩展到3D图像堆栈,其中可以包含数十亿的体素。 只有最节俭的算法可以在这样大量的数据上操作,而不需要以某种方式减小图的大小。 SLIC超体元将存储器要求和复杂性降低超过三个数量级,并且与常规立方体相比显着增加性能,如 图3(c) - (e)所示。 
    这里写图片描述 
    图3:SLIC应用于来自神经组织的2D和3D EM图像的线粒体。 (a)来自EM切片的SLIC超像素。 (b)来自[18]的方法的分割结果。 (c)1024×1024×600体积的SLIC超体元。 (d)使用[19]中描述的方法提取的线粒体。 (e)比较SLIC超体元与相似尺寸的立方体在(c)中体积的分割性能。

    VI.结论

    超像素已经成为视觉社区的重要工具,在本文中,我们为读者提供了对现代超像素技术性能的深入分析。我们以边界粘附性,分割速度和作为分割框架中预处理步骤时的性能为指标,比较了目前最好的五个超像素算法。此外,我们提出了一种基于kmeans聚类生成超像素的新方法,SLIC已被证明在几乎每个方面都优于现有的超像素方法。 
    虽然我们的实验是彻底的,但是有一个警告。某些超像素方法,即GC10和TP09,不考虑颜色信息,而其他方法考虑。这可能会对其性能产生不利影响。

    参考文献

    [1] Shai Avidan and Ariel Shamir. Seam carving for content-aware image resizing. ACM Transactions on Graphics (SIGGRAPH), 26(3), 2007. 
    [2] A. Ayvaci and S. Soatto. Motion segmentation with occlusions on the superpixel graph. In Workshop on Dynamical Vision, Kyoto, Japan, October 2009. 
    [3] Y. Boykov and M. Jolly. Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images. In International Conference on Computer Vision (ICCV), 2001. 
    [4] D. Comaniciu and P. Meer. Mean shift: a robust approach toward feature space analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(5):603–619, May 2002. 
    [5] T. Cour, F. Benezit, and J. Shi. Spectral segmentation with multiscale graph decomposition. In IEEE Computer Vision and Pattern Recognition (CVPR) 2005, 2005. 
    [6] Charles Elkan. Using the triangle inequality to accelerate k-means. International Conference on Machine Learning, 2003. 
    [7] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman. The PASCAL Visual Object Classes Challenge. International Journal of Computer Vision (IJCV), 88(2):303–338, June 2010. 
    [8] Pedro Felzenszwalb and Daniel Huttenlocher. Efficient graph-based image segmentation. International Journal of Computer Vision (IJCV), 59(2):167–181, September 2004. 
    [9] B. Fulkerson, A. Vedaldi, and S. Soatto. Class segmentation and object localization with superpixel neighborhoods. In International Conference on Computer Vision (ICCV), 2009. 
    [10] J.M. Gonfaus, X. Boix, J. Weijer, A. Bagdanov, J. Serrat, and J. Gonzalez. Harmony Potentials for Joint Classification and Segmentation. In Computer Vision and Pattern Recognition (CVPR), 2010. 
    [11] Stephen Gould, Jim Rodgers, David Cohen, Gal Elidan, and Daphne Koller. Multi-class segmentation with relative location prior. International Journal of Computer Vision (IJCV), 80(3):300–316, 2008. 
    [12] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Eighteenth annual symposium on Computational geometry, pages 10–18, 2002. 
    [13] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. A simple linear time (1+e)-approximation algorithm for k-means clustering in any dimensions. Annual IEEE Symposium on Foundations of Computer Science, 0:454–462, 2004. 
    [14] Vivek Kwatra, Arno Schodl, Irfan Essa, Greg Turk, and Aaron Bobick. Graphcut textures: Image and video synthesis using graph cuts. ACM Transactions on Graphics, SIGGRAPH 2003, 22(3):277–286, July 2003. 
    [15] A. Levinshtein, A. Stere, K. Kutulakos, D. Fleet, S. Dickinson, and K. Siddiqi. Turbopixels: Fast superpixels using geometric flows. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 2009. 
    [16] Yin Li, Jian Sun, Chi-Keung Tang, and Heung-Yeung Shum. Lazy snapping. ACM Transactions on Graphics (SIGGRAPH), 23(3):303– 308, 2004 
    [17] Stuart P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, IT-28(2):129–137, 1982. 
    [18] A. Lucchi, K. Smith, R. Achanta, V. Lepetit, and P. Fua. A fully automated approach to segmentation of irregularly shaped cellular structures in em images. International Conference on Medical Image Computing and Computer Assisted Intervention, 2010. 
    [19] Aur´elien Lucchi, Kevin Smith, Radhakrishna Achanta, Graham Knott, and Pascal Fua. Supervoxel-Based Segmentation of Mitochondria in EM Image Stacks with Learned Shape Features. IEEE Transactions on Medical Imaging, 30(11), 2011. 
    [20] D. Martin, C. Fowlkes, D. Tal, and J. Malik. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In IEEE International Conference on Computer Vision (ICCV), July 2001. 
    [21] Alastair Moore, Simon Prince, Jonathan Warrell, Umar Mohammed, and Graham Jones. Superpixel Lattices. IEEE Computer Vision and Pattern Recognition (CVPR), 2008. 
    [22] Greg Mori. Guiding model search using segmentation. In IEEE International Conference on Computer Vision (ICCV), 2005. 
    [23] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 22(8):888–905, Aug 2000. 
    [24] J. Shotton, J. Winn, C. Rother, and A. Criminisi. TextonBoost for Image Understanding: Multi-Class Object Recognition and Segmentation by Jointly Modeling Texture, Layout, and Context. International Journal of Computer Vision (IJCV), 81(1), January 2009. 
    [25] A. Vedaldi and S. Soatto. Quick shift and kernel methods for mode seeking. In European Conference on Computer Vision (ECCV), 2008. 
    [26] O. Veksler, Y. Boykov, and P. Mehrani. Superpixels and supervoxels in an energy optimization framework. In European Conference on Computer Vision (ECCV), 2010. 
    [27] O. Verevka and J.W. Buchanan. Local k-means algorithm for color image quantization. Graphics Interface, pages 128–135, 1995. 
    [28] Luc Vincent and Pierre Soille. Watersheds in digital spaces: An efficient algorithm based on immersion simulations. IEEE Transactions on Pattern Analalysis and Machine Intelligence, 13(6):583–598, 1991. 
    [29] Y. Yang, S. Hallman, D. Ramanan, and C. Fawlkes. Layered Object DetectionforMulti-ClassSegmentation. InComputer Visionand Pattern Recognition (CVPR), 2010. 
    [30] C. L. Zitnick and S. B. Kang. Stereo for image-based rendering using image over-segmentation. International Journal of Computer Vision (IJCV), 75:49–65, October 2007.

    文章下载:https://infoscience.epfl.ch/record/177415/files/Superpixel_PAMI2011-2.pdf 
    源码地址:http://ivrl.epfl.ch/research/superpixels

    展开全文
  • SLIC超像素分割算法

    万次阅读 多人点赞 2017-09-22 18:17:13
    它利用像素之间特征的相似性将像素分组,用少量的超像素代替大量的像素来表达图片特征,很大程度上降低了图像后处理的复杂度,所以通常作为分割算法的预处理步骤。已经广泛用于图像分割、姿势估计、目标跟踪、目标识别...
  • 计算像素轮廓的像素面积算法

    千次阅读 2015-01-09 14:41:02
    基于轮廓 计算像素轮廓的像素面积算法
  • 像素分割算法

    千次阅读 2015-05-21 10:29:07
    在迭代结束时,会有少量的迷失像素,即少量的像素和附近较大的分割块有相同的 标签,但它们并没有被关联进去。因为迭代聚类时没有明确地加强连通性,这种情况就可能发生。因此,我们可以在算法
  • 简介:最近项目使用到了超像素分割,因此顺道研究了以下SLIC这一算法。超像素分割这类low-level vision问题已经在CVPR,ICCV这种顶级会议上逐渐销声匿迹,越来越流行的learning method渐渐占据了这些顶级会议90%的...
  • 使用像素碰撞检测法算是最精确的算法了,当然,带来的代价也是比较明显的,那就是效率上的低下。除非是在极为特殊的情况下,要求使用非常精确的碰撞,否则,一般情况下在游戏中是不建议使用这种算法,特别是在运行...
  • SLIC超像素生成算法

    千次阅读 2015-10-09 18:58:48
    SLIC算法是simple linear iterative cluster的简称,该算法用来生成超像素(superpixel)。 基本思想 算法大致思想是这样的,将图像从RGB颜色空间转换到CIE-Lab颜色空间,对应每个像素的(L,a,b)颜色...
  • 新手求助,谁有Zernike亚像素边缘检测算法的matlab代码,
  • 像素分割算法SLIC的matlab实现

    千次阅读 多人点赞 2020-08-20 16:59:05
    SLIC是一种基于网格化KMeans聚类的超像素分割算法,其计算复杂度为O(N),其中N为像素点个数。SLIC的原理比较简单精致,具体的原理我这里就不介绍了,推荐大家自己去读原始论文加深理解。SLIC的算法流程如下: 如...
  • bmp图片内部任意区域像素提取算法

    千次阅读 2018-04-09 13:56:45
    有时候我们的需求是在一个bmp图片ABCD内部,指定一个基准点p0(x0,y0)(裁剪区域的中心点),在水平方向上任意旋转θ角度任意一块长度为l,宽度为w的矩形区域A'B'C'D',这是就需要进行像素提取,核心是坐标系的转换。...
  • FCOS: 最新的one-stage逐像素目标检测算法

    万次阅读 多人点赞 2019-04-07 18:50:02
    本文提出了一种全卷积one-stage目标检测算法(FCOS),以逐像素预测的方式解决目标检测问题,类似于语义分割。目前最流行的不论是one-stage目标检测算法,如RetinaNet,SSD,YOLOv3,还是two-stage目标检测算法,如...
  • python:超像素SLIC算法使用

    万次阅读 2018-07-01 21:45:33
    skimage作为图像处理库,包括多种图像分割算法。其中超像素slic目前表现较好,该部分代码如下。 from skimage.segmentation import slic,mark_boundaries from skimage import io import matplotlib.pyplot as plt ...
  • 图像可以是看成是一个多维的数组...图像的像素操作是比较基础的图像算法,下面列举三个常用的像素操作算法。图像加法图像的加法表示两个输入图像在同一位置上的像素相加,得到一个输出图像的过程。 imageProcessor = O
  • SLIC算法像素 superpixel

    千次阅读 2015-04-05 21:52:04
    SLIC算法是simple linear iterative cluster的简称,该算法用来生成超像素(superpixel)。 算法大致思想是这样的,将图像从RGB颜色空间转换到CIE-Lab颜色空间,对应每个像素的(L,a,b)颜色值和(x,y)坐标...
  • 介绍SLIC超像素分割算法,给出其与openCV的接口,代码用VS2012和openCV2.4.9测试可运行。
  • SLIC图像超像素分割算法解析

    万次阅读 2015-09-17 04:32:27
    1 概述 SLIC 即simple linear ...分簇的依据是像素之间的颜色相似性与邻近性。其中颜色相 似性的度量因子是lab 颜色空间的L1 范数,颜色邻近性的度量因子是图像二维坐标空间xy。因而综合的度量因子 是[labx
  • SLIC超像素(superpixel)算法

    千次阅读 2015-10-18 15:18:20
    SLIC算法是simple linear iterative cluster的简称,该算法用来生成超像素(superpixel)。 基本思想 算法大致思想是这样的,将图像从RGB颜色空间转换到CIE-Lab颜色空间,对应每个像素的(L,a,b)颜色
  • 快速亚像素边缘提取算法

    千次阅读 2010-09-19 12:53:00
    快速亚像素边缘提取算法   关键词: Facet模型,曲面拟合,离散切比雪夫正交多项式,亚像素边缘             特色书店,图像处理,机器视觉,C/C++,控制理论/工程,工程数学..... ...
  • 基于标准像素图像识别算法

    千次阅读 2015-03-05 16:27:48
    自己试着实现一些简单规则的图像识别算法,纯属交流,不喜勿喷!
  • 它利用像素之间特征的相似性将像素分组,用少量的超像素代替大量的像素来表达图片特征,很大程度上降低了图像后处理的复杂度,所以通常作为分割算法的预处理步骤。常见的超像素分割方法包括: Graph-based 、NCut 、...
  • OpenCV3中超像素分割算法SEEDS,SLIC, LSC算法在Contrib包里,需要使用Cmake编译使用。为了方便起见,我将三种算法的源码文件从contrib包里拎了出来,可以直接使用,顺便比较一下算法的效果。  三种算法的源码...
  • 像素级角点定位算法

    千次阅读 2017-02-08 13:47:29
    上篇文章,已对点和边缘两种情形的亚像素定位算法做了详细描述。因图像特征不同,亚像素定位算法也会不同,我们可以根据图像的具体特征,进行数学建模以达到定位目的。这里另起一篇说明角点情形的亚像素定位问题。 ...
  • 看了网上很多人说有个灰度公式,可以直接遍历每个像素,并把每个像素中的rgb换成如下值即可: P=0.299×Red+0.587×Green+0.114×BlueP=0.299\times Red +0.587\times Green+0.114\times BlueP=0.299×Red+0.587×...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 168,153
精华内容 67,261
关键字:

像素算法