英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
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 ]。
有许多方法来生成超像素，每一个都有自己的优点和缺点，它们可能更适合特定的应用程序。例如，如果图像边界吻合度是非常重要的，那么基于图的方法[8]会是一个理想的选择。然而，如果是用超像素来构建一幅图像，那么如[ 23 ]这种产生一个更为规则的晶格的方法可能是更好的选择。虽然很难界定什么是对所有应用都理想的方法，我们相信以下性能通常是人们期望达到的：
1. 超像素应该有好的图像边界吻合度。
2. 当用于减少计算的复杂性时，作为一个预处理步骤，超像素应该可被快速计算，占据较小的内存，且使用简单。
3. 当用于分割的目的时，超像素分割既要能够提高处理速度又要提高搜索结果的质量。
我们验证比较了5种目前使用的超像素算法[8],[23]，[26]，[25]，[15]的速度，图像边界吻合度以及分割性能的影响。我们也提供对这几种超像素分割法的定性评估。我们的结论是，没有一种现有的方法完全满足上述所有性能。
为了解决这个问题，我们提出了一种新的超像素的算法：简单线性迭代聚类（SLIC），它应用k-means聚类算法以相似的方法生成超像素[ 30 ]。显而易见的是，在伯克利基准[20]中证实了SLIC在图像边界的吻合度方面与现有的几种算法不相上下，在Pascal [ 7 ]和MSRC [ 24 ]数据集分割时优于现有算法。此外，它比起现有方法处理速度更快，占有内存更小。除了这些可量化的优点，SLIC便于使用，生成大量超像素时简洁灵活，可扩展到更高维度并且易于获得。1
2 现有的超像素算法
超像素生成算法大致可以分为基于图或梯度上升的算法。下面，我们回顾几种较为流行的超像素算法，包括一些原本不是专门为生成超像素而设计的算法。表1提供了一个检查方法的定性定量的总结，包括它们的相对性能。
图1 SLIC算法64,126,1024像素下的图像分割
2.1 基于图的算法
基于图的算法在生成超像素时把图形中的每一个像素当做节点来处理。两个节点间的边权与相邻像素间有相似的比例。超像素是通过使定义的图像成本函数最小化来实现的。
NC05.归一化切割算法[ 23 ]利用图像的轮廓和纹理作为线索，递归的划分了图中的所有像素，全局地得到了定义在划分边界的最小化成本函数。它产生了一种非常规则且看起来完美的超像素。然而，NC05的边界吻合度很小，并且虽然有试图加快运算速度的算法存在[ 5 ]，但它在各种方法中处理速度依然是最慢的（特别是大的图像）。NC05具有的复杂性，其中N是像素的数量。
GS04.Felzenszwalb和Huttenlocher [ 8 ]提供了一种可以替代基于图的方法，这种方法已被应用到超像素生成中。它提供了一种聚类像素作为图像中的节点的方法，这样每一个超像素都在组成像素的最小生成树上。GS04 的边界吻合度在实际运用中很好，但是会导致超像素的尺寸和形状不规则。它的复杂度为，并且在实际中处理速度很快。然而，它不提供对于超像素的数量或者致密性的准确控制。
SL08.摩尔等人提出了一种生成超像素的方法，通过网格寻找最优路径或接缝，使图像分解成更小的垂直或水平区域[ 21 ]。这种使用最佳路径进行图像切割的方法类似于Seam Carving[ 1 ]。然而SL08复杂度为 并不依赖于预计算的边界图，严重影响了输出的速度和质量。
GCa10和GCb10.在[ 26 ]中，Veksler等人使用类似于全局最佳路径的纹理合成工作[ 14 ]。通过拼接重叠的图像块来生成超像素，每一个像素都唯一属于重叠区域中的一个。他们认为这种方法有两个变种，一个产生紧凑的超像素（gca10）和一个强度恒定的超像素（gcb10）。
2.2 基于梯度上升的算法
从一个粗糙的初始像素聚类开始，梯度上升的方法迭代优化集群直到收敛准则满足以形成超像素。
MS02.在[ 4 ]中，mean shift作为一个用于定位局部密度函数的最大值的迭代模式搜索方法，被应用于寻找图像的颜色或强度特征空间的模式。将合并到相同模式的像素定义为超像素。MS02是一个产生不规则形状与不均匀规格超像素的传统方法。它的时间复杂度为，导致它的处理速度很慢，而且不能提供对超像素数量、规格和致密性的直接控制。
QS08.Quick shift[ 25 ]还使用了一种模式搜索分割机制。它使用medoid shift过程初始化分割。然后将特征空间中的每个点移动到邻节点以增加Parzen密度估计。虽然它的边缘吻合度较好，但是QS08的时间复杂度导致它的处理速度慢（d是一个小常量[25]）。QS08不支持对超像素规格和数量的明确控制。以前的工作都采用QS08进行对象定位[ 9 ]和运动分割[ 2 ]
表1
现有超像素算法总结
WS91.分水岭方法[ 28 ]从局部极小值开始执行一个梯度上升直到产生划分集水区的分水岭。由此产生的超像素通常大小和形状极不规则，边缘吻合度不佳。这种方法复杂度为，处理速度很快，但不提供对超像素数量或者致密性控制。
TP09.Turbopixel方法通过基于水平集的几何流逐步扩张了一系列种子位置[15]。几何流依赖于局部图像梯度，旨在定期分配图像平面超像素。不像WS91，TP09超像素具有大小均匀，致密性，和高边缘吻合度的特点。TP09依赖于复杂程度不同的算法，但在实践中，正如作者声称，其时间复杂度约为[15]。然而，它的性能介于已验证的处理速度最慢和边缘吻合度最差的算法之中。
3 SLIC算法
我们提出了新的超像素生成方法，比现有方法处理速度更快，占用内存更小，边缘吻合度更高，提高了分割算法的性能。简单线性迭代聚类是k-means为产生超像素的改版，它们有两个重要区别：
1. 距离计算中的最优化的数量通过限制搜索空间以正比于超像素大小的区域显著减小。这让算法的时间复杂度降低为与像素数N相关的线性复杂度，且超像素数量k独立。
2. 一种结合颜色和空间距离的加权距离度量，可以同时提供超像素的大小和紧凑性控制。
SLIC类似于 [30]中描述的深度估计预处理步骤，是在超像素生成的背景下未完全探索的方法。
3.1 算法
SLIC的使用和理解都很简单。默认情况下，该算法的唯一参数k为期望的相同大小的超像素的数量。2对于在CIELAB彩色空间的彩色图像，聚类过程以初始化步骤开始，其中k初始聚类中心是常规网格空间S像素分离的取样。为了产生大致同样大小的超像素，网格间隔为。中心都移动到33矩阵的最低梯度方位对应的种子位置。这样做是为了避免超像素中心在边缘出现，并减少产生一个具有噪声像素的超像素的机会。
接着，在分配步骤中，每个像素i与最接近的聚类中心的搜索区域重叠的位置相关联，如图2所述。这是加快算法速度的关键，因为限定搜索区域的大小显著减少距离计算的数量，并导致一个区别于k-means聚类的显著优势，其中每个像素必须与所有聚类中心相比。正如3.2节讨论，引入距离量度D确定对于每一个像素最近的聚类中心。由于一个超像素的预期空间范围近似为SS，那么搜索相似的像素的区域是超像素中心周围的2S2S区域。
一旦每个像素已经关联到最近的聚类中心，更新步骤将聚类中心调整至属于该聚类的所有像素点的均值矢量。基准被用来计算新聚类中心位置和旧聚类中心位置的残留误差E。分配和更新步骤可以重复迭代直至误差收敛，但我们发现，对于大多数图像以及本文所使用的标准，10次迭代已经足够。最后，后处理步骤通过再分配解体像素像素强制性使其与周围超像素进行联通。整个算法总结在算法1。
算法1.SLIC超像素分割
/*初始化*/
通过常规网格步骤S中采样像素初始 化聚类中心。
将聚类中心移动到33矩阵最小梯度 位置 。
为每一个像素i定义标签。
为每一个像素i定义距离。
repeat
/*分配*/
for 每个聚类中心 do
for 每个周围2S2S区域的像素i do
计算和i之间的距离D
if Dlt; then
设置=D
设置=k
end if
end for
end for
/*更新*/
计算新的聚类中心。
计算残留误差E。
until 临界值
3.2 距离计算
SLIC超像素符合labxy彩色图像平面空间的聚类。这呈现在确定距离度量D，其可能不会立即明显的问题。在算法1中D是像素i和聚类中心的距离。像素的颜色被由CIELAB颜色空间表示，其可能值范围已知。另一方面，像素的位置可以采取一系列随图像大小变化而变化的值。
简单地定义D作为labxy空间的5D欧氏距离，这将导致不同大小超像素的聚类行为的矛盾。对于大型超像素，空间距离比颜色近似度更为重要，空间近似度相对颜色更为重要。这将产生边缘吻合度不佳的紧凑超像素。对于较小的超像素，反过来也是如此。
为了将两个距离合并为一次测量，有必要通过颜色和空间到聚类各自的最大距离和对颜色近似度和空间近似度进行规范化。为此，被写作
一个给定聚类间的最大空间距离应该与采样间隔对应，。由于颜色距离会随着聚类到聚类、图像到图像而变化，因此确定最大颜色距离并不那么简单。这个问题可以通过将固定为常量m来避免，所以(1)就变为
在实际中可以简化为
- 标准k-means搜 (b)SLIC搜索局
索全部图像 部区域
图2.减少超像素搜索区域
通过以这种方式定义D，此时的m也允许我们衡量颜色相似度和空间接近度。当m很大时，空间接近度更为重要，所得到的超像素更加紧凑（即，它们具有更小的周长比范围）。当m较小时，所得到的超像素边缘吻合度更高，但具有较少的常规尺寸和形状。当使用CIELAB颜色空间时，m取值范围为[1,40]。
在灰度图像中方程(3)可以被改写为
它也可以扩展到处理3D 超体素，如图3所示，用深度和空间接近度改写方程(3)：
图3. SLIC 超体素
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[26176]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
