毕业设计外文资料翻译-与其他先进超像素方法相比较的SLIC超像素算法

1、毕业设计外文资料翻译学 院： 专业班级： 学生姓名： 学 号： 指导教师： 外文出处： The IEEE Computer Society 附 件：1. HYPERLINK l _Java技术介绍 外文资料翻译译文； 2. HYPERLINK l _Java_Technical_Description 外文原文 指导教师评语： 该英文资料选择合理，专业术语、词汇翻译准确度较高，体现了一定的英语应用水平。翻译工作认真细致，严格按照规定，翻译材料能与原文保持一致，能正确的表达出原文的意思，希望能够将细节部分处理得更加得当。签名： 2015 年 10 月 14 日 外文资料翻译译文 与其他先进超像素

2、方法相比较的SLIC超像素算法摘 要近年来，计算机视觉应用已经开始越来越依靠超像素，但它并不总是很明确什么是好的超像素算法。在努力了解现有方法的优点和缺点后，我们根据经验，从图像边缘的附着力、速度、存储效率以及分割能力的影响方面对五种最先进的超像素算法进行比较。接着，我们引入一种新的，能够自适应K-均值聚类方法来产生超像素的超像素算法，简单的线性迭代聚类（SLIC）。尽管简单，SLIC附着边界的能力甚至超过了之前的方法。同时，SLIC更快，提高分割性能，存储效率更高，并且直接延伸到超像素生成。【关键词】超像素，分割，聚类，k均值1.概述超像素算法像素组成感知上有意义的微粒区可用于替换像素栅格的

3、刚性结构。他们捕捉冗余的图像，提供从一个方便的原始计算图像特征，并大大降低了后续的图像处理任务的复杂性。他们已经成为许多计算机视觉算法关键构建模块，如得分最高的多类目标分割项，比如PASCAL VOC挑战，深度估计，分割，人体模型估计，和对象定位。有许多方法来产生超像素，虽然每一个都有各自的优点和缺点，但是也可能更适合于一个特定的应用。例如，如果遵守图像边界是非常重要的，对基于图的方法8可以是一个理想的选择。然而，如果超像素是被用来建立的曲线图，产生一个更规则晶格的方法，可能是一个更好的选择。虽然这是很难界定什么是所有应用的理想方法，我们认为以下属性通常是需要的：1.超像素应该很好地附着图像边

4、界；2.当作为预处理步骤而用于降低计算复杂度时，超像素应该有高效的计算和存储效率，并易于使用；3.当用于分割时，超像素应该增加速度并且改善的结果的质量。因此，我们进行的最先进的五种的经验比较超像素方法，评估他们的速度，附着图像边界的能力，和影响力分割性能。我们还提供了这些定性审查，以及其他超像素方法。我们的结论是，没有现有的方法在各个方面都令人满意。为了解决这个问题，我们提出了一种新的算法超像素：简单的线性迭代算法（SLIC），它适应K-均值聚类，类似于的方式来产生超像素。虽然方法十分简单，但是在使用PASCAL和MSRC数据集分割时，SLIC在保持图像边界方面世界领先，并优于现有的方法。此外

5、，它比现有方法更快和更存储器高效。除了这些可量化的好处，SLIC是易于使用，在该紧凑提供了灵活性和它产生的超像素的数目，是直接延伸到更高维度，并且是免费提供的。2.现有的超像素方法用于产生超像素算法可大致归类为图形或基于梯度上升的方法。下面，我们查看每一个类别的流行超像素方法，包括原本不是专为超像素生成一些。2.1.基于图论的算法基于图论的方法来产生超像素，就是将图中的每个像素当成一个节点。两个节点之间的边缘的权重与相邻像素之间的相似点成比例。超像素是通过最小化在图中定义的成本函数创建的。NC05归一化的削减算法递归分割使用轮廓和纹理的线索，全局最小化对在分区边界处的边缘限定的成本函数的图像中

6、的所有像素的曲线图。它产生非常有规律，视觉愉悦超像素。然而，NC05的边界粘附相对较差，这是上述方法（特别是对大型的图像）中最慢的，虽然存在企图加速的算法。 NC05的复杂度是O( QUOTE ) ，其中N是像素的数量.GS04。Felzenszwalb和Huttenlocher提出一种已经被应用到生成超像素替代基于图形的方法。它执行像素的凝聚聚类作为一个图，使得每个超像素是构成像素的最小生成树节点。 GS04能很好地粘附在图像的边界，但具产生的超像素的大小和形状非常不规则。实际上，它的复杂度是O( QUOTE )并且够快。然而，它不提供在超像素或它们紧凑的量的显式控制。SL08。Moore等

7、人，提出一种以产生通过找到最佳路径，或接缝符合网格超像素的方法，该图像分割成更小的垂直或水平区。最佳路径是使用图切割方法类似煤层雕刻发现。虽然SL08的复杂度是 QUOTE ，根据作者，这并不占预先计算的边界地图，并且极大地影响输出的质量和速度。GCa10和GCb10。Veksler等人使用类似的纹理合成工作的全局优化方法。超像素由缝合在一起的重叠图像块，使得每个像素属于只重叠区中的一个获得的。他们建议他们的方法的两个变体，一个用于产生紧凑超像素（GCA10），一个用于恒定强度超像素（GCB10）。2.2.基于梯度向上的算法从像素的粗略初始聚类开始，直到一些收敛条件得到满足并形成超像素，都用梯

8、度上升的方法进行提炼、集群。MS02。均值漂移，用于定位的密度函数的局部最大值的迭代方式寻求过程中，被施加到找到在图像的颜色或强度的特征空间模式，会聚到相同模式的像素来定义超像素。 MS02是一个较老的方法，生产非均匀大小的不规则形状的超像素。它 QUOTE 的复杂度，使得它相当慢，而且不能准确控制数量，大小，或超像素的紧凑度。QS08。快速移动也采用一种模式寻求分割方案。它使用medoid转变程序来初始化分割。然后将其移至特征空间，增加了Parzen窗密度估计的最近的邻居的每个点。虽然它能较好的附着图像边界，但是复杂度为 QUOTE 的QS08相当缓慢（d是一个很小的常数）。 QS08不允许

9、显式控制大小或超像素的数目。以前的工作已经使用QS08为对象定位和运动分割。WS91。分水岭的方法，从局部极小开始生产流域，从而进行梯度上升，即分离集水盆地线。所得超像素往往在尺寸和形状极不规则，并且不能显示出良好的边界的粘附性。相对比较快（复杂度为O( QUOTE )），但对那些超过超像素数量的或紧密度的不能控制。TP09。Turbopixel方法使用基于水平集的几何流逐步扩张一系列的种子位置。几何流动依赖于本地图像梯度，瞄准到像平面上定期分发超像素。不同于WS91，TP09超像素被限制为要求具有大小均匀，致密性，和边界粘附。 TP09依赖于复杂程度不同的算法，但在实践中，作者声称，大约反应

10、为 QUOTE 。但是，在被检查的算法中，TP09仍是最慢的并且边界的附着性也是相对较差的。3.SLIC超像素我们提出了一种生成超像素的新方法，它比现有方法更快，更高效。这种方法展现出了最先进的边界附着性，并且提高了图像分割算法的效率。简单线性迭代集群是为了使K-means能够适应超像素产生，有两个重要的区别：1.通过限制到正比于超像素尺寸的区域中的搜索空间，优化距离计算的数量急剧减少。这降低了像素N在数量上和独立超像素K的线性复杂度。2.加权距离量度组合颜色和空间邻近，同时提供在超像素的尺寸和紧凑性的控制。SLIC类似于用作在中描述的深度估计，这不完全是在超像素生成的背景下探索出的预处理步骤

11、的办法。3.1 算法SLIC易于使用，便于理解。在默认情况下，该算法的唯一参数为k，约同样大小的超像素所需的号码。在CIELAB颜色空间的彩色图像，聚类程序开始于初始化步骤，其中k初始聚类中心 QUOTE 的间距为小号像素上的规则网格取样。为了产生大致同样大小的超像素，像素间隔为 QUOTE 。聚类中心移动到对应于最低梯度位置的33邻域位置。这样做是为了避免在边缘定心一个超像素，并减少播种一个超像素与嘈杂象素的机会。接着，在分配步骤中，每个像素i与最接近的聚类中心的搜索区域重叠的位置相关联，如在图中描绘。 2.这是关键加快我们的算法，因为限制了搜索区域的大小显著减少距离计算的数量，并导致显著速

12、度优于常规k均值聚类，其中每个像素必须与所有聚类中心进行比较。这通过引入一个距离量度D，其确定每个像素最接近的聚类中心，如在第3.2节中讨论的是唯一可能的。由于超像素的预期空间范围近似大小SS的一个地区，相似像素的搜索是在一个区域2S2S围绕超像素中心完成。一旦各象素已被关联到最近的聚类中心，所有属于该集群的像素的载体，更新步骤调整聚类中心是平均 QUOTE 。 L2范数被用来计算新的群集中心位置和先前的聚类中心位置之间的残余误差E。分配和更新步骤可以反复重复，直至误差收敛，但我们已发现，10次迭代足以满足大多数图像，所以本文中的所有结果都使用该标准。最后，一个后置处理将脱离的像素再分配到附近

13、的超像素并使其强制连接。整个算法总结在算法1中。3.2 距离测量SLIC超像素对应于在实验室中彩色图象平面空间群集。这显现了定义测量距离D时的一个问题，当然这个问题不会立刻显现。D在算法1中计算了一个像素i和聚类中心Ck之间的距离。一个像素的颜色用CIELAB颜色空间L A BT来表示，其可能值的范围是已知的。像素位置的位置x yT，另一方面，可以采用值的范围，根据图像的大小而变化。简单地定义D为在实验室空间的欧氏距离，这将导致不同大小的超像素的群集行为不一致。对于大型超像素，空间距离超过颜色接近，给人以不是颜色空间接近更多的相对重要性。这将产生超像素紧凑不很好地粘附在图像边界。对于较小的超像

14、素，相反的是真实的。为了使两个距离结合成一个单一的测量，有必要通过在群集内其各自的最大距离Ns和Nc来规范化接近的颜色和邻近的空间。这样，D写成 QUOTE QUOTE QUOTE ds=(xj-xi)2+(yj-yi)2 QUOTE 预期在给定集群内的最大空间距离应该对应于采样间隔，N_S= S=（N/k）确定最大颜色距离数控不是那么简单，因为颜色距离可显著变化从集群到集群和形象的形象。可以通过数控固定常数m来避免此问题，（1）变成这简化了我们在实践中使用距离测量：通过这种方式限定D，M也让我们考虑了相似的颜色和邻近的空间之间的相对重要性。当m变大的，空间的接近更重要并且所得的超像素更紧凑（

15、即，它们具有较低的面积周长比）。当m为小，所得到的超像素图像边界附着性更紧密，但有规则的形状和大小也越少。当使用CIELAB颜色空间中，m可以是在范围1,40。等式可以通过设置来适于灰度图像它也可以扩展到处理，如图所示。通过包括深度尺寸的空间接近性术语：3.3 后期处理和其它超像素的算法一样，SLIC没有明确强制连接。在聚类程序的末尾，不属于同一连接的组件作为其聚类中心部分“孤立”像素可能仍然存在。为了校正此，这样的像素被分配到最接近的聚类中心，使用已连接的部件算法。3.4 复杂性通过聚类程序的局部化搜索，SLIC避免执行数千冗余的距离计算。在实践中，一个像素落在少于8个聚类中心的附近，这意味

16、着SLIC复杂度为 QUOTE 。与此相反，琐碎上限经典k均值算法是 QUOTE ，和实际的时间复杂度是 QUOTE ，其中I是收敛所需的迭代次数。而计划以减少的k均值复杂已经使用质数长度取样，随机抽样，本地群集交换提出的，通过设置上限和下限，这些方法是非常一般性质。 SLIC是专门针对超像素聚类的问题。最后，与大部分超像素的方法和上述的方法来加快k均值，在SLIC的复杂性是在像素的数目的直链，不考虑K值。4 与最先进算法的比较我们使用公开的源代码对SLIC算法和五个先进的超像素算法进行比较。这些算法包括GS04,3 NC05,4 TP09,5 QS09,6和提出的算法的两个版本，GCa10和

17、每个方法产生超像素分割图。4.1 边界的附着性可以说，一个超像素方法最重要的特性是它的边界附着能力。边界召回和下分割错误是坚持边界标准的措施。在图图4a和4b，SLIC，GS04，NC05，TP09，QS09和GC10使用Berkeley数据库在这些措施相比。此外，通过将图像分割成均匀的正方形而获得的基准性能被表示为“方”。伯克利数据集包含300321481的图像，和对应于各图象大约10人类注释的地面实况分割。边界召回测量了部分地面真实边缘，包括至少两个超像素边缘在内的像素。每个边界召回的方法绘制，都是为了增加超像素的数量。高边界召回表明，很少有真正的边缘被漏诊。由SLIC和GS04产生的超像

18、素显示了最好的边界召回性能。如果我们通过10这个默认值来减少SLIC的紧密度，SLIC将显示出优异于GS04的性能。欠切分错误，是另一种边界附着性的测量方法。从地面真理分割gi给定一个地区和所需的超像素组覆盖, QUOTE ,它测量了多少像素从 QUOTE “泄漏”到了 QUOTE 的边界。如果|.|在像素切割的尺寸,M是地面实况片段的数量,B表示 QUOTE 中像素的最小数值，欠分割错误表示为 QUOTE - N)在我们实验中，B被定义为 QUOTE 的5%，用来解释地面真值的歧义。如果超像素不紧密符合地面真实情况，会导致U值偏高。4.2 计算和存储效率超像素通常用来代替像素网格来帮助加速其

19、他算法。因此,在第一时间内有效的生成超像素和你重要。在一个英特尔双核2.26 GHz处理器2 GB RAM的同等条件下，我们比较各种超像素方法在增加分割图片大小时所用的时间。复杂度为 QUOTE 的SLIC是最快的超像素方法,其优势是可以增加图像的大小。除了复杂度为 QUOTE 的GS04能与SLIC一较高下,但其余方法在处理速度上与SLIC有很大的差距。同样重要的是, 为了处理大型图像，超像素算法具有较高的内存使用效率。SLIC是存储效率最高的方法,只需要N来存储每个像素到其最近的聚类中心的距离。其他方法有比较高的内存需求:GS04和GC10需要5N浮点数存储四个结点的边的权值和阈值（或者9

20、N来存储八个结点）。4.3 分割性能超像素通常用作分割算法的预处理步骤。一个好的超像素算法应该提高被使用的分割算法的性能。我们比较了MSRC上SLIC、GS04 NC05,TP09,QS09,GC10分割的数据集。这些结果使用的方法,即使用超像素计算颜色,纹理,几何形状和位置特征。然后训练分类器的21个对象类和学习CRF模型。表1中的结果显示SLIC 超像素的性能最佳。SLIC也减少了计算时间，超过NC05 500倍,该方法用于。我们还测试了2010年帕斯卡VOC数据集使用的方法。在分割精确度上，SLIC比QS09更好，并且通过数量级减少了生成超像素所花费的时间。4.4 总结除了上面讨论的属性

21、, 其他因素也应该考虑到超像素算法的质量中。其中一个要考虑的因素是易于使用。有许多复杂且不和谐参数的超像素方法会导致用时长、质量差。另一个考虑是并不是所有的方法都能提供的明确超像素数量的的能力。最后,能够控制超像素的密实度也是很重要的。紧凑且定期超像素往往是可取的,因为他们的有限的大小和几个邻居形成了更易于判断的曲线,可以提取更多的局部相关特性。然而,以密实度为代价的边界依从性和控制这种权衡的能力是有用的。下面,我们从边界的依从性、速度、内存效率,分割质量、参数调优、明确超像素数量的能力、控制超像素密实度的能力来审查每个超像素方法的性能。TP09。虽然TP09能产生一些最紧凑且持续保持一定大小

22、的超像素,但是在边界召回和欠分割错误上表现最差。TP09还运行缓慢并导致分割性能很差。NC05,这是最慢的超像素算法; 处理20481536的图像时，几乎比SLIC慢100倍,耗时800s。另外，TP09只用一个参数进行优化并能直接控制超像素的数量。NC05。相比TP09，归一划割只有一个小的改进。NC05产生的超像素比TP09更加紧凑,基于图论的应用程序使其吸引力。然而,边界的附着性很差,在边界召回方面排名第六和在欠分割错误方面排名第五。尽管如此,分割质量高得惊人。NC05的运行时间是非常缓慢的,该方法不能分割20481536图片,会发出“内存溢出”错误。GCa10 GCb10。这两种方法性

23、能类似,尽管他们的设差有异计(紧凑且强度恒定的超像素)。GCb10 产生的“紧凑”超像素比GCa10更紧凑,尽管远低于TP09 NC05。在边界召回方面,GCa10 和GCb10排名中间,分别是第五和第四。他们在欠分割错误方面持续缓慢提高(第三和第四)。尽管GCa10和GCb10速度比NC05 TP09快,但是缓慢的运行时间限制了它的效用(要求分别是235s和315s),他们是被报道出的分割性能最差的方法之一。GC10有三个参数调优,包括很难设定的补丁的大小。从积极的一面来看,GC10允许控制超像素的数量,并能产生超像素。QS09。快速转换表现出了良好的欠分割误差和边界召回能力,整体排名第二和

24、第三。然而,QS09则显示出了相对落后的分割性能,加上其他的限制，使其成为并不理想的选择。它运行时间缓慢 (181s),需要几个反直观的参数进行调优,并且不能控制超过一定数量和紧密度的超像素。最后,源代码无法确保超像素各部分完整的连接,这可能成为后续要处理的问题。GS04。尽管超像素非常不规则，它仍然能够很好的附着在图像的边界。它在边界召回中位列第一,优于SLIC算法。它是第二快的方法,分割20481536图像只需在18.19 s(没有执行参数搜索)。然而,GS04的分割性能和欠分割错误相对贫穷,可能因为它的大和不规则形状的超像素使其不适合分割方法。最后,GS04不允许超像素的数量和密实度被三

25、个输入参数控制。SLIC。这里考虑的超像素方法,SLIC显然是整体表现最好的。它是最快的方法,分割一张20481536的图片只需14.94s,并且存储效率最高。它拥有优秀的边界附着能力, 在欠分割错误方面优于所有其他方法和在边界召回方面以小的劣势仅次于GS04 (通过调整m,它排名第一)。当用于分割,SLIC显示出最佳的性能来提升MSRC和帕斯卡数据集。SLIC易于使用,其唯一参数就是被期望超像素的数量,并且是为数不多的能产生超立体像素的几个方法之前已。最后,在现有的方法中,SLIC的独特之处在于它能够通过m来控制所需的超像素密度和边界附着能力之间的平衡。4.5 更复杂的距离度量读者可能想知道

26、, 考虑了第3节中描述的简单方法，如果用更复杂的距离措施改善SLIC的性能会怎么样。我们研究了这个问题，并用自适应归一化距离测量(ASLIC)和测地线距离测量(GSLIC)替换了其距离。但令人惊讶的是，在速度、内存和边界附着性方面，在简单的距离测量中使用它，优于ASLIC和GSLIC。自适应SLIC，或称ASLIC，适应每个集群内的颜色和标准化的空间。这些常量值用于正常颜色和空间距离,所以他们可以组合成一个单一的聚类的距离测量。不使用常量值，而是从上一次迭代，ASLIC动态规范化接近每个集群使用的最大观测空间和颜色距离 QUOTE 。因此,测量的距离为和之前一样,恒定的标准化因素用于第一个迭代

27、,但后跟踪算法记录每个集群的最大距离。这种方法的优点是,超级像素密实度是一致的,且不需要设置m。这是以减少边界召回为价格的。测量距离的SLIC，或称为GSLIC，用测量的距离来代替其距离。从第一个像素 QUOTE 到另一个 QUOTE ，为定义的测量距离为定义为将 QUOTE 到 QUOTE 之间的所有路径设置为T， QUOTE 值与P有联系，给出其中 QUOTE 是CIELAB颜色向量 QUOTE 和 QUOTE 之间的欧几里得距离。这种方法的优点是保证在 QUOTE 平面上连接,不再需要后续处理步骤。然而,计算成本太高高，并且边界粘附性能受到损害。5 生物医学应用许多流行的基于图论的图像分

28、割算法，如Graph-cuts，随着加到图中的点越多，价格也越贵，但是实际上图片的大小也被限制了。对于一些应用，如从电子显微照片（EM）看线粒体分割，图像是大但是不能以降低分辨率为代价。在这种情况下，像素网格定义的曲线分割就变得棘手了。SLIC超像素显著降低了图形的复杂性，使分割易于处理。这种方法推广到3D图像栈中，它可以包含数十亿的立体像素。只有最节俭的算法可以不使用某些方法减少图的大小，并且能够操作如此庞大的数据。SLIC超像素通过超过三个数量级来降低存储器要求和复杂性，并通过常规立方体显著地提高了性能。6 结束语超像素已经成为了视觉领域的一个重要工具，在本文中，我们为读者提供了现代化的超

29、像素技术并对此进行了深入的性能分析。我们对五个最先进的算法进行了实证比较。如在预处理步骤使用分割框架时，专注于自己的边界依从性，分割速度和性能。此外，我们提出了基于K-均值聚类的SLIC算法，这个产生超像素的新方法已被证明几乎在各个方面超越已经存在的超像素方法。虽然我们的实验很周密，但还是有不周全的地方。某些超像素方法，具体地比如GC10和TP09，没有考虑彩色信息，但是其它方法做到了。这可能会在其性能产生负面影响。致谢这项工作是由美国国家竞争力中心的研究移动信息和通信系统（NCCR-MICS）、欧盟项目（ERC微纳下授权号码5005-67322）支持，部分由瑞士国家科学基金会支持。2.外文原

30、文SLIC Superpixels Compared to State-of-the-Art Superpixel MethodsAbstractComputer vision applications have come to rely increasingly on superpixels in recent years, but it is not always clear what constitutes a good superpixel algorithm. In an effort to understand the benefits and drawbacks of exist

31、ing methods, we empirically compare five state-of-the-art superpixel algorithms for their ability to adhere to image boundaries, speed, memory efficiency, and their impact on segmentation performance. We then introduce a new superpixel algorithm, simple linear iterative clustering (SLIC), which adap

32、ts a k-means clustering approach to efficiently generate superpixels. Despite its simplicity, SLIC adheres to boundaries as well as or better than previous methods. At the same time, it is faster and more memory efficient, improves segmentation performance, and is straightforward to extend to superv

33、oxel generation. Index TermsSuperpixels, segmentation, clustering, k-means.1 INTRODUCTIONSUPERPIXEL algorithms group pixels into perceptually meaningful atomic regions which can be used to replace the rigid structure of the pixel grid (Fig. 1). They capture image redundancy, provide a convenient pri

34、mitive from which to compute image features, and greatly reduce the complexity of subsequent image processing tasks. They have become key building blocks of many computer vision algorithms, such as top scoring multiclass object segmentation entries to the PASCAL VOC Challenge , depth estimation, seg

35、mentation, body model estimation, and object localization.There are many approaches to generating superpixels, each with its own advantages and drawbacks that may be better suited to a particular application. For example, if adherence to image boundaries is of paramount importance, the graph-based m

36、ethod of may be an ideal choice. However, if superpixels are to be used to build a graph, a method that produces a more regular lattice, such as, is probably a better choice. While it is difficult to define what constitutes an ideal approach for all applications, we believe the following properties

37、are generally desirable:1. Superpixels should adhere well to image boundaries.2. When used to reduce computational complexity as a preprocessing step, superpixels should be fast to compute, memory efficient, and simple to use.3. When used for segmentation purposes, superpixels should both increase t

38、he speed and improve the quality of the results.We therefore performed an empirical comparison of five stateof-the-art superpixel methods, evaluating their speed, ability to adhere to image boundaries, and impact on segmentation performance. We also provide a qualitative review of these, and other,

39、superpixel methods. Our conclusion is that no existing method is satisfactory in all regards.To address this, we propose a new superpixel algorithm: simple linear iterative clustering (SLIC), which adapts k-means clustering to generate superpixels in a manner similar to it. While strikingly simple,

40、SLIC is shown to yield state-of-the-art adherence to image boundaries on the Berkeley benchmark, and outperforms existing methods when used for segmentation on the PASCAL and MSRC data sets. Furthermore, it is faster and more memory efficient than existing methods. In addition to these quantifiable

41、benefits, SLIC is easy to use, offers flexibility in the compactness and number of the superpixels it generates, is straightforward to extend to higher dimensions, and is freely available.2 EXISTING SUPERPIXEL METHODSAlgorithms for generating superpixels can be broadly categorized as either graph-ba

42、sed or gradient ascent methods. Below, we review popular superpixel methods for each of these categories, including some that were not originally designed specifically to generate superpixels. Table 1 provides a qualitative and quantitative summary of the reviewed methods, including their relative p

43、erformance.2.1 Graph-Based AlgorithmsGraph-based approaches to superpixel generation treat each pixel as a node in a graph. Edge weights between two nodes are proportional to the similarity between neighboring pixels. Superpixels are created by minimizing a cost function defined over the graph.NC05.

44、 The Normalized cuts algorithm recursively partitions a graph of all pixels in the image using contour and texture cues, globally minimizing a cost function defined on the edges at the partition boundaries. It produces very regular, visually pleasing superpixels. However, the boundary adherence of N

45、C05 is relatively poor and it is the slowest among the methods (particularly for large images), although attempts to speed up the algorithm exist it. NC05 has a complexity of O( QUOTE ), where N is the number of pixels.GS04. Felzenszwalb and Huttenlocher propose an alternative graph-based approach t

46、hat has been applied to generate superpixels. It performs an agglomerative clustering of pixels as nodes on a graph such that each superpixel is the minimum spanning tree of the constituent pixels. GS04 adheres well to image boundaries in practice, but produces superpixels with very irregular sizes

47、and shapes. It is O( QUOTE ) complex and fast in practice. However, it does not offer an explicit control over the amount of superpixels or their compactness.SL08. Moore et al. propose a method to generate superpixels that conform to a grid by finding optimal paths, or seams, that split the image in

48、to smaller vertical or horizontal regions. Optimal paths are found using a graph cuts method similar to Seam Carving1. While the complexity of SL08 is QUOTE according to the authors, this does not account for the precomputed boundary maps, which strongly influence the quality and speed of the output

49、.GCa10 and GCb10. Veksler et al. use a global optimization approach similar to the texture synthesis work of. Superpixels are obtained by stitching together overlapping image patches such that each pixel belongs to only one of the overlapping regions. They suggest two variants of their method, one f

50、or generating compact superpixels (GCa10) and one for constantintensity superpixels (GCb10).2.2 Gradient-Ascent-Based AlgorithmsStarting from a rough initial clustering of pixels, gradient ascent methods iteratively refine the clusters until some convergence criterion is met to form superpixels.MS02

51、. mean shift, an iterative mode-seeking procedure for locating local maxima of a density function, is applied to find modes in the color or intensity feature space of an image. Pixels that converge to the same mode define the superpixels. MS02 is an older approach, producing irregularly shaped super

52、pixels of nonuniform size. It is QUOTE complex, making it relatively slow,and does not offer direct control over the amount, size, or compactness of superpixels.QS08. Quick shift also uses a mode-seeking segmentation scheme. It initializes the segmentation using a medoid shift procedure. It then mov

53、es each point in the feature space to the nearest neighbor that increases the Parzen density estimate. While it has relatively good boundary adherence, QS08 is quite slow, with an QUOTE complexity (d is a small constant). QS08 does not allow for explicit control over the size or number of superpixel

54、s. Previous works have used QS08 for object localization and motion segmentation.WS91. The watershed approach performs a gradient ascent starting from local minima to produce watersheds, lines that separate catchment basins. The resulting superpixels are often highly irregular in size and shape, and

55、 do not exhibit good boundary adherence. The approach of is relatively fast (O( QUOTE ) complexity), but does not offer control over the amount of superpixels or their compactness.TP09. The Turbopixel method progressively dilates a set of seed locations using level-set-based geometric flow. The geom

56、etric flow relies on local image gradients, aiming to regularly distribute superpixels on the image plane. Unlike WS91, TP09 superpixels are constrained to have uniform size, compactness, and boundary adherence. TP09 relies on algorithms of varying complexity, but in practice, as the authors claim,

57、has approximately QUOTE behavior. However, it is among the slowest algorithms examined and exhibits relatively poor boundary adherence.3 SLIC SUPERPIXELSWe propose a new method for generating superpixels which is faster than existing methods, more memory efficient, exhibits state-of-the-art boundary

58、 adherence, and improves the performance of segmentation algorithms. Simple linear iterative clustering is an adaptation of k-means for superpixel generation, with two important distinctions:1. The number of distance calculations in the optimization is dramatically reduced by limiting the search spa

59、ce to a region proportional to the superpixel size. This reduces the complexity to be linear in the number of pixels Nand independent of the number of superpixels k.2. A weighted distance measure combines color and spatial proximity while simultaneously providing control over the size and compactnes

60、s of the superpixels.SLIC is similar to the approach used as a preprocessing step for depth estimation described in 30, which was not fully explored in the context of superpixel generation.3.1 AlgorithmSLIC is simple to use and understand. By default, the only parameter of the algorithm is k, the de