Point Convolutional Neural Networks by Extension Operators

Abstract

This paper presents Point Convolutional Neural Networks (PCNN): a novel framework for applying convolutional neural networks to point clouds. The framework consists of two operators: extension and restriction, mapping point cloud functions to volumetric functions and vise-versa. A point cloud convolution is defined by pull-back of the Euclidean volumetric convolution via an extension-restriction mechanism.

The point cloud convolution is computationally efficient, invariant to the order of points in the point cloud, robust to different samplings and varying densities, and translation invariant, that is the same convolution kernel is used at all points. PCNN generalizes image CNNs and allows readily adapting their architectures to the point cloud setting.

Evaluation of PCNN on three central point cloud learning benchmarks convincingly outperform competing point cloud learning methods, and the vast majority of methods working with more informative shape representations such as surfaces and/or normals.

Introduction

The huge success of deep learning in image analysis motivates researchers to generalize deep learning techniques to work on 3D shapes. Differently from images, 3D data has several popular representation, most notably surface meshes and points clouds. Surface-based methods exploit connectivity information for 3D deep learning based on rendering , local and global parameterization , or spectral properties . Point cloud methods rely mostly on points’ locations in three-dimensional space and need to implicitly infer how the points are connected to form the underlying shape.

Invariance to point order in $X$ was previously tackled in by designing networks that are composition of euuquivariant layers (i.e., commute with permutations) and a final symmetric layer (i.e., invariant to permutations). As shown in , any linear equivariant layer is a combination of scaled identity and constant linear operator and therefore missing many of the degrees of freedom existing in standard linear layers such as fully connected and even convolutional.

Volumetric grid methods use 3D occupancy grid to deal with the point order in $X$ and provide translation invariance of the convolution operator. However, they quantize the point cloud to a 3D grid, usually producing a crude approximation to the underlying shape (i.e., piecewise constant on voxels) and are confined to a fixed 3D grid structure.

We take $\mathcal{E}_{X}$ to be a Radial Basis Function (RBF) approximation operator, and $\mathcal{R}_{X}$ to be a sampling operator, i.e., sample a volumetric function at the points in $X$. As $O$ we take continuous volumetric convolution operators with general kernels $\kappa$ represented in the RBF basis as-well. In turn (1) is calculated using a sparse linear tensor combining the learnable kernel weights $k$, function values over the point cloud $X$, and a tensor connecting the two, defined directly from the point cloud $X$.

This means that two different samplings $X,X^{\prime}\subset S$ of the same surface function are extended to the same volumetric function, up to an approximation error. In particular, we show that extending the simplest, constant one function over the point cloud, $\mathcal{E}_{X}[\mathbf{1}]$, approximates the indicator function of the surface $S$, while the gradient, $\nabla\mathcal{E}_{X}[\mathbf{1}]$, approximates the mean curvature normal field over the surface. Then, the translation invariance and robustness of our convolution operator naturally follows from the fact that the volumetric convolution is translation invariant and the extension operator is robust.

PCNN provides a flexible framework for adapting standard image-based CNNs to the point cloud setting, while maintaining data only over the point cloud on the one hand, and learning convolution kernels robust to sampling on the other. We have tested our PCNN framework on standard classification, segmentation and normal estimation datasets where PCNN outperformed all other point cloud methods and the vast majority of other methods that use more informative shape representations such as surface connectivity.

Previous Work

We review different aspects of geometric deep learning with a focus on the point cloud setting. For a more comprehensive survey on geometric deep learning we refer the reader to .

PointNet pioneered deep learning for point clouds with a Siamese, per-point network composed with a symmetric max operator that guarantees invariance to the points’ order. PointNet was proven to be a universal approximator (i.e., can approximate arbitrary continuous functions over point clouds). A follow up work suggests a hierarchical application of the PointNet model to different subsets of the point cloud; this allows capturing structure at different resolutions when applied with a suitable aggregation mechanism. In the PointNet model is used to predict local shape properties from point clouds. In a related work suggest to approximate set function, with equivariant layers composed with a symmetric function such as max. Most related to our work is the recent work of that suggested to generalize convolutional networks to point clouds by defining convolutions directly on kd-trees built out of the point clouds , and that suggested a convolutional architecture for modeling quantum interactions in molecules represented as point clouds, where convolutions are defined by multiplication with continuous filters. The main difference to our work is that we define the convolution of a point cloud function using an exact volumetric convolution with an extended version of the function. The approximation properties of the extended function facilitate a robust convolution on point clouds.

Volumetric methods.

Another strategy is to generate a tensor volumetric representation of the shape restricted to a regular grid (e.g., by using occupancy indicators, or a distance function) . The main limitation of these methods is the approximation quality of the underlying shape due to the low resolution enforced by the three dimensional grid structure. To overcome this limitation a few methods suggested to use sparse three dimensional data structures such as octrees . Our work can be seen as a generalization of these volumetric methods in that it allows replacing the grid cell’s indicator functions as the basis for the network’s functions and convolution kernels with more general basis functions (e.g., radial basis functions).

Deep learning on Graphs.

Shapes can be represented as graphs, namely points with neighboring relations. In spectral deep learning the convolution is being replaced by a diagonal operator in the graph-Laplacian eigenbasis . The main limitation of these methods in the context of geometric deep learning is that different graphs have different spectral bases and finding correspondences between the bases or common bases is challenging. This problem was recently targeted by using the functional map framework.

Deep learning on surfaces.

Other approaches to geometric deep learning work with triangular meshes that posses also connectivity and normal information, in addition to the point locations. One class of methods use rendering and 2D projections to reduce the problem to the image setting . Another line of works uses local surface representations or global parameterizations of surfaces for reducing functions on surfaces to the planar domain or for defining convolution operators directly over the surfaces.

RBF networks.

Method

Goal.

Efficiency: $O_{X}$ is computationally efficient.

Invariance: $O_{X}$ is indifferent to the order of points in $X$, that is, $O_{X}$ is equivariant.

Translation invariance: $O_{X}$ is translation invariant, defined by a stationary (i.e., location independent) kernel.

In the next paragraphs we define these operators and show how they are used in defining the main building blocks of PCNN, namely: convolution, pooling and upsampling. We discuss the above theoretical properties in Section 4.

Extension operator

where $c$ is a constant depending on the RBF $\Phi$ and $\omega_{i}$ can be thought of the amount of shape area corresponding to point $x_{i}$. A practical choice of $\omega_{i}$ is

Note that although this choice resembles the Nadaraya-Watson kernel estimator , it is in fact different as the denominator is independent of the approximation point $x$; this property will be useful for the closed-form calculation of the convolution operator.

As we prove in Section 4, the point cloud convolution operator, $O_{X}$, defined using the extension operator, (4)-(5), satisfies the properties (1)-(4) listed above, making it suitable for deep learning on point clouds. In fact, as we show in Section 4, robustness is the result of the extension operator $\mathcal{E}_{X}$ approximating a continuous, sampling independent operator over the underlying surface $S$ denoted $\mathcal{E}_{S}$. This continuous operator applied to a function $f$, $\mathcal{E}_{S}[f]$, is proved to approximate the restriction of $f$ to the surface $S$.

Figure 2 demonstrates the robustness of our extension operator $\mathcal{E}_{X}$; applying it to the constant one function, evaluated on three different sampling densities of the same shape, results in approximately the same shape.

Kernel model

Restriction operator

Sparse extrinsic convolution

Applying our restriction operator finally gives our point cloud convolution operator:

Choice of RBF

Our choice of radial basis function $\Phi$ stems from two desired properties: First, we want the extension operator (4) to have approximation properties; second, we want the computation of the convolution of a pair of RBFs in (11) to have an efficient closed-form solution. A natural choice satisfying these requirements is the Gaussian:

Let $\Phi$ denote the Gaussian as in (12). Then,

where $\gamma=\sqrt{\alpha^{2}+\beta^{2}}$.

1 Up-sampling and pooling

Pooling does not require the extension/restriction operators and (similarly to ) is defined by

where $\mathcal{V}_{i^{*}}\subset\left\{1,2,\ldots,I\right\}$ denotes the set of indices of points in $X$ that are closer in Euclidean distance to $x^{*}_{i}$ than any other point in $X^{*}$. The point cloud $X^{*}\subset X$ in the next layer is calculated using farthest point sampling of the input point cloud $X$.

Lastly, similarly to we implement deconvolution layers by an upsampling layer followed by a regular convolution layer.

Properties

In this section we discuss the properties of the point cloud operators we have defined above.

The equivariance of our point cloud operators $O_{X}$ stems from the invariance property of the extension operator and equivariance property of the restriction operator. We will next show these properties.

The extension operators defined in (4) is invariant to permutations, i.e., $\mathcal{E}_{\pi X}[f]=\mathcal{E}_{X}[f]$, for all permutations $\pi\in\Pi_{I}$. The restriction operator (9) is equivariant to permutations, $\mathcal{R}_{\pi X}[\psi]=\pi\mathcal{R}_{X}[\psi]$, for all $\pi\in\Pi_{I}$.

The properties follow from the definitions of the operators.

Theorem 1 applies in particular to convolutions (7), and therefore our point cloud convolutions are all equivariant by construction. Note that this model provides ”data-dependent” equivariant operator that are more general than those suggest in .

2 Robustness

We introduce a continuous extension operator $E_{S}$ from surface functions to volumetric functions. We show that $E_{S}$ has several favorable properties.

We show that (under mild assumptions) our extension operator $\mathcal{E}_{X}$, defined in (4)-(5) converges to $\mathcal{E}_{S}$,

We deduce that (under mild assumptions) the properties of $\mathcal{E}_{S}$ are inherited by $\mathcal{E}_{X}$ and in particular we have:

Continuous extension operator.

where $da$ is the area element of the surface $S$.

The operator $\mathcal{E}_{S}$ enjoys several favorable approximation properties: First,

These results are summarized in the following theorem which is proved in appendix A.

the Voronoi cell of $x_{i}\in S$, where $d_{S}$ denotes the distance function of points on $S$, satisfies

where $X\subset S$ is a $\delta$-net and $\delta\rightarrow 0$. Furthermore, $\mathcal{E}_{S}$ satisfies the approximation and mean curvature properties as defined in (19), (20), (21).

3 Revisiting image CNNs

Experiments

We have tested our PCNN framework on the problems of point cloud classification, point cloud segmentation, and point cloud normal estimation. We also evaluated the different design choices and network variations.

At test time, similarly to we use voting: we sample ten different samples of size 1024 from 1200 points on each point cloud, apply anisotropic scaling, propagate it through the net and sum the label probability vectors before taking the label with the maximal probability.

We used standard convolution architecture, see Figure 4:

where conv_block(#points in, #points out ,#channels) consists of a convolution layer, batch normalization, Relu activation and pooling. The fully connected block is a concatenation of a two fully connected layers with dropout after each one.

The inset compares our method with when feeding a trained $1024$ point model on sparser test point clouds of size $k=1024,512,256,128,64$.

The favorable robustness of our method to sub-sampling can be possibly explained by the fact that our extension operator possess approximation power, even with sparse samples, e.g., for smooth shapes, see Figure 2.

Method variants.

Feature visualizations.

Figure 5 visualizes the features learned in the first layer of PCNN on a few shapes from the ModelNet40 dataset. As in the case of images, the features learned on the first layer are mostly edge detectors and directional derivatives. Note that the features are consistent through different sampling and shapes. Figure 6 shows 9 different features learned in the third layer of PCNN. In this layer the features capture more semantically meaningful parts.

2 Point cloud segmentation

Our method can also be used for part segmentation: given a point cloud that represents a shape the task is to label each point with a correct part label. We evaluate PCNN performance on ShapeNet part dataset . ShapeNet contains 16,881 shapes from 16 different categories, and total of 50 part labels.

Table 3 compares per-category and mean IoU(%) scores of PCNN with state of the art point cloud methods: PointNet , kd-network , and 3DCNN (results taken from ). Our method outperforms all of these methods. For completeness we also provide results of other methods that use additional shape features or mesh normals as input. Figure 7 depicts several of our segmentation results.

For this task we used standard convolution segmentation architecture, see Figure 4:

where deconv_block(#points in,#points out,#features) consists of an upsampling layer followed by a convolution block. In order to provide the last layers with raw features we also add skip-layers connections, see Figure 4(b). This is a common practice in such architectures where fine details are needed at the output layer (e.g., ).

We use the data from (2048 uniformly sampled points on each model). As done in we use a single network to predict segmentations for each of the object classes and concatenate a hot-one encoding of the object’s label to the bottleneck feature layer. At test time, we use only the part labels that correspond to the input shape (as in ).

3 Normal estimation

Estimating normals of a point cloud is a central sub-problem of the 3D reconstruction problem. We cast this problem as supervised regression problem and employ segmentation network with the following changes: the output layer is composed of $3$ channels instead of $50$ which are then normalized and fed into cosine-loss with the ground truth normals.

We have trained and tested our network on the standard train/test splits of the ModelNet40 dataset (we used the data generator code by ). Table 4 compares the mean cosine loss (distance) of PCNN and the normal estimation of and . Figure 8 depicts normal estimation examples from this challenge.

4 Training details, timings and network size

We implemented our method using the TensorFlow library in Python. We used the Adam optimization method with learning rate 0.001 and decay rate 0.7. The models were trained on Nvidia p100 GPUs. Table 5 summarizes running times and network sizes. Our smaller classification network achieves state of the art result (see Table 2, previous to last row) and has only 1.4M parameters with a total model size of 17 MB.

Conclusions

This paper describes PCNN: a methodology for defining convolution of functions over point clouds that is efficient, invariant to point cloud order, robust to point sampling and density, and posses translation invariance. The key idea is to translate volumetric convolution to arbitrary point clouds using extension and restriction operators.

Acknowledgements

This research was supported in part by the European Research Council (ERC Consolidator Grant, ”LiftMatch” 771136), the Israel Science Foundation (Grant No. 1830/17). We would like thank the authors of PointNet for sharing their code and data.

References

Appendix A Proofs

where $\mu=\mu_{1}+\mu_{2}$, $\sigma=\sqrt{\sigma_{1}^{2}+\sigma_{2}^{2}}$ and $C(\sigma_{1},\sigma_{2})=\frac{B(\sigma_{1})B(\sigma_{2})}{B(\sigma)}$

It is well known that the convolution of two normal distributions is again a normal distribution:

The result above follows from the linearity of the convolution. ∎

A.2 Theoretical properties of the extension operator

To show (19) first let $x\notin S$. Then as $\sigma\rightarrow 0$ we have $\max_{y\in S}\Phi_{\sigma}(|y-x|)\rightarrow 0$ and therefore $\mathcal{E}_{S}[f](x)\rightarrow 0$. Next consider $x\in S$. It is enough to show that

Indeed, let $\epsilon>0$. Since $f$ is uniformly continuous, take $\delta>0$ sufficiently small so that $\left|f(x)-f(x^{\prime})\right|<\epsilon$ if $d_{S}(x,x^{\prime})<\delta$. Take $\sigma>0$ sufficiently small so that

where $B(x,\delta)=\left\{y\ |\ |y-x|<\delta\right\}$ and

Using an argument from (see Section 4.2) where we take $\sigma^{2}=2t$ in their notation and get convergence to $-\frac{1}{2}\Delta_{S}x$, where $\Delta_{S}$ is the Laplace-Beltrami operator on surfaces $S$. To finish the proof remember that

Denote $T_{x}S$ the tangent plane to $S$ centered at $x\in S$. Let $y=y(u):T_{x}S\rightarrow S$ be the local parameterization to $S$ over $T_{x}S$, where $u$ is the local coordinate at $T_{x}S$. Since $S$ is smooth and compact we have that $\forall u\in\Upsilon_{\delta}=T_{x}S\cap B(x,\delta)$,

where $|dy(u)|$ is the pulled-back area element of $S$ . We break the error to $\left|\frac{1}{2\pi\sigma^{2}}\int_{S}\Phi_{\sigma}(|x-y|)da(y)-1\right|$

First, we note that $(iii)=0$. Now, take $\delta=\sigma^{1-\tau}$, for some fixed $0<\tau<1$, where $\sigma>0$. Then, $(i)=\mathcal{O}(\sigma)$, $(iv)=\mathcal{O}(\sigma)$. Lastly $(ii)$

where we used Lemma 5 in the last inequality. Taking any $\tau<1/4$ proves the result. ∎

$\left|g_{x}(y)-g_{x}(y^{\prime})\right|$

where in the last inequality we used $\left|\left|x-y\right|-\left|x-y^{\prime}\right|\right|\leq\left|y-y^{\prime}\right|$ and Lemma 5. Since $f,\left|\cdot\right|$ are both uniformly continuous over $S$ (as continuous functions over a compact surface), $f$ is bounded, i.e., $|f|_{\infty}<\infty$, equicontinuity of $\left\{g_{x}\right\}$ is proved. ∎

The gaussian satisfies $\left|\Phi_{\sigma}(r^{\prime})-\Phi_{\sigma}(r)\right|\leq\frac{(r^{\prime}-r)}{\sigma e^{1/2}}$ for $0\leq r<r^{\prime}$.

where in the last inequality we used the fact that $te^{-\frac{t^{2}}{2\sigma^{2}}}\leq\sigma e^{-1/2}$. ∎

Lastly, to justify (6) let us use Theorem 2 and consider $f(x)\equiv 1$,