Learning Semantic Segmentation of Large-Scale Point Clouds with Random Sampling

We study the problem of efficient semantic segmentation of large-scale 3D point clouds. By relying on expensive sampling techniques or computationally heavy pre/post-processing 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. Comparative experiments show that our RandLA-Net can process 1 million points in a single pass up to 200x faster than existing approaches. Moreover, extensive experiments on five large-scale point cloud datasets, including Semantic3D, SemanticKITTI, Toronto3D, NPM3D and S3DIS, demonstrate the state-of-the-art semantic segmentation performance of our RandLA-Net.


INTRODUCTION
E FFICIENT semantic segmentation of large-scale 3D point clouds is a fundamental and essential capability for real-time 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.
A handful of recent works have started to tackle the task of directly processing large-scale point clouds. SPG [2] preprocesses the large point clouds as super graphs before applying neural networks to learn per super-point semantics. However, the preprocessing steps are too computationally heavy to be deployed in real-time applications. Both FCPN [32] and PCT [33] combine voxelization and pointlevel networks to process massive point clouds. However, they still partition the point clouds into small blocks for learning, resulting in the overall performance being suboptimal.
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 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 to efficiently process largescale 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.
Amongst existing sampling methods, farthest point sampling and inverse density sampling are the most frequently used for small-scale point clouds [1], [7], [19], [34], [35]. 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 a more suitable strategy 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.
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 Semantic3D [36], SemanticKITTI [3] and Toronto-3D [37] benchmarks. Figure 1 shows qualitative results of our approach. Our key contributions are: • We analyse and compare existing sampling approaches, identifying random sampling as a 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.
A preliminary version of this work has been published in [38] and our code is available at https://github.com/QingyongHu/RandLA-Net.
(1) Projection and Voxel-Based Networks. To leverage the success of 2D CNNs, many works [49], [50], [51], [52] project/flatten 3D point clouds onto 2D images to address the task of object detection. However, geometric details may be lost during projection. For example, the commonlyused birds-eye-view projection can drop some points due to occlusion. Alternatively, several other approaches [53], [54], [55], [56], [57] use spherical projection to convert the LiDAR point clouds back to raw range images without dropping points. However, these methods usually suffer from blurry CNN outputs and quantization errors in practice [53]. Point clouds can also be voxelized into dense 3D grids and then processed with powerful 3D CNNs [58], [59], [60]. However, their memory consumption and computational time are significant if a high voxel grid resolution is required. This issue can be alleviated using Octree [61] or sparse-tensor [62], [63], but these advanced data structures and sophisticated operations are not always easily supported by existing tools, especially on GPUs.
(2) Point Based Networks. Inspired by Point-Net/PointNet++ [1], [4], many recent works introduced sophisticated neural modules to learn per-point local features. These modules can be generally classified as 1) neighbouring feature pooling [5], [6], [7], [8], 2) graph message passing [9], [10], [11], [12], [13], [14], [15], [64], 3) kernelbased convolution [17], [18], [19], [20], [21], [22], [23], [24], [65], and 4) attention-based aggregation [28], [29], [30], [31]. 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  1 the complexity denotes the actual computational complexity when sampling M points from a large-scale point cloud P with N points, K denotes the number of nearest neighbours. 2 The time consumption is computed for sampling 10% points from 1 million points. We use the same hardware as in Section 3.5, unless specified otherwise. 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 coupled with the simple random sampling, therefore being efficient for large-scale point clouds.
(3) Learning for Large-scale Point Clouds. SPG [2] preprocesses the large point clouds as superpoint graphs to learn per superpoint semantics. However, both the geometric partition and superpoint graph construction are computationally expensive. The recent FCPN [32] and PCT [33] apply both voxel-based and point-based networks to process the massive point clouds. Based on the assumption that points are sampled from locally Euclidean surfaces, TangentConv [66] firstly projects the local surface on the tangent plane and then operates on the projected geometry. Despite being able to process large-scale point clouds, it requires a relatively heavy preprocessing step to calculate the normal. In contrast, our RandLA-Net is end-to-end trainable without requiring additional expensive operations.
(4) Sampling Methods for 3D Point Clouds. Existing point sampling approaches [1], [19], [34], [35], [40], [41] can be roughly classified into heuristic and learning-based methods. Farthest point sampling [1], [34] is the most commonly used heuristic sampling strategy in recent works. It iteratively samples the points most distant to the remaining subset from the entire point set. Groh et al. [35] use inverse density importance sub-sampling (IDIS) to preserve points with lower density. Hermosilla et al. [67] utilize Poisson disk sampling (PDS) to achieve a uniform distribution for the sampled points. For learning-based approaches, Yang et al. [30] introduce Gumbel subset sampling, an end-toend learnable and task-agnostic sampling method, to obtain better performance for downstream tasks. Dovrat et al [40] propose a generater network to directly generate a point set to approximate the original point set. However, all these methods are either ineffective or computationally heavy as evaluated in Section 3.2 and Table 1.

Overview
As illustrated in Figure 2, given a large-scale point cloud with millions of points which could span 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.     Fig. 3: The proposed local feature aggregation module. The top panel shows the local spatial encoding block that extracts features, and the attentive pooling mechanism that weights the important neighbouring features, based on the local context and geometry. The bottom panel shows how two of these components are chained together, to increase the receptive field size, within a residual block.

The quest for efficient sampling
To determine the most suitable method for processing largescale point clouds, we provide an empirical analysis and comparison of different sampling approaches. In particular, the relative merits and complexity of the commonly used sampling strategies are shown in Table 1.
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. PDS is relatively faster, but has worse performance, as shown in the ablation study. 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 believe that random sampling is more suitable than other approaches to efficiently process large-scale point clouds. 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.

Local Feature Aggregation
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.
(1) Local Spatial Encoding Given a point cloud P together with per-point features (e.g., raw RGB, or intermediate learned 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: Finding Neighbouring Points. For the i th point, its neighbouring points are firstly gathered by the simple K-nearest neighbours (KNN) algorithm for efficiency. The KNN is based on point-wise Euclidean distances.
Relative Point Position Encoding. For each of the nearest K points {p 1 i · · · p k i · · · p K i } of the center point p i , we explicitly encode the relative point position as follows: where p i and p k i are the absolute x-y-z positions of points, ⊕ is the concatenation operation, and || · || calculates the Euclidean distance between the neighbouring and center points. It seems that r k i 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 p k i , the encoded relative point positions r k i are concatenated with its corresponding point features f k i , obtaining an augmented feature vectorf k i . For simplicity, we keep the feature vectors r k i and f k i with the same dimension in the implementation, but they are flexible and can have different dimensions.
Eventually, the output of the LocSE unit is a new set of neighbouring featuresF i = {f 1 i · · ·f k i · · ·f K i }, which explicitly encodes the local geometric structures for the center point p i . We notice that the recent work [68] also uses point positions to improve semantic segmentation. However, the positions are used to learn point scores in [68], while our LocSE explicitly encodes the relative positions to augment the neighbouring point features.
(2) Attentive Pooling This neural unit is used to aggregate the set of neighbouring point featuresF i . Existing works [1], [34] typically use max/mean pooling to hard integrate the neighbouring features, resulting in the majority of the information being lost. By contrast, we turn to the powerful attention mechanism to automatically learn important local features. In particular, inspired by [69], our attentive pooling unit consists of the following steps.  Computing Attention Scores. Given the set of local featureŝ we design a shared function g(·) to learn a unique attention score for each feature. Essentially, the function g(·) consists of a shared MLP followed by sof tmax. It is formally defined as follows: where W is the learnable weights of a shared MLP. Weighted Summation. The learned attention scores can be regarded as a soft mask which automatically selects the important features. Formally, these features are weighted summed as follows:f where is the element-wise product. To summarize, given the input point cloud P , for the i th point p i , our LocSE and Attentive Pooling units learn to aggregate the geometric patterns and features of its K nearest points, and finally generate an informative feature vectorf i .

(3) Dilated Residual Block
Since the large point clouds are going to be substantially downsampled, it is desirable to significantly increase the receptive field for each point, such that the geometric details of input point clouds are more likely to be preserved, even if some points are dropped. As shown in Figure 3, inspired by the successful ResNet [70] and the effective dilated networks [71], we stack multiple LocSE and Attentive Pooling units to achieve the dilation of point receptive fields, and add a skip connection to achieve residual learning.
To further illustrate the capability of our dilated residual block, Figure 5 shows that the red 3D point observes K neighbouring points after the first LocSE/Attentive Pooling operation, and then is able to receive information from up to K 2 neighbouring points i.e. its two-hop neighbourhood after the second. This is a cheap way of dilating the receptive field and expanding the effective neighbourhood through feature propagation. Theoretically, the more units we stack, the more powerful this block as its sphere of reach becomes greater and greater. However, more units would inevitably sacrifice the overall computation efficiency. In addition, the entire network is likely to be over-fitting. In our RandLA-Net, we simply stack two sets of LocSE and Attentive Pooling as the standard residual block, achieving a satisfactory balance between efficiency and effectiveness. Overall, our local feature aggregation module is designed to effectively preserve complex local structures via explicitly considering neighbouring geometries and significantly increasing receptive fields. Moreover, this module only consists of feed-forward MLPs, thus being computationally efficient. Figure 4 shows the detailed architecture of RandLA-Net, which stacks multiple local feature aggregation modules and random sampling layers. The network follows the widely-used encoder-decoder architecture with skip connections. The input point cloud is first fed to a shared MLP layer to extract per-point features. Four encoding and decoding layers are then used to learn features for each point. At last, three fully-connected layers and a dropout layer are used to predict the semantic label of each point. Note that, our RandLA-Net can be wider and deeper by altering the number of layers, feature channels, and adjusting the sampling rate. However, larger models require additional computation and may more easily lead to overfitting. The details of each component are as follows:

Network Architecture
Network Input: The input is a large-scale point cloud with a size of N × d in (the batch dimension is dropped for simplicity), where N is the total number of input points, d in is the feature dimension of each input point. For both S3DIS [72] and Semantic3D [36] datasets, each point is represented by its 3D coordinates and color information (i.e., x-y-z-R-G-B), while each point of the SemanticKITTI [3] dataset is only represented by 3D coordinates.
Encoding Layers: Four encoding layers are used in our network to progressively reduce the size of the point clouds and increase the per-point feature dimensions. Each encoding layer consists of a local feature aggregation module (Section 3.3) and a random sampling operation (Section 3.2). The point cloud is downsampled with a four-fold decimation ratio. In particular, only 25% of the point features are retained after each layer, i.e., . Meanwhile, the per-point feature dimension is gradually increased each layer to preserve more information, i.e., Decoding Layers: Four decoding layers are used after the encoding layers. For each layer in the decoder, we adopt the nearest-neighbor interpolation for efficiency and simplicity. In particular, the coordinates of all downsampled points in each encoding layer are temporally stored for reference. For each query point in the decoding layers, we use the KNN algorithm to find the nearest neighboring point from the points of the previous layer. The features of the nearest point are copied to the target point. Subsequently, the upsampled feature maps are concatenated with the intermediate feature maps produced by encoding layers through skip connections, after which a shared MLP is applied to the concatenated feature vectors.

Final Semantic Prediction:
The final semantic label of each point is obtained through three shared fully-connected layers ( N , 64) → ( N , 32) → ( N , n class ) and a dropout layer. The dropout ratio is 0.5.

Network Output:
The output of RandLA-Net is the predicted semantics of all points, with a size of N × n class , where n class is the number of classes.

Implementation
We use the same network architecture for all the five largescale open datasets, Semantic3D [36], SemanticKITTI [3], Toronto-3D [37], NPM3D [73], S3DIS [72]. The Adam optimizer [74] with default parameters is applied. The initial learning rate is set to 0.01 and decreases by 5% after each epoch. The network is trained for 100 epochs. We implement the KNN search in our framework based on the nanoflann 1 package, which leverages an efficient KD-Tree data structure for fast search and query. In addition, we also use OpenMP for better parallelization, and the number of nearest points K is set to 16. For several extremely large datasets such as Semantic3D [36], which have more than 10 6 or even 10 8 points in a single point cloud, we crop sub-clouds to feed into our RandLA-Net. During training, we sample a fixed number of points (∼ 10 5 ) from each point cloud as the input for parallelization. During testing, we iteratively infer several sub-clouds with overlaps to eventually cover all 3D points. Since many points have been inferred more than once, we follow [23] to use a simple voting scheme for better 1. https://github.com/jlblancoc/nanoflann performance. To alleviate the problem of class imbalance, we use weighted cross-entropy as the loss function. In particular, the weight of each class is determined by its inverse frequency in the training split. We do not use any explicit data augmentation techniques such as rotation, scaling, and translation during training. Note that, our random downsampling in each encoding layer can be regarded as implicit data augmentation. All experiments are conducted on an NVIDIA RTX2080Ti GPU.

EXPERIMENTS
We first evaluate the efficiency of existing sampling approaches in Section 4.1, and compare the efficiency of our RandLA-Net with existing networks in Section 4.2. Secondly, we conduct extensive experiments on multiple benchmarks to compare the semantic segmentation in Section 4.3. At last, our ablation study is presented in Section 4.4.

Efficiency of Random Sampling
In this section, we empirically evaluate the efficiency of existing sampling approaches including FPS, IDIS, PDS, RS, GS, CRS, and PGS, which have been discussed in Section 3.2. In particular, we conduct the following 4 groups of experiments.
• Group 1. Given a small-scale point cloud (∼ 10 3 points), we use each sampling approach to progressively downsample it. Specifically, the point cloud is downsampled by five steps with only 25% points being retained in each step on a single GPU i.e. a four-fold decimation ratio. This means that there are only ∼ (1/4) 5 × 10 3 points left in the end. This downsampling strategy emulates the procedure used in PointNet++ [1]. For each sampling approach, we sum up its time and memory consumption for comparison. • Group 2/3/4. The total number of points is increased towards large-scale, i.e., around 10 4 , 10 5 and 10 6 points respectively. We use the same five sampling steps as in Group 1. Analysis. Figure 6 compares the total time and memory consumption of each sampling approach to process different scales of point clouds. It can be seen that: 1) For small-scale point clouds (∼ 10 3 ), all sampling approaches tend to have similar time and memory consumption, and are unlikely to incur a heavy or limiting computation burden. 2) For largescale point clouds (∼ 10 6 ), FPS/IDIS/PDS/GS/CRS/PGS are either extremely time-consuming or memory-costly for large-scale computation. By contrast, random sampling has superior time and memory efficiency overall. This result clearly demonstrates that most existing networks [1], [7], [19], [30], [34], [68] are only able to be optimized on small blocks of point clouds primarily because they rely on the expensive sampling approaches. Motivated by this, we use the efficient random sampling strategy in our RandLA-Net.

Efficiency of RandLA-Net
In this section, we systematically evaluate the overall efficiency of our RandLA-Net on real-world large-scale point clouds for semantic segmentation. Particularly, we evaluate RandLA-Net on the SemanticKITTI [3] dataset, showing the  The runtime decomposition and peak memory of different approaches for semantic segmentation of input point clouds with 12×81920 (∼ 10 6 ) points, which is sampled from the LiDAR point clouds on Sequence 08 (around 80K-120K points per frame) of the SemanticKITTI [3] dataset. In particular, † this is achieved by inference half of the input point clouds twice, since PointNet is unable to process the whole inputs in a single pass. ‡ The original implementation of PointNet++ adopts an extremely inefficient KNN during trilinear interpolation. Hence, we also report the result of re-implemented PointNet++ * for a fair comparison. Note that, because SPG does not have explicit sampling and neighboring search modules, its runtime decomposition is not reported. We measure the peak memory consumption based on the TensorFlow profiler (https://www.tensorflow.org/guide/profiler). Note the peak memory may be different from the actual allocated GPU memory. detailed runtime of each component. We also evaluate the time consumption of recent representative works [1], [2], [4] on the same dataset. For a fair comparison, we feed the same number of points (i.e., 12×81920, the batch size is 12) from the sequence into each neural network.
In addition, we also evaluate the memory consumption of RandLA-Net and the baselines. In particular, we report the peak memory (GPU) of each network with the same input point clouds during inference. Note that, all experiments are conducted on the same machine with an AMD 3700X @3.6GHz CPU and an NVIDIA RTX2080Ti GPU.
Analysis. Table 2 quantitatively shows the total time and memory consumption of different approaches. It can be seen that, 1) SPG [2] has the lowest GPU memory consumption, but takes the longest time to process the point clouds due to the expensive geometrical partitioning and super-graph construction steps; 2) PointNet++ [1] is also computationally expensive mainly because of the FPS sampling operation; 3) PointNet [4] are unable to take extremely large-scale point clouds (e.g. 10 6 points) in a single pass due to their memory inefficient operations. 4) Thanks to the simple random sampling together with the efficient MLP-based local feature aggregator, our RandLA-Net takes around 0.5s to infer the semantic labels of large-scale point clouds with nearly 1 million points (12×81920 points).

Semantic Segmentation on Benchmarks
In this section, we evaluate the semantic segmentation of our RandLA-Net on multiple large-scale public datasets: the outdoor Semantic3D [36], SemanticKITTI [3], Toronto-3D [37], NPM3D [73], and the indoor S3DIS [72]. For a fair comparison, we follow KPConv [23] to pre-process the whole input point clouds by using the grid-sampling strategy at the beginning. In fact, this is likely to reduce the point density and help increase the actual receptive field for each 3D point.
(1) Evaluation on Semantic3D The Semantic3D dataset [36] consists of 15 point clouds for training and 15 for online testing. Each point cloud has up to 10 8 points, covering up to 160×240×30 meters in realworld 3D space. The raw 3D points belong to 8 classes and contain 3D coordinates, RGB information, and intensity. We only use the 3D coordinates and color information to train and test our RandLA-Net. Overall Accuracy (OA) and mean Intersection-over-Union (mIoU) of all classes are used as the evaluation metrics. For a fair comparison, we only include the results of recently published strong baselines [2], [8], [12], [23], [75], [76], [77], [78] and the current state-of-the-art approach RGNet [79]. Table 3 presents the quantitative results of different approaches achieved on the reduced-8 test set. RandLA-Net clearly outperforms all existing methods in terms of both mIoU and OA. Notably, RandLA-Net also achieves superior performance on six of the eight classes, except low vegetation and scanning artefact. We also report the results on semantic-8 subset on Table 4. Note that, compared with the reduced-8 subset, the semantic-8 subset has 10× more points and much stronger category imbalance, and therefore it is more challenging. Our RandLA-Net also achieves the best performance in terms of overall accuracy, but ranks third in mIoU performance, primary because ConvPoint [86] and SPGraph [2] achieves much better results on hard scape and scanning artifact. Figure 7 shows the qualitative results of RandLA-Net on this dataset.
(3) Evaluation on Toronto-3D The Toronto-3D dataset [37] consists of 78.3 million points acquired by the mobile laser systems (MLS), which covers approximately 1KM of urban outdoor 3D space. Following [37], the section L002 is used for testing and the remaining three sections are used for training. OA and mIoU over 8 categories are used as evaluation metrics. Table 6 reports the quantitative results achieved by our RandLA-Net with several recently published baselines [1], [9], [23], [37], [87], [88], and Figure 9 shows the qualitative results. Note that, only the 3D coordinates of each point are feed into the network for fair comparison [37]. It can be seen that our RandLA-Net achieves the best results on this dataset in terms of mIoU, improving the previous state-ofthe-art MS-TGNet [37] from 70.50% to 77.71%.
It is observed that Road marking is the hardest to be recognized by all approaches. Primarily, this is because the pure geometric patterns of Road marking can not be easily   distinguished against its neighbourhood. Particularly, given only 3D coordinates of points, it is virtually impossible to differentiate the Road marking and Road, as illustrated in Figure 9. This motivates us to include the appearance of points to further improve the accuracy. We simply train our RandLA-Net with both 3D coordinates and color information as input. As shown in the last row of Table 6, the IoU score of Road marking has been significantly improved by 22%, demonstrating the importance of appearance in this difficult case.

(4) Evaluation on NPM3D
The NPM3D dataset [73] is a large-scale and high-quality urban point clouds dataset. Similar to the Toronto-3D dataset, the NPM3D dataset also consists of around 2KM MLS point cloud acquired in two cities. The mean IoU (mIoU) of the total 10 classes are used as the main evaluation metric. Table 7 quantitatively shows the results achieved by our RandLA-Net and exiting baselines [23], [77], [83], [86], [90], [91]. In this dataset, only the 3D coordinates of each point is available. Due to the relatively lower scores of two minority classes Trash can and Pedestrian, our RandLA-Net achieves a mean IoU score of 78.5%, ranking after the latest LightConvPoint [83] and KPConv [23]. Primarily, the point features of Trash can and Pedestrian are very likely to be randomly dropped in our RandLA-Net because the two categories only have extremely small number of points scanned.

(5) Evaluation on S3DIS
The S3DIS dataset [72] consists of 271 rooms belonging to 6 large areas. Each point cloud is a medium-sized single room (∼ 20×15×5 meters) with dense 3D points. To evaluate the semantic segmentation of our RandLA-Net, we use the   standard 6-fold cross-validation in our experiments. The mean IoU (mIoU), mean class Accuracy (mAcc) and Overall Accuracy (OA) of the total 13 classes are compared. Table 8 quantitatively compares the performance of our RandLA-Net with existing baselines on this dataset. Our RandLA-Net achieves on-par or better performance than state-of-the-art methods. Note that, most of these baselines [1], [7], [8], [9], [34], [95] tend to use sophisticated but expensive operations or samplings to optimize the networks on small blocks (e.g., 1×1 meter) of point clouds, and the relatively small rooms act in their favours to be divided into tiny blocks. By contrast, RandLA-Net is able to take the entire rooms as input and efficiently infer per-point semantics in a single pass.

Ablation Studies
Since the impact of random sampling is fully studied in Section 4.1, we conduct the following ablation studies for our local feature aggregation module. All ablated networks are trained on sequences 00∼07 and 09∼10, and tested on the sequence 08 of SemanticKITTI dataset [3].

Ablation of RandLA-Net Framework
Since our RandLA-Net stacks multiple of our key components: LocSE, Attentive Pooling and Dilated Residual Block, we therefore conduct the following 5 ablation studies to demonstrate the effectiveness of each component.
(1) Removing local spatial encoding (LocSE). This unit enables each 3D point to explicitly observe its local geometry. After removing locSE, we directly feed the local point features into the subsequent attentive pooling.
(2∼4) Replacing attentive pooling by max/mean/sum pooling. The attentive pooling unit learns to automatically combine all local point features. By comparison, the widely used max/mean/sum poolings tend to hard select or combine features, therefore their performance may be sub-optimal.    (5) Simplifying the dilated residual block. The dilated residual block stacks multiple LocSE units and attentive poolings, substantially dilating the receptive field for each 3D point. By simplifying this block, we use only one LocSE unit and attentive pooling per layer, i.e. we do not chain multiple blocks as in our original RandLA-Net. Table 9 compares the mIoU scores of all ablated networks. From this, we can see that: 1) The greatest impact is caused by the removal of the chained spatial embedding and attentive pooling blocks. This is highlighted in Figure  5, which shows how using two chained blocks allows in- formation to be propagated from a wider neighbourhood, i.e. approximately K 2 points as opposed to just K. This is especially critical with random sampling, which is not guaranteed to preserve a particular set of points.
2) The removal of the local spatial encoding unit shows the next greatest impact on performance, demonstrating that this module is necessary to effectively learn local and relative geometry context. 3) Removing the attention module diminishes performance by not being able to effectively retain useful features. From this ablation study, we can see how the proposed neural units complement each other to attain our state-of-the-art performance.

Ablation of LocSE
As designed in Section 3.3, our LocSE component encodes the relative point position based on the following equation: We further investigate the effects of different spatial information in our framework. Particularly, we conduct the following 8 ablative experiments for LocSE:  Table 10 compares the mIoU scores of our network with different designs of LocSE. We can see that: 1) Explicitly encoding all spatial information leads to the highest mIoU scores. 2) The relative position p i − p k i plays an important role in the LocSE component, primarily because the relative point position enables the network to be aware of the local geometric patterns. 3) Only encoding the point position p i , p k i or Euclidean distance ||p i − p k i || is sub-optimal, because the individual point positions and distance only are less informative for capturing the local geometric patterns.

Ablation of Dilated Residual Block
As shown in Figure 3, we stack two sets of LocSE and Attentive Pooling units as the standard dilated residual block to gradually increase the receptive field. To further evaluate how the number of aggregation units in our dilated residual block impact the entire network, we conduct the following two more ablative experiments.
(1) Using only one set of LocSE and attentive pooling. In this setting, the receptive field for each 3D point becomes smaller.
(2) Using three sets of LocSE and attentive pooling. The receptive field becomes exponentially larger.  Table 11 shows the mIoU scores of our RandLA-Net with different number of aggregation units in each dilated residual block. It can be seen that: 1) Only one set of LocSE and attentive pooling in the dilated residual block leads to a significant drop of the mIoU score, due to the limited receptive field. 2) Three sets of LocSE and attentive pooling do not improve the accuracy as expected. This is because the significantly increased receptive fields and the large number of trainable parameters tend to be overfitted.

Ablation of Sampling Approaches
We conduct additional experiments to evaluate the segmentation performance of our framework when adopting different sampling strategies as discussed in Section 3.2. The experimental settings are the same as in Section 4.4.1. As shown in Table 12, all results are achieved on the validation set (i.e., sequence 08) of the SemanticKITTI dataset and the S3DIS dataset (Area-5), respectively.
It can be seen that the segmentation performance of our framework is comparable when used with random sampling, farthest point sampling, or policy gradient-based sampling, showing that our local feature aggregation module is indeed effective and amenable to other sampling methods. Note that, the performance significantly drops when the inverse density importance sampling is used, primarily because the selected points have lower density and tend to be outliers and noisy in practice.

Analysing Point Neighbours
In our RandLA-Net, we use the simple KNN to find a fixed number of neighboring points to extract local patterns for each 3D point. Intuitively, the choice of K in KNN

Choice of K in KNN
Intuitively, the larger the K, the more complex the local geometric patterns that can be learned and the heavier computation required. We conduct 7 groups of experiments where K varies from 4 to 64. The evaluation setting and protocol are the same as used in Section 4.4. Figure 10 (a) shows the variation of segmentation performance given different choices of K in KNN. It can be seen that, the network achieves a significant gain (mIoU score: 46% → 57%) when the number of neighbouring points K increases from 4 to 16, after which the mean IoU score drops gradually given a larger size of K. This demonstrates that, 1) a very small set of neighbouring points is not helpful for the network to learn useful point local features due to the limited receptive field; 2) an extremely large set of neighbouring points is also unlikely to improve the accuracy, since the learned complex local features tend to overfit the training examples and are not general.

KNN vs. Spherical Neighbour
To further investigate how the neighbouring query mechanism impacts the performance, we replace the KNN with spherical radius query in our RandLA-Net without modifying any other components. Similarly, we also conduct 7 groups of experiments by gradually increasing the radius of the first encoding layer from 0.1 to 0.7, and then doubling the radius after each sampling layer. For a fair comparison and better parallelization, we consistently select K = 16 neighborhood points in each spherical neighborhood. This is achieved by following PointNet++ [1] to downsample or pad within each neighboring point set.
As shown in Fig 10 (b), the network achieves the best performance when the radius of the first layer is set to 0.6m, with a mean IoU score of 55.08%. This is slightly lower than the best model with KNN (55.08% vs 57.11%), demonstrating that our framework is able to adapt to the spatial inconsistency potentially caused by KNN. Primarily, this is because the attentive pooling mechanism of our LocSE unit tends to automatically learn different weighs for all neighbouring points, and the spatial locations of all points have been implicitly considered.

Attention Scores of Neighbouring Points
After the neighbouring points are selected by KNN, their features are aggregated by the attentive pooling as shown in Figure 3. To investigate how the features are effectively integrated, we visualize and analyze the learned attention scores in this section. As shown in Figure 11, for a specific center point, the learned attention scores for its 16 neighboring points tend to be similar in the first encoding layer, whereas the learned attention scores for its new 16 neighboring points in the subsequent layers are dramatically different. In effect, this is because the neighbouring points at the first layer are likely to be similar and equally informative, thus their learned attention scores are similar as well. After the large-scale point cloud is significantly downsampled and progressively aggregated, the retained point features tend to be highly compact and have different semantic context. Therefore, the attention scores of those neighbouring points which do not have similar semantic meanings with the center point, tend to be zero, while the most similar neighbouring point tends to have a high attention score.

DISCUSSION
Our RandLA-Net achieves excellent performance in semantic segmentation of large-scale 3D point clouds, it also has limitations. First, the KNN used for searching point neighbours does not scale up linearly. This would be a major computation bottleneck to process extremely largescale point clouds (e.g., > 10 6 points). One possible solution is to leverage the point-voxel representation [48], [96] by searching neighbours within each voxel instead of the entire point cloud. Alternatively, the random sampling together with KNN can be replaced by K-random path selection from KD-Tree or OcTree. In this case, the KNN could be efficiently retrieved during sampling. Second, the random sampling used in our framework focuses on the observed points and cannot produce potentially interesting information at some missing/occluded regions. Therefore, it would be interesting to generate new random point sets to learn better local patterns. Finally, combining the efficiency of random sampling and the effectiveness of advanced point convolutions [23], [23], [34] is also worth to be further investigated.

CONCLUSION
In this paper, we demonstrated that it is possible to efficiently and effectively segment large-scale point clouds by using a lightweight network architecture. In contrast to most current approaches, that rely on expensive sampling strategies, we instead use random sampling in our framework to significantly reduce the memory footprint and computational cost. A local feature aggregation module is also introduced to effectively preserve useful features from a wide neighbourhood. Extensive experiments on multiple benchmarks demonstrate the high efficiency and the stateof-the-art performance of our approach. It would be interesting to extend our framework for the end-to-end 3D instance segmentation on large-scale point clouds by drawing on the recent work [97] and also for the real-time dynamic point cloud processing [98].

APPENDIX A DETAILS FOR THE EVALUATION OF SAMPLING.
We provide the implementation details of different sampling approaches evaluated in Section 4.1. To sample M points (point features) from a large-scale point cloud P with N points (point features): 1) Farthest Point Sampling (FPS): We follow the implementation 2 provided by PointNet++ [1], which is also widely used in [7], [19], [34], [68], [95]. In particular, FPS is implemented as an operator running on GPU. 2) Inverse Density Importance Sampling (IDIS): Given a point p i , its density ρ is approximated by calculating the summation of the distances between p i and its nearest t points [35]. Formally: where p j i represents the coordinates (i.e. x-y-z) of the j th point of the neighbour points set N (p i ), t is set to 16. All the points are ranked according to the inverse density  [40]. We first train a Pro-gressiveNet [40] to transform the raw point clouds into ordered point sets according to their relevance to the task. After that, the first M points are kept, while the rest is discarded. 6) Continuous Relaxation based Sampling (CRS): CRS is implemented with the self-attended gumbel-softmax sampling [41] [30]. Given a point feature set P ∈ R N ×(d+3) with 3D coordinates and per point features, we firstly estimate a probability score vector s ∈ R N through a score function parameterized by a MLP layer, i.e., s = sof tmax(M LP (P )), which learns a categorical distribution. Then, with the Gumbel noise g ∈ R N drawn from the distribution Gumbel(0, 1). Each sampled point feature vector y ∈ R d+3 is calculated as follows: where s (i) and g (i) indicate the i th element in the vector s and g respectively, P (i) represents the i th row vector in the input matrix P . τ > 0 is the annealing 2. https://github.com/charlesq34/pointnet2 3. https://pdal.io/ 4. https://github.com/orendv/learning to sample temperature. When τ → 0, Equation 6 approaches the discrete distribution and samples each row vector in P with the probability p(y = P (i) ) = s (i) . 7) Policy Gradients based Sampling (PGS): Given a point feature set P ∈ R N ×(d+3) with 3D coordinates and per point features, we first predict a score s for each point, which is learnt by an MLP function, i.e., s = sof tmax(M LP (P )) + , where ∈ R N is a zeromean Gaussian noise with the variance Σ for random exploration. After that, we sample M vectors in P with the top M scores. Sampling each point/vector can be regarded as an independent action and a sequence of them form a sequential Markov Decision Process (MDP) with the following policy function π: where a i is the binary decision of whether to sample the i th vector in P and θ is the network parameter of the MLP. Hence to properly improve the sampling policy with an underivable sampling process, we apply REINFORCE algorithm [99] as the gradient estimator. The segmentation accuracy R is applied as the reward value for the entire sampling process as J = R. It is optimized with the following estimated gradients: where M is the batch size, b c and b(P (i) ) are two control variates [100] for alleviating the high variance problem of policy gradients.

B.1 Evaluation on ScanNet
We conduct an experiment on the ScanNet dataset to further evaluate the performance of our method. The detailed results on the online test set are shown in Table 13. It can be seen that our approach achieves satisfactory results on this dataset, but not the best. Our mean IoU score is lower than KPConv [23] and SparseConvNet [62], because our RandLA-Net performs much worse on several small categories such as refrigerator and cabinet. One possible reason is that the major information of small objects may be lost due to the aggressive random sampling used in our framework. Note that, the ScanNet dataset is mainly composed of relatively small indoor scenes (average spatial size: 5m×5m×2m 5 ), hence it is not in favor of our method which is primarily designed for large-scale point clouds (e.g., point clouds spanning up to 250m×260m×80m in Semantic3D dataset). We observe that the performance gap between our approach and KPConv on the ScanNet is greater than that on the S3DIS dataset. This may be caused by the KNN used in our framework, where the receptive field of each point is not stable as that of the spherical neighborhood used in KPConv, especially for the RGBD-reconstructed dataset 5. This is computed by averaging the spatial sizes of all scenes in the dataset.  such as ScanNet (extremely non-uniform, incomplete, and noisy.)

B.2 Evaluation on DALES
The DALES dataset [104] consists of large-scale point clouds with 505 million labeled points acquired by the aerial laser systems (ALS), which covers urban areas spanning 10 km 2 . Each point is labeled with one of 8 semantic categories, and there is no color information available in this dataset. Following the evaluation protocol in [104], we further compare the segmentation performance of our RandLA-Net with other approaches on this dataset. The detailed results are shown in Table 14. It can be seen that our RandLA-Net also achieves satisfactory overall performance on this dataset, with the mean IoU score of 80.0%. It also achieves the best performance on categories such as trucks and vegetation. We also notice that the performance is slightly lower than KPConv [23], primarily because of the poor performance on the poles. This is likely caused by the aggressive downsampling used in our framework.

B.3 Ablation of Voting Scheme
As presented in Section 3.5, the voting scheme is applied to obtain the final predictions during inference. To further investigate the impact of the voting scheme on the overall segmentation performance, we conduct the following experiments by removing the voting scheme from our RandLA-Net. We obtained new mIoU scores on Toronto-3D [37], NPM3D [73], and SemanticKITTI [3] datasets. In particular, instead of voting from multiple runs, we only keep the perpoint result in the last inference. The detailed results are shown in Table 15.
It can be seen that the overall mIoU scores of RandLA-Net has decreased by 2%-4% on Toronto-3D [37], NPM3D [73], and SemanticKITTI [3] datasets, showing that the commonly used voting scheme is helpful to boost the performance, yet it may incur extra computation burdens.

B.4 Ablation of Nearest-Neighbor Interpolation
As mentioned in Sec. 3.4, we choose the nearest-neighbor interpolation for simplicity and efficiency. However, our framework is flexible and allows the integration of different weighted interpolation strategies or other learnable layers. Therefore, we further compare the impact of different upsampling strategies on the overall segmentation performance, including random upsampling and weighted interpolation (e.g., trilinear interpolation). In particular, we implement random upsampling by randomly copy the point features from the current feature map to create the upsampled feature map. For trilinear interpolation, we follow [1] to weight the point features of the nearest three points according to the Euclidean distance. The detailed results are shown in Table 16.
It can be seen that, (1) random upsampling is not applicable in the decoding stage, primarily because the skip connection used in our framework requires that the features at the same spatial location should be related, instead of being randomly selected. (2) the mIoU scores with trilinear  interpolation and attentive upsampling are inferior to the nearest upsampling (57.1%). One possible reason is that the input point clouds are significantly down-sampled after all encoding layers, which means that the final subset of points preserved are very sparse and have different semantic meanings. Therefore, at the beginning stage of up-sampling, if multiple points with different semantic meanings are selected (e.g., by KNN) to trilinearly interpolate the features of a new point, it might be detrimental. Instead, if only the nearest point is selected, it tends to be more robust.

B.5 Ablation of Preprocessing
Different preprocessing steps are adopted for different segmentation approaches. For example, PointNet-based methods [1], [4], [19] adopt block random sampling (e.g., sampling 4k points from 1mx1m blocks) to preprocess the point clouds at the beginning, while KPConv [23] and SCN [62] first use grid sampling to process the point clouds. Here, we conduct additional experiments to further compare the segmentation performance of our method under different preprocessing steps. In particular, we evaluate the performance of our framework with grid sampling, block random sampling (1m×1m with 4096 points and 6m×6m with 40960 points). The detailed results are shown in Table 17. It can be seen that our framework achieves comparable performance under different preprocessing steps when being fed with large point clouds (i.e., grid subsampling with 40960 points vs. block random sampling (6m×6m with 40960 points)). However, the segmentation performance decreases from 61.63% to 59.10% when the block size is reduced to 1m×1m, because the excessive block partitions severely break the geometrical structures and the network is hard to learn meaningful and robust representations. For the detailed analysis of the data preparation, please refer to [105].

B.6 Sensitivity of RandLA-Net
Due to the usage of random sampling, the segmentation results of our RandLA-Net may be different given different runs. To further evaluate the sensitivity (e.g., variance) of our method, we run the well trained model on the S3DIS dataset (Area 5) 5 times, with exactly the same experimental settings. The detailed results are shown in Table 19.
The average mIoU scores of our method on the Area5 of the S3DIS dataset is 62.44%, with a standard deviation of 0.75. We observe that the main difference of results lies in the minor categories such as sofa, column, board and door. Since these categories only have a small number of points, their segmentation results have noticeable fluctuations within multiple runs.

B.7 Variants of RandLA-Net
RandLA-Net can be deeper with more layers and wider with more channels. However, deeper or wider networks inevitably introduce larger models and massive training parameters, making the optimization more difficult in practice. Further, the overall computation efficiency would also be sacrificed.
In this section, we compare the segmentation performance of RandLA-Net with deeper layers and wider channels. In particular, for a deeper model, we increase the number of encoding layers from 4 to 8, and the feature dimensions gradually increase from (8 → 16 → 32 → 64 → 128 → 256 → 512 → 1024). Accordingly, the downsampling rate is decreased from 4 to 2 to preserve sufficient information for the decoder. For a wider model, we double the predefined per-point feature dimensions in our framework, that is: (16 → 64 → 256 → 512 → 1024). All other hyperparameters such as the number of nearest neighbors, learning rate, batch size, and the number of points per batch remain unchanged for a fair comparison. The detailed results achieved on the SemanticKITTI dataset are shown in Table 18.
It can be seen that the segmentation performance is slightly improved when more channels are added (i.e., the wider model), but slightly decreased when more layers are added (i.e, the deeper model). One possible reason is that the deeper model has nearly 20 times more parameters, making it prone to overfitting and difficult to optimize. Additionally, the same hyperparameters may not always be optimal for each model.

B.8 Overfitting issue of RandLA-Net
Several point-based methods [19], [23], [34] tend to be overfitting training datasets. We present both the training and validation accuracy of our RandLA-Net in three datasets in Table 20.  Overall, our RandLA-Net has good generalization ability, without suffering from overfitting. The reasons are two-fold. First, RandLA-Net is lightweight with far fewer network parameters (1.24M) than PointConv [19] (21.7M), KPConv [23] (14.3M), and PointCNN [34] (11.5M). These parameters are shared by a large amount of 3D points and their neighbours, thus capturing more general patterns. Second, the random sampling in our framework can be regarded as an implicit way of data augmentation and regularization. With the same input point cloud, the preserved 3D points can be different in multiple training iterations, thereby preventing the network from overfitting the training set.