LatticeNet: Fast Point Cloud Segmentation Using Permutohedral Lattices

I Introduction

Environment understanding is a crucial ability for autonomous agents. Perceiving not only the geometrical structure of the scene but also distinguishing between different classes of objects therein enables tasks like manipulation and interaction that were previously not possible. Within this field, semantic segmentation of 2D images is a mature research area, showing outstanding success in dense per pixel categorization on images . The task of semantically labelling 3D data is still an open area of research however as it poses several challenges that need to be addressed.

First, 3D data is often represented in an unstructured manner — unlike the grid-like structure of images. This raises difficulties for current approaches which assume a regular structure upon which convolutions are defined.

Second, the performance of current 3D networks is limited by their memory requirements. Storing 3D information in a dense structure is prohibitive for even high-end GPUs, clearly indicating the need for a sparse structure.

Third, discretization issues caused by imposing a regular grid onto point clouds can negatively affect the network’s performance and interpolation is necessary to cope with quantization artifacts .

In this work, we propose LatticeNet, a novel approach for point cloud segmentation which alleviates the previously mentioned problems. Hence, our contributions are:

a hybrid architecture which leverages the strength of PointNet to obtain low-level features and sparse 3D convolutions to aggregate global context,

a framework suitable for sparse data onto which all common CNN operators are defined, and

a novel slicing operator that is end-to-end trainable for mapping features of a regular lattice grid back onto an unstructured point cloud.

II Related Work

Semantic segmentation approaches applied to 3D data can be categorized depending on data representation upon which they operate.

Point cloud networks: The first category of networks operates directly on the raw point cloud.

From this area, PointNet is one of the pioneering works. The approach processes raw point clouds by individually embedding the points into a higher-dimensional space and applying max-pooling for permutation-invariance to obtain a global scene descriptor. The descriptor can be used for both classification and semantic segmentation. However, PointNet does not take local information into account which is essential for the segmentation of highly-detailed objects. This has been partially solved in the subsequent work of PointNet++ which applies PointNet hierarchically, capturing both local and global contextual information.

Chen et al. use a similar approach but they input the point responses w.r.t. a sparse set of radial basis functions (RBF) scattered in 3D space. Optimizing jointly for the extent and center of the RBF kernels allows to obtain a more explicit modelling of the spatial distribution.

Instead, PointCNN deals with the permutation invariance not by using a symmetric aggregation function, but by learning a $K\times K$ matrix for the $K$ input points that permutes the cloud into a canonical form.

Voxel networks: Voxel-based approaches discretize the space in cubic or tetrahedral volume elements which are used for 3D convolutions.

SEGCloud voxelizes the point cloud into a uniform 3D grid and applies 3D convolutions to obtain per-voxel class probabilities. A Conditional Random Field (CRF) is used to smooth the labels and enforce global consistency. The class scores are transferred back to the points using trilinear interpolation. The usage of a dense grid results in high memory consumption while our approach uses a permutoherdral lattice stored sparsely. Additionally, their voxelization results in a loss of information due to the discretization of the space. Our approach avoids quantization issues by using a PointNet architecture to summarize the local neighborhood.

Rethage et al. perform semantic segmentation on a voxelized point cloud and employ a PointNet architecture as a low-level feature extractor. The usage of a dense grid, however, leads to high memory usage and slow inference, requiring various seconds for medium-sized point clouds.

SplatNet is the work most closely related to ours. It alleviates the computational burden of 3D convolutions by using a sparse permutohedral lattice, performing convolutions only around the surfaces. It discretizes the space in uniform simplices and accumulates the features of the raw point cloud onto the vertices of the lattice using a splatting operation. Convolutions are applied on the lattice vertices and a slicing operation barycentrically interpolates the features of the vertices back onto the point cloud. A series of splat-conv-slice operations are applied to obtain contextual information. The main disadvantage is that splat and slice operations are not learned and repeated application slowly degrades the point clouds features as they act as Gaussian filters . Furthermore, storing high-dimensional features for each point in the cloud is memory intensive which limits the maximum number of points that can be processed. In contrast, our approach has learned operations for splatting and slicing which brings more representational power to the network. We also restrict their usage to only the beginning and the end of the network, leaving the rest of the architecture fully convolutional.

Mesh networks: Mesh-based approaches operate on triangular or quadrilateral meshes. The connectivity information provided by the faces of the mesh allows to easily compute normal vectors and to establish local tangent planes.

GCNN operates on small local patches which are convolved using a series of rotated filters, followed by max pooling to deal with the ambiguity in the patch orientation. However, the max pooling disregards the orientation. MoNet deals with the orientation ambiguity by aligning the kernels to the principal curvature of the surface. Yet, this does not solve cases in which the local curvature is not informative, e.g. for walls or ceilings. TextureNet further improves on the idea by using a global 4-RoSy orientations field. This provides a smooth orientation field at any point on the surface which is aligned to the edges of the mesh and has only a 4-direction ambiguity. Defining convolution on patches oriented according to the 4-RoSy field yields significantly improved results.

Graph networks: Graph-based approaches operate on vertices of a graph connected in an arbitrary topology, without the restrictions of triangular or quadrilateral meshes.

Wang et al. and Wu et al. define a convolution operator over non-grid structured data by having continuous values over the full vector space. The weights of these continuous filters are parametrized by an multi-layer perceptron (MLP).

Defferrard et al. formulate CNNs in the context of spectral graph theory. They define the convolution in the Fourier domain with Chebychev polynomials to obtain fast localized filters. However, spectral approaches are not directly transferable to a new graph as the Fourier basis changes. Additionally, the learned filters are rotation invariant which can be seen as a limitation to the representational power of the network.

Multi-view networks: The convolution operation is well defined in 2D and hence, there is an interest in casting 3D segmentation as a series of single-view segmentations which are fused together.

Pham et al. simultaneously reconstruct the scene geometry and recover the semantics by segmenting sequences of RGB-D frames. The segmentation is transferred from 2D images to the 3D world and fused with previous segmentations. A CRF finally resolves noisy predictions.

TangentConv assumes that the data is sampled from locally Euclidean surfaces and project the local surface geometry onto a tangent plane to which 2D convolutions can be applied. A heavy preprocessing step for normal calculation is required. In contrast, our approach can deal with raw point clouds without requiring normals.

III Notation

Throughout this paper, we use bold upper-case characters to denote matrices and bold lower-case characters to denote vectors.

We denote with $I_{p}$ the set of lattice vertices of the simplex that contains point $p$. The set $I_{p}$ always contains $d+1$ vertices as the lattice tessellates the space in uniform simplices with $d+1$ vertices each. Furthermore, we denote with $J_{v}$ the set of points $p$ for which vertex $v$ is one of the vertices of the containing simplices. Hence, these are the points that contribute to vertex $v$ through the splat operation.

IV Permutohedral Lattice

The lattice tessellates the space into uniform $d$-dimensional simplices. Hence, for $d=2$ the space is tessellated with triangles and for $d=3$ into tetrahedra. The enclosing simplex of any point can be found by a simple rounding algorithm .

The vertices of the permutohedral lattice are stored in a sparse manner using a hash map in which the key is the coordinate $\mathbf{c}_{v}$ and the value is $\mathbf{x}_{v}$. Hence, we only allocate the simplices that contain the 3D surface of interest. This sparse allocation allows for efficient implementation of all typical operations in CNNs (convolution, pooling, transposed convolution, etc.).

The permutohedral lattice has several advantages w.r.t. standard cubic voxels. The number of vertices for each simplex is given by $d+1$ which scales linearly with increasing dimension, in contrast to the $2^{d}$ for standard voxels. This small number of vertices per simplex allows for fast splatting and slicing operations. Furthermore, splatting and slicing create piece-wise linear outputs as they use barycentric interpolation. In contrast, standard quantization in cubic voxels create piece-wise constant outputs, leading to discretization artefacts.

V Method

The input to our method is a point cloud $P=\left(\mathbf{G},\mathbf{F}\right)$ containing coordinates and per-point features.

In this section we will explain in detail the standard operations on a permutohedral lattice that are used in previous works .

Splatting refers to the interpolation of point features onto the values of the lattice $V$ using barycentric weighting (Fig. 3a). Each point splats onto $d+1$ lattice vertices and their weighted features are summed onto the vertices.

Convolving operates analogously to standard spatial convolutions in 2D or 3D, i.e. a weighted sum of the vertex values together with its neighbors is computed. We use convolutions that span over the 1-hop ring around a vertex and hence convolve the values of $2(d+1)+1$ vertices (Fig. 2).

Slicing is the inverse operation to splatting. The vertex values of the lattice are interpolated back for each position with the same weights used during splatting. The weighted contributions from the simplexes $d+1$ vertices are summed up (Fig. 5a).

V-B Proposed Operations on Permutohedral Lattice

The operations defined in section Sec. V-A are typically used in a cascade of splat-conv-slice to obtain dense predictions . However, splatting and slicing act as Gaussian kernel low-pass filtering encoded information . Their repeated usage at every layer is detrimental to the accuracy of the network. Additionally, splatting acts as a weighted average on the feature vectors where the weights are only determined through barycentric interpolation. Including the weights as trainable parameter allows the network to decide on a better interpolation scheme. Furthermore, as the network grows deeper and feature vectors become higher-dimensional, slicing consumes increasingly more memory, as it assigns the features to the points. Since in most cases $\lvert P\rvert\gg\lvert V\rvert$, it is more efficient to store the features only in the lattices vertices.

To address these limitations, we propose four new operators on the permutohedral lattice which are more suitable for CNNs and dense prediction tasks.

Distribute is defined as the list of features that each lattice vertex receives. However, they are not summed as done by splatting:

where $\mathbf{x}_{v}$ is the value of lattice vertex $v$ and $b_{pv}$ is the barycentric weight between point $p$ and lattice vertex $v$.

Instead, our distribute operators $\mathcal{D}_{G}$ and $\mathcal{D}_{F}$ concatenate coordinates and features of the contributing points:

Note that we use a different distribute function for coordinates then for point features. For coordinates, we subtract the mean of the contributing coordinates. The intuition behind this is that coordinates by themselves are not very informative w.r.t. the potential semantic class. However, the local distribution is more informative as it gives a notion of the geometry.

Upsampling follows a similar reasoning. The fine vertices need first to be embedded in the coarse lattice using a division by 2. Afterwards, the neighboring vertices over which we convolve are separated by a vector of form $\pm\left[-0.5,\ldots,-0.5,d/2,-0.5,\ldots,-0.5\right]$. The careful reader will notice that in this case, the coordinates of the neighboring vertices may not be integer anymore; they may have a fractional part and will therefore lie in the middle of a coarser simplex. In this case we ignore the contribution of this neighboring vertices and only take the contribution of the center vertex. The upsampling operation effectively performs a transposed convolution.

DeformSlicing: While the slicing operation $\mathcal{Y}$ barycentrically interpolates the values back to the points by using barycentric coordinates:

Here, $\Delta b_{pv}$ are offsets that are applied to the original barycentric coordinates. A parallel branch within our network first gathers the values from all the vertices in a simplex and regresses the $\Delta b_{pv}$:

However, this prediction has the disadvantage of not being permutation equivariant; therefore permutation of the vertices would not imply the same permutation in the barycentric offsets:

where $\pi$ is the set of all permutations of the $d+1$ vertices.

It is important for our prediction to be permutation equivariant because the vertices may be arranged in any order and the barycentric offsets need to keep a consistent preference towards a certain vertexes features, regardless of its position within a simplex.

In order for the prediction of the offsets to be consistent with permutations of the vertices, we take inspiration from the work of and of equivariant layers and design $\mathcal{F}$ as:

The difference between the slicing and our DeformSlicing is visualized in Fig. 5

VI Network Architecture

Input to our network is a point cloud $P$ which may contain per-point features stored in $\mathbf{F}$. The output is class probabilities for each point $p$.

Our network architecture has a U-Net structure and is visualized in Fig. 6 together with the used individual blocks.

The first layers distribute the point features onto the lattice and use a PointNet to obtain local features. Afterwards, a series of ResNet blocks , followed by repeated downsampling, aggregates global context. The decoder branch mirrors the encoder architecture and upsamples through transposed convolutions. Finally, a DeformSlicing propagates lattice features onto the original point cloud. Skip connections are added by concatenating the encoder feature maps with matching decoder features.

VII Implementation

Our lattice is stored sparsely on a hash map structure, which allows for fast access of neighboring vertices. Unlike , we construct the hash map directly on the GPU, saving us from incurring an expensive CPU to GPU memory copy.

For memory savings, we implemented the DeformSlice and the last linear classification layer in one fused operation, avoiding the storage of high-dimensional feature vectors for each point in the point cloud.

All of the lattice operators containing forwards and backwards passes are implemented on the GPU and exposed to PyTorch .

Following recent works , all convolutions are pre-activated using Group Normalization and a ReLU unit. We chose Group Normalization instead of the standard batch normalization because it is more stable when the batch size is small. We use the default of $32$ groups.

The models were trained using the Adam optimizer, using a learning rate of $0.001$ and a weight decay of ${10}^{-4}$. The learning rate was reduced by a factor of $10$ when the loss plateaued.

We share the PyTorch implementation of LatticeNet at https://github.com/AIS-Bonn/lattice_net.

VIII Experiments

We evaluate our proposed lattice network on three different datasets: ShapeNet , ScanNet and SemanticKITTI . For the task of semantic segmentation we report the mean Intersection over Union (mIoU). We use a shallow model for ShapeNet and a deeper model for ScanNet and SemanticKITTI as the datasets are larger. We augment all data using random mirroring and translations in space. For ScanNet, we also apply random color jitter. A video with additional footage of the experiments is available online http://www.ais.uni-bonn.de/videos/RSS_2020_Rosu/.

ShapeNet part segmentation is a subset of the ShapeNet dataset which contains objects from $16$ different categories each segmented into $2$ - $6$ parts. The dataset consists of points sampled from the surface of the objects, together with the ground truth label of the corresponding object part. The objects have an average of $2613$ points. We train and evaluate our network on each object individually. The results for our method and five competing methods are gathered in Tab. I and visualized in Fig. 8.

We observe that for some classes, we obtain state-of-the-art performance and for other objects, the IoU is slightly lower than for other approaches. We ascribe this to the fact that training one fixed architecture size for each individual object is suboptimal as some objects like the ”cap” have as few as $55$ examples while others like the table have more than $5$K. This causes the network to be prone for overfitting on the easy object or underfitting on the difficult ones. A fair evaluation would require finding an architecture that performs well for all objects on average. However due to various issues with mislabeled ground truths we deem that experimentation with more architectures or with different regularization strengths for individual objects would overfit the dataset.

ScanNet 3D segmentation consists of 3D reconstructions of real rooms. It contains $\approx 1500$ rooms segmented into $20$ classes (bed, furniture, wall, etc.). The rooms have between $9$K and $537$K points — on average $145$K. We segment an entire room at once without cropping.

SemanticKITTI contains semantically annotated scans from the KITTI dataset which consists of laser scans from real urban environments. The scans are annotated with a total of $19$ classes and each scan contains between $82$K and $129$K points. We process each scan entirely without any cropping. The results are provided in Tab. II. Our LatticeNet outperforms all other methods — in case of the most similar SplatNet by more than a factor of two. It is to be noted that DarkNet53Seg , DarkNet21Seg and SqueezeSegV2 are methods that operate on a 2D image by wrapping the laser scans to 2D using spherical coordinates. In contrast, our method can operate on general point clouds, directly in 3D.

Bonn Activity Maps is a dataset for human tracking, activity recognition and anticipation of multiple persons. It contains annotations of persons, their trajectories and activities. The 3D reconstruction of the four kitchen scenarios is however of more interest to us. The environments are reconstructed as 3D colored meshes and have no ground truth semantic annotations. We trained our LatticeNet on the ScanNet dataset and evaluate it on the $4$ kitchens in order to provide an annotation for each vertex of the mesh. The results are shown in Fig. 7. We can observe that our network generalizes well to unseen datasets, recorded with different sensors and with different noise properties as the semantic segmentations look plausible and exhibit sharp borders between classes.

VIII-B Ablation Studies

We perform various ablations regarding our contribution to judge how much they affect the network’s performance.

DeformSlice. We assess the impact that DeformSlice has on the network by comparing it with the Slice operator which does not use learned barycentric interpolation. We evaluate it on the SemanticKITTI, the largest dataset that we are using.

We also evaluate a version of DeformSlice which ensures that the new barycentric coordinates still sum up to one by adding an additional loss term:

However, we observe little change after adding this regularization term and hence use the default version of DeformSlice for the rest of the experiments.

Distribute and PointNet. Another contribution of our work is the usage of a Distribute operator to provide values to the lattice vertices which are later embedded and in a higher-dimensional space by a PointNet-like architecture. The positions and features of the point cloud are treated separately where the features (normals, color) are distributed directly. From the positions, we substract the locally averaged position as we assume that the local point distribution is more important than the coordinates in the global reference frame. We evaluate the impact of elevating the point features to a higher-dimensional space and subtracting the local mean against a simple splatting operator which just averages the features of the points around each corresponding vertex.

We observe that not subtracting the local mean, and just using the $xyz$ coordinates as features, heavily degrades the performance, causing the IoU to drop from $52.9$ to $43.0$. This further reinforces the idea that the local point distribution is a good local feature to use in the first layers of the network.

Not elevating the point cloud features to a higher-dimensional space before applying the max-pool operation also hurts performance but not as severely. In our experiments, we elevate the features to $64$ dimensions by using a series of fully connected layers.

Finally, naively performing a splat operation performs worst with a mere $37.8$ IoU.

VIII-C Performance

We report the time taken for a forward pass and the maximum memory used in our shallow and deep network on the three evaluated datasets. The performance was measured on a NVIDIA Titan X Pascal and the results are gathered in Tab. V.

Despite the reduced memory usage compared to SplatNet and increased speed of execution, there are still memory savings possible by fusing the Distribute and PointNet operators into one GPU operation. This is similar to fusing our DeformSlice and the classification layer. Additionally, we expect the network to become even faster as further advances on highly optimized kernels for convolution on sparse lattices become available. At the moment, the convolutions are performed by our custom CUDA kernels. Tighter integration however with highly optimized libraries like cuDNN could be beneficial.

IX Conclusion

We presented LatticeNet, a novel method for semantic segmentation of point clouds. A sparse permutohedral lattice allows us to efficiently process large point clouds. The usage of PointNet together with a data-dependent interpolation alleviates the quantization issues of other methods. Experiments on three datasets show state-of-the-art results, at a reduced time and memory budget. In the future, we would like to incorporate temporal information into our model in order to process sequential data.

References