IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL.34, NO.11, NOVEMBER 2012
SLIC超像素分割算法和目前
超像素算法的比较
Radhakrishna Achanta, IEEE专业会员, Appu Shaji, Kevin Smith, IEEE专业会员,
Aurelien Lucchi, Pascal Fua, IEEE会士, and Sabine Susstrunk, IEEE高级会员
摘要 近年来计算机视觉应用已经越来越依赖于超像素处理，但它并不总是很清楚什么是一个好的超像素的算法。为了了解目前算法的优点和缺点，我们验证比较了5种目前使用的超像素算法与图像边缘吻合的能力，速度，内存使用率和它们对于分割效果的影响。我们引入了一种基于应用k-means聚类算法的简单线性迭代聚类（SLIC）的新的超像素算法以有效生成超像素。尽管它很简单，SLIC对于边界的吻合度与之前的算法相比不分上下甚至更好。同时，它速度更快，占用内存更小，分割性能更优，并直接扩展了超体素生成。 索引词汇 超像素，分割，聚类，k-means
1 简介
超像素算法组像素在感知上有意义的原子区域中可以取代像素网格的刚性结构（图 1）。他们捕捉图像冗余，提供了一种便捷的计算图像特征，并大幅降低后续图像处理任务的复杂度的原始方法。他们已经成为很多计算机视觉算法的关键构建模块，比如在PASCAL VOC挑战赛中得分最高的多类对
象分割[ 9 ]，[ 29 ]，[ 11 ]
，深度估计[ 30 ]，分割[ 16 ]，人体模型估计[ 22 ]，以及目标定位[ 9 ]。 有许多方法来生成超像素，每一个都有自己
Published by the IEEE Computer Society
的优点和缺点，可能更适合特定的应用程序。例如，如果图像边界吻合度是非常重要的，那么基于图的方法会是一个理想的选择。然而，如果是用超像素来构建一幅图像，那么如[ 23 ]这种产生一个更为常规的晶格的方法可能是更好的选择。虽然很难界定什么是对所有应用都理想的方法，我们相信以下性能通常是可取的：
1. 超像素应该有好的图像边界吻合度。 2. 当用于减少计算的复杂性时，作为一个预处理步骤，超像素应该可被快速计算，占据较小的内存，和简单的使用。
3. 当用于分割的目的时，超像素分割既要能够提高处理速度又要提高搜索结果的质量。 我们验证比较了5种目前使用的超像素算法[ 8 ]，[ 23 ]，[ 26 ]，[ 25 ]，[ 15 ]
的速度，图像边界吻合度以及分割性能的影响。我们也提供对这几种超像素分割法的定性评估。我们的结论是，没有一种现有的方法完全满足上述所有性能。
为了解决这个问题，我们提出了一种新的超像素的算法：简单线性迭代聚类（SLIC），它应用k-means聚类算法以相似的方法生成超像素[ 30 ]。显而易见的是，在伯克利基准中证实SLIC在图像边界的吻合度方面不如现有的几种算法[20]，在Pascal [ 7 ]和MSRC [ 24 ]
数据集分割时优于现有算法。此外，它比起现有方法处理速度更快，占有内存更小。除了这些可量化的优点，SLIC便于使用，生成大量超像素时简洁灵活，可扩展到更大规模并且易于获得。1
2 现有的超像素算法
超像素生成算法大致可以分为基于图或梯
度上升的算法。下面，我们回顾几种较为流行的超像素算法，包括一些原本不是专门为生成超像素而设计的算法。表1提供了一个检查方法的定性定量的总结，包括它们的相对性能。
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL.34, NO.11, NOVEMBER 2012
图1 SLIC算法64,126,1024像素下的图像分割
2.1 基于图的算法
基于图的算法在生成超像素时把图形中的每一个像素当做节点来处理。两个节点间的边权与相邻像素间有相似的比例。超像素是通过图像成本函数的最小值来定义的。 NC05.归一切割算法[ 23 ]利用图像的轮廓和纹理作为线索递归的划分了图中的所有像素，全局最小化成本函数根据划分边界的边缘定义。它产生了一种非常正规完美的超像素。然而，NC05的边界吻合度很小，并且虽然有试图加快算法存在[ 5 ]，但它在各种方法中处理速度依然是最慢的（特别是大3的图像）。NC05具有O(N2)的复杂性，其中N是像素的数量。
GS04.Felzenszwalb和Huttenlocher [ 8 ]提供了一种可以替代基于图的方法，这种方法已被应用到超像素生成中。它提供了一种聚类像素作为图像中的节点的方法，这样每一个超像素都在组成像素的最小生成树上。GS04 的边界吻合度在实际中很好，但是会导致超像素的尺寸和形状不规则。它是
O(NlogN)复合体，并且在实际中处理速度
很快。然而，它不提供对于超像素的数量或者致密性的准确控制。
SL08.摩尔等人提出了一种生成超像素的方法，通过网格寻找最优路径或接缝，使
Published by the IEEE Computer Society
图像分解成更小的垂直或水平区域[ 21 ]。这种使用最佳路径进行图像切割的方法类似于Seam Carving[ 1 ]。然而SL08复杂度
3O(N2logN) 并没有对预计算边界地图作
出解释，着强烈影响了输出的质量速度。 GCa10和GCb10.在[ 26 ]中，Veksler等人使用类似于全局最佳路径的纹理合成工作[ 14 ]。通过拼接重叠的图像块来生成超像素，每一个像素抖唯一属于一个重叠区域。他们认为这种方法的两个变种，一个产生紧凑的超像素（gca10）和一个强度恒定的超像素（gcb10）。
2.2 基于梯度上升的算法
从一个粗糙的初始像素聚类开始，梯度上升的方法迭代优化集群直到收敛准则满足形成超像素。
MS02.在[ 4 ]中，均值漂移作为一个用于定位局部密度函数的最大值的迭代模式搜索方法被应用于寻找图像的颜色或强度特征空间的模式。将收敛到相同的方式的像素定义为超像素。MS02是一个产生不规则形状不均匀规格超像素的传统方法。它的复杂度为O(N2)，导致它的处理速度很慢，而且不能提供对超像素数量、规格和致密性的直接控制。
QS08.快速漂移[ 25 ]还使用了一种模式搜索分割机制。它使用中心漂移过程初始化分割。然后将特征空间中的每个点移动到邻节点以增加Parzen密度估计。虽然它的边缘吻合度较好，但是QS08O(dN2)的复杂度导致处理速度慢（d是一个小常量[25]）。QS08不支持对超像素规格和数量的明确控制。以前的作品都采用QS08进行对象定位[ 9 ]和运动分割[ 2 ]。
WS91.分水岭方法[ 28 ]从局部极小值开
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL.34, NO.11, NOVEMBER 2012
表1
现有超像素算法总结
始执行一个梯度上升知道产生划分集水区的分水岭。由此产生的超像素通常在大小和形状极不规则，边缘吻合度不佳。这种方法复杂度为O(NlogN)，处理速度很快，但不提供对超像素数量或者致密性控制。 TP09.Turbopixel方法通过基于水平集的几何流逐步扩张了一系列种子位置[15]。几何流依赖于局部图像梯度，旨在定期分配图像平面超像素。不像WS91，TP09超像素具有大小均匀，致密性，和高边缘吻合度的特点。TP09依赖于复杂程度不同的算法，但在实践中，正如作者声称，复杂度行为约为
O(N)[15]。然而，它的性能介于已验证的处
理速度最慢和边缘吻合度最差的算法之中。
3 SLIC算法
我们提出了新的超像素生成方法，比现有方
法处理速度更快，占用内存更小，边缘吻合度更高，提高了分割算法的性能。简单线性迭代聚类是k-means为产生超像素的改版，有两个重要区别：
1. 距离计算中的最优化的数量通过限制搜索空间以正比于超像素大小的区域显著地减小。这降低了像素数量的线性复杂度N和超像素数量k的独立性。
2. 一种加权的距离量度组合颜色和空间距离，同时提供超像素的规格和紧凑性控制。
Published by the IEEE Computer Society
SLIC类似于用作在[30]中描述的深度估计，这是不完全的超像素生成的背景下探索出了预处理步骤的方法。
3.1 算法
SLIC使用和理解都很简单。默认情况下，该算法的唯一参数k的所需数量大约相当于超像素的规格。2对于在CIELAB彩色空间的彩色图像，聚类程序以初始化步骤开始，其中k初始聚类中心次
Ci?[li,ai,bi,xi,yi]T是常规王哥空间S
像素分离的取样。为了产生大致同样大小的超像素，网格间隔为S?NK。中心都移动到3?3矩阵的最低梯度方位对应的种子位置。这样做是为了避免在边缘定心一个超像素，并减少播种一个超像素与噪声像素的机会。
接着，在分配步骤中，每个像素i与最接近的聚类中心的搜索区域重叠的位置相关联，如图2所述。这是加快算法速度的关键，因为限定搜索区域的大小显著减少距离计算的数量，并导致一个区别于k-means聚类的显著优势，其中每个像素必须与所有聚类中心相比。正如3.2节讨论，引入距离量度D确定对于每一个像素最近的聚类中心。由于一个超像素的预期空间范围近似为S?S，那么搜索相似的像素的区域是超像素中心周围的2S?2S区域。
一旦每个像素已经关联到最近的聚类中心，更新步骤将聚类中心调整至属于该聚类的所有像素点的均值矢量[l,a,b,x,y]T。基准L2被用来计算新聚类中心位置和旧聚类中心位置的残留误差E。分配和更新步骤可以重复迭代直至误差收敛，但我们发现，对于大多数图像以及本文所使用的标准，10