SLIC超像素分割算法和目前超像素算法的比较

IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.34,NO.11,NOVEMBERIEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,VOL.34,NO.11,NOVEMBER2012PublishedbytheIEEEComputerSocietyPublishedbytheIEEEComputerSocietySLIC超像素分割算法和目前

超像素算法的比较RadhakrishnaAchanta,IEEE专业会员，

AppuShaji,KevinSmith,IEEE专业会员，

AurelienLucchi,PascalFua,IEEE会士，

andSabineSusstrunk,

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

次迭代已经足够。最后，后处理步骤通过再分配解体像素像素强制性使其与周围超像素进行联通。整个算法总结在算法1。算法1.SLIC超像素分割/*初始化*/通过常规网格步骤S中采样像素初始化聚类中心。=[l,a,b,x,y]T。kkkkkk将聚类中心移动到3x3矩阵最小梯度位置。为每一个像素i定义标签l(i)=-1。为每一个像素i定义距离d(i)=8。repeat/*分配*/for每个聚类中心。dokfor每个C周围2sx2s区域k的像素ido计算。和i之间的距离kifDvd⑴then设置d(i)=D设置l(i)=kendifendforendfor/*更新*/计算新的聚类中心。计算残留误差E。untilE＜临界值SLIC超像素符合labxy彩色图像平面空间的聚类。这呈现在确定距离度量D，其可能不会立即明显的问题。在算法1中D是像素Ci和聚类中心匕的距离。像素的颜色被由CIELAB颜色空间[l,a,b]T表示，其可能值范围已知。另一方面，像素的位置[x,y]T可以采取一系列随图像大小变化而变化的值。简单地定义D作为labxy空间的5D欧氏距离，这将导致不同大小超像素的聚类行为的矛盾。对于大型超像素，空间距离比颜色近似度更为重要，空间近似度相对颜色更为重要。这将产生边缘吻合度不佳的紧凑超像素。对于较小的超像素，反过来也是如此。将两个距离进行一次测量，有必要通过颜色NN和空间到聚类各自的最大距离N和Nc对颜色近似度和空间近似度进行规范化。为此，D'被写作4—J冉厂卜出「片)‘十四一b1f:=一修了~«出一玷「， (p|小陶葡一个给定聚类间的最大空间距离应该与采N=S=j(NK)样间隔对应，s 。由于颜色距离会随着聚类到聚类、图像到图像二变N化，因此确定最大颜色距离Nc并不如此简N单。这个问题可以通过将c固定为常量m3.2距离计算 在实际中可以简化为3.2距离计算 在实际中可以简化为(a)标准k-means搜 (b)SLIC搜索局索全部图像 部区域图2.减少超像素搜索区域通过以这种方式定义D,m也允许我们衡量颜色相似度和空间接近度。当m很大时，空间接近度更为重要,所得到的超像素更加紧凑(即,它们具有更小的周长比范围)。当m较小时，所得到的超像素边缘吻合度更高,但具有较少的常规尺寸和形状。当使用CIELAB颜色空间时，m取值为［1,40］。在灰度图像中方程(3)可以被改写为它也可以扩展到处理3D超体素，如图3所示,用深度和空间接近度改写方程(3)：后处理像其他一些超像素算法［8］一样，SLIC没有明确强制连接性。在聚类过程的结尾，一些不像聚类中心那样属于相同链接节点的“孤儿”像素依然存在。为了校正，这样的像素利用连接节点算法被分配的最近的聚类中心。复杂度通过聚类程序的局域化搜索，SLIC避免上千次冗余的的距离计算。在实践中,一个像素落在少于8个聚类中心的附近,这意味着SLIC的复杂度为O(N)。与此相反，经典k-means算法的琐碎上届是O(kN)口7］，实际的时间复杂度O(NkI)［6］，其中I是收敛所图3.SLIC超体素计算了一个视频序列4与基于图形的方法的比较我们将SLIC和五种代码开元的基于图像的算法进行定量比较。这些算法包括GS04,3NC05,4TP09,5QS09,6和两个［26］中提出的算法版本GCa10和GCb10.图3.SLIC超体素计算了一个视频序列4与基于图形的方法的比较我们将SLIC和五种代码开元的基于图像的算法进行定量比较。这些算法包括GS04,3NC05,4TP09,5QS09,6和两个［26］中提出的算法版本GCa10和GCb10.7图7为各种方法产生超像素分割的结果。4.1边缘吻合度可证明，超像素算法中最重要的特性是边缘吻合度。边界召回和欠分割误差是边界吻合度的标准规范［15］，［26］。图4a和4b是SLIC，GS04,NC05,TP09,QS09和GC10在伯克利数据库［20］下的比较。此外，通过将图像分割成均匀的正方形得到基线效率。伯克利数据集包含300个321x481的图像，以及对应于每个图像大约10人类注释的地面实况分割。部分地面真实边缘的边界召回方法至少衰落了两个超像素边缘的像素。图4a所示为超像素数量增加时各种方法的边界召回性能比较。高边界召回表明，很少有真正的边缘被错过。由SLIC和GS04产生的超像素边界召回性能最好。如果我们从缺省值10开始减少SLIC的紧密度m，SLIC显示出比GS04优异的性能。GHz处理器的硬件条件下所需的处理时间。SLIC，以其0(N)的复杂度，是最快的超像素算法，它的优势随着图像大小的增加而更加显著。复杂度为0(N)logN的GS04是竞争性的，其余的方法显示在处理速度上存在显著间隙。图4b所示的欠分割误差是边界吻合度的另一种衡量方法。从地面实况分割g开始的给i定区域给定的区域以及需要覆盖的超像素点集sispg计算了从漏洞$开始直到jji j边界g有多少像素。如果g是像素分割的i大小，那么M就是地面实况分割的数量，而B是s和g图4b所示的欠分割误差是边界吻合度的另一种衡量方法。从地面实况分割g开始的给i定区域给定的区域以及需要覆盖的超像素点集sispg计算了从漏洞$开始直到jji j边界g有多少像素。如果g是像素分割的i大小，那么M就是地面实况分割的数量，而B是s和g重叠的像素的最小数量，欠ji分割误差表示为u= EhlVv- ⑶B在本实验中设置为5%,以补偿地面实况歧义。当U的值很大时，超像素不能完全适合地面实况结果。0.0..Q0.0.0.口Number(a)边界召回+GSU4*TP09-•QSQ9'，GCalOGCbia£quapes■--GSUG-*-ASLiCEg 1000IMO2000Nurtiaftrd\帛Lip^rpi左母1日4.2计算和存储效率超像素经常被用来代替像素网格以帮助加快其他算法。因此，超像素可以被预先高效生成是很重要的。图4c中，我们比较各种分割方法在2GBRAM的Intel双核2.26(b)欠分割误差13080ao4020(c)分割速度■心S加,TP%qOS加■13080ao4020(c)分割速度GCalO

GCt)10SUC,图4.边界吻合度和分割速度原始图像地面实况SLIC超像素分割图5.多级分割4.3分割性能超像素通常用作在分割算法的预处理步骤。一个好的超像素算法应该能够改善分割算法的性能。我们在MSRC数据集［24］上比较了SLIC，GS04,NC05,TP09,QS09和GC10的分割性能。利用［11］的方法可以得到这些结果，即用超像素来计算颜色，纹理，形状，和位置特征。然后，训练21个对象类的分类并且学习CRF模式。表1为结果，表明SLIC超像素产生最佳性能。SLIC利用［11］中提到的通过超过500以上NC05的方法减少了计算时间。图5是举例示范使用SLIC使用SLIC分割图像。利用［10］中提到的方法我们也对PASCAL2010数据集［7］进行了测试。如表2所示，SLIC提升了QS09的分割精确度，减少生成固定大小的超像素花费的时间。4.4讨论4.4讨论TP09.虽然TP09产生了一些最紧凑和尺寸一致的超像素，但它是所有方法中在边界召回和欠分割误差方面都是最差的。TP09处理速度慢，并导致穷分割性能。而NC05,它是最慢的超像素算法;处理2048x1536的图像需要800s，几乎比SLIC慢100倍。另一方面，TP09只有一个参数来调整，并提供直接控制超像素的数量。NC05.标准化切割结果只比TP09有一些小的改进。由NC05产生的超像素甚至比那些TP09的更紧凑，这使得它们对于基于图像处理的应用具有吸引力。然而，边缘吻合度非常差，边界召回排名第五欠分割误差排名第六。尽管如此，分割质量高得惊人。NC05的运行时间非常慢，该方法无法分割2048x1536的图像，从而产生“内存不足”

的报错。GCa10和GCb10.这两种方法表明，尽管它们在设计上的差异相似的性能（相对紧凑恒定强度超像素）。GCb10的“紧凑型”超像素比GCa10更加紧凑，虽然比TP09和NC05要少得多。在边界召回方面，GCalO和GCblO排在中游，分别为第五和第四。他们的欠分割误差在中游（第三和第四）。虽然GCalO和GCblO比NC05和TP09更快，它们的运行速度依旧限制了它们的可用性（分别需要235s和315s），这是它们分割性能最差的表现之一。GC10有三个参数来调整，包括贴片尺寸，这可能是难以设置。从积极的方面，GC10允许超像素数量的控制，并能产生超体素。QS09.快速漂移的欠分割误差和边界召回整体方面表现不错，排名分别为第二和第三。然而，QS09显示分割性能相对较差，和其他限制使它低于理想选择。它处理时间缓慢（181s）,需要几个不直观的参数进行调整，并没有提供过量或超像素的密实度控制。最后，在源代码失败，以确保超像素是完全连接的组件，它可以是有问题的后续处理。GS04.虽然超像素是非常不规则，边界吻合度很好。它的边界召回排名第一，略胜SLIC一筹。分割2048x1536图像用时18.19s,是第二个最快速的方法（不进行参数搜索）。然而，GS04显示相对差的分割性能和欠分割错误，可能是因为它的大的，不规则形状的超像素不适应分割的方法，如Ui］。最后，GS04不允许其三个输入参数来控制超像素或紧凑的数量。SLIC.在这里考虑的超像素方法，SLIC显然是最佳的整体表演。这是最快的方法，分割2048x1536图像用时14.94秒，内存效率也是最高的。它的边界吻合度很高，在欠分割误差方面胜过其他所有方法，并且在边界召回方面仅次于GS04（通过调整m时，排名第一）。当用于分割，SLIC显示，在MSRC和PASCAL数据集性能最好的提升。SLIC使用简单，它的唯一参数是期望超像素的数量，并且它是为数不多的方法生产超体素之一。最后，在现有的方法中，SLIC是在其控制超像素紧凑，如果需要，通过m界线坚持之间的权衡的独特能力。吃£g7…”h”J世二&做如也贴划甘胤茹玷脂匐丸笈胞心如由anW窗」!/坦耐费In贴”艰源对划n叫JU那表2PASCALVOC2010数据集下的多级对象分割-SSW金当4«5IV.5 1 25J3.5 4 43FakuPwilrK&Rale-SSW金当4«5IV.5 1 25J3.5 4 43FakuPwilrK&Rale(%)4.5更复杂的距离计算读者可能会问，如果更复杂的距离的措施提

高SLIC的表现，考虑在第3节所描述的方法的简单起见，我们通过更换距离研究这个问题(3)与自适应归一化距离度量(ASLIC)和测地距离度量(GSLIC)o令人惊讶的是,在(3)中使用的简单的距离度量在速度，存储器，和边界吻合度方面优于ASLIC和GSLICo图7.通过各种方法产生的超像素的对比色彩的距离(m,m)。因此，该距离测量变sc为自适应图7.通过各种方法产生的超像素的对比色彩的距离(m,m)。因此，该距离测量变sc为和以前一样，常数规一化因子是用于第一迭代中，但该算法随后跟踪的最大距离为每个聚类。这种方法的优点是，超像素致密性更加一致，并且它是从未必要设置m。图4a所示是以降低的边界召回性能。短程线和以前一样，常数规一化因子是用于第一迭代中，但该算法随后跟踪的最大距离为每个聚类。这种方法的优点是，超像素致密性更加一致，并且它是从未必要设置m。图4a所示是以降低的边界召回性能。短程线-SLIC或GSLIC，取代的(3)与一个测地距离的距离。无符号的测地距离从一个像素I(P)到另一个I(P)被定义为

ij冢通)【也))=9闻由1 ⑺r是i(p)和i(p)之间的所有路径集，ijd(P)是相关联的路径P的花销，由下式给出出力=£||18)_1他_川|, (8)0其中||I(p)-1(p)||是像素p和p在i i-1 i i-1CIELAB颜色矢量之间的欧氏距离。这种方法具有在xy平面上的连接得到保证，省去了后处理步骤的优点。然而，计算成本较高和边界粘附性能会受到影响，如图4a所示。生物医学应用许多流行的基于图的分割的方法，例如图像切割［3］变得越来越昂贵，因为更多节点被添加到该图中，限制图像尺寸在实践中。对于一些应用，如从电子显微照片(EM)的线粒体分割，图像是大而降低分辨率不是一个选项。在这种情况下，分段上定义在像素网格的曲线图将是棘手的。在［18］中，SLIC超像素显著降低的图形的复杂性，使得分割易于处理。图6a和6b是线粒体［18］分段。在［19］中，这种方法推广到3D图像栈，它可以包含数十亿的超体素。只有最节俭的算法在不降低以某种方式的曲线图的尺寸，大容量的数据上都可以操作。SLIC超体素降低对存储器的要求和复杂性通过幅度超过三个数量级，并显著提高了性能比常规的立方体，如图6c，6d和6e所示。结论超像素已经成为一个不可或缺的工具到社区的愿景，并在本文中，我们为读者提供了现代超像素技术进行了深入的性能分析。我们进行的国家的最先进的五个算法进行了实证比较，作为一个分割的框架预处理步骤使用时，专注于自己的边界坚持，分割速度和性能。止匕外，我们提出了一种基于k-means聚类的SLIC算法，这已被证明优于现有的超像素方法在几乎每个方面产生超像素的新方法。虽然我们的实验是彻底的，他们提出一个警告。具体来说,某些超像素的方法比如GC10和TP09,它们不处理彩色信息这可能会对其性能产生不利影响。致谢这项工作是由受瑞士国家科学基金会支持的国家竞争力中心研究移动信息和通信系统(NCCR-MICS)支持，下批号码5005-67322，部分由欧盟对外关系与合作项目微纳中心支持。参考文献S.AvidanandA.Shamir,“SeamCarvingforContent-AwareImageResizing,”ACMTrans.Graphics,vol.26,no.3,Article10,2007.A.AyvaciandS.Soatto,“MotionSegmentationwithOcclusionsontheSuperpixelGraph,”Proc.WorkshopDynamicalVision,Oct.2009.Y.BoykovandM.Jolly,“InteractiveGraphCutsforOptimalBoundaryandRegionSegmentationofObjectsinN-DImages,”Proc.IEEEInt’lConf.ComputerVision,2001.D.ComaniciuandP.Meer,“MeanShift:ARobustApproachtowardFeatureSpaceAnalysis,”IEEETrans.PatternAnalysisandMachineIntelligence,vol.24,no.5,pp.603-619,May2002.T.Cour,F.Benezit,andJ.Shi,“SpectralSegmentationwithMultiscaleGraphDecomposition,”Proc.IEEEConf.ComputerVisionandPatternRecognition,2005.C.Elkan,“UsingtheTriangleInequalitytoAccelerateK-Means,”Proc.Int’lConf.MachineLearning,2003.M.Everingham,L.VanGool,C.K.I.Williams,J.Winn,andA.Zisserman,“ThePASCALVisualObjectClassesChallenge,”Int’lJ.ComputerVision,vol.88,no.2,pp.303-338,June2010.P.FelzenszwalbandD.Huttenlocher,“EfficientGraph-BasedImageSegmentation,”Int’lJ.ComputerVision,vol.59,no.2,pp.167-181,Sept.2004.B.Fulkerson,A.Vedaldi,andS.Soatto,“ClassSegmentationandObjectLocalizationwithSuperpixelNeighborhoods,”Proc.IEEEInt’lConf.ComputerVision,2009.J.M.Gonfaus,X.Boix,J.Weijer,A.Bagdanov,J.Serrat,andJ.Gonzalez,“HarmonyPotentialsforJointClassificationandSegmentation”Proc.IEEEConf.ComputerVisionandPatternRecognition,2010.S.Gould,J.Rodgers,D.Cohen,G.Elidan,andD.Koller,“Multi-ClassSegmentationwithRelativeLocationPrior,”Int’lJ.ComputerVision,vol.80,no.3,pp.300-316,2008.T.Kanungo,D.M.Mount,N.S.Netanyahu,C.D.Piatko,R.Silverman,andA.Y.Wu,“ALocalSearchApproximationAlgorithmforK-MeansClustering,”Proc.18thAnn.Symp.ComputationalGeometry,pp.10-18,2002.A.Kumar,Y.Sabharwal,andS.Sen,“ASimpleLinearTime(1+e)-ApproximationAlgorithmforK-MeansClusteringinAnyDimensions,”Proc.Ann.IEEESymp.FoundationsofComputerScience,pp.454-462,2004.V.Kwatra,A.Schodl,I.Essa,G.Turk,andA.Bobick,“GraphcutTextures:ImageandVideoSynthesisUsingGraphCuts,”ACMTrans.Graphics,vol.22,no.3,pp.277-286,July2003.A.Levinshtein,A.Stere,K.Kutulakos,D.Fleet,S.Dickinson,andK.Siddiqi,“Turbopixels:FastSuperpixelsUsingGeometricFlows,”IEEETrans.PatternAnalysisandMachineIntelligence,vol.31,no.12,pp.2290-2297,Dec.2009.Y.Li,J.Sun,C.-K.Tang,andH.-Y.Shum,“LazySnapping,”ACMTrans.Graphics,vol.23,no.3,pp.303-308,2004.S.P.Lloyd,“LeastSquaresQuantizationinPCM,”IEEETrans.InformationTheory,vol.28,no.2,pp.129-137,Mar.1982.A.Lucchi,K.Smith,R.Achanta,V.Lepetit,andP.Fua,“AFullyAutomatedApproachtoSegmentationofIrregularlyShapedCellularStructuresinEMImages,”Proc.Int’lConf.MedicalImageComputingandComputerAssistedIntervention,2010.A.Lucchi,K.Smith,R.Achanta,G.Knott,andP.Fua,“Supervoxel-BasedSegmentationofMitochondriainEMImageStackswithLearnedShapeFeatures,”IEEETrans.MedicalImaging,vol.30,no.11,pp.474-486,Feb.2011.D.Martin,C.Fowlkes,D.Tal,andJ.Malik,“ADatabaseofHumanSegmentedNaturalImagesandItsApplicationtoEvaluatingSegmentationAlgorithmsandMeasuringEcologicalStatistics,”Proc.IEEEInt’lConf.ComputerVision,July2001.A.Moore,S.Prince,J.Warrell,U.Mohammed,