Large-scale Point Cloud Semantic Segmentation with Superpoint Graphs

Introduction

Semantic segmentation of large 3D point clouds presents numerous challenges, the most obvious one being the scale of the data. Another hurdle is the lack of clear structure akin to the regular grid arrangement in images. These obstacles have likely prevented Convolutional Neural Networks (CNNs) from achieving on irregular data the impressive performances attained for speech processing or images.

Previous attempts at using deep learning for large 3D data were trying to replicate successful CNN architectures used for image segmentation. For example, SnapNet converts a 3D point cloud into a set of virtual 2D RGBD snapshots, the semantic segmentation of which can then be projected on the original data. SegCloud uses 3D convolutions on a regular voxel grid. However, we argue that such methods do not capture the inherent structure of 3D point clouds, which results in limited discrimination performance. Indeed, converting point clouds to 2D format comes with loss of information and requires to perform surface reconstruction, a problem arguably as hard as semantic segmentation. Volumetric representation of point clouds is inefficient and tends to discard small details.

Deep learning architectures specifically designed for 3D point clouds display good results, but are limited by the size of inputs they can handle at once.

We propose a representation of large 3D point clouds as a collection of interconnected simple shapes coined superpoints, in spirit similar to superpixel methods for image segmentation . As illustrated in Figure 1, this structure can be captured by an attributed directed graph called the superpoint graph (SPG). Its nodes represent simple shapes while edges describe their adjacency relationship characterized by rich edge features.

The SPG representation has several compelling advantages. First, instead of classifying individual points or voxels, it considers entire object parts as whole, which are easier to identify. Second, it is able to describe in detail the relationship between adjacent objects, which is crucial for contextual classification: cars are generally above roads, ceilings are surrounded by walls, etc. Third, the size of the SPG is defined by the number of simple structures in a scene rather than the total number of points, which is typically several order of magnitude smaller. This allows us to model long-range interaction which would be intractable otherwise without strong assumptions on the nature of the pairwise connections.

We introduce superpoint graphs, a novel point cloud representation with rich edge features encoding the contextual relationship between object parts in 3D point clouds.

Based on this representation, we are able to apply deep learning on large-scale point clouds without major sacrifice in fine details. Our architecture consists of PointNets for superpoint embedding and graph convolutions for contextual segmentation. For the latter, we introduce a novel, more efficient version of Edge-Conditioned Convolutions as well as a new form of input gating in Gated Recurrent Units .

We set a new state of the art on two publicly available datasets: Semantic3D and S3DIS . In particular, we improve mean per-class intersection over union (mIoU) by $11.9$ points for the Semantic3D reduced test set, by $8.8$ points for the Semantic3D full test set, and by up to $12.4$ points for the S3DIS dataset.

Related Work

The classic approach to large-scale point cloud segmentation is to classify each point or voxel independently using handcrafted features derived from their local neighborhood . The solution is then spatially regularized using graphical models or structured optimization . Clustering as preprocessing or postprocessing have been used by several frameworks to improve the accuracy of the classification.

Deep Learning on Point Clouds. Several different approaches going beyond naive volumetric processing of point clouds have been proposed recently, notably set-based , tree-based , and graph-based . However, very few methods with deep learning components have been demonstrated to be able to segment large-scale point clouds. PointNet can segment large clouds with a sliding window approach, therefore constraining contextual information within a small area only. Engelmann et al. improves on this by increasing the context scope with multi-scale windows or by considering directly neighboring window positions on a voxel grid. SEGCloud handles large clouds by voxelizing followed by interpolation back to the original resolution and post-processing with a conditional random field (CRF). None of these approaches is able to consider fine details and long-range contextual information simultaneously. In contrast, our pipeline partitions point clouds in an adaptive way according to their geometric complexity and allows deep learning architecture to use both fine detail and interactions over long distance.

Graph Convolutions. A key step of our approach is using graph convolutions to spread contextual information. Formulations that are able to deal with graphs of variable sizes can be seen as a form of message passing over graph edges . Of particular interest are models supporting continuous edge attributes , which we use to represent interactions. In image segmentation, convolutions on graphs built over superpixels have been used for post-processing: Liang et al. traverses such graphs in a sequential node order based on unary confidences to improve the final labels. We update graph nodes in parallel and exploit edge attributes for informative context modeling. Xu et al. convolves information over graphs of object detections to infer their contextual relationships. Our work infers relationships implicitly to improve segmentation results. Qi et al. also relies on graph convolutions on 3D point clouds. However, we process large point clouds instead of small RGBD images with nodes embedded in 3D instead of 2D in a novel, rich-attributed graph. Finally, we note that graph convolutions also bear functional similarity to deep learning formulations of CRFs , which we discuss more in Section 3.4.

Method

The main obstacle that our framework tries to overcome is the size of LiDAR scans. Indeed, they can reach hundreds of millions of points, making direct deep learning approaches intractable. The proposed SPG representation allows us to split the semantic segmentation problem into three distinct problems of different scales, shown in Figure 3, which can in turn be solved by methods of corresponding complexity:

Geometrically homogeneous partition: The first step of our algorithm is to partition the point cloud into geometrically simple yet meaningful shapes, called superpoints. This unsupervised step takes the whole point cloud as input, and therefore must be computationally very efficient. The SPG can be easily computed from this partition.

Superpoint embedding: Each node of the SPG corresponds to a small part of the point cloud corresponding to a geometrically simple primitive, which we assume to be semantically homogeneous. Such primitives can be reliably represented by downsampling small point clouds to at most hundreds of points. This small size allows us to utilize recent point cloud embedding methods such as PointNet .

Contextual segmentation: The graph of superpoints is by orders of magnitude smaller than any graph built on the original point cloud. Deep learning algorithms based on graph convolutions can then be used to classify its nodes using rich edge features facilitating long-range interactions.

The SPG representation allows us to perform end-to-end learning of the trainable two last steps. We will describe each step of our pipeline in the following subsections.

In this subsection, we describe our method for partitioning the input point cloud into parts of simple shape. Our objective is not to retrieve individual objects such as cars or chairs, but rather to break down the objects into simple parts, as seen in Figure 4. However, the clusters being geometrically simple, one can expect them to be semantically homogeneous as well, i.e. not to cover objects of different classes. Note that this step of the pipeline is purely unsupervised and makes no use of class labels beyond validation.

We follow the global energy model described by for its computational efficiency. Another advantage is that the segmentation is adaptive to the local geometric complexity. In other words, the segments obtained can be large simple shapes such as roads or walls, as well as much smaller components such as parts of a car or a chair.

The global energy proposed by is defined with respect to the $10$-nearest neighbor adjacency graph $G_{\text{nn}}=\left(C,E_{\text{nn}}\right)$ of the point cloud (note that this is not the SPG). The geometrically homogeneous partition is defined as the constant connected components of the solution of the following optimization problem:

2 Superpoint Graph Construction

We define $G_{\text{vor}}=\left(C,E_{\text{vor}}\right)$ as the symmetric Voronoi adjacency graph of the complete input point cloud as defined by . Two superpoints $S$ and $T$ are adjacent if there is at least one edge in $E_{\text{vor}}$ with one end in $S$ and one end in $T$:

Important spatial features associated with a superedge $\left(S,T\right)$ are obtained from the set of offsets $\delta(S,T)$ for edges in $E_{\text{vor}}$ linking both superpoints:

Superedge features can also be derived by comparing the shape and size of the adjacent superpoints. To this end, we compute $\left\lvert S\right\rvert$ as the number of points comprised in a superpoint $S$, as well as shape features $\text{length}\left(S\right)=\lambda_{1}$, $\text{surface}\left(S\right)=\lambda_{1}\lambda_{2}$, $\text{volume}\left(S\right)=\lambda_{1}\lambda_{2}\lambda_{3}$ derived from the eigenvalues $\lambda_{1},\lambda_{2},\lambda_{3}$ of the covariance of the positions of the points comprised in each superpoint, sorted by decreasing value. In Table 1, we describe a list of the different superedge features used in this paper. Note that the break of symmetry in the edge features makes the SPG a directed graph.

3 Superpoint Embedding

The goal of this stage is to compute a descriptor for every superpoint $S_{i}$ by embedding it into a vector $\mathbf{z_{i}}$ of fixed-size dimensionality $d_{z}$. Note that each superpoint is embedded in isolation; contextual information required for its reliable classification is provided only in the following stage by the means of graph convolutions.

Several deep learning-based methods have been proposed for this purpose recently. We choose PointNet for its remarkable simplicity, efficiency, and robustness. In PointNet, input points are first aligned by a Spatial Transformer Network , independently processed by multi-layer perceptrons (MLPs), and finally max-pooled to summarize the shape.

In order for PointNet to learn spatial distribution of different shapes, each superpoint is rescaled to unit sphere before embedding. Points are represented by their normalized position $p^{\prime}_{i}$, observations $o_{i}$, and geometric features $f_{i}$ (since these are already available precomputed from the partitioning step). Furthermore, the original metric diameter of the superpoint is concatenated as an additional feature after PointNet max-pooling in order to stay covariant with shape sizes.

4 Contextual Segmentation

The final stage of the pipeline is to classify each superpoint $S_{i}$ based on its embedding $\mathbf{z}_{i}$ and its local surroundings within the SPG. Graph convolutions are naturally suited to this task. In this section, we explain the propagation model of our system.

Our approach builds on the ideas from Gated Graph Neural Networks and Edge-Conditioned Convolutions (ECC) . The general idea is that superpoints refine their embedding according to pieces of information passed along superedges. Concretely, each superpoint $S_{i}$ maintains its state hidden in a Gated Recurrent Unit (GRU) . The hidden state is initialized with embedding $\mathbf{z}_{i}$ and is then processed over several iterations (time steps) $t=1\ldots T$. At each iteration $t$, a GRU takes its hidden state $\mathbf{h}^{(t)}_{i}$ and an incoming message $\mathbf{m}^{(t)}_{i}$ as input, and computes its new hidden state $\mathbf{h}^{(t+1)}_{i}$. The incoming message $\mathbf{m}^{(t)}_{i}$ to superpoint $i$ is computed as a weighted sum of hidden states $\mathbf{h}^{(t)}_{j}$ of neighboring superpoints $j$. The actual weighting for a superedge $(j,i)$ depends on its attributes $F_{ji,\cdot}$, listed in Table 1. In particular, it is computed from the attributes by a multi-layer perceptron $\Theta$, so-called Filter Generating Network. Formally:

We argue that GRU should possess the ability to down-weight (parts of) an input vector based on its hidden state. For example, GRU might learn to ignore its context if its class state is highly certain or to direct its attention to only specific feature channels. Equation 6 achieves this by gating message $\mathbf{m}^{(t)}_{i}$ by the hidden state before using it as input $\mathbf{x}^{(t)}_{i}$.

Edge-Conditioned Convolution.

ECC plays a crucial role in our model as it can dynamically generate filtering weights for any value of continuous attributes $F_{ji,\cdot}$ by processing them with a multi-layer perceptron $\Theta$. In the original formulation (ECC-MV), $\Theta$ regresses a weight matrix to perform matrix-vector multiplication $\Theta(F_{ji,\cdot};W_{e})\mathbf{h}^{(t)}_{j}$ for each edge. In this work, we propose a lightweight variant with lower memory requirements and fewer parameters, which is beneficial for datasets with few but large point clouds. Specifically, we regress only an edge-specific weight vector and perform element-wise multiplication as in Equation 7 (ECC-VV). Channel mixing, albeit in an edge-unspecific fashion, is postponed to Equation 5. Finally, let us remark that $\Theta$ is shared over time iterations and that self-loops as proposed in are not necessary due to the existence of hidden states in GRUs.

State Concatenation.

Inspired by DenseNet , we concatenate hidden states over all time steps and linearly transform them to produce segmentation logits $\mathbf{y}_{i}$ in Equation 8. This allows to exploit the dynamics of hidden states due to increasing receptive field for the final classification.

Relation to CRFs.

In image segmentation, post-processing of convolutional outputs using Conditional Random Fields (CRFs) is widely popular. Several inference algorithms can be formulated as (recurrent) network layers amendable to end-to-end learning , possibly with general pairwise potentials . While our method of information propagation shares both these characteristics, our GRUs operate on $d_{z}$-dimensional intermediate feature space, which is richer and less constrained than low-dimensional vectors representing beliefs over classes, as also discussed in . Such enhanced access to information is motivated by the desire to learn a powerful representation of context, which goes beyond belief compatibilities, as well as the desire to be able to discriminate our often relatively weak unaries (superpixel embeddings). We empirically evaluate these claims in Section 4.3.

5 Further Details

In this paper, we use two different adjacency graphs between points of the input clouds: $G_{\text{nn}}$ in Section 3.1 and $G_{\text{vor}}$ in Section 3.2. Indeed, different definitions of adjacency have different advantages. Voronoi adjacency is more suited to capture long-range relationships between superpoints, which is beneficial for the SPG. Nearest neighbors adjacency tends not to connect objects separated by a small gap. This is desirable for the global energy but tends to produce a SPG with many small connected components, decreasing embedding quality. Fixed radius adjacency should be avoided in general as it handles the variable density of LiDAR scans poorly.

Training.

While the geometric partitioning step is unsupervised, superpoint embedding and contextual segmentation are trained jointly in a supervised way with cross entropy loss. Superpoints are assumed to be semantically homogeneous and, consequently, assigned a hard ground truth label corresponding to the majority label among their contained points. We also considered using soft labels corresponding to normalized histograms of point labels and training with Kullback-Leibler divergence loss. It performed slightly worse in our initial experiments, though.

Testing.

In modern deep learning frameworks, testing can be made very memory-efficient by discarding layer activations as soon as the follow-up layers have been computed. In practice, we were able to label full SPGs at once. To compensate for randomness due to subsampling of point clouds in PointNets, we average logits obtained over $10$ runs with different seeds.

Experiments

We evaluate our pipeline on the two currently largest point cloud segmentation benchmarks, Semantic3D and Stanford Large-Scale 3D Indoor Spaces (S3DIS) , on both of which we set the new state of the art. Furthermore, we perform an ablation study of our pipeline in Section 4.3.

Even though the two data sets are quite different in nature (large outdoor scenes for Semantic3D, smaller indoor scanning for S3DIS), we use nearly the same model for both. The deep model is rather compact and $6$ GB of GPU memory is enough for both testing and training. We refer to Appendix A for precise details on hyperparameter selection, architecture configuration, and training procedure.

Performance is evaluated using three metrics: per-class intersection over union (IoU), per-class accuracy (Acc), and overall accuracy (OA), defined as the proportion of correctly classified points. We stress that the metrics are computed on the original point clouds, not on superpoints.

Semantic3D is the largest available LiDAR dataset with over 3 billion points from a variety of urban and rural scenes. Each point has RGB and intensity values (the latter of which we do not use). The dataset consists of 15 training scans and 15 test scans with withheld labels. We also evaluate on the reduced set of 4 subsampled scans, as common in past work.

In Table 2, we provide the results of our algorithm compared to other state of the art recent algorithms and in Figure 4, we provide qualitative results of our framework. Our framework improves significantly on the state of the art of semantic segmentation for this data set, i.e. by nearly 12 mIoU points on the reduced set and by nearly 9 mIoU points on the full set. In particular, we observe a steep gain on the ”artefact” class. This can be explained by the ability of the partitioning algorithm to detect artifacts due to their singular shape, while they are hard to capture using snapshots, as suggested by . Furthermore, these small object are often merged with the road when performing spatial regularization.

2 Stanford Large-Scale 3D Indoor Spaces

The S3DIS dataset consists of 3D RGB point clouds of six floors from three different buildings split into individual rooms. We evaluate our framework following two dominant strategies found in previous works. As advocated by , we perform $6$-fold cross validation with micro-averaging, i.e. computing metrics once over the merged predictions of all test folds. Following , we also report the performance on the fifth fold only (Area 5), corresponding to a building not present in the other folds. Since some classes in this data set cannot be partitioned purely using geometric features (such as boards or paintings on walls), we concatenate the color information $o$ to the geometric features $f$ for the partitioning step.

The quantitative results are displayed in Table 3, with qualitative results in Figure 4 and in Appendix D. S3DIS is a difficult dataset with hard to retrieve classes such as white boards on white walls and columns within walls. From the quantitative results we can see that our framework performs better than other methods on average. Notably, doors are able to be correctly classified at a higher rate than other approaches, as long as they are open, as illustrated in Figure 4. Indeed, doors are geometrically similar to walls, but their position with respect to the door frame allows our network to retrieve them correctly. On the other hand, the partition merges white boards with walls, depriving the network from the opportunity to even learn to classify them: the IoU of boards for theoretical perfect classification of superpoints (as in Section 4.3) is only $51.3$.

Computation Time. In Table 4, we report computation time over the different steps of our pipeline for the inference on Area 5 measured on a 4 GHz CPU and GTX 1080 Ti GPU. While the bulk of time is spent on the CPU for partitioning and SPG computation, we show that voxelization as pre-processing, detailed in Appendix A, leads to a significant speed-up as well as improved accuracy.

3 Ablation Studies

Conclusion

We presented a deep learning framework for performing semantic segmentation of large point clouds based on a partition into simple shapes. We showed that SPGs allow us to use effective deep learning tools, which would not be able to handle the data volume otherwise. Our method significantly improves on the state of the art on two publicly available datasets. Our experimental analysis suggested that future improvements can be made in both partitioning and learning deep contextual classifiers.

The source code in PyTorch as well as the trained models are available at https://github.com/loicland/superpoint_graph.

References

Appendix

Appendix A Model Details

We pre-process input point clouds with voxelization subsampling by computing per-voxel mean positions and observations over a regular 3D grid ($5$ cm bins for Semantic3D and $3$ cm bins for S3DIS dataset). The resulting semantic segmentation is interpolated back to the original point cloud in a nearest neighbor fashion. Voxelization helps decreasing the computation time and memory requirement, and improves the accuracy of the semantic segmentation by acting as a form of geometric and radiometric denoising as well (Table 4 in the main paper). The quality of further steps is practically not affected, as superpoints are usually strongly subsampled for embedding during learning and inference anyway (Section 3.3 in the main paper).

Geometric Partition.

We set regularization strength $\mu=0.8$ for Semantic3D and $\mu=0.03$ for S3DIS, which strikes a balance between semantic homogeneity of superpoints and the potential for their successful discrimination (S3DIS is composed of smaller semantic parts than Semantic3D). In addition to five geometric features $f$ (linearity, planarity, scattering, verticality, elevation), we use color information $o$ for clustering in S3DIS due to some classes being geometrically indistinguishable, such as boards or doors.

PointNet.

Segmentation Network.

We use embedding dimensionality $d_{z}=32$ and $T=10$ iterations. ECC-VV is used for Semantic3D (there are only $15$ point clouds even though the amount of points is large), while ECC-MV is used for S3DIS (large number of point clouds). Filter-generating network $\Theta$ is a MLP with 4 layers (widths 32, 128, 64, and 32 or $32^{2}$ for ECC-VV or ECC-MV) with ReLUs. Batch Normalization is used only after the third parametric layer. No bias is used in the last layer. Superedges have $d_{f}=13$ dimensional features, normalized by mean subtraction and scaling to unit variance based on the whole training set.

Training.

We train using Adam with initial learning rate 0.01 and batch size 2, i.e. effectively up to 1024 superpoints per batch. For Semantic3D, we train for 500 epochs with stepwise learning rate decay of 0.7 at epochs 350, 400, and 450. For S3DIS, we train for 250 epochs with steps at 200 and 230. We clip gradients within $$.

Appendix B CRF-ECC

In this section, we describe our adaptation of CRF-RNN mean field inference by Zheng et al. for post-processing PointNet embeddings in SPG, denoted as unary potentials $U_{i}$ here.

The original work proposed a dense CRF with pairwise potentials $\Psi$ defined to be a mixture of $m$ Gaussian kernels as $\Psi_{ij}=\mu\sum_{m}w_{m}K_{m}(F_{ij})$, where $\mu$ is label compatibility matrix, $w$ are parameters, and $K$ are fixed Gaussian kernels applied on edge features.

We replace this definition of the pairwise term with a Filter generating network $\Theta$ parameterized with weights $W_{e}$, which generalizes the message passing and compatibility transform steps of Zheng et al. . Furthermore, we use superedge connectivity $\mathcal{E}$ instead of assuming a complete graph. The pseudo-code is listed in Algorithm 1. Its output are marginal probability distributions $Q$. In practice we run the inference for $T=10$ iterations.

Appendix C Extended Ablation Studies

In this section, we present additional set of experiments to validate our design choices and present their results in Table 6.

a) Spatial Transformer Network. While STN makes superpoint embedding orientation invariant, the relationship with surrounding objects are still captured by superedges, which are orientation variant. In practice, STN helps by $4$ mIoU points.

b) Geometric Features. Geometric features $f_{i}$ are computed in the geometric partition step and can therefore be used in the following learning step for free. While PointNets could be expected to learn similar features from the data, this is hampered by superpoint subsampling, and therefore their explicit use helps (+4 mIoU).

c) Sampling Superpoints. The main effect of subsampling SPG is regularization by data augmentation. Too small a sample size leads to disregarding contextual information (-4 mIoU) while too large a size leads to overfitting (-2 mIoU). Lower memory requirements at training is an extra benefit. There is no subsampling at test time.

d) Long-range Context. We observe that limiting the range of context information in SPG harms the performance. Specifically, capping distances in $G_{\text{vor}}$ to $1$ m (as used in PointNet ) or $5$ m (as used in SegCloud ) worsens the performance of our method (even more on our Semantic 3D validation set).

e) Input Gate. We evaluate the effect of input gating (IG) for GRUs as well as LSTM units. While a LSTM unit achieves higher score than a GRU (-3 mIoU), the proposed IG reverses this situation in favor of GRU (+1 mIoU). Unlike the standard input gate of LSTM, which controls the information flow from the hidden state and input to the cell, our IG controls the input even before it is used to compute all other gates.

f) Regularization Strength $\mu$. We investigate the balance between superpoints’ discriminative potential and their homogeneity controlled by parameter $\mu$ . We observe that the system is able to perform reasonably over a range of SPG sizes.

Appendix D Video Illustration

We provide a video illustrating our method and qualitative results on S3DIS dataset, which can be viewed at https://youtu.be/Ijr3kGSU_tU.