RGCNN: Regularized Graph CNN for Point Cloud Segmentation

Introduction

The development of depth sensors like Microsoft Kinect and 3D scanners like LiDAR has enabled convenient acquisition of 3D point clouds, a popular signal representation of arbitrarily-shaped objects in the 3D space. Point clouds consist of a set of points, each of which is composed of 3D coordinates and possibly attributes such as color and normal. Thanks to the efficient representation, point clouds have been widely deployed in various fields, such as 3D immersive tele-presence, navigation for unmanned vehicles, free-viewpoint videos and heritage preservation (tulvan16, ). Hence, the analysis of point clouds, such as point cloud segmentation, becomes active research topics in order to exploit the informative value of point clouds.

Previous point cloud segmentation works can be classified into model-driven segmentation and data-driven segmentation. Model-driven methods include edge-based (rabbani2006segmentation, ), region-growing (rusu2008towards, ) and model-fitting (tarsha2007hough, ), which are based on the prior knowledge of the geometry but sensitive to noise, uneven density and complicated structure. Data-driven segmentation, on the other hand, learns the semantics from data, such as deep learning methods (qi2017pointnet, ). Nevertheless, typical deep learning architectures require regular input data formats, such as images on regular 2D grids or voxels on 3D grids, in order to perform operations like convolution and pooling. For irregular 3D point clouds, most previous works convert them to regular 3D voxel grids (maturana2015voxnet, ) or collections of images (su2015multi, ) before feeding them into typical convolutional neural networks (CNN). This, however, introduces quantization error in the conversion process and renders the resulting data unnecessarily voluminous.

Recently, Graph Convolutional Neural Network (GCNN) has been proposed to generalize CNNs to graphs (kipf2016semi, ). The key idea is to consider the convolution of graphs in the spectral domain, leveraging on spectral graph theory (chung97, ). However, this requires the eigen-decomposition of graph Laplacian matrices (chung97, ) that describe the connectivity of graphs, which is computationally expensive. Hence, several methods propose to approximate the convolution in the spectral domain by spatial filtering, such as Chebyshev polynomials (hammond2011wavelets, ), Lanczos method (susnjara2015accelerated, ), Cayley polynomials (levie2017cayleynets, ), etc. Nevertheless, the graph Laplacian matrix is always fixed, which is unable to represent the structures of dynamic graphs in the learning process. Also, though GCNN has shown its efficiency in semi-supervised classification, it hasn’t been deployed to point cloud segmentation yet.

In order to address the above problems, we propose a regularized graph convolutional neural network (RGCNN) for point cloud segmentation. As depicted in Fig. 1, RGCNN treats the features of points as graph signals, and takes the feature matrix and adjacency matrix of irregular point clouds as the input. Specifically, we choose the coordinates and normals of each point as the features to represent the underlying geometry of point clouds. The output is the per point segmentation labels for each point of the input. Leveraging on the basic framework of GCNN with truncated Chebyshev approximation, we design a three-layer GCNN with high-order Chebyshev polynomials. In particular, we incorporate a graph-signal smoothness prior into the loss function, which regularizes the learning process. This essentially combines data-driven methods with model-driven ones. Further, we prove the spectral smoothing property of this prior, which essentially enforces Laplacian smoothing in the spectral domain. Besides, instead of fixing the graph structure as in previous works (e.g., (yi2016syncspeccnn, )), we update the graph Laplacian matrix in each layer, thus capturing the dynamic topology of graphs. We also prove the permutation-invariance property of the proposed RGCNN, so that when the input permutes, the output permutes in the same way. Finally, we extend the architecture of RGCNN for the application of point cloud classification.

While details are presented in the paper, the key contributions are as follows:

To the best of our knowledge, we are the first to design GCNN for point cloud segmentation, which is suitable for consuming unordered 3D point clouds;

We regularize each layer of RGCNN by adding graph-signal smoothness prior in the loss function, and prove the spectral smoothing property of this prior;

We update the graph Laplacian matrix in each layer of RGCNN, in order to adaptively capture the structure of dynamic graphs.

Extensive experiments show that RGCNN significantly reduces the computation complexity while achieving competitive results with the state of the art. It is also much more robust to both low density and noise in comparison with other methods.

The rest of the paper is organized as follows. Section 2 provides a review on previous works of point cloud coding and introduce GCNN as the basic framework. We present the problem statement of point cloud segmentation in Section 3, and then elaborate on the proposed RGCNN in Section 4. The proposed loss function and theoretical analysis is discussed in Section 5. Next, performance evaluation and comparison is presented in Section 6. Finally, we conclude the paper in Section 7.

Related Work

We will first review previous works on point cloud segmentation, and then introduce GCNN, which inspires the proposed method.

Previous works on point cloud segmentation can be mainly classified into two categories: model-driven methods and data-driven methods.

Model-driven methods: This class of approaches segment point clouds by assuming certain models of the underlying geometry. According to different models, they are further categorized as follows.

Edge-based methods: Rabbani et al. propose an edge-based method in (rabbani2006segmentation, ), which outlines the borders of different regions by edge detection and then groups points inside the borders to deliver final segments. Jiang et al. (jiang1996fast, ) propose scan-line grouping methods to represent surfaces, and divide them by edges. This achieves good performance on range images, but is unsuitable for point clouds with uneven density. Although edge-based methods are fast, they are sensitive to noise and uneven density.

Region growing methods: Starting from one or more points with specific characteristics, these methods grow around adjacent and similar points. Further, these methods can be divided into top-down approaches and bottom-up approaches. The difference includes the initial choice of points and how they grow afterwards. The main disadvantage lies in the selection of initial points and in the presence of complicated structures.

Model fitting methods: This category is based on the observation that many man-made objects can be decomposed into geometric primitives like planes, cylinder and spheres. Points that conform to some primitive shapes are treated as one segment. Two popular algorithms include the Hough Transform (tarsha2007hough, ) and the Random Sample Consensus approach (chen2014methodology, ). However, details may fail to be modelled into easily recognizable geometric primitives.

Model-driven methods are primarily limited by the assumed prior knowledge. Also, objects with complex structures are great challenges for small-scale model datasets.

Data-driven methods This class is concerned with Artificial Intelligence algorithms based on empirical and training data. As 3D point clouds are irregular, traditional data-driven methods cannot be applied directly. Preprocessing, such as feature extraction, is thus required. Features of high quality can greatly improve the learning efficiency.

Segmentation based on clustering: Clustering groups (3D) points into clusters based on attributes or features. Biosca et al. deploy unsupervised clustering and fuzzy algorithms for laser point clouds (biosca2008unsupervised, ). Filin et al. proposes an approach using normal vectors derived from a neighborhood system called slope adaptive (filin2002surface, ), where the slopes of normal vectors and height difference between each point and its neighbors are applied as features. Ma et al. exploit spectral clustering for point cloud segmentation (ma2010point, ), and propose a novel approach to find k-nearest-neighbors for graph construction. Clustering-based segmentation achieves better performance than model-driven methods under complex scenes. However, there lacks the view of local information.

Deep learning segmentation: Deep learning methods have shown great potential in 3D shape recognition, such as view-based learning (su2015multi, ), 3D ShapeNets (wu20153d, ), VoxNet (maturana2015voxnet, ) and VoxelNet (zhou2017voxelnet, ), which are mainly designed for point cloud classification.

Regarding point cloud segmentation, Qi et al. come up with PointNet, a neural network which consumes point clouds directly (qi2017pointnet, ). The key breakthrough is the proposed symmetric function applied to the raw point cloud data. However, PointNet processes each point identically and independently. Hence, PointNet++ is proposed in (qi2017pointnet++, ) by introducing hierarchical grouping, which achieves better performance.

2. Graph Convolutional Neural Network

As CNN only deals with data defined on regular grids, it is extended to graphs for irregular data, which is referred to as GCNN. The key challenge is to define convolution over graphs, which is difficult due to the irregularity.

Spectral methods: The convolution over graphs is defined in the spectral domain, which is the multiplication of the signal on graph with the eigenvector matrix of the graph Laplacian matrix (hammond2011wavelets, ; henaff2015deep, ). The computation complexity, however, is high due to the eigen-decomposition of the graph Laplacian matrix in order to get the eigenvector matrix. Hence, it is improved by (defferrard2016convolutional, ) through fast localized convolutions, where Chebyshev expansion is deployed to approximate graph Fourier transform (GFT). Susnjara et al. introduce the Lancoz method for approximation (susnjara2015accelerated, ).

Spatial methods: In this method , many techniques are introduced to implement convolution directly on each node and its neighbors. Gori et al. introduce recurrent neural networks that operate on graphs in (gori2005new, ). Duvenaud et al. propose a convolution-like propagation to acculmulate local features (duvenaud2015convolutional, ). Bruna et al. deploy the multiscale clustering of graphs in convolution to implement multi-scale representation (bruna2013spectral, ). Furthermore, Niepert et al. define convolution on a sequence of nodes and perform normalization afterwards (niepert2016learning, ). Spatial methods provide strong localized filters, but it also means it is difficult to learn the global structure.

Spectral GCNN has shown its efficiency in semi-supervised classification (kipf2016semi, ), which outperforms many state-of-the-art methods significantly on citation networks and node classification. However, to the best of our knowledge, we are the first to extend it to point cloud segmentation.

Problem Statement

In the proposed RGCNN, the input is a $n\times m$ feature matrix $\mathbf{P}$ and a $n\times n$ adjacency matrix $W$. Assuming we have $k$ semantic labels, RGCNN outputs $n\times k$ scores $\mathbf{S}$ for each of the $n$ points and each of the $k$ labels.

The Proposed RGCNN

We first present the overall RGCNN architecture, and then elaborate on important modules including graph construction, graph convolution and feature learning respectively.

As depicted in Fig. 2, RGCNN consists of one general model for extracting features and two branches for segmentation and classification tasks respectively. It takes raw point clouds with coordinates and normals as the input, learns local features by graph convolution and then outputs the segmentation or classification score. In the segmentation branch, we deploy graph convolution to aggregate features, and then concatenate features from different layers to represent both local and global features. The per-point label is finally given in the output layer. In the classification branch, we additionally deploy global max pooling to collect global features and use multilayer perceptron (MLP) to get the final score. Specifically, RGCNN has three regularized graph convolution layers. Each layer consists of graph construction, graph convolution and feature filtering, which are elaborated in order as follows.

2. Graph Construction

As the graph construction has crucial effect on the efficiency of the network, we first discuss the proposed approach to construct graphs over point clouds.

Graph and Graph Laplacian. We consider an undirected graph $\mathcal{G}=\{\mathcal{V},\mathcal{E},\mathbf{A}\}$ composed of a vertex set $\mathcal{V}$ of cardinality $|\mathcal{V}|=n$, an edge set $\mathcal{E}$ connecting vertices, and a weighted adjacency matrix $\mathbf{A}$. $\mathbf{A}$ is a real symmetric $n\times n$ matrix, where $a_{i,j}$ is the weight assigned to the edge $(i,j)$ connecting vertices $i$ and $j$. We assume non-negative weights, i.e., $a_{i,j}\geq 0$.

The Laplacian matrix is defined from the adjacency matrix. Among different variants of Laplacian matrices, the combinatorial graph Laplacian used in (Shen10, ; Hu12, ; Hu14, ) is defined as $\mathcal{L}_{c}:=\mathbf{D}-\mathbf{A}$, where $\mathbf{D}$ is the degree matrix—a diagonal matrix with $d_{i,i}=\sum_{j=1}^{n}a_{i,j}$. One normalized graph Laplacian matrix is defined as $\mathcal{L}=\mathbf{D}^{-\frac{1}{2}}\mathcal{L}_{c}\mathbf{D}^{-\frac{1}{2}}$, which is used in the sequel because of its normalization property.

Graph signal. Graph signal refers to data residing on the vertices of a graph. In this paper, the graph signal is the features of each point in the point cloud, i.e., the feature vector $\mathbf{p}_{i}$ of the $i$-th point.

Graph Construction. Though there exist various ways to construct graphs, we choose complete graphs, which connect each point with all the other points in the point cloud and thus consider the relationship among all the points. The edge weight is defined based on the distance between features of points, which is able to measure the similarity among points in terms of structure. Specifically, the weight of an edge connecting points $i$ and $j$ is defined as

where $\beta$ is a scalar parameter. We empirically set $\beta=1$ in the experiments.

3. Graph Convolution

The core of GCNN is graph convolution. Unlike images or videos, it is difficult to define convolution over graphs in the vertex domain, because a meaningful translation operator in the vertex domain is nontrivial to define due to the unordered vertices. Hence, inspired by (defferrard2016convolutional, ), we start from filtering of graph signals in the spectral domain, and then deploy Chebyshev approximation to reduce the computational complexity.

Spectral filtering of graph signals. The convolution operator on a graph $\ast_{\mathcal{G}}$ is first defined in the spectral domain (bruna2013spectral, ), specifically in the GFT domain. GFT is computed from the graph Laplacian matrix. As the graph Laplacian is symmetric and positive semi-definite, it admits a complete set of orthonormal eigenvectors. The GFT basis $\mathbf{U}$ is then the eigenvector set of the Laplacian matrix. The GFT of a graph signal $\mathbf{x}$ is thus defined as $\hat{\mathbf{x}}={\mathbf{U}^{T}}\mathbf{x}$, and the inverse GFT follows as $\mathbf{x}^{\prime}=\mathbf{U}\hat{\mathbf{x}}$.

Hence, the convolution between two graph signals $\mathbf{x}$ and $\mathbf{y}$ can be defined as the multiplication of the corresponding GFT coefficients, followed by the inverse GFT, i.e.,

where $\odot$ is the element-wise Hadamard product. Then the spectral filtering of a graph signal $\mathbf{x}$ by $g_{\theta}$ is

Chebyshev approximation for localized filtering. The spectral filtering, however, has two limitations: 1) it has high computational complexity of $\mathcal{O}(n^{3})$ due to the eigen-decomposition of the graph Laplacian; 2) it is not localized. Hence, Defferrard et al. propose to use truncated Chebyshev polynomials to approximate the spectral filtering (defferrard2016convolutional, ). The K-localized filtering operation is described as follows.

where $\theta_{k}$ denotes the $k$-th Chebyshev coefficient. $T_{k}(\mathcal{L})$ is the Chebyshev polynomial of order $k$. It is recurrently calculated by $T_{k}(\mathcal{L})=2\mathcal{L}T_{k-1}(\mathcal{L})-T_{k-2}(\mathcal{L})$, where $T_{0}(\mathcal{L})=1,T_{1}(\mathcal{L})=\mathcal{L}$. Now the computational complexity is reduced to $\mathcal{O}(K|\mathcal{E}|)$.

4. Feature learning

Following the graph convolution, we generate a new feature vector for each point from a weight matrix, a bias and the ReLU activation function. This is formulated as follows:

In practice, each output feature is calculated by $y_{i}=\sum\limits_{j=1}^{F_{2}}w_{i,j}x_{i}$, $i=0,...,K-1$. When $K=1$, it is equivalent to a one-layer perceptron shared by all the points, which plays an important role in some deep learning networks, such as PointNet. This works well in capturing features of individual points, but loses the neighborhood information. In our model, we take the neighborhood into consideration by graph convolution with truncated Chebyshev polynomials of order $K>1$, thus incorporating local features.

Fig. 3 demonstrates that the feature space varies in different layers. We observe that a deeper layer is able to capture semantically similar structures better in the high-dimensional feature space.

The Proposed Loss Function and Theoretical Analysis

This section presents the proposed loss function, in which a graph-signal smoothness prior is added. We then provide theoretical analysis of the added prior, and also prove the permutation invariance property of RGCNN.

While the common error function in the loss function is the consistency of outputs with targets, i.e., the cross entropy, we propose to additionally incorporate a graph-signal smoothness prior as the regularization term. This prior essentially enforces the features of adjacent vertices to be more similar, which eases the segmentation task.

Graph-signal Smoothness Prior. A graph signal $\mathbf{y}$ defined on a graph $\mathcal{G}$ is smooth with respect to the topology of $\mathcal{G}$ if

where $\epsilon$ is a small positive scalar, and $i\sim j$ denotes two vertices $i$ and $j$ are one-hop neighbors in the graph. In order to satisfy Eq. (6), $y_{i}$ and $y_{j}$ have to be similar for a large edge weight $a_{i,j}$, and could be quite different for a small $a_{i,j}$. Hence, Eq. (6) enforces $\mathbf{y}$ to adapt to the topology of $\mathcal{G}$, which is thus coined graph-signal smoothness prior.

As $\mathbf{y}^{T}\mathcal{L}\mathbf{y}=\sum\limits_{i\sim j}a_{i,j}(y_{i}-y_{j})^{2}$ (Spielman04, ), Eq. (6) is concisely written as $\mathbf{y}^{T}\mathcal{L}\mathbf{y}<\epsilon$ in the sequel.

Loss Function. We add the aforementioned graph-signal smoothness prior in the loss function. In particular, the prior is computed from all the three graph convolution layers. The mathematical description is

where $\mathbf{y}^{o}$ is the output score, $\mathbf{y}^{\prime}$ is the ground truth label, and $\mathbf{y}_{l}$ is the feature map of the $l$-th layer. $\gamma$ is the penalty parameter for the smoothness term, which is empirically set to $10^{-9}$ in our experiments.

2. Theoretical analysis

We provide analysis for the spectral property of the graph-signal smoothness prior and the permutation-invariance property of the proposed architecture.

Theorem 1. The graph-signal smoothness prior enforces more low-frequency components in the GFT domain.

Proof. While we have discussed that the added graph-signal smoothness prior regularizes the graph signal to be adapted to the structure of the graph, we further analyze the spectral behaviour of this prior. Specifically, as $\mathcal{L}$ is diagonalizable as $\mathbf{U}\Lambda\mathbf{U}^{T}$ as mentioned earlier, we have

Hence, when we try to minimize the graph-signal smoothness prior in the loss function, the higher-frequency coefficients are weighted by a larger eigenvalue, and are thus penalized more heavily. This means that by adding this prior into the loss function, low-frequency components are better preserved, which leads to smoothing in the spectral domain. The smoothing operation enforces the features of vertices within each connected component of the graph similar, thus greatly easing the segmentation task.

Theorem 2. The proposed RGCNN is permutation-invariant, i.e., if the rows of the input feature matrix are permuted, the output permutes in the same way.

Theorem 2 indicates that the segmentation result of RGCNN is irrelevant to the order of the input, which is suitable for the unordered point cloud data. The proof is as follows.

Proof. Denote a $n\times n$ permutation matrix by $\mathbf{H}$. We prove if the input $n\times m$ feature matrix $\mathbf{P}$ is permuted by $\mathbf{H}$, i.e., $\mathbf{H}\mathbf{P}$, then the $n\times k$ output $\mathbf{S}$ permutes as $\mathbf{H}\mathbf{S}$.

Since the main operation of RGCNN is graph convolution, according to Eq. (4), we have

Experimental Results

In order to evaluate the performance of RGCNN, we carry out extensive experiments for point cloud segmentation, in terms of the segmentation accuracy and the robustness to density and noise. Further, we apply the network architecture to the classification task and provide comparison with the state-of-the-art methods. Finally, we provide analysis on the space and time complexity, and discuss the connections and differences of RGCNN with other competing methods.

Architecture parameters. In the architecture depicted in Fig. 2, the network comprises of three graph convolution layers with the Chebyshev order $K=(6,5,3)$ and dimensions of generated features $F=(128,512,1024)$, followed by three MLP layers $(512,192,50)$.

Training. We conduct experiments on ShapeNet part dataset (yi2016scalable, ). This contains 16881 shapes from 16 categories, annotated with 50 labels in total. In the experiments, we first utilize random sampling to extract 2048 points from each model, which form the input point clouds. Then we feed the coordinates and normal of each point into our model as raw features. We follow the training/validation/test setting proposed in (yi2016scalable, ), assuming each category label is known for each sample. Our full model is trained on a single Nvidia GeForce GTX 1080Ti with 100 epochs.

Evaluation metric. We evaluate segmentation by mean Intersection of Union (mIoU). IoU is widely used in semantic segmentation to measure the ratio of the ground truth and prediction, and mean IoU is the average of IoU for each label appearing in the model categories. We compare our method with ShapeNet (yi2016scalable, ), PointNet (qi2017pointnet, ), PointNet++ (qi2017pointnet++, ) and SynSpecCNN (yi2016syncspeccnn, ).

2. Point cloud segmentation results

The evaluation results are listed in Table 1. Our model outperforms the other competing methods in 5 categories, and achieves competitive results with the state-of-the-art. Further, we demonstrate some visual results in Table 2. It can be observed that RGCNN has better and more consistent segmentation results than PointNet for some challenging objects. More segmentation results of RGCNN are shown in Fig. 8.

Also, we evaluate the proposed graph construction of fully-connected graphs. We test the commonly used $k$-nearest-neighbor graphs with $k=30$. The resulting mean mIoU is $80.4\%$, which is much lower than using the proposed fully-connected graph. This confirms that the fully-connected graph is able to capture more abundant information, thus leading to better segmentation results.

3. Robustness test

Robustness to noise. In order to test the robustness of our model to random noise, we jitter the coordinates of the raw data with Gauss noise, with zero mean and standard deviation $\sigma\in[0.02,0.2]$. Fig. 4 provides mIoU under different noise levels for PointNet and our method. We see that while the performance of PointNet drops quickly with increasing noise variance, RGCNN is robust to noise even when the noise level is high. Also, our segmentation result is visually close to the ground truth from the macroscopic view even when $\sigma=0.1$, as demonstrated in Fig. 5.

Robustness to density. We also test the robustness of our model to point clouds of low density. Random dropping is adopted to remove points with missing ratios $\{0.5,0.75,0.85,0.95\}$. As depicted in Fig. 6, our accuracy keeps $85\%$ even when the missing ratio is $0.75$, which outperforms PointNet ($73\%$) significantly. This is also visualized in Fig. 7, where our segmentation result is still satisfactory compared with the ground truth.

Hence, RGCNN is very robust to sparse and noisy point clouds. This gives credit to the proposed updated graph Laplacian and graph-signal smoothness prior in the loss function. This property is important in practical applications, since point clouds often suffer from noise or low density mainly due to inherent limitations of acquisition sensors.

4. Application to point cloud classification

We extend our model to the task of point cloud classification, as shown in the second branch of Fig. 2. It is tested on ModelNet40 dataset to predict the category of a given model. This dataset includes 12311 models from 40 categories, among which we utilize 9843 models for training and 2468 for testing. For each model, we select 1024 points with coordinates and normals randomly as the input point cloud, and then normalize each point cloud to a unit cube. Table 3 lists the classification results of different competing methods. It can be seen that our classification accuracy is better than PointNet and comparable to PointNet++.

5. Space and time complexity

We further compare the space and time complexity with other methods. Here, we choose our classification model to test the space and time complexity. Table 4 shows that our model has the fastest forward time with acceptable model size among these methods. Hence, our model is amenable to real-time classification tasks. Further, we test that the forward time will be even shorter (4.8 ms approximately) if we use fixed graphs instead.

6. Discussion

Finally, we discuss the connections between our method and the other competing methods, as well as the advantages and limit in the following.

In graph-based neural networks, the structure of the constructed graph plays an important role for tasks such as point cloud segmentation. Compared with existing graph-based methods in which the graph is fixed in general, our graph structure is dynamic to features in the learning process, thus adaptively capturing the generated features. Also, our graph construction is more computationally efficient.

PointNet deploys MLP to extract the feature of each individual point and utilizes global pooling to extract the global feature, which is a special case in our model when the order of the Chebyshev polynomial is $K=0$. Additionaly, our model is able to take the features of the $K$-hop neighborhood into consideration when $K\geq 1$.

In SynSpecCNN, the connection between the spectral and spatial domain is learned, while our graph convolution is another form of spectral approximation but with more flexibility because of the dynamically updated graph Laplacian.

The boundary between two segments is sometimes not quite sharp in our results, which limits the performance to some extent.

Conclusion

We propose RGCNN, a regularized graph convolutional neural network architecture that directly consumes irregular 3D point clouds. We introduce a graph-signal smoothness prior into the loss function, which essentially enforces Laplacian smoothing in both the spectral and spatial domain. Further, we update the graph Laplacian in each layer of the network in order to adaptively capture the dynamic graphs. Also, we prove the permutation-invariance property of RGCNN, which is suitable for the applications of unordered point clouds. Experimental results on the ShapeNet part dataset for point cloud segmentation validate the effectiveness of RGCNN, showing that RGCNN achieves competitive performance with the state of the art, with much lower computational complexity. We also evaluate that RGCNN is much more robust to both low density and noise than other competing methods. Further, we extend RGCNN for point cloud classification and achieve competitive results on ModelNet40 dataset.

References