Learning to Sample

摘要

处理大型点云是一项具有挑战性的任务。因此，数据通常被抽样到一个可以更容易处理的大小。问题是如何对数据进行采样？一个流行的采样技术是最远点采样（FPS）。然而，FPS与下游应用（分类、检索等）是无关的。其基本假设似乎是，最小化最远点距离，如FPS所做的，是其他目标函数的一个很好的代理。

我们表明，最好是学习如何采样。为了做到这一点，我们提出了一个深度网络来简化三维点云。该网络被称为S-NET，它接收一个点云并产生一个较小的点云，该点云为一个特定的任务而优化。简化后的点云不能保证是原始点云的一个子集。因此，我们在后处理步骤中将其与原始点的一个子集相匹配。我们通过在两个标准数据集上的实验，将我们的方法与FPS进行了对比，并在各种应用中显示了明显更好的结果。我们的代码是公开可用的1

1. 引言

近年来，捕获三维数据越来越容易，网上有越来越多的三维形状库。这些数据可以用各种方式表示，包括点云、多视图图像和体素网格。点云只包含关于三维物体表面的信息，而基于网格的表示方法也包含关于自由空间的数据，这使得前者的效率更高。然而，处理点云可能是一个挑战，因为它可能包含大量的数据点。减少点的数量在很多方面都是有益的，比如减少功耗、计算成本和通信负载等等。

一种减少数据负载的天真方法是随机抽取一个点的子集。另一种在文献中常用的方法是最远点取样（FPS）[27, 28, 21]。这种抽样方法考虑到了点云的结构，并选择了一组相互之间距离最远的点[6, 24]。这些抽样方法，以及文献中的其他方法[3, 18]，都是按照非学习的预定规则来操作的。

在过去的几年里，深度学习技术已经被成功地应用于点云数据。在各种应用中，人们可以发现点云分类[27, 28, 21, 42, 30, 36]、部分分割[27, 28, 21, 30, 36, 20]、语义分割[27, 21, 36, 34, 32, 12]和检索[35, 17]。其他技术进行点云自动编码[1, 38, 8]、生成[1, 33, 19]、完成[1, 2, 41]和向上采样[40, 39, 43]。然而，一个学习点云的采样方法，受制于后续的任务目标，以前还没有被提出。

我们提出了一个简化网络，称为S-NET，它是基于PointNet[27]的结构。S-NET学习生成一个较小的（简化的）点云，为下游任务（如分类、检索或重建）进行优化。

简化的点云必须平衡两个相互冲突的约束。一方面，我们希望它能保持与原始形状的相似性。另一方面，我们希望将其优化到后续任务中。我们通过训练网络以生成一组满足两个目标的点来解决这个问题：采样损失和任务损失。采样损失促使生成的点接近输入点云。任务损失确保这些点对任务来说是最佳的。

FPS的一个优点是它对原始点的一个子集进行采样。相反，S-NET产生的简化点云不能保证是输入点云的一个子集。为了解决这个问题，我们在推理时进行了一个后处理步骤，将生成的点与输入点云相匹配，并得到它的一个子集，也就是一组采样点（见图1）。实验表明，与FPS相比，使用我们的采样点可以在几个任务中取得更好的结果。

图1. 拟议的学习采样方法的图示。在训练阶段，S-NET产生的点被传递给一个任务网络，该网络被预先训练并保持固定。最小化目标包含任务的损失和采样损失。后者作为一个正则器，鼓励输入点和生成点之间的接近性。在推理时，我们将S-NET生成的点与输入点云相匹配，并得到其中的一个子集。然后只有这些点被送入任务网络进行性能评估。

我们的方法可以被认为是一种特征选择机制[9, 16]。每个点都是底层形状的一个特征，我们试图选择对任务贡献最大的点。它也可以被解释为一种视觉注意力的形式[22, 14]，将后续的任务网络集中在重要的点上。

S-NET的训练是为了输出一个固定的样本大小，这意味着我们需要为每个目标大小训练一个不同的S-NET。为了克服这个限制，我们引入了一个S-NET的扩展，称为ProgressiveNet。渐进式网络根据任务的重要性对各点进行排序。这使得在推理时可以选择样本大小，允许根据要求和可用资源进行动态的细节管理。

建议的抽样方法被应用于三个不同的任务：点云分类、检索和重建。我们将我们的方法与常见的非数据驱动方法进行了比较：随机抽样和FPS。在第一个任务中，我们显示了更好的分类精度；在第二个任务中，我们显示了更好的检索结果；在最后一个任务中，我们得到了更低的重建误差。总而言之，我们的主要贡献是。

- 一种特定任务的数据驱动的点云采样方法；

- 一种渐进式采样方法，根据点与任务的相关性排序；

- 改进点云分类的性能，用采样的点云进行检索和重建。

2. 相关工作

点云简化和采样 文献中提出了几种点云简化[25, 23]或采样[15, 5]的技术。Pauly等人[25]提出并分析了几种点采样表面的简化方法，包括：聚类方法、迭代简化和粒子模拟。这些算法所产生的简化点集并不限于原始点集的一个子集。Moenning和Dodgson[23]的工作中采用了最远点取样，作为简化几何形状的点云的一种手段，以统一以及对特征敏感的方式进行。

Katz和Tal[15]提出了一种依赖于视图的算法来减少点的数量。他们使用了隐蔽点去除和目标点遮挡操作，以提高人类对采样点集的理解。最近，Chen等人[5]采用基于图形的过滤器来提取每个点的特征。保留特定信息的点有可能被他们的采样策略所选择。所需的信息被认为是对后续应用有益的。

上述采样方法旨在优化各种采样目标。然而，他们并没有直接考虑要遵循的任务目标。

渐进式简化 在一篇开创性的论文中，Hoppe[11]提出了一种渐进式的网格简化技术。在他的方法中，每一步都有一条边被折叠，从而引入最小的几何畸变。

Hanocka等人[10]最近的一项工作提出了一个神经网络来执行任务驱动的网格简化。他们的网络依赖于网格顶点之间的边缘。这个信息对于点云来说是不可用的。

一些研究人员研究了点集压缩的主题[26, 13, 29]。一个八叉树数据结构被用来对点云进行渐进式编码。压缩过程的目标是低失真误差。

点集的深度学习 Qi等人的开创性工作[27]提出了PointNet，这是第一个直接在无序点云数据上操作的神经网络。他们的网络由每点多层感知器、对称池操作和几个全连接层构成。PointNet被用于分类和分割任务，并显示出令人印象深刻的结果。为了评估PointNet对减少输入点数量的适用性，他们使用了随机抽样和FPS。在我们的工作中，我们提出了一种数据驱动的抽样方法，与这些抽样方法相比，它提高了抽样集的分类性能。

后来，Qi等人将他们的网络结构扩展为分层特征学习[28]。在训练阶段，局部特征聚合的中心点是由FPS选择的。与他们之前的工作[27]类似，FPS被用来评估他们的网络在较少的输入点上运行的能力。

Li等人[20]建议通过自组织地图（SOM）来学习特征聚合的中心点。他们在点和SOM节点之间使用了特征传播，并显示了对点云分类和零件分割的改进结果。作为预处理步骤，SOM被单独优化。

在Qi等人[27]的工作基础上，Achlioptas等人[1]为点云开发了自动编码器和生成式对抗网络。他们的网络输出是一组三维点，而不是形状类别或每个点的标签。在这项工作中，我们将我们的采样方法与Achlioptas等人提出的自动编码器一起用于点云重建的任务。

一些研究人员解决了点云整合的问题。Yu等人[40]从网状模型的测点斑块中提取点云。他们对点集进行随机抽样，并训练一个网络来重建原始补丁点。他们的后续工作[39]加入了边缘信息以提高重建的准确性。Zhang等人[43]研究了采样策略对点云向上采样的影响。他们使用了蒙特卡洛随机采样和基于曲率的采样。他们的网络被训练为从其样本中产生一个固定大小的点云。与这些工作相比，我们的研究重点是下采样策略。

3. 方法

问题陈述 给定一个点集

样本大小k≤n和任务网络T，找到一个k点的子集S∗，使任务网络的目标函数f最小：

这个问题提出了一个挑战，因为抽样似乎类似于集合，但在集合中，集合值是向前传播的，因此可以计算与之有关的梯度。然而，离散采样就像 "argpooling"，传播的值不能被增量更新。因此，不能直接进行采样操作的训练。因此，我们提出了一个两步的过程：首先，我们采用一个神经网络，即S-NET，来生成一组点。其次，我们将生成的点与输入点云相匹配，以获得其点的一个子集，即采样点。图1说明了这个过程。

S-NET的输入是一组n个三维坐标，即点，代表一个三维形状。S-NET的输出是k个生成的点。S-NET之后是一个任务网络。任务网络在n个点的输入上进行预训练，以便在点云上执行特定的任务（即分类、检索或重建）。在S-NET的训练和测试过程中，它保持固定。这确保了采样被优化到任务中，而不是任务被优化到任意的采样。

在训练阶段，生成的点被送入任务网络。这些点通过最小化任务损失被优化到手头的任务。我们使用一个额外的采样正则化损失项，鼓励每个生成的点接近一个输入点，并迫使生成的点分布在输入云中。

在推理中，生成的点与输入的点云相匹配，以获得它的一个子集。这些是采样点，是我们过程的最终输出。这些点通过任务网络并对其性能进行评估。

我们提出了两个采样版本。S-NET和ProgressiveNet。在第一个版本中（图1），我们为每个样本大小训练一个不同的采样网络。在第二个版本中（图2），我们训练一个网络，可以用来产生任何小于输入尺寸的样本尺寸。

3.1. S-NET

S-NET的结构遵循Qi等人[27]的观点。输入点经过一组1×1的卷积层，产生一个每点的特征向量。然后，使用对称特征的最大集合操作来获得一个全局特征向量。最后，我们使用几个全连接层。最后一层的输出是生成的点集。

我们把生成的点集表示为G，把输入的点集表示为P。我们构建了一个采样正则化损失，由三个项组成：

2和3分别使G中的点接近P中的点，在平均和最坏情况下。这旨在鼓励在接下来的匹配过程中进行紧密匹配。我们发现，混合平均和最大操作可以加快收敛速度。4确保生成的点很好地分布在输入点上，减少了匹配过程中的碰撞次数。采样正则化损失是这三个项的加权和:

注意这是Chamfer距离[7]的一般化，在β=0，γ=1和δ=0时实现。

此外，我们把表示为任务网络损失。总的S-NET损失是：

其中α控制正则化的权值。S-NET的输出是一个k×3的矩阵，其中k是样本大小，我们为每个k单独训练。

3.2. 匹配

生成的点G不能保证是输入点P的子集。为了得到输入点的子集，我们将生成的点与输入点云进行匹配。

一个广泛使用的匹配两个点集的方法是地球移动距离（EMD）[1, 41, 43, 7]。EMD在两个点集之间找到一个偏向，使对应点的平均距离最小，同时要求点集具有相同的大小。然而，在我们的案例中，G和P的大小是不同的。

我们研究了两种匹配方法。第一种是将EMD适应于不均匀的点集。第二种是基于近邻（NN）的匹配。这里我们描述了后者，它产生了更好的结果。关于另一种匹配方法的细节，请读者参阅补充材料。

在基于NN的匹配中，每个点x∈G被替换为其最接近的欧氏对应点：

由于G中的几个点可能最接近P中的同一个点，独特采样点的数量可能小于要求的样本量。因此，我们删除重复的点，得到一个初始采样集。然后，我们通过运行最远点取样（FPS）[28]来完成这个集合，直到G的大小，在每一步中，我们从P中添加一个离当前取样集合最远的点。

匹配过程只在推理时应用，作为推理的最后一步。在训练期间，生成的点由任务网络按原样处理，因为匹配不是可分的，不能将任务损失传播回S-NET。

3.3. ProgressiveNet：作为排序的抽样

S-NET被训练成对单一的、预先确定的样本大小的点进行抽样。如果需要一个以上的样本量，就需要训练一个以上的S-NET。但是，如果我们想训练一个可以产生任何样本大小的网络，即以任何抽样比例对输入进行抽样呢？为此，我们提出了ProgressiveNet。ProgressiveNet被训练为通过一个特定大小的点云，返回一个由相同的点组成的大小相同的点云。但是，虽然输入的点是任意排序的，但输出的点是按其与任务的相关性排序的。这允许对任何大小的样本进行抽样：为了得到一个大小为k的样本，我们只需从ProgressiveNet的输出点云中抽取前k个点，然后丢弃其余的。ProgressiveNet的结构与S-NET相同，最后一个全连接层的大小等于输入点云的大小（有3n个元素）。

图2. 渐进式网络训练。生成的点被分为规模越来越大的组，这样，每组都是下一个大组的子集。每组都有相应的任务和采样损失。总体目标是每组损失的总和。任务网络是预先训练过的，并保持固定。

为了训练ProgressiveNet（图2），我们定义了一个数据集，大小为

对于每个尺寸，我们计算一个任务损失项和一个采样正则化损失项，这样，ProgressiveNet的总损失就成为

其中

是方程6中定义的损失项，是ProgressiveNet生成的点的前c个点（输出层的前3c个元素）。这个损失函数定义了一个点子集的嵌套结构。例如，第一个子集，由两个点组成，被用于所有条款

，c≥2。因为这个子集被用于所有术语，所以它包含在所有更大的子集中。同样地，前4个点定义了第二个子集，它包括第一个子集，是所有较大子集的一部分。

在这个训练过程中，最初生成的k个点（对于任何k）被优化为既适合于手头的任务，作为一个独立的集合，又适合于与它们前面的点整合，以创建一个更大的集合，从而提高对给定任务的结果。这确保了对任务更重要的点将在生成的点集中出现得更早，而额外的点将给出递减的边际效用，从而形成一个面向任务的渐进式的点云分解[31]。

在推理中，生成的点（ProgressiveNet的输出层）与输入的点云使用我们在第3.2节用于S-NET的相同匹配过程进行匹配。我们将生成点的顺序转移到它们的匹配点上。为了获得一个特定的样本量k，我们取前k个采样点。

4. 结果

我们将S-NET应用于三个任务：点集分类[27]、检索和重建[1]。对于分类和检索，我们采用Qi等人[27]提供的ModelNet40[37]点云数据和PointNet[27]作为任务网络。对于重建，我们采用ShapeNet Core55库[4]和Achlioptas等人[1]的点集自动编码器。

随机抽样和FPS被用作替代的非数据驱动抽样方法，与我们建议的方法进行比较。为了进行公平的比较，我们只使用匹配过程后的S-NET点，所以我们的采样点和替代方法的点都是输入点云的子集。进一步的实验细节可以在补充材料中找到。

4.1. 分类

我们报告了ModelNet40数据集的实例分类结果，采用官方的训练-测试分割。我们采用完整版的PointNet作为S-NET的任务网络，而采用原生版的PointNet作为ProgressiveNet（以节省训练时间），除非另有说明。

图3. 用于分类的S-NET。PointNet在完整的点云（1024个点）上进行了训练，并使用不同的抽样方法对测试集的抽样点云进行了评估：随机、FPS和S-NET。使用S-NET的准确率显然更高。

S-NET 图3显示了PointNet在完整数据（每个点云有1024个点）上训练并在不同大小的样本上测试时的分类精度。我们比较了几种不同的采样方法：在输入点上均匀分布的随机采样、FPS和S-NET。我们训练了10个不同的S-NET，样本大小为k∈{2, 4, 8, .... , 1024}点。采样率被定义为n/k = 1024/k。我们观察到，在任何抽样比例下，使用S-NET的抽样点的分类精度都等于或优于使用FPS的抽样点，差值高达34.2%（对于抽样比例32）。

表1显示，在S-NET采样的点上进行训练时，PointNet的精度也比较高。表中的每一个数字都代表一个不同的PointNet，每一个都是在用不同采样方法采样的特定大小的点云上训练和测试的。例如，我们看到，在只有16个点的点云上训练和测试的PointNet，在使用S-NET时达到了85.6%的准确性，而使用FPS时只有76.7%。这表明，S-NET并没有过度适应它所训练的分类器的具体实例。相反，它以一种使采样集容易分类的方式对点进行采样，在数据中的不同类别之间形成强烈的区分。

表1. 在采样的点云上训练PointNet分类器。我们用不同的采样方法对训练和测试数据进行采样：随机采样、FPS和S-NET。之后，在取样数据上对PointNet进行训练和评估。应用S-NET，即使在最小的数据上进行训练，也能实现良好的分类。我们的结论是，S-NET将数据转化为更可分离的表示。

图4. ProgressiveNet vs. S-NET. 原始PointNet在完整的点云（1024个点）上进行训练，并在[2, 1024]范围内的每个样本大小k上进行评估。采样率被定义为1024/k。我们比较了三种不同的采样方法。FPS、S-NET和ProgressiveNet。S-NET对于它所训练的样本大小来说是比较好的，而ProgressiveNet对于介于两者之间的样本大小表现得更好。

ProgressiveNet 在图4中，我们比较了原始PointNet对S-NET（在这种情况下，用原生PointNet训练的）和ProgressiveNet取样的点的准确性。该评估是针对[2, 1024]范围内的所有样本量进行的。S-NET的结果来自10个不同的S-NET，每个S-NET都针对特定的样本大小进行训练，其大小为k∈{2, 4, 8, .... , 1024}点。对于介于这些值之间的样本大小，我们采取为较低的样本大小训练的S-NET，然后用FPS完成所需的大小。例如，为了得到48个大小的样本，我们采取了被训练为32个点的S-NET采样，然后用FPS做了16步。渐进式的结果是来自一个输出大小为1024的渐进式网络，该网络是用分类和采样损失项训练的，大小为Cs={2, 4, 8, .... , 1024}.

我们观察到，S-NET在其训练的样本大小上有更好的表现，而ProgressiveNet在两者之间的任何样本大小上都表现得更好。这显示了ProgressiveNet的优势，它按优先级对各点进行排序，因此准确率在样本大小上近似于单调地增加。

T-NET的可扩展性 S-NET假定任务网络已经被训练过。这在非常大的点云的情况下会造成问题。我们表明，可以在FPS采样的点云上训练任务网络，并使用它来训练S-NET。然后，所得的S-NET可以用来重新训练任务网络，使其达到更高的精度。请参阅图5，了解所建议的训练和测试程序的说明。

图5. S-NET的可扩展性。在大型点云上的拟议训练和推理程序的说明。在第一阶段，我们使用FPS对点云进行采样，以达到可训练的大小，并使用采样的点云来训练任务网络。在第二阶段，我们在采样的点云上训练S-NET，采用固定的任务网络。在第三阶段，我们应用S-NET对大的点云进行重新采样，在第四阶段，我们再次训练任务网络，这次是在S-NET的点上。在推理时，我们使用S-NET对大的点云进行采样，使其达到任务网络训练的大小。

下面的小规模模拟证明了这一点。我们用FPS对ModelNet40进行采样，每个点云中有k=32个点，并在这些采样点上训练PointNet。这就是我们的基线。基线在测试集上的准确率是82.2%。当我们用大小为1024的点云来训练PointNet时，准确率只有46.6%。然后，我们使用32大小的点云训练集和基线PointNet作为任务网络来训练S-NET。然后，我们再次对ModleNet40进行采样，大小为k=32，这次使用S-NET。最后，我们在S-NET取样的点上训练PointNet。在测试集上重新训练的PointNet的准确率提高到86.0%。采用S-NET使我们能够提高PointNet的准确性，而不需要在更大的点云上进行训练。

时间和空间的考虑 类似PointNet的网络的时间复杂度由其每点卷积层主导，因此强烈依赖于输入点云的大小。S-NET的空间复杂度是其输出大小k的线性函数。S-NET在空间（参数数量）和推理时间（浮点运算数量）之间提供了一个权衡。例如，与在完整的点云上运行PointNet相比，在空间只增加5%的情况下，对1024个点的点云进行采样的级联S-NET到16个点的推理时间减少90%以上。完整的细节见补充材料。

近似采样 到此为止，我们应用匹配的后处理步骤，直接与FPS进行比较。然而，可能有这样的设置，即k个输出点不一定是原始点云的子集。在这种情况下，我们可以直接使用S-NET的生成点，放弃匹配步骤。我们既可以使用生成的点，也可以使用采样的点。第三种选择是在两者之间进行插值，即使用与原始输入点相距最多ǫ的点。这是通过将每个生成的点与其匹配的采样点进行内插来实现的，从而在它们之间的直线上得到第三个点，与采样点的距离不超过ǫ。图6显示，当向PointNet提供生成的点时，其精度更高。对于归一化为单位球体的点云，我们发现选择ǫ=0.05会使分类精度处于采样点和生成点精度的中间位置。请注意，ǫ是在推理时设置的。

临界集采样 正如Qi等人[27]所定义的，临界集是对最大集合特征有贡献的点的集合。我们的方法的一个合理的替代方法可能是对贡献最大特征的临界点进行采样。我们尝试了这种方法，发现只有在小的采样比率下才是可行的。完整的细节见补充材料。

4.2. 检索

我们现在表明，采用S-NET而不是FPS可以带来更好的检索结果。具体来说，我们把用PointNet进行分类训练的SNET作为任务网络，没有重新训练它。我们对送入PointNet的点进行采样，并使用其倒数第二层作为形状描述符。检索是基于这个形状描述符的L2距离进行的。我们用ModelNet40测试集中的每一个形状作为查询形状来重复实验。该实验在S-NET和FPS的不同样本量下重复进行。

表2总结了不同采样比例和采样方法的平均精度（mAP）。我们看到，S-NET在采样率大于4的情况下表现得更好，而且对采样率不是很敏感。图7显示了原始数据和使用FPS和S-NET的采样数据的精度-召回曲线，每个形状的采样点为k=32。我们观察到，在所有的召回值中，应用S-NET时的精度明显更好。

4.3. 重构

我们接下来学习用自动编码器作为任务网络进行采样。我们使用了Achlioptas等人[1]提供的ShapeNet Core55点云数据，以及他们的自动编码器，并对四个形状类别进行了训练：桌子、汽车、椅子和飞机。这些类别有最多的可用模型。每个形状类被分成85%-5%-10%的训练验证-测试集。自动编码器被训练用来接收和重建2048个点的点云。

自动编码器的重建误差由Chamfer距离[1]来衡量。为了比较不同的采样方法，我们使用归一化重建误差（NRE）。也就是说，我们从一个点的子集和完整的点集中重建完整的点集，并取两者的重建误差比。我们训练了几个S-NET，样本大小如下：k∈{16, 32, . . 2048}，以及一个具有相同规模的损失项的单一ProgressiveNet。作为一种替代的采样方法，我们使用了FPS。

归一化重建误差 图8显示了NRE作为采样率的函数，其中采样率被定义为n/k = 2048/k。我们将FPS与S-NET和ProgressiveNet进行比较。对于小的采样率，我们采样点的NRE与FPS相似。然而，随着采样率的增加，我们的采样方法优于FPS。例如，在采样率为32时，FPS的NRE略高于2，而S-NET和ProgressiveNet的NRE分别约为1.5和1.75。S-NET的NRE比ProgressiveNet低，因为前者是按采样率单独优化的，从而提高了重建性能。我们学习从未见过的形状中取样，使重建误差降低。

采样和重建可视化 图9比较了整个点云的重建结果和64个点的采样结果，其中采样是由S-NET或FPS产生的。使用S-NET的重建质量高于使用FPS的重建质量，并接近使用整个点云的重建质量。有趣的是，由S-NET采样的点是非均匀分布的，而由FPS采样的点则是均匀分布的。

逆向简化 在这个概念证明中，我们展示了如何欺骗自动编码器。我们简化了点云，使其在视觉上类似于一个类别，但被自动编码器重构为不同类别的形状。我们用一对单一的输入和目标形状来训练S-NET，其中输入是一个类别的形状，目标是另一个类别的形状。采样损失是在输入和S-NET生成的点之间。重建损失是在目标形状和重建的形状之间。图10显示了将飞机变成汽车的结果。

5. 结论

我们提出了一种学习如何对点云进行采样的方法，该方法对下游的任务进行了优化。该方法包括一个简化网络，S-NET，然后是一个后处理匹配步骤。我们还提出了一个网络，称为ProgressiveNet，用于根据每个点对任务的贡献来排序点云。由此产生的方法在几个任务的取样点上优于FPS：分类、检索和点云的重建。

所提出的方法是通用的，可以产生一个由不一定属于原始输入形状的点组成的小型点云。输出的点云在优化下游任务的目标函数的同时，使相对于输入点云的几何误差最小。我们已经表明，学习采样可以改善结果，并与各种应用结合起来使用。