点云分割一直是点云研究领域一个很重要的分支，它在SLAM、自动驾驶、机器人等领域都有着重要的应用。点云相比于2D图像，其有着更丰富的3D空间信息，对物体的表面描述也更接近实际。然而，点云的无序的特点以及缺乏直观的拓扑结构，以及大场景下的爆炸般的点云数据量，一直是点云的核心问题。点云的特征表示、数据处理、算法结构都是研究的热门方向。深度学习已经在2D图像领域遍地开花，而在点云领域，尤其是点云分割领域，还有着很长的路要走。

MASK RCNN在2D图像分割领域算是一个非常有突破性的工作，在图片或者视频的每一帧上，车、人等物体，都被精确的分割出来。然而这一切都是在2D上做的，2D照片本身是缺乏3D信息的，我们不能知道照片中的人究竟距离我们有多远，而这便限制了计算机去和这个世界的理解和交互。我们希望有更理想的计算机或者说机器人，能够更像人一样去和所见的东西，进行理解和交互，比如机器人的抓取，自动驾驶的感知，实时地图构建，以及室内机器人导航，而这些工作，3D信息将成为十分重要的输入数据。

3D信息在计算机中一般有以下几种表示：

点云的很大的应用优势就是，可以实时被传感器测量出来、可以很紧凑的表示一个大规模场景的3D信息、可以非常好的表示物体的3D形状信息，对光照等外界因素并不敏感（因为是主动式的发射反射光信息，2D只是接受其它光源的反射光）。

当然，点云也有其不好处理的一面。点云是不规则的、不均匀的、无序的。虽然有这些缺点，但是其巨大的优点，让研究者们不断去想尽办法，寻找足够好的算法，去更好的处理点云。

点云处理可以分为传统方法和深度学习的方法，深度学习方法中又分为非点云输入和直接点云输入。前者将点云先处理成如多角度图片集或者体素网格等，后者则直接把点云以原始的点集直接输入处理。作者提到了一篇19年的点云深度学习领域的survey: Deep Learning for 3D Point Clouds: A Survey(链接://arxiv.org/abs/1912.12033)，这是一篇非常好的survey，把点云分类、检测、分割几个领域，详细介绍了一遍，并且相关贡献都以时间轴进行展示，推荐大家阅读。

作者挑选了两套处理点云的方法：Voxel-based 和 Point-based。

PointNet和PointNet++是Point-based领域开拓性的工作，PointNet直接输入点集，然后使用共享多层感知机及最大池化函数来提取逐点及全局特征并同时确保点云特征的置换不变性。PointNet++相比于PointNet，增加了层次的局部特征提取，相比于PointNet直接通过max-pooling得到的全局特征有更好的效果。这两篇文章是直接在点云上进行处理的算法的基础，后续又有许多跟进的工作，进一步提升了分类识别及分割的效果。

如果你看过点云相关的代码，你会发现大部分点云方法都是在一个块上进行操作的。比方说一间房子的点云，20m×20m，里面的点非常多，所以一般会在俯视视角上，切一个比如1m×1m×H的长方体，在这个长方体内做操作，而且这个长方体内的点云也是非常多的，所以还要再做一个采样，比如采样4096个点。那么这种切块操作带来的问题就显而易见了，一个桌子切成两半，然后在各自的块内做分割，这就缺少了一种整体的特征。因此，大场景下的点云处理很有必要，也很有挑战。如下图，一个桌子在不同块里面被预测成不同的类别。

作者先简单介绍了两篇前人的工作，PointCNN和KPConv，这两篇论文并不是做大场景的，但是它们提出的想法是基础性的，就是自定义卷积，通过自定义的卷积在点云上进行操作，可以提取更好的特征。

在大场景领域，作者也简单提了两篇工作，SPG和FCPN。SPG为整个场景的点云构建了一个超点图，边信息表征了点云内在的关联，然后在graph上进行操作。FCPN是结合了point-based和voxel-based，将无规则的点云，转换为内部有序的数据结构，然后再使用3D卷积进行处理。作者提到之前做大场景的工作，处理起来都非常耗时，因此RandLA-Net工作motivation便有了。

那现有的方法，比如pointnet和pointnet++能直接迁移到大场景领域吗？作者做了相关实验，首先pointnet是直接用max pooling来取得全局特征，局部特征的提取是缺失的。随着切块的块越来越大，直接max pooling，必然会损失很多信息，因此pointnet的性能会越来越低。那结合了局部特征的pointnet++呢？通过实验，我们发现随着块的变大，性能也在变好。然而耗时也越来越严重，因为pointnet++中使用的点集的降采样算法，是和点数的二次方成正比的，块越大，点数越多，速度越慢。

那么大场景点云语义分割领域的难点在哪？作者提了三点，首先是整体的点云相比于一个小块的点云的结构要复杂很多；其次是点数的增多势必会带来GPU显存的上升；最后是传感器采集到的点云数是非固定的，之前都是切块后再采固定数量的点。

作者希望能找到一个符合以下三点的大场景处理方法：1)不用切块，直接全局输入；2)计算复杂度和显存占用要低；3)还要保证精度和能够自适应输入点数。

对于大场景的点云，如何直接处理呢？一个核心的步骤就是降采样。作者认为我们需要一个更有效的降采样算法，来保留点云的key points。同时还希望能够有一种更好的局部特征提取和聚合的算法来学到局部特征。

首先是降采样。

作者先对现有的点云降采样技术做了总结，大范围可以分为两类：Heuristic Sampling(启发式的)、Learning-based Sampling(可学习的)。

对于启发式的降采样：

• Farthest Point Sampling(FPS)：这是一种在点云领域被广泛使用的降采样方法，如PointNet系列。每次采样都去离采上一个点最远的点，迭代进行，这样可以把一些边边角角的点都能找到，但是算法计算复杂度O(N^2)；

• Inverse Density Importance Sampling (IDIS)：先对每个点的密度进行排序，然后密集的部分多采样，稀疏的部分尽可能都保留。然而这种算法会容易受到噪声的影响，计算复杂度O(N)；

• Random Sampling (RS)：随机采样，计算复杂度为O(1)，与输入点数无关，当然可能会丢掉一些重要的点

对于可学习的降采样：

• Generator-based Sampling (GS)：算法通过学习来生成一个点云子集来实现降采样。这是很新颖的方法，然而这种方法可能比FPS方法的复杂度更高；

• Continuous Relaxation based Sampling (CRS)：通过学习一个矩阵，类似与实现一个全连接网络，然后和输入点云相乘得到输出的低维点云空间。然而当输入点数非常大的时候，矩阵需要的显存也将非常大；

• Policy Gradient based Sampling (PGS)：使用一个马尔科夫决策来对每一个点进行决策，决定其是否被保留。当输入点数很多的时候，其决策过程非常缓慢，搜索空间非常大，而且很容易不收敛。

通过以上的对比，最后作者认为也许随机采样才是最适合大场景的点云分割任务的。然而，随机采样很容易去丢掉那些重要的点，我们该如何解决这个问题呢？作者提出了Local Feature Aggregation。这个Local Feature Aggregation主要包括三个子模块，分别是LocSE、Attentive Pooling、Dilated Residual Block。

该模块希望从输入点云里得到一个局部空间特征。步骤是先对于每一个点进行K近邻，找到它的邻域点集；然后将中心点的坐标、邻域点的坐标、邻域点和中心点的相对坐标和邻域点和中心点的欧式距离连在一起；再过一个MLP，和邻域点的特征在连在一起，得到最终输出。

将上面提取到的特征聚合在一起，PointNet系列一般都是直接一个Max Pooling，实现特征聚合。作者认为Max Pooling有些粗暴，容易丢掉一些重要的信息。作者使用Attention机制，在SeNet工作中提到过，学习一个MASK，来作为每个特征的权值，然后加权，再过一个MLP，实现聚合。

随机降采样不可避免会丢掉一些重要的点，如何解决这个问题，作者认为如果每个点的感受野足够大，其能够更好地聚合局部的特征，而且当这种感受野足够大时，即便有些点的特征被随机的丢掉了，但整个点云的大部分信息还是能够被有效地保留下来。因此我们将多个LocSE和Attentive Pooling模块连在一起，组成一个大的Dilated Residual Block。这样的话，输入点云通过不断的聚合，便增大了保留下点的视野。

基于上面的方法，作者设计了一个沙漏网络的结构，即点数先降低，再增加。每一层局部特征聚合和随机采样交替进行，点数下来了，每个点的视野也上去了。

通过实验，作者发现随机采样方法，无论是从速度还是显存，都是对比最优的，整体方法的效率，在大场景领域对比也是速度最快。再看精度，在Semantic3D、SemanticKITTI和S3DIS上，作者的方法也取得的非常好的效果。

实例分割和语义分割的区别是，语义分割是将每一个点进行分类，如桌子、椅子等。而实例分割不仅要分出这个点是什么类，还要分出来不同的物体，即桌子1、桌子2、椅子1、椅子2等。

点云的实例分割在深度学习中的发展最早的一篇工作是CVPR18的SPGN，目前一般可以分为两类方法：Proposal-based methods和Proposal-free methods。前者是基于检测的，即先检测出点云中每个物体的Bounding Box，点云中的BBox是一个长方体，然后在每一个BBox中进行物体和背景的点的分类。后者是不基于检测，直接通过点的特征进行聚类。两个方法都有优缺点。基于检测的，往往是两阶段的，也要进行NMS，速度较慢。不基于检测的虽然相比骨架速度较快，但是它的分割出来的物体的整体性比较差，而且需要比较麻烦的后处理，后处理主要是基于特征空间的度量。

因此作者希望能找到一种方法，结合两种方法的优点。即单阶段、不需要检测的锚点、端到端训练的一种方法——3D-BoNet。

整体思想很简单，即点云输入，然后特征提取，直接吐出来一系列的BBox，这些Bbox没有类别标签，就是一些框框，然后再在这些Bbox里进行点的分类。

说到这里是不是有些疑惑了，这不还是基于检测的吗？和基于检测有区别吗？我一开始也不能理解。其实要注意，这里生成的BBox首先是没有类别标签的，你可以理解成，它这个过程只是完成了二阶段检测任务的第一个阶段，即RPN阶段，预测出一堆可能存在物体的属于BBox，然后再在里面进行点的分类。

先说预测BBox部分，点云输入，提取一个特征，然后过几个FC即可得到一系列的BBox，而且这种方法是预设一个K值，表示预测的BBox的个数。在实际场景中，让K大于输入点云最大的实例数即可。

那得到了K个BBox之后，如何结合Groud Truth来进行监督学习呢？所以这设计到一个匹配问题。比如预测5个BBox，GT中有3个BBox，根据匹配算法，找到预测中的3个BBox，然后去回归这两个BBox，抑制另外2和BBox，这样就解决了监督学习的问题。

但是如何设计匹配算法呢？作者设计了3个标准：

1)  预测和GT的BBox的顶点的欧氏距离：空间距离越近越好；

2)  预测和GT的BBox的IoU：重合度越高越好；

3)  预测和GT的BBox交叉熵：预测的Bbox越大越好。

然后将上面三个部分的loss加和就得到最终的loss。

实验结果部分，提交的时候，在Scannet和S3DIS上，本算法是最优的。在速度上，相比之前的算法也是相对比较快的。

作者提了几个有意义的工作，值得各位未来去探索：

点云是一个非常有前景的研究领域，这个领域还有很多很多问题没有解决，希望大家如果感兴趣，就付诸努力，为这个领域添砖加瓦吧！