论文翻译 | RandLA-Net: Efficient Semantic Segmentation of Large-Scale Point Clouds

论文：RandLA-Net: Efficient Semantic Segmentation of Large-Scale Point Clouds
代码：code

前言：最近很犹豫要不要继续翻译点云方面的论文，直到看到这篇论文的作者是自己学校以前的学长，他的科研经历挺振奋人心的。突然觉得应该好好读一下他的文章。

摘要

我们研究了一个高效的大规模3D点云的语义分割问题。通过代价很高的下采样策略或高运算量的预处理或后处理步骤，大多数已有的方法只能在小规模点云上训练或运算。在这篇文章中，我们引入了RandLA-Net，一个高效且轻量级的神经架构来直接在大规模点云上推断语义信息。我们的方法的关键是用随机采样的点替代复杂的采样方案。尽管计算量和存储空间上高效，随机采样随机的丢掉一些关键点。为了克服它，我们引入了一个新型的局部特征聚合模块来逐步的增加3D点的感受野，因此高效的保留了一些几何信息。扩展实验展示了我们的RandLA-Net可以一次处理100万个点，比现有的方法快200个×。此外，我们的RandLA-Net在两个大规模的数据集Semantic3D和SemanticKITTI上都超过了当前的语义分割方法。

We study the problem of efficient semantic segmentation for large-scale 3D point clouds. By relying on expensive sampling techniques or computationally heavy pre/postprocessing steps, most existing approaches are only able to be trained and operate over small-scale point clouds. In this paper, we introduce RandLA-Net, an efficient and lightweight neural architecture to directly infer per-point semantics for large-scale point clouds. The key to our approach is to use random point sampling instead of more complex point selection approaches. Although remarkably computation and memory efficient, random sampling can discard key features by chance. To overcome this, we introduce a novel local feature aggregation module to progressively increase the receptive field for each 3D point, thereby effectively preserving geometric details. Extensive experiments show that our RandLA-Net can process 1 million points in a single pass with up to 200× faster than existing approaches. Moreover, our RandLA-Net clearly surpasses state-of-the-art approaches for semantic segmentation on two large-scale benchmarks Semantic3D and SemanticKITTI.

引言
大规模的3D点云的高效语义分割是一个实时智能系统上基础且重要的能力，比如自动驾驶和增强现实。一个重要的挑战是通过深度传感器获取的原始点云通常是不规则采样的，非结构的且无序的。尽管深度卷积网络展示了在结构化的2D视觉任务上的优秀的性能，它们却不能直接用在非结构化的数据上。

Efficient semantic segmentation of large-scale 3D point clouds is a fundamental and essential capability for realtime intelligent systems, such as autonomous driving and augmented reality. A key challenge is that the raw point clouds acquired by depth sensors are typically irregularly sampled, unstructured and unordered. Although deep convolutional networks show excellent performance in structured 2D computer vision tasks, they cannot be directly applied to this type of unstructured data.

近年来，里程碑式的工作PointNet掀起了一个直接处理3D点云的方法。它用共享的多层感知机学习到每个点的特征。这是在计算上很高效的，但是它却不能捕捉到每个点更宽的内容信息。为了学习更丰富的局部结构，许多专用的神经模块随后被迅速引入。这些模块通常可以被分为：1）相邻的特征池化2）基于图的信息传递 3）基于核的卷积 4）基于注意力机制的聚合。尽管这些方法在目标识别或语义分割任务上取得了令人印象深刻的效果，它们大多数还是限制在了小的3D点云上（4k points or 1×1 meter blocks），并且也不能不经过预处理的步骤比如块的分割，直接扩展到大的点云上。这样做的局限性有三点：第一，最常用的点的下采样方法要么计算量大要么占内存，比如一个最常用的快速点云下采样的方法，处理100万个点花200秒只能处理到10%。第二，已有的局部特征学习器通常依赖与计算量大的核化或图的构造，因此不能适用于大量的点云。第三，对于大规模点云来说，通常包括几百个物体，已有的局部特征学习器由于感受野受限，要么不能处理复杂的结构，要么不高效。

Recently, the pioneering work PointNet has emerged as a promising approach for directly processing 3D point clouds. It learns per-point features using shared multilayer perceptrons (MLPs). This is computationally efficient but fails to capture wider context information for each point. To learn richer local structures, many dedicated neural modules have been subsequently and rapidly introduced. These modules can be generally categorized as: 1) neighbouring feature pooling, 2) graph message passing , 3) kernel-based convolution, and 4) attentionbased aggregation. Although these approaches achieve impressive results for object recognition and semantic segmentation, almost all of them are limited to extremely small 3D point clouds (e.g., 4k points or 1×1 meter blocks) and cannot be directly extended to larger point clouds (e.g., millions of points and up to 200×200 meters) without preprocessing steps such as block partition. The reasons for this limitation are three-fold. 1) The commonly used point-sampling methods of these networks are either computationally expensive or memory inefficient. For example, the widely employed farthest-point sampling
takes over 200 seconds to sample 10% of 1 million points. 2) Most existing local feature learners usually rely on computationally expensive kernelisation or graph construction,thereby being unable to process massive number of points.3) For a large-scale point cloud, which usually consists of hundreds of objects, the existing local feature learners are either incapable of capturing complex structures, or do so inefficiently, due to their limited size of receptive fields.

目前的大量工作都开始着手解决直接在大规模点云上的处理的任务。SPG在应用神经网网络来学习每个点的语义信息之前将点云作为超图进行预处理。 FCPN和PCT结合了voxel化和点层的网络来处理大量的点云。尽管它们都取得了不错的分割精度，预处理和voxel化的操作在实际应用中计算量都太大了。

A handful of recent works have started to tackle the task of directly processing large-scale point clouds. SPG preprocesses the large point clouds as super graphs before applying neural networks to learn per super-point semantics. Both FCPN and PCT combine voxelization and point-level networks to process massive point clouds. Although they achieve decent segmentation accuracy, the preprocessing and voxelization steps are too computationally heavy to be deployed in real-time applications.

在这篇论文中，我们目的是设计一个计算量和存储量都很高效的架构，它可以一次性的，不用voxel化或模块划分或图构造的预处理方式直接处理大规模的3D点云。然而，这个任务是极具挑战性的，因为它要求：1.一个存储而计算都很高效的采样方式来逐步下采样大规模的点云来适应现在GPU的一些局限。2. 一个高效的局部特征聚合器来逐步增加感受野来保护复杂的几何结构。最后，我们首先系统证实了随机采样是深度神经网络有效处理大规模点云的关键促成因素。但是，随机采样会丢掉一些关键信息，特别是对稀疏点物体而言。为了对抗随机抽样的潜在有害影响，我们提出了一种新型的高效的局部特征聚合模块在逐步更小的点集上来捕获到复杂的局部结构。

In this paper, we aim to design a memory and computationally efficient neural architecture, which is able to directly process large-scale 3D point clouds in a single pass, without requiring any pre/post-processing steps such as voxelization, block partitioning or graph construction. However, this task is extremely challenging as it requires: 1) a memory and computationally efficient sampling approach to progressively downsample large-scale point clouds to fit in the limits of current GPUs, and 2) an effective local feature learner to progressively increase the receptive field size to preserve complex geometric structures.To this end, we first systematically demonstrate that random sampling is a key enabler for deep neural networks toefficiently process large-scale point clouds. However, random sampling can discard key information, especially for objects with sparse points. To counter the potentially detrimental impact of random sampling, we propose a new and efficient local feature aggregation module to capture complex local structures over progressively smaller point-sets.

在已有的下采样方法中，最远点采样和反密度采样是小规模点云最常用的采样方法。点采样是这些网络中的一个基础的步骤，我们在3.2节调研了不同方法的相对优势，我们发现最常用的采样方法限制了大点云的缩放，并且也是实时处理的一个重要瓶颈。然而，我们认为随机抽样是迄今为止最适合大规模点云处理的组件，因为它是快速和并且缩放很高效。随机采样也并不是没有成本的，因为突出的点的特征有可能会被偶然的丢失，它不能不造成性能损失的直接用于现有的网络中。为了克服这个问题，我们在3.3节设计了一个新的局部特征聚合的模块，它可以通过在每层逐步增加感受野的方式高效的学习复杂的局部结构。特别的，对每个3D点而言，我们首先引入了一个局部空间编码单元(LocSE) 来保护局部几何特征，其次，我们利用注意力池化来自动的保护有用的特征。第三，我们堆叠了多个LocSE单元和注意力池化的模块作为扩张的残余块，大大增加了每个点的有效接受野。注意到所有的这些组成都是用共享MLP实现的，这也是存储计算都很高效的。

Amongst existing sampling methods, farthest point sampling and inverse density sampling are the most frequently used for small-scale point clouds. As point sampling is such a fundamental step within these networks, we investigate the relative merits of different approaches in Section 3.2, where we see that the commonly used sampling methods limit scaling towards large point clouds, and act as a significant bottleneck to real-time processing. However, we identify random sampling as by far the most suitable component for large-scale point cloud processing as it is fast and scales efficiently. Random sampling is not without cost, because prominent point features may be dropped by chance and it cannot be used directly in existing networks without incurring a performance penalty. To overcome this issue, we design a new local feature aggregation module in Section 3.3, which is capable of effectively learning complex local structures by progressively increasing the receptive field size in each neural layer. In particular, for each 3D point, we firstly introduce a local spatial encoding (LocSE) unit to explicitly preserve local geometric structures. Secondly, we leverage attentive pooling to automatically keep the useful local features. Thirdly, we stack multiple LocSE units and attentive poolings as a dilated residual block, greatly increasing the effective receptive field for each point. Note that all these neural components are implemented as shared MLPs, and are therefore remarkably memory and computational efficient.

总之，我们建立了一个简单随机采样的准则和一个局部特征局部的方法，我们这个高效的方法叫做 RandLA-Net，不仅仅是在大规模的点云上快了不止200倍，并且也在两个基准数据集上Semantic3D 和 SemanticKITTI 超越了最新的语义分割的方法。图一展示了我们的方法：

Overall, being built on the principles of simple random sampling and an effective local feature aggregator, our efficient neural architecture, named RandLA-Net, not only is up to 200× faster than existing approaches on large-scale point clouds, but also surpasses the state-of-the-art semantic segmentation methods on both Semantic3D [17] and SemanticKITTI [3] benchmarks. Figure 1 shows qualitative results of our approach. Our key contributions are:

我们的贡献包括：
我们分析比较了已有的采样方法，确定随机抽样是最适合在大规模点云上有效学习的组件。
我们提出了一个高效的局部特征聚合模块通过增加每个点的感受野的方式来保护复杂的局部结构
我们证明了在基线上显著的内存和计算收益，并在多个大规模基准上超过了最先进的语义分割方法。

• We analyse and compare existing sampling approaches, identifying random sampling as the most suitable component for efficient learning on large-scale point clouds.
• We propose an effective local feature aggregation module to preserve complex local structures by progressively increasing the receptive field for each point.
• We demonstrate significant memory and computational gains over baselines, and surpass the state-of-the-art semantic segmentation methods on multiple large-scale benchmarks.

相关工作
为了提取3D点的特征，传统的方法经常依赖与手工提取的特征。最近基于学习的方法主要包括：基于投影法，voxel化的方法和基于点方案，这个将详述。

To extract features from 3D point clouds, traditional approaches usually rely on hand-crafted features. Recent learning based approaches mainly include projection-based, voxel-based and point-based schemes which are outlined here.

基于投影法和voxel化方法
为了更好的利用2DCNN，一些工作将3D点投影到2D图像上以此来解决目标识别的问题。然而，几何的细节会在投影中损失。替代的方案是，点云可以被 voxel化成一个三维的网格，因此就可以应用强大的3DCNN了。尽管它们在目标识别或语义分割领域取得了不错的成就，它们一个最大的限制就是计算量很大，特别是对于大规模点云而言。

(1) Projection and Voxel Based Networks. To leverage the success of 2D CNNs, many works
project/flatten 3D point clouds onto 2D images to address the task of object detection. However, geometric details may be lost during the projection. Alternatively, point clouds can be voxelized into 3D grids and then powerful 3D CNNs are applied in. Although they achieve leading results on semantic segmentation and object detection, their primary limitation is the heavy computation cost, especially when processing large-scale point clouds

基于点的网络
受到 PointNet/PointNet++的启发，一些最近的工作引入了一些复杂的模块来学习每个点的局部特征。这些模块可以被简单的分类为：1邻域特征池化 2图信息传递 3核卷积 4基于注意力机制。尽管这些工作在小点云上展现了强大的性能，大多数因为计算量和存储量的受限不能直接扩展到大规模的数据集场景。比起它们，我们的方法有三个突出之处：1它依赖的是网络的随机采样，因此只需要少得多的内存和计算量 2，提出的局部特征聚合模块可以通过不断的增加感受野来考虑到局部的空间关系和点的特征，因此在复杂的局部图案上更高效鲁棒 3整个网络只用共享的MLP组成不依赖图卷积或核化的方式，因此对于大规模的点云非常有效。

(2) Point Based Networks. Inspired by PointNet/PointNet++, many recent works introduced sophisticated neural modules to learn per-point local features. These modules can be generally classified as 1) neighbouring feature pooling , 2) graph message passing, 3) kernel-based convolution , and 4) attention-based aggregation. Although these networks have shown promising results on small point clouds, most of them cannot directly scale up to large scenarios due to their high computational and memory costs. Compared with them, our proposed RandLA-Net is distinguished in three ways: 1) it only relies on random sampling within the network, thereby requiring much less memory and computation; 2) the proposed local feature aggregator can obtain successively larger receptive fields by explicitly considering the local spatial relationship and point features, thus being more effective and robust for learning complex local patterns; 3) the entire network only consists of shared MLPs without relying on any expensive operations such as graph
construction and kernelisation, therefore being superbly efficient for large-scale point clouds.

对于大规模点云的学习
SPG预处理了大的点云网络作为超点图来学习每个点的超点语义。最近的FCPN和PCT 都依赖与基于voxel或基于点的网络来处理大量的点云。然而，图分割和voxel化的方法计算量都很大。相反， RandLA-Net的方法是一个不需要额外预处理或后处理的一种端到端的可学习的方法。

(3) Learning for Large-scale Point Clouds. SPG preprocesses the large point clouds as superpoint graphs to learn per super-point semantics. The recent FCPN and PCT apply both voxel-based and point-based networks to process the massive point clouds. However, both the graph partitioning and voxelisation are computationally expensive. In constrast, our RandLA-Net is end-to-end trainable without requiring additional pre/post-processing steps.

RandLA-Net

总述
正如图2所示那样，给定有一个跨越数百米的数百万个点的大规模点云，来用深度神经网络的方法处理它，这就不可避免的要求这些点要逐渐且高效的，却不损失信息的在每层神经元处下采样。RandLA-Net中，我们提出了一种用简单且快速的方法来随机采样来减少点的密度，同时应用一个精心设计的本地特性聚合器来保留突出的特性。这使得整个网络能够在有效效率和有效性之间实现良好的权衡。

As illustrated in Figure 2, given a large-scale point cloud with millions of points spanning up to hundreds of meters, to process it with a deep neural network inevitably requires those points to be progressively and efficiently downsampled in each neural layer, without losing the useful point features. In our RandLA-Net, we propose to use the simple and fast approach of random sampling to greatly decrease point density, whilst applying a carefully designed local feature aggregator to retain prominent features. This allows the entire network to achieve an excellent trade-off between efficiency and effectiveness.

寻求高效的采样

已有的点采样的方法可以被粗略的分类到启发式方法和基于学习的方法。然而，，现在没有一个适合大规模点云的标准的采样方法。因此，我们分析并比较了它们的相对优势和复杂度。

Existing point sampling approaches can be roughly classified into heuristic and learning based approaches. However, there is still no standard sampling strategy that is suitable for large-scale point clouds.Therefore, we analyse and compare their relative merits and complexity as follows.

基于启发式的采样
最远点采样：为了从大规模的N个点的点云中采样K个点，FPS返回了一个度量空间 {p1 · · · pk · · · pK}，这样每个pk就是前k-1个点的最远点。FPS被广泛用于小点集的语义分割。虽然它能很好地覆盖整个点集，但其计算复杂度为O(n2)。对于一个大规模的点云(N∼106次方)，FPS在单个GPU上处理需要多达200秒。这说明FPS不适用于大尺度的点云。

Farthest Point Sampling (FPS): In order to sample K points from a large-scale point cloud P with N points, FPS returns a reordering of the metric space {p1 · · · pk · · · pK}, such that each pk is the farthest point from the first k 1 points. FPS is widely used in for semantic segmentation of small point sets. Although it has a good coverage of the entire point set, its computational complexity is O(N2). For a large scale point cloud (N ~ 106次方), FPS takes up to 200 seconds to process on a single GPU. This shows that FPS is not suitable for large-scale point clouds.

反密度重要性抽样
为了在N个点中采样K个点，IDIS根据每个点的密度重新排序，然后选择前K个点。其计算复杂度约为O(N)。根据经验，处理106次方个点需要10秒。与FPS相比，IDIS的效率更高，但对异常值也更敏感。然而，它在实时系统中使用仍然太慢。

Inverse Density Importance Sampling (IDIS): To sample K points from N points, IDIS reorders all N points according to the density of each point, after which the top K points are selected. Its computational complexity is approximately O(N). Empirically, it takes 10 seconds to process 106 points. Compared with FPS, IDIS is more efficient, but also more sensitive to outliers. However, it is still too slow for use in a real-time system.

随机采样
随机抽样从原始的N个点中统一选择K个点。它的计算复杂度是O（1），这与输入点的总数无关，即它是恒定时间的，因此具有可伸缩的。与FPS和IDIS相比，无论输入点云的规模如何，随机采样的计算效率都最高。处理106次方个点只需要0.004秒。

Random Sampling (RS): Random sampling uniformly selects K points from the original N points. Its computational complexity is O(1), which is agnostic to the total number of input points, i.e., it is constant-time and hence inherently scalable. Compared with FPS and IDIS, random sampling has the highest computational efficiency, regardless of the scale of input point clouds. It only takes 0.004s to process 106 points.

基于学习的采样
基于生成器的采样(GS)：GS学习生成一个小的点集来近似地表示原始的大的点集。然而，FPS通常用于在推理阶段将生成的子集与原始子集进行匹配，这样会产生额外的计算。在我们的实验中，采样106次方个点的10%需要1200秒。

Generator-based Sampling (GS): GS learns to generate a small set of points to approximately represent the original large point set. However, FPS is usually used in order to match the generated subset with the original set at inference stage, incurring additional computation. In our experiments, it takes up to 1200 seconds to sample 10% of 106 points.

基于连续松弛的采样(CRS)：CRS方法使用重新参数化技巧将采样操作放松到一个连续域进行端到端训练。特别地，每个采样点都是基于点云的加权和学习的。当同时采样所有新点时，它会产生一个大的权重矩阵，导致一个负担不起的内存成本。例如，估计采样106次方个点中的10%需要超过100GB的内存占用。

Continuous Relaxation based Sampling (CRS): CRS approaches use the reparameterization trick to relax the sampling operation to a continuous domain for end-to-end training. In particular, each sampled point is learnt based on a weighted sum over the full point clouds. It results in a large weight matrix when sampling all the new points simultaneously with a one-pass matrix multiplication, leading to an unaffordable memory cost. For example, it is estimated to take more than a 300 GB memory footprint to sample 10% of 106 points.

基于策略梯度的抽样(PGS)：PGS将采样操作定义为一个马尔可夫决策过程。它依次学习一个概率分布来采样这些点。但当点云较大时，由于勘探空间极大，学习概率的方差较大。例如，对106次方个点中的10%进行采样，勘探空间为C105 106 ，不太可能学习到有效的采样策略。经验表明，如果将PGS用于大点云，网络很难收敛。

Policy Gradient based Sampling (PGS): PGS formulates the sampling operation as a Markov decision process. It sequentially learns a probability distribution to sample the points. However, the learnt probability has high variance due to the extremely large exploration space when the point cloud is large. For example, to sample 10% of 106 points, the exploration space is C 105 106 and it is unlikely to learn an effective sampling policy. We empirically find that the network is difficult to converge if PGS is used for large point clouds.

总之，FPS, IDIS 和 GS对于大规模点云应用计算量都太大了。 CRS方法内存占用过多，PGS很难学习。相反的是，随机采样有以下优点：1.计算很高效，和输入的点数无关 2它不需要额外的计算内存 。因此，我们可以有把握地得出结论，与所有现有的替代方案相比，随机抽样是迄今为止处理大规模点云的最合适的方法。然而，随机抽样可能会导致许多有用的点特征被丢弃。为了克服这个问题，我们提出了一个功能强大的局部特性聚合模块，如下一节所述。

Overall, FPS, IDIS and GS are too computationally expensive to be applied for large-scale point clouds. CRS approaches have an excessive memory footprint and PGS is hard to learn. By contrast, random sampling has the following two advantages: 1) it is remarkably computational efficient as it is agnostic to the total number of input points, 2) it does not require extra memory for computation. Therefore, we safely conclude that random sampling is by far the most suitable approach to process large-scale point clouds compared with all existing alternatives. However, random sampling may result in many useful point features being dropped. To overcome it, we propose a powerful local feature aggregation module as presented in the next section.

局部特征聚合
正如图3所示，我们的局部特征聚合模块并行的应用到每个3D点，它包括了三个神经元单元。1 局部空间编码LocSE，2注意力池化 3扩张残差块

As shown in Figure 3, our local feature aggregation module is applied to each 3D point in parallel and it consists of three neural units: 1) local spatial encoding (LocSE), 2) attentive pooling, and 3) dilated residual block.

局部空间编码
给一个有着每个点特征的点云P，这个局部空间编码单元显示的嵌入了点每个邻域的x-y-z的坐标，这样的对应点特征总是注意到了它的相对空间位置。这使得LocSE单元显示的注意了局部的几何图案，因此最终使网络学习到复杂的局部结构。特别是，这个单元包括以下步骤：

(1) Local Spatial Encoding
Given a point cloud P together with per-point features (e.g., raw RGB, or intermediate learnt features), this local spatial encoding unit explicitly embeds the x-y-z coordinates of all neighbouring points, such that the corresponding point features are always aware of their relative spatial locations. This allows the LocSE unit to explicitly observe the local geometric patterns, thus eventually benefiting the entire network to effectively learn complex local structures. In particular, this unit includes the following steps:

找邻域：对第i个点，它的邻点被最近邻KNN算法收集。KNN是基于点的欧几里得空间的。
相对位置编码：对每个Pi最近的K个点，我们按如下来编码它的相对位置：

Finding Neighbouring Points. For the ith point, its neighbouring points are firstly gathered by the simple K nearest neighbours (KNN) algorithm for efficiency. The KNN is based on the point-wise Euclidean distances.
Relative Point Position Encoding. For each of the nearest K points {p1i· · · pki· · · pKi } of the center point pi , we explicitly encode the relative point position as follows:

pi和pik是三维坐标点，⊕ 是cat操作， || · || 计算邻点对中心点的欧几里得距离。rki似乎编码了不需要的点位置。有趣的是，这往往有助于网络学习局部特征，并在实践中获得良好的性能。

where pi and pki are the x-y-z positions of points, ⊕ is the concatenation operation, and || · || calculates the Euclidean distance between the neighbouring and center points. It seems that rki
is encoded from redundant point positions. Interestingly, this tends to aid the network to learn local features and obtains good performance in practice.

点的特征增强
对每个邻点，编码的相对点位置连接了对应的点的特征，得到一个增强特征

Point Feature Augmentation. For each neighbouring point pki, the encoded relative point positions rki are concatenated with its corresponding point features fik, obtaining an augmented feature vector ˆfik.

最终， LocSE单元的输出是一个新的邻域集合ˆFi = {ˆfi1 · · ·ˆfik · · ·ˆfiK}，显示的编码了中心点局部几何结构。我们注意到最近的工作也用电的位置来提升语义分割。然而，位置被用于学习点的分数，而我们的LocSE 显示的编码了相对位置来增强邻点特征。

Eventually, the output of the LocSE unit is a new set of neighbouring features ˆFi = {ˆfi1 · · ·ˆfik · · ·ˆfiK}, which explicitly encodes the local geometric structures for the center point pi. We notice that the recent work [36] also uses point positions to improve semantic segmentation. However, the positions are used to learn point scores in [36], while our LocSE explicitly encodes the relative positions to augment the neighbouring point features.