论文阅读：Adaptive Hierarchical Down-Sampling for Point Cloud Classification

Adaptive Hierarchical Down-Sampling for Point Cloud Classification

用于点云分类的自适应分层下采样法

摘要

深度神经网络中无序点云的确定性下采样到目前为止还没有得到严格的研究。现有的方法对点进行下采样，而不考虑它们对网络输出的重要性，并且经常在处理前对原始点云进行下采样。结果，点云中的一些重要的点可能被删除，而价值较低的点可能被传递到下一层。相比之下，所提出的自适应下采样方法通过考虑每个点的重要性来对点进行采样，而每个点的重要性因应用、任务和训练数据而异。在本文中，我们提出了一种新型的确定性、自适应、互变性下采样层，称为关键点层（CPL），它可以学习减少无序点云中的点的数量，同时保留重要（关键）的点。与大多数基于图形的点云下采样方法不同，CPL是一种全局下采样方法，使其在计算上非常高效。所提出的层可以与基于图形的点云卷积层一起使用，形成一个卷积神经网络，在本文中称为CP-Net。我们介绍了一个用于三维物体分类的CP-Net，它在基于点云的方法中对ModelNet40数据集取得了很高的精度，这验证了CPL的有效性。

1. 引言

在大多数机器人应用中，激光点云数据在感知周围环境方面起着关键作用。尤其是自主移动机器人系统使用点云数据来训练深度模型以解决不同的问题，如动态物体检测、同步定位和绘图（SLAM）、路径规划等。使用深度网络从无序的点云中提取特征已经成为一个非常活跃的研究领域，引入了许多新方法，如PointNet[19]、PointNet++[20]、DGCNN[26]、PointCNN[11]和SO-Net[10]。这些方法在点云分类基准中被证明是相当成功的，如ModelNet40[27]。

在实际场景中，点云中与物体相关的点的数量可能相当大，特别是由于使用高密度的传感器，如Velodyne-64[16]。减少计算的一个可能的方法是在点云通过网络时对其进行向下取样。一类方法被提出，其中k-NN搜索[18]被用来寻找每个点的邻域，并根据这些邻域进行下采样。然而，这些方法用一种昂贵的计算（邻域搜索）换取另一种计算（处理大型点云）。

在另一个系列的工作中，如[19]和[20]，三维点云被直接处理，而其他工作将点云转换为常规体素，如[27，14，6]的方法。然而，转换为常规体素会导致损失计量信息和高计算复杂性。最近，RS-CNN[12]中介绍的方法试图学习类似CNN的不规则过滤器来捕捉点云的局部特征，在分类中取得了最先进的准确性。除了上述论文外，[5]还提出了一个用于点云采样的深度学习网络。[5]中的方法从原始和无序的输入点云中产生了一个下采样的点云，它不能保证是原始点云的一个子集。因此，需要一个后处理的匹配步骤，导致了一个更复杂的系统。

为了充分利用下采样方法，我们非常需要一种对内容敏感但快速的下采样无序点云的确定方法，这种方法可以被整合到深度神经网络中--这种技术与传统CNN中的最大池类似，有效且高效。在本文中，我们介绍了关键点层（CPL），它可以满足这些要求。

与之前产生一组与输入点不同的下采样方法不同，CPL不仅从输入中选择输出点，而且还在网络中下采样，在这个过程中不会丢失关键点。与在推理时随机产生不同点集的随机抽样层不同，CPL是一个确定的层，每次运行后产生相同的点集。它对输入点的变异是不变的，也就是说，是不分先后的。它是自适应的，因为它学会了在训练过程中减少取样点，而且它是一种全局方法，不限于邻域搜索，这使它很有效率。

2. 相关工作

2.1. 点云上的深度学习

为了应对点云的稀疏性，深度学习方法倾向于将空间体素化，然后对体素应用三维CNN[14, 28]。这种方法的一个问题是，网络规模和计算复杂性随着空间分辨率的提高而迅速增长。反过来说，较低的空间分辨率意味着更大的体素和更高的量化误差。缓解这一问题的方法之一是使用八叉树[25]或kd树[8]来代替体素。例如，在[8]中，建立了点云的kd树，然后通过分层特征提取器进行遍历，利用了点云在不同空间尺度的不变性。然而，这种方法仍然依赖于对边界体积的细分，不能利用点本身的局部几何结构。相比之下，基于点的神经网络不需要将点云转换为其他格式。因此，可以避免分辨率损失[29]。

2.2. 作为图的点云上的CNN

利用局部几何信息的一个有希望的方法是将点云建模为无序（非欧几里得）点的图，然后将CNN应用到它。这个重要的研究方向[23]有两个主要变化。

谱系方法将空间图卷积重新定义为谱域中的乘法[23, 22]。沿着这条路线提出的第一个方法缺乏滤波器的空间定位性。卷积滤波器的参数化为特征值的切比雪夫多项式，并对其进行近似评估，这就为创建本地化的空间滤波器提供了一种高效的计算方法[4]。不幸的是，这些滤波器是在谱域中学习的[1]，因此对数据集中的所有图形都必须是相同的。这意味着当数据集中的图形结构发生变化时，如点云，在一种形状上学习的图形不能推广到其他图形。

与此相反，局部空间过滤[23, 17, 9, 24, 30, 3, 13, 15]采用了空间过滤器。图形上的局部补丁的概念被采用，以允许类似卷积的运算器被应用于每个局部补丁。根据每个局部补丁中的过滤器权重和节点之间的具体对应关系，我们有MoNet[15]、GCNN[7]和DCNN[2]这样的变种。尽管在一般图上应用空间滤波进行深度学习的工作已经做了很多，但只有少数方法，如KCNet[21]、FoldingNet[29]、ECC[23]和DGCNN[26]在点云图上使用深度学习。

2.3. 深度网络中的点云下采样

虽然点云上的图卷积最近受到了极大的关注，但输入点云的下采样在很大程度上还没有被探索。由于一些原因，这种下采样是非常可取的。

- 大多数点云上的图形卷积方法使用k-NN搜索来寻找每个点的邻域。因此，对点进行下采样可以减少后续卷积层的计算成本。

- 减少网络中的点的数量会降低运行时的内存使用。

- 下采样可以提高对输入数据中某些扰动的鲁棒性。

在典型的基于点的神经网络中，如PointNet和DGCNN，点云中的点的数量在整个网络中是固定的。PointNet++使用最远点取样（FPS）对点云进行向下取样。然而，由于它通过寻找每个采样点周围的k-NN点来生成重叠的分区，因此需要比PointNet[20]多得多的计算。

KCNet[21]和FoldingNet[29]使用基于图形的最大集合对图形进行下采样，该方法使用预先建立的k-NN图（KNNG）在每个节点的邻域上获取最大特征。然而，这些方法不能保证最重要的点，也就是我们所说的关键点，会被传递到下游。一个具有不太相关的特征的点可能被选中或生成，而一个重要的点可能被删除或贬值。

此外，其中一些网络中使用的下行采样是静态的，采样只基于输入点云中的点的空间位置，但不基于它们相应的学习特征。另一方面，确实使用点之间的特征空间距离的方法，如PointNet++[20]，如前所述，在计算上是很困难的。在另一个突出的方法中，[5]介绍了一种优化点云采样的深度学习方法，其中一个NN模型被训练成从原始数据集生成一个下采样的点云。

最后，所有这些方法都会生成一组新的点，而不是选择一个输入点的子集。这使得跟踪每个输入点对输出的贡献变得困难。

在本文中，我们引入了一个计算效率高的临界点层（CPL），它根据学习到的特征对点进行自适应降样。CPL根据一个点对全局最大集合（最大还原特征向量）的贡献程度，全局过滤掉不重要的点而保留重要的点。CPL在计算上是非常高效的，因为它不需要本地近邻搜索。此外，由于从图卷积层得到的特征向量已经包含了每个重要点的局部邻域信息，CPL产生了一个较小的子集，而不会丢失相关信息。在接下来的两节中，我们将详细解释CPL并报告我们的实验结果。

3. 建议的解决方案

在本节中，我们提出了两种新的自适应下采样方法，可用于深度神经网络。所提方法的重点是引入一个系统的解决方案，在任意的神经网络架构中对点（或与之相关的特征向量）进行下采样。这与[5]等方法不同，其中提出了一种新的方法来对特定的数据集进行下采样。这两个新的层被命名为临界点层（CPL）和加权临界点层（WCPL），可以有效地对无序点云的相关特征进行下采样，同时具有包络不变性。在本节中，将详细解释CPL、WCPL以及在深度神经网络中使用这两个层的系统方法，特别是分类神经网络。

图1：关键点层（CPL）[实线]和加权关键点层（WCPL）[实线和虚线] 。

3.1. 临界点层（CPL）

让我们假设CPL的输入是一个有n个点的无序点云，每个点表示为一个特征向量，其中R是实数集合，d是特征向量的维度。CPL的目标是生成一个输入点的子集，称为临界点（CP），有m≤n个点，每个点表示为一个特征向量，其中l是新特征向量的维度。点云的临界点是具有最大信息量的点，在下采样（或池化）过程中需要保留。这些点可以根据任务和应用而改变。

图1显示了拟议的关键点层（CPL）的框图。为了更详细地阐述CPL的功能，其伪代码也在算法1中提供。该算法的步骤详细解释如下。

1. 输入点云是一个有n行（对应于n个输入点）和d列（对应于d维特征向量）的矩阵。

2. 在第一步（操作3）中，为矩阵的每一列获得最大特征值。这与PointNet[19]中的max-pooling操作相同。得到的d维特征向量，用表示，具有与输入特征向量相同的维度，可以独立用于分类和分割任务。然而，我们感兴趣的是对输入点进行下采样，而不是从它们中生成一个单一的特征向量。为了这个目的，具有最大特征值的每一行的索引也被保存在索引向量idx中。向量idx包含所有对特征向量有贡献的点的索引。根据定义，我们把这些点称为关键点（CP）。这些是在下采样过程中应该保留的重要点。

3. 索引向量idx可能包含同一个点的多个实例。为了避免这些重复，使用 "set (unique) "函数（操作6）从idx中提取唯一指数。具有唯一索引的输出集被称为关键集（CS），用uidx表示。除了找到唯一向量，我们还将中对应于相同点或索引的特征值相加（操作7）。由此产生的特征向量以后将被用来对输入点进行排序。

4. 接下来，对特征向量进行排序（按升序排列）。uidx中的相应指数也会根据排序输出重新排列（操作12），产生一个指数向量，用suidx表示。这个步骤对于下面的采样（调整大小）操作是必要的。它还使CPL对输入点的顺序不发生变化。

5. suidx中的元素数量对于输入批次中的不同点云可能有所不同。然而，对于批处理来说，这些数字需要是相同的。为了解决这个问题，对于输入批次中的每个点云，索引向量suidx被上采样为一个固定大小的向量rusidx，使用整数阵列的上采样方法，如近邻调整大小（操作18）。

6. 作为最后一步，上采样的索引向量rsuidx包含所有临界点的索引，用来收集点和它们相应的特征向量。由于不同的特征向量可能对应于一个点，并且由于信息在隐藏的NN层中被过滤，我们可能希望从其他层（用表示）收集特征，而不是用来选择点（用表示）的层。然而，临界点的定义是基于从获得的最大特征向量中每个点的贡献，因此这里我们使用。

任何用于点云处理的层的主要要求之一是它对点云变化的不变性。拟议的CPL通过以下特性满足了这一要求。

- 在步骤4中对特征向量的排序是独立的，因为排序是基于特征值而不是基于点的索引。

- 第5步中的近邻调整对交换输入点的索引是不变的，即

其中排序是基于特征值的，而交换是仅适用于索引的。

3.2. 加权关键点层（WCPL）

在CPL中，如果点云中的任何一个特征对输出的最大特征向量有贡献，则该点被算作关键点，而不考虑其贡献特征的数量。例如，如果一个点贡献了它的两个特征，而另一个点有10个贡献的特征，在CPL中两者的处理是一样的。换句话说，在CPL中，一个点的 "重要性 "有一个二进制值：一个给定的点要么是重要的（关键），要么是不重要的（非关键）。在本节中，我们介绍了CPL的一个修改版本，称为加权关键点层（WCPL）。拟议的WCPL根据各点对的贡献程度为其分配权重。

在这种情况下，为了将一个点的权重增加C的系数，我们将该点的索引重复C次。通过增加重复频率，在下采样过程中选择该点的概率也会增加。从另一个角度看，在WCPL中，输出中遗漏临界点的概率比CPL中低。算法1中使用if语句给出了WCPL的伪代码。

3.3. 临界点网络（CP-Net）

在这一节中，我们提出了一个分层结构，将深度卷积神经网络应用于点云，通过使用提议的CPL/WCPL系统地减少点的数量。在拟议的网络模型中，命名为临界点网络（CP-Net），任何图卷积方法，如DCNN[2]、GCNN[13]、MoNet[15]或EdgeConv（来自DGCNN[26]）都可以用于卷积层。以EdgeConv为例，CP-Net的框图显示在图2。

图2中的输入是大小为n的无序点云。在第一步中，点云被传递到选择的卷积层中，将输入过滤成更丰富的特征集。然后，过滤后的输出点云被用作第一个CPL/WCPL的输入。使用具有下采样系数的CPL/WCPL，中的点的数量被减少到点。这些步骤在必要时重复多次，以达到理想的点云大小（在点的数量和特征向量大小方面）。请注意，在第j个CPL/WCPL块，只要它们对应于相同的点，也可以从使用或串联所有或部分前层的特征中受益，即。因此，输出点的数量将是。

3.4. CP-Net在三维物体分类中的应用

这里我们给出一个CP-Net在三维物体分类问题中的应用实例。图3是该网络的方框图。该网络由三个子网组成。1）n点特征提取子网，2）（n/4）点子网和3）分类子网。该网络的具体步骤如下。

- 网络输入是大小为n×3的无序点云，其中每个点是一个三维矢量。

- 输入的数据要经过一个空间变换器网络，如[19]中所解释的那样，以使其对任何刚性变换（包括旋转和平移）具有鲁棒性。值得注意的是，不使用原始输入，而是使用EdgeConv [26]边缘特征的修改版进行空间转换，在下一步1中解释。

- 空间变换的输出进入一个过滤CNN，这里是EdgeConv [26]，以产生更丰富的特征。与原始的EdgeConv [26]算子不同，它在边缘特征函数中使用两个核，我们使用三核版本

，其中是每个点xi和其邻点xj之间的元素级的平方运算。在拟议的网络中，将具有128个过滤器的EdgeConv应用于大小为n×3的输入点云，从而得到大小为n×128的点云。

- 多层感知器（MLP）层将特征维度从128扩展到1024，得到大小为n×1024的点云。

- 接下来，CPL/WCPL被应用于寻找关键点并减少输入点的数量。如第4节所示，这一步降低了计算的复杂性，但分类的准确性没有任何损失。选择1/4的下采样系数，将点的数量从n减少到n/4。

- 另一个EdgeConv层被用来过滤点云，这次是通过保留深度和大小来进一步处理收到的点云。请注意，减少前一层的点的数量可以高度降低这一层的计算复杂性。

- 在n×1024大小的点云中，使用减少-最大层来生成一个1024大小的向量。

- 最后，应用大小为512、256和40的全连接层，将大小为1024的特征向量转化为ModelNet40数据集[27]中的类的数量，即40。

在拟议的三维分类方法中，标准的softmax交叉熵被用作损失函数。此外，所有层都包括ReLU激活函数和批量归一化。

4. 实验

4.1. 数据预处理

我们在ModelNet40三维物体分类数据集上评估我们的模型[27]。该数据集包含12,311个来自40个不同对象类别的网格化CAD模型，其中9,843个模型用于训练，2,468个模型用于测试。从每个模型的网格表面，1024个点被均匀采样并归一到单位球体。为了增加数据，我们在三维空间中随机地缩放、旋转和移动每个物体点云。

4.2. 训练细节

为了训练模型，我们使用亚当优化器，初始学习率为0.001，并以每200，000步0.5的速率进行指数衰减。批量规范化的衰减率从0.5开始，增加到0.99。在最后两个全连接层中使用概率为0.5的Dropout。在Nvidia P100 GPU上用TensorFlow训练网络，批量大小为32，400个epochs需要9-10小时。

4.3. 统计结果

为了评估三维点云分类方法的性能，我们使用了总体准确率和每类平均准确率，在所有测试样本中计算。

我们提出的CP-Net/WCP-Net的分类精度结果显示在表1中，并与之前提出的方法进行了比较。如图所示，我们的CP-Net/WCP-Net方法是[12]的亚军，并且超过了表1中所有其他方法和ModelNet40基准排行榜的准确性。

4.4. 定性结果

图4显示了所提出的CPL是如何学习对不同的点云进行缩小采样的。图4(a)显示了灯、飞机、花盆、笔记本电脑和汽车这些物体类别的1024大小的原始点云。图4(b-e)对应的是分别在第1、100、200和300个历时中使用0.25的下采样率得到的输出。如图4(b)所示，在训练开始时，由于下采样的结果，物体的一些重要部分，如灯柱、花叶和笔记本屏幕被部分丢失。然而，经过300次的训练，CPL学会了对点云进行下采样，从而使物体的关键点得到了大部分保留。在点云分类的背景下，我们所说的物体的重要点是指那些包含必要信息的点，以区分数据集中的不同物体。

图4(f)显示了在300个训练周期后，按1 16的比例下采样的相应点云。如图所示，即使在如此小的64个点的点云中，每个物体的重要点仍被保留下来。灯柱、飞机机翼和笔记本电脑的六个角是被保留下来的重要物体部分的一些例子。

4.5. 消融研究

EdgeConv核 使用双核和三核（在DGCNN[26]中使用的EdgeConv算子）对整体分类精度和执行时间的影响见表2。对于双核版本，我们使用[26]中使用的版本。三核版本的定义见3.4-c节。正如所见，三核版本在计算上比双核版本更复杂。在这两种情况下，由于CP-Net/WCP-Net在分类精度上优于DGCNN，它的计算复杂性也较低，因为CPL/WCPL点云下采样。

表2：边缘特征核对总体分类精度（%）和执行时间（ms）的影响。

瓶颈维度的影响 瓶颈层大小（输出特征向量中的特征数量）对分类精度的影响如表3所示。显然，增加瓶颈层尺寸可以提高准确率，但是在1024个特征左右时几乎达到了饱和。请注意，即使瓶颈大小为64，拟议的CP-Net的准确率（%89.35）也比瓶颈大小为1024的PointNet（%89.20）高。

表3：瓶颈尺寸对准确性的影响（%）

下采样率的影响 表4显示了下采样率对分类精度的影响。

正如预期的那样，点云缩小得越多，精确度就越低。这是因为一些关于物体的重要信息会因为下采样而丢失。然而，拟议的CPL和WCLP层尽可能地保留了重要的物体点。这一点可以从表4中得到验证，在下采样率为1和1/16（对应于1024和64点大小的点云）时，准确度值之间的差异只有0.73%。这意味着在下采样过程中，CPL保留了每个物体最重要的信息，因此在如此小的点数量下，物体仍能以高精确度分类。

以比例为4，即256个点的下采样效果来看，CPL与随机下采样的准确性值得比较。如果我们用比率为4的随机下采样代替CPL/WCPL，CP-Net分类网络的准确率从CPL和WCPL的92.33和92.41分别下降到91.47，这表明CPL在获得架构中的关键点和特征方面的有效性。值得注意的是，虽然在训练中使用随机下采样是可行的，但在推理时，它在数学和统计学上并不健全。原因是每次推理运行时，随机采样器都会产生一组新的下采样指数，从而导致对相同输入的非确定性输出/分类。

时间和空间复杂度 表5比较了运行拟议的CP-Net/WCP-Net与其他最先进的物体分类方法的执行时间，在一台带有单个P100 GPU和Intel 1.2 GHz CPU的Ubuntu机器上。所有的实验中都使用了32个1024点的点云批处理。

就模型大小而言，最小的模型是由KCNet生成的。CP-Net和WCP-Net生成的模型最大，因为它们的网络参数数量较多。模型大小可以通过减少瓶颈维度来减少。

就计算复杂性而言，CP-Net和WCP-Net比DGCNN和PointNet++运行得更快。然而，它们比PointNet和KCNet要慢。与DGCNN相比，CP-Net的计算复杂度较低，这是因为其网络中采用了CP层。同样，通过适当的网络设计，所提出的CPL/WCPL有望加速其他分类深度网络，如KCNet和PointNet++。

5. 结论

在本文中，我们提出了一种新的确定性自适应下采样方法，可以通过训练将最重要的点（关键点），传递到神经网络的下一层。我们提出了两个下采样层，即临界点层（CPL）和它的加权版本，加权CPL（WCPL）。作为在深度神经网络中使用CPL/WCPL的系统方法，还介绍了CP-Net，一个这些层的分层实现。最后，基于所提出的CP-Net设计了一个深度分类网络，用于3D物体分类。使用普通数据集的实验结果表明，与之前最先进的方法相比，所提出的方法在分类精度上具有竞争力。CPL是一个自适应层，可以动态地对无序数据进行下采样。这一特性可能会激发设计一种新型的自动编码器，可以处理无序数据，如点云。这种方法已经在调查中，结果将在未来的工作中展示。

图4：（从上到下，从左到右）ModelNet40数据集[27]中笔记本电脑和汽车物体类别的原始点云，以及图3所示的分类CP-Net训练后得到的下采样版本（比例为1 /4），分别为1、100、200和300个历时。(f) 下采样率为1 /16的300个历时的训练结果。这些图像用颜色编码以反映深度信息。