基于局部凹凸性进行目标分割

基于局部凹凸性进行目标分割

Object Partitioning using Local Convexity

摘要

如何对场景进行适当的三维分割仍然是一个难题。

尽管目前阶段的方法持续提高基准性能，但是他们依旧变得越来越复杂

例如在合并分类器链中需要大量的人工标注的，作为一个替代的方法，我们提出一个新的高效的不需要模型和训练的方法将点云分割为物体块。该算法依据体素栅格将场景分割为毗邻的图的面片。图中的边被分类为凸的或凹的，使用对这些斑块的局部几何结构操作的简单准则的新组合。这样，图被划分为局部凸连通子图，这些子图以高精度表示对象部分。

此外，我们还提出了一种新的深度相关体素网格来处理点云中远距离点密度的下降。这改善了分割，允许使用固定参数的巨大不同的场景。该算法实现简单，无需任何训练数据，无需任何训练数据，生成的结果可与包含高级概念的分类、学习和模型拟合的最新方法相媲美。

1. introduction and State-of-the-Art

尽管已有几十年的研究，将场景分割成物体仍然是计算机视觉中最具挑战性的课题之一。为了解决这个问题，最近的方法经常使用层次结构，即创建一个从小的局部超级像素到大规模区域的自底向上的排列顺序。作为可选择的方式，研究者也严格最求自上而下的方式。首先是使用多尺度滑动窗口检测器进行粗分割[26]，后来发展到基于对象部分的细粒度分割和检测[8，6]。这两种搜索途径自然导致了一种组合自下而上的层次结构和自上而下物体和块的检测方法。尽管这些方法在复杂环境下也取得了很好的效果，但是通过数据集，使他们失去了大量的不需要学习的方法。一般来说，迄今为止最强大的方法是使用经过训练的分类筛选器进行分割[22，9]。这意味着，这些方法无法运用到没有被训练过的任意场景，对每一个测试的环境需要获取特定的数据集。

本文研究了一种不需要模型和学习的自下而上的RGB-D点云的分割。特别是，我们将重点放在将杂乱的场景划分为基本对象部分，而不需要训练数据。作为将场景分割为基本部分的一般规则的灵感，我们着力物理方面的研究，大部分体现在2D图像上，这表明凹凸性之间的过渡将指示物体之间或者物体的部分之间的分割。虽然这一特性在机器视觉中得到了一定程度的应用[10，17，20，24，11]，但成功的可能性仍然有限，最近的研究还试图将这一特性与额外的、通常是非常复杂的特征相结合，以实现良好的场景划分[20，24，11]。因此，这表明从2D直接根据传统的、几何定义的凹凸性转换是不太可能获得比较好的3D分割效果，如图2a。这种令人目瞪口呆的观察，最好用一个例子来理解。

图1a，显示了两种情况，其中一种是人们通常一致地认为是单个地物体（左边地结构），他们认为右边的部分有锯齿状的三个台阶，在这种情况下，简单的凹凸准则通常会失败，因为它会产生两个实质性的错误：一方面，它可以在整个表面奇点上绑定补丁，其中一个在图1a（蓝色框）中被去除。另一方面，它可以分离出物体和孤立的凹陷（图1A，红色条）。两个错误之间有一个自然的权衡，这使得在两种情况进行近似地分割不可能。因此，在这项研究中，我们设计了一个新的三维兼容凹分离准则，它直接解决了这两个问题，并将其与深度相关变换相结合，有助于降低RGB数据传感器的噪声和稀疏深度测量的影响。这将导致对真实场景进行非常精确的划分，这可以与几个标准基准所示的更复杂的最新方法竞争。该算法简单，易于实现，并且我们证明了所得到的分割效果可以用人类的术语理解为“对象”或“对象部分”。

本文的主要工作如下：首先，在第二节中，我们提出了我们的分割算法，并将其各个步骤可视化。在第三节我们评估我们的方法，将其与其他方法进行对比并讨论结果。最后，第4节将总结我们的发现。这一方法的源码在PCL中免费提供。

2 Methods

我们的主要目标是将场景解构为“可命名”的对象部分，而无需进行训练或分类。由于心理物理研究表明物体的最低层次分解与三维凹凸关系密切相关，我们提出了一种算法，其概述如图1所示，可以稳定识别点云中的局部凸性的区域。

2.1. Building the Surface-Patch Adjacency Graph

为了构建面片连接图，我们使用体素云连接分割VoxelCloud  Connectivity  Segmentation  (VCCS)  [18]，一种将三维点云数据分割成块的新方法，称为超体素分割（超像素的3D模拟），体素云连接分割采用K-Mean的局部区域生长变体聚类生成各自的超体素

，其中质心x ，法线n ，相邻超体素的边 e∈Ni。 体素化三维空间中的超体素保持邻接关系（具体来说，26个相邻），通过在体素网格中搜索邻接叶，在八叉树中有效地保持了超体素（和底层体素）的邻接图， 指定了octree的分辨率。该邻接图既可用于区域生长以生成超体素，也可用于确定生成的超体素本身的邻接性。超级体素是从一组种子点生长出来的，这些种子点在网格上以分辨率Rseed分布在空间中。从种子点开始的扩展由距离度量控制，这一度量是在一个特征空间中由空间距离，颜色，法向量组成。本文只对形状特征感兴趣，我们只使用空间信息，（权重Ws=1），法线信息（权重Wn=4）. 此外，我们还通过修改曲面法线的计算方式扩展了VCCS算法。有两个变化：首先，我们不使用简单的半径搜索，而是使用邻接图来决定哪些邻近点包含在正常计算中（具体来说，我们使用邻接点和邻接点的邻接点）。其次，我们使用了Boulch和Marlet的概率正态方法[5]。这两点使得法线更加明显，也使得产生的超体素具有更加明显的边缘。

2.2. Locally Convex Connected Patches (LCCP) 

局部凸连通片（LCCP）接下来我们通过分析两个超体素之间的联系是否是凸性的（valid）还是凹形的（invalid）来分割超体素近邻图。

扩展凸性准则（CC）考虑了两个毗邻的超体素，他们的质心分别在x1,x2 ,法向量分别为n1,n2 ，从曲面法线与连接它们的质心的向量之间的关系可以推断出这两个超体素之间连接是凸性的还是凹性的。

质心连线与法向量的夹角可以被计算出，对于凸性连接（convex）， （如图2a），所以有 ，其中 是单位向量。对于凹形连接同理，

这些结果是可交换的，因此 是哪一个不影响结果，只要他们在表面上 是可以被替换的。为了补偿RGB-D数据中的噪声，引入了一个偏差来处理具有非常相似法线的凹连接。

对于凸性连接，因为它们通常代表平面，具有低曲率的凹性表面会被看作是凸性连接，进而被合并到分割中，这种现象取决于曲率阈值βthresh。为了不忽略变换比较小的两个平面，为此我们使用

True代表是凸性连接，在原来的基础上又加了一个集合。（一些小小的凹陷也被认为是凸连接了）

CCb定义了基本的凸性连接，然而，由数据中的噪声引起的特征估计中的局部误差很容易传播，有可能导致分割结果的误差。这也使得识别小凹坑更加困难，因为子特征对噪声更敏感。为了改进这一点，我们最后还将邻域信息包括在边缘分类中：对凸性边缘e=(pi,pj)，我们要求pi,pj存在一个公共的邻居pj ，新邻居pc 与pi,pj 都存在凸连接。因此我们定义了扩展凸性判据CCe

按照扩展凸性的判断，需要更多的证据来表明连接是凸性连接，我们的实现基于Moosmann[16]提出的思想。在某些情况下，即使不使用这种类型的邻域信息，结果也已经令人满意。因此，在results部分中，我们将始终指示是否使用扩展凸性判断。

Sanity criterion (SC):

正如引言中在讨论表面奇异性问题时所指出的，两个超体素平面之间只有一个奇异点连接，因为它们的表面是不连续的，在这种情况下，判断两个超体素是凸或凹是没有意义的。因此，如果表面不连续，则表明存在几何边界，这意味着对应的（最初可能是凸的）连接应被识别并失效。但是如果使用上文的判断标准CCb,e来判断的话，会将这两个认为是凸的并在分割中合并，显然这是不对的。为此，我们使用连接质心的向量d和两片的法向量的叉积s=n1×n2之间的夹角v进行判断，如图所示，夹角v越接近90°，那么两个超体素的表面是连接的；v角越接近于0°，则两个超体素的表面是不连接的。因为s有两个方向，所以这里我们取v为d和s之间小于180°的哪个角度，也就是：

这里p1,p2为超体素面片。也就是说，夹角v越接近90°，那么两个超体素的表面是连接的；角越接近于0°，则两个超体素的表面是不连接的。当v值较小时，可以通过引入阈值Vthresh来处理。当v<vthresh时，应为奇异点连接，应确认无效。与上文的CC标准类似，对于具有相似法向量的超体素，该条件应该适当地放宽，以补偿传感器噪声。这里通过将法向量之间的角度带入到软化阶梯函数中完成：

其中β=(n1,n2)为两个超体素面片之间的角度，使用实验导出Vthresh_max = 60°、β= 25°和a=0.25° 。综上，设定的SC标准为

这里的有效就是这两下·；无效就是 实在太小了，法向量也补偿不了这个问题了，这两个超体素面片是不连接的。我们将凸边表示为

这样当第二个判断标准SC有效时（两个面片还是有大部分的连接的），可以根据第一个判断条件CCbe进行判断；当第二个标准无效时，就将两个超体素面片看作是不连接的、独立的，这时应对他俩进行分割。

区域增长

最后，通过区域生长划分获得的凸度图，过程如下:首先，选择和标记任意的种子超体素，然后区域 生长将种子标签传播到和它相邻的且具有凸边关系的超体素上（因为凸的认为是一个物体，进行合并），直到和相邻体素都属于凹边关系则停 止生长。然后该过程再以新的种子开始，直到所有超体素被标记。以这种方式确定所有超体素的凹凸性关系。（凸边合并，凹边分割）需要指出的是我们的标准（所有的分类结果顺序）是可以交换的，所以输出的结果与种子点的选择无关。

去噪

含有噪声的表面法线（以边界为主）将导致凸性分类错误并且将连接的表面错误地分割开来。这种噪声很小，可以在后续的处理步骤中被滤除。对每一个分割，我们检查该聚类是否包括至少n_filter个超体素。如果一个分割的尺寸不超过我们设置的滤波的阈值，就把他合并到周围最大尺寸的分割结果上。一直执行这个步骤，直到没有比n_filter更少的分割结果。在这篇文献中，我们将阈值n_filter=3 。

2.3 Depth Dependent Voxel Grid（DDVG）

截止到目前，我们已经描述了分割的主要算法。接下来，我们介绍一种普遍适用的深度变换，它改进了这种具体的分析，还可以用于各种各样的图像分析。这里我们解决了基于VCCS的体素网格的缺点.很明显，从RGBD相机观测到的结果有一个明显的缺点---点的密度的问题。因此，场景几何的细节会随着到相机的距离而迅速减少。此外，噪声会随着到相机的距离呈现二次增长，导致了几何特征的质量进一步退化。这种点密度随深度的变化，在获取小场景的细节（用小的体素voexl）和避免背景噪声之间去了一个折衷。这一问题很普遍，所有以一个固定值对从单视角获取的点云进行操作的算法都具有这个问题。

我们提出一种补偿方式，以补偿随着深度值z的增加而引起的点云密度和quantization下降的问题。我们提出一种方法，通过转换T将点转换为倾斜空间，即：

其中，

x和y坐标的除以z，反转了透视变换，平均了x-y平面上的点密度。变换坐标有助于随着深度的增加压缩点来处理深度量化的效果。显然，改变换有以下性质：

因为导数相等，局部坐标系通过变换沿所有轴均匀拉伸。这一变换的重要之处在于，小立方体在变换之后仍然是小立方体。这使得前景中的空间的几何性质基本上没有受到影响（如果voxel的大小被选的足够小），然而(while)背景中的voxel是扭曲和增长的，以补偿数据中可用的细节数量的减少。我们并不是来回变换点云，而是转换八叉树本身的存储箱(bins)，创建一个存储箱体积，可以随着深度而有效增加。如图3所示。其中

对于一个z处的一个点x,y,变换后的该深度处的两个点之间的距离比不变换的两点之间的距离缩小为原来的1/z倍。显然这样点云的密度就上去了）

3.1 Object Segmentation Database

超过两米的点被裁掉，以便于观察。所有的物体的分割线是凹面边线。可以观察到空心物体（碗、杯等）在侧面显示多个分段，因为这些凹面上曲面法线的方向变化很大，以至于被认为是不同的物体。尽管大多数物体都很简单，但是有一些对象是有意义的，比如瓶盖和杯子的把手，我们的算法可以将他们分割开来。

定性分析的表1显示了我们的方式可以和最先进的方法相媲美。和基于学习的方式对比，我们实现了更好的欠分割(Fus )的同时，也有更高的过分割值(Fos)。过分割高是因为我们有时会检测对象部分（例如手柄），并且我们没有利用模型拟合来防止噪声。注意我们的目标是将复杂的对象划分为多个部分，这与其他两种方法不同。

NYU Indoor Dataset(NYUv2)，这一数据集包括1449=795+654(training+testing),为了和其他方法对比我们选择测试集进行判断。在数据集中，物体与摄像机的距离通常很大。在这些数据中，虽然我们的分割有时是过分割的，但是我们并不认为是错误的。因为我们只使用了单一的几何信息（凹性），为了说明使用凹边界划分部分的一般思想有多好，我们将在下一节中给出具有高数据质量的复杂对象的结果。

定量结果（表2）表明，我们的算法能够在挑战者数据集上产生良好的结果。尽管我们的方法简单得多，而且不需要学习人类注释的基本真理，但是当只使用深度信息时，我们还是与文献[22]中的方法竞争。此外和基于学习的方法对比，我们仍能达到其方法的93%。我们应该强调的是，我们的竞争对手（基于学习的方法）并不是以目标的某一部件为目标，而是以“整个目标”的检测为目标，特别是那些从这个特殊的有注释的基本事实中学习到的目标。相反，我们的方法为对象性建立了一个通用规则，它不依赖于这个特定的数据集，也不依赖于特定的人类注释者的突发奇想。

使用In-tel Core i7 3.2 GHz处理器，平均每个场景的运行时间为470毫秒，95%的时间用于计算超级体素。注意，超体素可以通过GPU并行化，这将导致速度提高10倍。

3.3.Partitioning of Higher Quality Data

由于NYU数据集和OSD数据集不提供复杂对象的特写镜头，我们在图6中给出了一个定性示例，该示例显示了高质量数据的结果。很容易看出，我们的算法将图像分割成有意义的部分，尽管我们还没有了解组成部分的内容。特别是，很明显，我们的算法将对象划分为容易“命名”的部分。我们应该强调的是，图5a-C和图6中的部分是使用具有相同固定参数的深度相关体素网格创建的。这表明了我们的算法在无需参数调整的情况下对不同内容的适用性.

4. Conclusion

在这项工作中，我们提出并评估了一种在3D点云上运行的新颖的，无需模型和学习的自底向上的分割算法。尽管我们的算法旨在对对象进行分割，但我们在两个著名的基准测试中获得了最新的结果：对象细分数据库和纽约大学室内数据集。后者之所以特别有趣，有两个原因：首先，所有已发布的结果都需要学习（需要带注释的地面真相）以及颜色信息。相反，我们的方法是第一个不需要这两个信息的已发布算法。其次，地面真相将场景任意划分为“完整”的对象，因此将对象分割为它们的各个部分将降低总体得分。尽管如此，我们还是得到了与最先进水平相当的结果。无需学习的方法具有多种优点，其中最重要的就是不需要创建新的训练数据和附带注释的真实图像。这不仅意味着该方法可以作为自动引导过程的第一步直接应用，还可以用于任意未知场景（通过依赖深度的相关网格实现）或由新设备（如Kinect 2.0或激光扫描仪）获取的场景。

关于我们

目前微信交流群不断壮大，由于人数太多，目前有两个群，为了鼓励大家分享，我们希望大家能在学习的同时积极分享，将您的问题或者小总结投稿发到群主邮箱主邮箱[e-mail]。