快速计算内容敏感的超像素和超体素的方法

37700使用q距离快速计算内容敏感的超像素和超体素0叶子鹏1*，易然1*，于敏静2†，刘永进1†，何颖301 清华大学 2 天津大学 3 南洋理工大学0摘要0许多计算机视觉任务受益于超像素/超体素，它们可以有效地降低输入图像和视频的复杂性。为了计算内容敏感的超像素/超体素，最近的方法将输入图像或视频表示为低维流形，并在其上计算测地线重心沃罗诺伊镶嵌（GCVT）。尽管它们可以产生高质量的结果，但由于频繁查询计算代价高昂的测地距离，这些方法速度较慢。在本文中，我们提出了一种新的方法，不仅可以计算出质量优于现有技术的超像素，而且在基准数据集上运行速度比现有方法快6-8倍。我们的方法基于一种快速的基于队列的图距离（称为q距离），适用于图像和视频。它具有最优的近似比O（1）和线性时间复杂度O（N），适用于N像素图像或N体素视频。对五个图像数据集上的31种超像素方法和四个视频数据集上的8种超体素方法进行了全面评估，结果表明我们的方法提供了一种全能解决方案，并在各种指标下始终表现良好。我们还展示了我们的方法在最优图像和视频闭包以及前景传播应用中的效果。01. 引言0超像素将相似的像素分组成原子区域，可以有效地捕捉图像中的低级特征。类似地，超体素是视频中有意义的原子区域。通过用适量数量的超像素/超体素（在本文中统称为超原子）替换大量的像素/体素，可以大大降低许多计算机视觉算法的复杂性，例如显著性检测[19]、前景分割[22]、3D重建[4]和场景理解[18]等。作为图像/视频中的特殊过分割，超像素/超体素（简称超原子）可以有效地减少输入图像和视频的复杂性。0* 共同第一作者 †通讯作者0超原子应该反映“自然规律”，以便在感知上有意义[35]。一些常用的标准包括：（1）紧凑性：超原子的形状是规则的，因此超原子之间的邻近关系也是规则的；（2）连通性：每个超原子都是简单连通的；（3）高性能：超原子能够很好地保留图像/视频边界，并且计算速度快、内存效率高且可扩展；（4）简洁性：高性能是通过尽可能少的超原子实现的；（5）易用性：用户只需指定超原子的数量，无需调整其他参数。01.1. 相关工作0已经提出了大量的超原子生成方法，它们可以广泛地分为两类：（1）传统方法，具有人工设计的特征；（2）基于深度学习的方法。第一类方法中应用了多种策略，例如图分割[14]，聚类[1]，轮廓演化[23]，基于格点的能量优化[11]，以及其他分层、生成和统计方法[39,45]。第二类方法的典型代表是最近的两项工作[40,21]。然而，目前不存在的方法能够满足所有上述标准。一些最近的方法[6,25,26,41,46]侧重于简洁原则，并计算内容敏感的超原子（CSS），即在内容密集区域（强度、颜色或运动变化较大的区域）中较小，在内容稀疏区域中较大，因此在所有其他标准之间提供了良好的平衡（参见图1和图2）。在现有的CSS方法中，最近的两种方法[26,46]（在第2节中总结）将输入图像和视频建模为嵌入在高维特征空间中的低维流形，然后通过计算均匀的镶嵌（例如，测地线重心沃罗诺伊镶嵌）来生成CSS。尽管GCVT可以产生高质量的CSS，但计算它是耗时的，因为测地距离的计算代价很高。01.如果一个区域是单连通的，那么在该区域内的任何简单闭合曲线/曲面都可以连续收缩到一个点而不离开该区域。�������� ���������������������������������������� ������� ������� ����� �������M��������� � M����������������������������M����������������37710����������� ������ ��������������������������������������������������������������������������������������������������������������������������������������������������������������������������������0图1. 我们的方法与8种代表性超像素方法的视觉比较：TurboPixels [23]、SEEDS [11]、ETPS [45]、SLIC [1]、MSLIC [25]、IMSLIC[26]、SEAL [40]、SSN[21]和我们的方法。用户指定了300个超像素，生成的实际超像素数量在括号中。只有IMSLIC、SEAL和我们的方法可以精确控制超像素的数量，但我们的方法比IMSLIC快6-8倍，比SEAL快4-5倍。我们的方法在欠分割误差、边界召回率和紧凑性方面表现良好，并适用于图像和视频。详见第5节。0图2. 通过GB [14]、GBH [17]、SWA [32, 33, 10]、MeanShift [29]、TSP [7]、Yi-CSS[46]和我们的方法计算的超体素的视觉比较。所有方法都生成了大约1,000个超体素。我们的方法在四个视频数据集上的UE3D、BRD、SA3D和CO方面的结果优于其他方法。01.2. 我们的贡献0在本文中，我们提出了一种用于计算精确GCVT的新方法，其运行速度比最先进的GCVT方法[26]快6-8倍。我们的方法具有经过验证的线性时间复杂度，即对于N像素图像或N体素视频，其为O(N)，并且可以保证最优逼近比O(1)。我们在五个图像数据集上评估了31种超像素方法，在四个视频数据集上评估了8种超体素方法，并在包括最优图像和视频闭包[22]以及视频前景传播[20]在内的应用中对它们进行了测试。结果表明，我们的方法提供了一个全能的解决方案，并在各种指标下始终表现良好。02. 前提条件0我们的方法基于图像和视频流形以及K-means++，以下简要总结。02.1. 图像流形M20MSLIC和IMSLIC [25, 26]都采用了一个嵌入映射Φ，将彩色图像I映射到一个2维流形M2 �R3。0Φ(r, s) � (r, s, λ1l, λ1a, λ1b), (1)0其中(r, s)是空间坐标，(l, a,b)是CIELAB颜色空间中的像素颜色，λ1是一个常数。0图3. MSLIC和IMSLIC。 (a) 这两种方法将像素p(r, s)(红点)表示为一个单位正方形(黄色区域)，其角点(绿点)是其相邻像素的中心。方程(1)中的拉伸映射Φ将彩色图像I映射到曲面2维流形M2 � R5，其面积元素是图像内容的良好度量。(b)为了便于可视化，我们以灰度图像为例，将其映射到一个3D曲面M2 � R3。(c) MSLIC [25]和IMSLIC[26]都在M2上计算出一个规则的镶嵌T(T中的单元格通过颜色区分)。逆映射Φ^(-1)(T)在I上引入了内容敏感的超像素。0如[25]中所示，RGBD图像可以被映射到一个M2 � R6，其中(r, s,λ1l, λ1a, λ1b,λ2d)，其中d是深度。如图3所示，映射Φ拉伸内容密集的区域。(r+1, s�1, t�1)(r�1, s�1, t�1)(r+1, s�1, t�1)(r+1, s�1, t�1)(r�1, s�1, t�1)(r+1, s�1, t�1)(r�1, s�1, t�1)a1a4a2a3a5a6a7a8�� � R3M3 = �(�) � R6�(a1)�(a4)�(a2)�(a3)�(a5)�(a6)�(a7)�(a8)̸̸minz∈Mζ�37720v0图4. Yi-CSS [46]通过Φ：Φ→M3 �R6，将视频Ξ中的体素v（r，s，t）（即中间的红色框）映射到弯曲的3维流形M3。体素框的每个角ai是其八个周围体素的中心。0（内容稀疏）区域在I中转化为M上的大（小）区域。然后，M2上的均匀镶嵌通过逆映射Φ-1在I中产生高质量的CSS。02.2. 视频流形M30Yi-CSS [46]将体素v(r, s,t)的视频剪辑Ξ映射到嵌入在R6中的3维流形M3（图4）0Φ(r, s, t) � (r, s, λ1t, λ2l, λ2a, λ2b) (2)0其中（r，s）是像素坐标，t是帧索引，（l，a，b）是CIELAB颜色空间中的像素颜色，λ1和λ2是两个常数。Yi等人[46]表明，类似于图像的2维流形M2，均匀镶嵌的逆映射Φ-1在Ξ中产生良好的CSS。02.3. K-means++0给定具有度量D(x, y)的实数度量空间X中的N个点X ={xi}Ni=1，数据聚类技术通过在X中选择K个聚类中心{cj}Kj=1来最小化以下潜在函数：0E � {cj}Kj=1 � 0i=1 min j=1, 2, ∙∙∙ ,K Dl(xi, cj) (3)0其中指数l ∈Z+是一个问题参数。中心{ci}Ki=1将点集X划分为K个簇，每个簇都是X中满足Dl(xs, ci) ≤ Dl(xs, cj)，i ≠j的子集Xi。特别地，当l =2且D是欧氏度量时，它被称为K-means问题[13]。K-means++算法迭代地选择聚类中心[3]。一开始，它从X中随机选择一个中心c1。在每个后续的步骤i，1 < i ≤K，一个新的聚类中心从X\{cj}i−1j=1中的点xs ∈ X以与minc ∈{cj}i−1j=1 Dl(xs, c)成比例的概率随机选择。0给定一个固定的K，令{coptj}Kj=1是最小化潜在函数（3）的（未知的）最优中心。如果对于任何{cj}Kj=1，算法具有近似比α，则称该算法具有近似比α。已经证明0从该算法的输出，E({cj}kj=10E({coptj}kj=1) ≤ α。0在[42]中证明，对于任意的常数因子β >1，通过K-means++算法选择βk个聚类中心可以期望获得O(1)的近似解。03.我们方法的概述0最先进的CSS工作[26,46]将输入图像或视频映射到嵌入在Rd中的ζ维流形Mζ，其中ζ = 2, 3, ζ  va.dist + l(va,vb)，则9：vb.dist = va.dist + l(va, vb)10：vb.pre =va11：结束如果012：如果vb.visit ==FALSE，则13：将vb插入队列Q的尾部。014：设置vb.visit =TRUE。15：结束如果16：结束对17：结束当018：对于V \C中的每个顶点v，输出q距离v.dist；19：（可选）对于V \C中的每个顶点v，通过回溯前置节点从v开始，直到达到C中的一个源，输出q路径。0图5（c）说明了q路径�c1vf上三个顶点vi，vj和vf的三个可允许区域Ω(vi)，Ω(vj)和Ω(vf)。0性质3. 对于任意c ∈ C，v ∈ V \ C和G上c到v的最短路径cv= {vIj1 = c, vIj2, ∙∙∙, vIjn′ =v}，从算法2输出的q路径�cv恰好是最短路径cv，当且仅当对于任意i，1 ≤ i ≤n′，路径cvIi的子路径包含在vi的可允许区域中。0根据性质2，如果在算法2的第8-10步中，由于Φ(vb).dist >Φ(va).dist + l(va,vb)而更新了q-距离值Φ(vb).dist，并且索引b 

下载后可阅读完整内容，剩余1页未读，立即下载