Title: NPTC-NET: NARROW-BAND PARALLEL TRANSPORT CONVOLUTIONAL NEURAL NETWORK ON POINT CLOUDS

Abstract: Convolution plays a crucial role in various applications in signal and image processing, analysis and recognition. It is also the main building block of convolution neural networks (CNNs). Designing appropriate convolution neural networks on manifold-structured point clouds can inherit and empower recent advances of CNNs to analyzing and processing point cloud data. However, one of the major challenges is to define a proper way to "sweep" filters through the point cloud as a natural generalization of the planar convolution and to reflect the point cloud's geometry at the same time. In this paper, we consider generalizing convolution by adapting parallel transport on the point cloud. Inspired by a triangulated surface based method Schonsheck et al. ( 2018), we propose the Narrow-Band Parallel Transport Convolution (NPTC) using a specifically defined connection on a voxelized narrow-band approximation of point cloud data. With that, we further propose a deep convolutional neural network based on NPTC (called NPTC-net) for point cloud classification and segmentation. Comprehensive experiments show that the proposed NPTC-net achieves similar or better results than current stateof-the-art methods on point clouds classification and segmentation.

1. INTRODUCTION:

Convolution is one of the most widely used operators in applied mathematics, computer science and engineering. It is also the most important building block of Convolutional Neural Netowrks (CNNs) which are the main driven force in the recent success of deep learning LeCun et al. (2015) ; Goodfellow et al. (2016) .

In the Euclidean space R n , the convolution of function f with a kernel (or filter) k is defined as

(f * k)(x) := R n k(x -y)f (y)dy.

(1)

This operation can be easily calculated in Euclidean spaces due to the shift-invariance of the space so that the translates of the filter k, i.e. k(x-y) is naturally defined. With the rapid development of data science, more and more non-Euclidean data emerged in various fields including network data from social science, 3D shapes from medical images and computer graphics, data from recommending systems, etc. Therefore, geometric deep learning, i.e. deep learning of non-Euclidean data, is now a rapidly growing branch of deep learning Bronstein et al. (2017) . In this paper, we will discuss how we can generalize the definition of convolution to (manifold-structured) point clouds in a way that it inherits desirable properties of the planar convolution, thus it enables to design convolutional neural networks on point clouds.

One of the main challenges of defining convolution on manifolds and point clouds (a discrete form of manifolds) is to define translation x -y on the non-Euclidean domain. Other than convolutions, we also need to properly define pooling to enable networks to extract global features and to save memory during training. Multiple types of generalization of convolutions on manifolds, graphs and point clouds have been proposed in recent years. We shall recall some of them and discuss the relation between existing definitions of convolutions and the proposed narrow-band parallel transport convolution.

1.1. RELATED WORK OF CONVOLUTIONS ON NON-EUCLIDEAN DOMAINS:

Spectral methods avoid the direct definition of translation x -y by utilizing the convolution theorem: for any two functions f and g, f * g = f • ĝ. Therefore, we have f * g = ( f • ĝ) ∨ , where ∧ and ∨ represent generalized Fourier transform and inverse Fourier transform provided through the associated Laplace-Beltrami (LB) eigensystem on manifolds. To avoid computing convolution through full eigenvalue decomposition, polynomial approximation is proposed and yields convolution as action of polynomials of the LB operator Hammond et al. (2011) ; Dong (2017) . Thus, convolutional neural networks can be designed Bruna et al. (2014) ; Defferrard et al. (2016) ; Levie et al. (2019) . Spectral methods, however, suffer two major drawbacks. First, these methods define convolution in the frequency domain. As a result, the learned filters are not spatially localized. Secondly, spectral convolutions are domain-dependent as deformation of the ground manifold will change the corresponding LB eigensystem. This obstructs the use of learning networks from one training domain to a new testing domain Schonsheck et al. (2018) .

Spatial mesh-based methods are more similar to the Euclidean case, and this is one of the reasons why most of the existing works fall into this category. The philosophy behind these methods is that the tangent plane T x M of a 2-dimensional manifold M in each point x ∈ M is embedded to a 2-dimensional Euclidean domain where convolution can be easily defined. In this paper, we make the first attempt to interpret some of the existing mesh-based methods in a unified framework. We claim that most of the spatial mesh-based methods can be formulated as

EQUATION

Here, k : R 2 → R is a convolution kernel and

EQUATION

where u j x ∈ T x M, j = 1, 2. For simplicity, we will denote u x = ( u 1 x , u 2 x ). Most of the designs of the existing manifold convolutions focused on the designs of u x . We remark that possible singularities will lead to no convolution operation at those points. These are isolated points on a closed manifold and for more discussion of singularities, please refer to the Appendix.

For example, GCNN Masci et al. (2015) and ACNN Boscaini et al. (2016) construct a local geodesic polar coordinate system on a manifold, formulating the convolution as

(f * k)(x) = k ((φ • ψ)(θ, r)) (Q x f )(r, θ)drdθ,

where Q is a local interpolation function with interpolation domain an isotropic disc for GCNN and an anisotropic ellipse for ACNN. A local geodesic polar coordinate system on a manifold can also be transformed to a 2-dimensional planar coordinate system on its tangent plane. Such transformation is the mapping ψ which is defined by the inverse exponential map: v = exp -1 (z(θ, r)) with z(θ, r) being a point in the local geodesic polar coordinate system at x ∈ M with coordinates (θ, r). With this, we can easily interpret ACNN within the framework of (2). Indeed, ACNN essentially chooses u x as the directions of the principal curvature at point x. For GCNN, on the other hand, it avoids choosing a specific vector field on the manifold by taking max-pooling among all possible directions of u 1

x at each point. Such definition of convolution, however, ignores the correspondence of the convolution kernels at different locations.

The newly proposed PTC Schonsheck et al. (2018) defines convolution directly on the manifold, while using tangent planes to transport kernels by a properly chosen parallel transport. PTC can be equivalently cast into the form of (2) using the inverse exponential map, and implementation of the proposed parallel transported is realized through choosing specific vector fields { u j

x } x∈M , j = 1, 2 guided by a Eikonal equation for transforming vectors along geodesic curves on manifolds. Spatial point-based methods have wider applications due to their weaker assumptions on the data structure, a point cloud P = {x i ∈ R 3 : i = 1, . . . , N } ⊂ R 3 consists of points in a 3-dimensional Euclidean space with the coordinates of the points as the only available information. Manifolds can be approximated by point clouds via sampling. Computing k-nearest neighborhoods of x or neighbors within a fixed radius can easily convert a point cloud to a local graph or mesh. This is why point cloud is simple, flexible and attracts much attentions lately.

There are mainly two types of point-based convolution. The first type is to combine the information of points directly. These methods can be formulated as

EQUATION

where N (x i ) ⊂ P is a neighborhood of x i and kernel k takes different forms in different methods.

PointNet Qi et al. (2017a) 

(x i , x j ) = I xj =arg max z∈N (x i ) f (z) . Pointcnn Li et al. (2018b) chooses k(x i , •) = β A xi where β ∈ R K and A xi ∈ R K×K are trainable variables with K = |N (x i )|.

The second type of convolution is defined by first projecting the point cloud locally on an Euclidean domain and then employ regular convolution. This type of methods can also be formulate as (2). In this paper, we propose Narrow-Band Parallel Transport Convolution (NPTC), which is a geometric convolution based on point cloud discretization of a manifold parallel transport defined in a specific way. As we observed in the previous section, convolutions in many methods can be written in the form of ( 2) and (3), while the differences mostly lie in the choices of the vector field { u x } x∈M . As observed by Schonsheck et al. (2018) that choosing the vector field properly, the associated convolution can be interpreted as parallel transporting the kernels using the parallel transport associated to the prescribed vector field. We propose to define convolution on point clouds by combining narrow-band approach Adalsteinsson & Sethian (1995) and geometric convolution. The formal definition of parallel transport and general ideal will presented in Section 2 and detailed descriptions on NPTC will be given in Section 3. Now, we describe how NPTC is computed on point clouds. Firstly, point clouds are approximated by voxel narrow-band with appropriate resolution. For a manifold M or point cloud P, its narrow-band is defined as the region with distance from M (or P) less than :

N B(M) := {x ∈ R 3 |dist(x, M) < },

where dist represents a distance function. For calculation efficiency and robustness to noise, we choose voxel narrow-band approximation. It should be noted that the result of the traditional voxelization method Wu et al. (2015) is a solid 3-d structure and the voxel narrow-band can be understood as the "shell" with a certain thickness of the former (if the point cloud is sampled from the surface of the object). It is very efficient to calculate the distance function in voxel approximation with appropriate resolution. The vector field { u x } x∈M is defined as the projections of the gradient field of a narrow-band-based distance function on the approximated tangent plane of the point cloud. Such definition of the vector field is robust to noise, since if the distortion of the coordinates of the points by noise does not exceed the width of the narrow-band, the computed gradient field of the distance function in the narrow-band remains unchanged. After the vector field { u x } x∈M , we use local PCA to estimate normal vectors on the point cloud following Xu et al. (2018) . Finally, the convolution kernel can be constructed on the tangent plane and the corresponding f (v) can be obtained by interpolating the value f (x) on the point cloud.

Note that we prefer to use geometric convolution in NPTC because compared with methods that translate kernels in the ambient space of the manifold, NPTC translates kernels on the tangent planes which effectively avoids having convolution kernels defined away from the underlying manifold of the point cloud. In other words, NPTC can well reflect point cloud geometry and is a natural generalization of planar convolution in the sense that when the point cloud reduces to planar grids, the NPTC reduces to the planar convolution.

1.3. CONTRIBUTIONS:

• We introduce a new point cloud convolution, NPTC, based on parallel transport defined by a narrow-band approximation of the point cloud. The proposed NPTC is a natural generalization of planar convolution.

• The proposed NPTC combines voxelization and geometric convolution. Voxelization with appropriate resolution brings robustness and geometric convolution can better reflect point cloud's geometry.

• Based on NPTC, we designed convolutional neural networks, called NPTC-net, for point clouds classification and segmentation with state-of-the-art performance.

2. BACKGROUND AND GENERAL IDEA:

We recommend the book Nakahara (2003) for readers who are unfamiliar with differential geometry. A short intuitive introduction to parallel transport will be provided after recalling the notion.

Let M be a 2 dimensional differential manifold embeded in R 3 and T x M be the tangent plane at point x ∈ M. T x M can be defined as the 2-dimensional linear space formed by the span of 2 tangent vectors. The disjoint union of the tangent planes at each point on the manifold defines the tangent bundle T M. A vector field X is a section of T M. Collection of all smooth vector fields X(x) ∈ T x M, ∀x ∈ M is denoted as Γ(T M). An affine connection is a bilinear mapping ∇:

Γ(T M) × Γ(T M) → Γ(T M).

A section of a vector field is called parallel along a curve γ if ∇ γ X = 0. Suppose we are given an vector e ∈ T x0 at x 0 = γ(0) ∈ M. The parallel transport of e along γ is the extension of e to a parallel section X on γ.

Intuitively, in differential geometry parallel transport is a way of translating a vector along a smooth curve "parallel" to the original. In fact, by given smooth vector fields { u 1 , u 2 }, we can define linear transformation among tangent planes then the corresponding parallel transport can be induced Knebelman (1951) Therefore, parallel transport defined in this way can be viewed as parallel transporting the vector on the manifold with respect to the connection that is reconstructed from the vector field { u 1 x } x∈M . That is to say, if given a vector field, we can define a way to "transport" vectors between tangent planes.

To select a suitable vector field, we first recall the choice of the vector fields of PTC which defines convolution on triangulated surfaces via parallel transport with respect to the Levi-Civita connection Schonsheck et al. (2018) . Geodesic curve represents, in some sense, the "straightest" path between two points on a Riemannian manifold. Given a geodesic connecting two points x and y, the tangential direction at x corresponds to the ascent direction of geodesic distance from y. That is to say, all tangential directions of one geodesic form a parallel vector field. PTC chooses such direction as u 1

x and defines u 2 x = u 1 x × n x with n x the normal vector at x. One naive approach to extend mesh based methods to point cloud is to generate a triangulated surface based on the point cloud. However, this is not as convenient as working directly with the point cloud since in practice not every point cloud corresponds to a legitimate parameterized surface and pooling is not as easy to implement on triangulated surfaces as on point clouds. In addition, it is time-consuming to construct meshes on point clouds. When applied in practice, mesh construction time may be much longer than inference time of some methods directly applied on the point cloud.

If we want to construct a vector field on point cloud, gradients of some sort of distance function can be a good choice. However, unlike triangulated surfaces, distance function is not easily defined on point clouds due to the lack of connectivity. It is then natural to approximate the point cloud with another data structure with connectivity, so that distance function can be easily calculated. We use voxel to approximate the point cloud in a narrow-band in R 3 covering the point cloud. We denote such distance function as ρ : R 3 → R + .

Then, we review how a distance function is calculated. Distance functions can be easily computed by solving the Eikonal equation. The Eikonal equation is a non-linear partial differential equation describing wave propagation:

EQUATION

where Λ ⊂ Ω ⊂ R n and h(x) is a strictly positive function. The solution ρ(x) of ( 5) can be viewed as the shortest time needed to travel from x to Λ with h(x) being the speed of the wave at x. For the special case when h = 1, the solution ρ(x) represents the distance from x to Λ limited in the Ω.

The Eikonal equation can be solved by the fast marching method Sethian (1996) .

Note that if the point cloud is sampled from a plane, the narrow-band is flat as well. Then, by a proper choice of the distance function, the vector fields { u j x } x∈M , j = 1, 2, can be reduced to the global coordinate { e j }, j = 1, 2 on the plane. This means that NPTC is reduced to the traditional planar convolution.

Once the distance function ρ is computed, we choose u 1

x = ∇ P ρ(x), where ∇ P ρ(x) is a projection of ∇ρ(x) on an approximated tangent plane at x. Then, u 2

x can be calculated by the outer product u 2

x = u 1 x × n x with n x the normal vector at x. For convenience, instead of transporting the kernel on the manifold, we can locally construct the parallel transported kernel at every point x by formulating k as k(φ(x, •)), where φ(x, v) is defined in (3). It is known in differential geometry that transporting the kernel to every point on the manifold is the same as locally reconstructing the kernel in the aforementioned way. x } ({∇ P ρ(x)}) on the point cloud. We can see that distance propagates from the bottom center to the top center reflecting the geometry of the sphere.

3.1.1. VOXELIZATION AND COMPUTING DISTANCE FUNCTION:

Assuming that the point cloud has been normalized so that it is enclosed by the unit cube. The unit cube is then discretized by N × N × N grids. The narrow-band approximation of the point cloud is constructed by including each voxel with a distance less than k N from any point on the point cloud. Then the voxel narrow-band approximation of point cloud has been constructed. N depends on the requirements of speed and accuracy. k need to be large enough to make the narrow-band continuous (if the point cloud represents a continuous manifold) and small enough to make the distance in narrow-band approximate the geodesic distance. In the next experiments, we choose N as 100, k as 2 and L ∞ as distance function. If the sampling of point cloud is very sparse, it may be necessary to construct a narrow-band by the estimation of the normal or some other strategies.

Then we can compute distance functions on the voxels using the well-known fast marching method based on regular grid provided by the voxelization Sethian (1996) . The solution ρ(x) of the Eikonal equation |∇ρ(x)| = 1 presents the distance form Λ to x limited inside the narrow-band. Here Λ is chosen as certain point on the point cloud.

3.1.2. COMPUTING THE VECTOR FIELDS ON POINT CLOUDS:

We first compute the tangent plane on each point. Tangent planes are important features of manifolds and have been well-studied in the literature Lai et al. (2013) . In this paper, we use local principal component analysis (LPCA) to estimate the tangent plane. We estimate the local linear structure near x ∈ P using the covariance matrix

x k ∈N (x) (x k -c) (x k -c), c = 1 k x k ∈N (x)

x k ,

where N (x) is the set of neighboring points of x. The eigenvectors of the covariance matrix form an orthogonal basis. If the point cloud is sampled from a two dimensional manifold, and the local sampling is dense enough to resolve local features, the eigenvectors corresponding to the largest two eigenvalues provide the two orthogonal directions of the tangent plane, and the remaining vector represents the normal direction at x ∈ P. Here, we denote the space spanned by the two eigenvectors of the covariance matrix at x as

T x P ⊂ R 3 .

With the computed distance function ρ(x), it is natural to define the vector field by projecting ∇ρ on the approximated tangent planes of the point cloud. Given a point x k ∈ P close enough to x ∈ P, we have ∇ρ,

x k -x ≈ ρ(x k ) -ρ(x),

where ρ(x k ) and ρ(x) are known. If we consider k-nearest neighbors of x, we have k -1 equations with 3 unknowns that are the three components of ∇ρ. We can use least squares to find ∇ρ. We then project the vector ∇ρ(x) onto the tangent plane at x. We denote the projected vector ∇ P ρ, which is the vector we eventually need to define NPTC.

After defining the vector field on the tangent plane, we choose the convolution kernel of hexagon (Figure 1 ), that is, a convolution kernel is composed of a central point and six evenly distributed points around. The value f (v) is computed by f (v) = f (z) where z ∈ P is the closest point to v in R 3 . Note that one may use a more sophisticated method to compute f (v) rather than using the closest point interpolation. We choose the closest point interpolation because of its simplicity.

3.2. NPTC-NET: ARCHITECTURE DESIGN FOR CLASSIFICATION AND SEGMENTATION:

This section, we present how to use NPTC to design convolutional neural networks on point clouds for classification and segmentation tasks. For that, other than the NPTC, we need to define some other operations that are frequently used in neural networks. Note that, some point-wise operations like MLP and ReLu are the same on point cloud as the Euclidean case. Here, we only focus on the operations that are not readily defined on point clouds.

Down-sampling::

In our implementation, the sub-sampled set of points of the next layer is generated by the farthest point sampling Eldar et al. (1997) .

Convolution layer: Our k-th convolution layer takes points P k ∈ R N k ×3 and their corresponding feature maps F k ∈ R N k ×c k as input, where N k is the number of the points and c k is the number of channels at layer k. The corresponding output is F k+1 ∈ R N k+1 ×c k+1 living on the points P k+1 ∈ R N k+1 ×3 . The NPTC-net have encoding and decoding stages. Normally, N k+1 < N k during encoding and N k < N k+1 during decoding. Convolution at the k-th layer is only performed on the point set P k+1 , which resembles convolution with stride > 1 for planar convolutions.

Residual block: One residual block takes the feature maps F ∈ R N ×c on the point set P ∈ R N ×3 as input and same number of points and same number of channels of features as output. One residual layer consists of three components: MLP from c channels to c 2 channels, convolution layer from c 2 channels to c 2 channels, MLP from c 2 channels to c channels plus the feature maps from the bypass connection. A residual block consists of several residual layers.

NPTC-net consists of the aforementioned operations and its architecture is given by Figure 3 . The left half of the NPTC-net is the encoder part of the network for feature extraction. For classification, features at the bottom of the network are directly attached to a classification network; while for segmentation, features are decoded using the right half of the NPTC-net (decoder part of the network) to output the segmentation map. 

4. EXPERIMENTS:

In order to evaluate our new NPTC-nets, we conduct experiments on three widely used 3D datasets, ModelNet Wu et al. (2015 ), ShapeNet Yi et al. (2016) , S3DIS Armeni et al. (2016) . We implement the model on a GTX TITAN Xp GPU. For more implementation details, please refer to the Appendix.

4.1. 3D SHAPE CLASSIFICATION AND SEGMENTATION:

We test the NPTC-net on ModelNet40 for classification tasks. ModelNet40 contains 12,311 CAD models from 40 categories with 9,842 samples for training and 2,468 samples for testing. For comparison, we use the data provided by Qi et al. (2017a) sampling 2,048 points uniformly and computing the normal vectors from the mesh. As shown on Tabel 1, our networks outperform other state-of-art methods. (If a compared method has results on both 2048 (or 1024) and 5000 points, we only compare with the former.).

We also evaluate the NPTC-net on ShapeNet Part for segmentation tasks. ShapeNet Part contains 16,680 models from 16 shape categories with 14,006 for training and 2,874 for testing, each annotated with 2 to 6 parts and there are 50 different parts in total. We follow the experiment setup of previous works, putting object category into networks as known information. We use point intersection-over-union (IoU) to evaluate our NPTC-net. Table 1 shows that our model ranks second on this dataset and is fairly close to the best known result. As pointed out earlier, using voxelization can bring rubustness to the definition of geometric convolution. In order to show the robustness of our model for real data, we tested scene semantic segmentation on the "Stanford Large-Scale 3D Indoor Spaces Dataset" (S3DIS). S3DIS covers six large-scale indoor areas from 3 different buildings for a total of 273 million points annotated with 13 classes. This is a real-word scanned dataset without normal and with noise. Following Tchapmi et al. (2017) , we advocate the use of Area-5 as test scene to better measure the generalization ability of our method. Following Li et al. (2018b) , the data of S3DIS is firstly split by room, and then the rooms are sliced into 1.5m by 1.5m blocks, with 0.3m padding on each side. The points in the padding areas serve as context of the internal points, and themselves are not linked to loss in the training phase, nor used for prediction in the testing phase. Each block will be viewed as a point cloud during training and testing.

We do inferences on the augmented data during testing by voting following Qi et al. (2017b) . To clarify this, let x i be one data from the test set and x i j be the augmented data generated from x i . p i j = f (x i j ) denotes the predict possibility vector after Softmax. The final inference result of x i is Predict( Total pre-processing time mainly depends on the grid's density. For most cases, the resolution of 100 3 is enough to describe the shape of the point cloud, which is what we chose for our experiments.

x i ) = arg max k ( j p i j ) k . A.2 RUNNING STATISTICS

We also remark that the whole computation cost of constructing convolution is linearly depending on the resolution of voxel and the size of data. On a PC with Core i7-7700 CPU, the pre-processing takes about 0.5 seconds per point cloud with Matlab, and the whole dataset of ModelNet40 (12,311 shapes with 10,000 points each) takes only about 1.5 hours. It is negligible compared to the training of the deep neural networks and acceptable to do inference in practice. x . { v i } represent the vector field with the origin y i and d(y i , x) represent the geodesic distance. The absolute value of combination coefficient for one vector field will descend to 0 as x approaches the origin to prevent the singularity at the origin.

We note that on non-parallelizable manifolds such as the sphere, it is not possible to construct a smooth vector field. Helgason (1979) So that the vector field must have at least one a singularity, and the frame around the singularity will rotate violently. Figure 5 shows vector fields defined on the surface with and without singularity.

If singularity can not be avoided. It is natural to ask how much singularities affect the result. This has been discussed in section 4.4 of PTC. Schonsheck et al. (2018) In surface MNIST experiment, convolutions defined by taking the middle point of a surface as the origin of the distance function (which means that there is a singularity in the middle like Figure 5 (b)) will reach the accuracy of 94.92% and convolutions using the smooth strategy will reach 96.36%. Singularity does cause some problems, but we think it's in the acceptable range. In our experience, activation in segmentation task have been visualized as before, we find no direct relationship with the location of the singularity.

If we have some prior knowledge about a shape that can have no singularity. Strategies can be applied to get a smooth vector field or reduce the influence of singularity. For example, if the shape is essentially like a wrinkled sheet, then we can choose the starting point(s) Λ of the Eikonal equation as points on one edge of the sheet or the linear combination of two vector fields with different origins Fig 5 (c ).

Most of the shapes in the three experiment datasets are closed manifolds like boxes, beds, airplanes, on which singularity can not be avoided. Experiments show that applying more strategies we know can not improve the results obviously, so we choose to select one initial point directly.

:

This paper proposed a new way of defining convolution on point clouds, called the narrow-band parallel transport convolution (NPTC), based on a point cloud discretization of a manifold parallel transport. The parallel transport was defined specifically by a vector field generated by the gradient field of a distance function on a narrow-band approximation of the point cloud. The NPTC was used to design a convolutional neural network (NPTC-net) for point cloud classification and segmentation. Comparisons with state-of-the-art methods indicated that the proposed NPTC-net is competitive with the best existing methods.

Figures and Tables:

Figure 1: Narrow-band parallel transport convolution on point cloud: black and blue points are sample points of the surface (blue). Each kernel (colored dots) is defined on the tangent plane (yellow). The vectors on the tangent planes that are of the same color are in a parallel fashion.

Figure 2: Illustration of a point cloud P sampled from the unit sphere. (a) shows the narrow-band approximation (blue boxes) of part of P (in red). (b) is a cross section of (a). (c), (d) show the distance function ρ and vector field { u 1x } ({∇ P ρ(x)}) on the point cloud. We can see that distance propagates from the bottom center to the top center reflecting the geometry of the sphere.

Figure 3: Architecture of NPTC-net. The network for segmentation tasks is at the top right with encoding and the network for classification tasks is at the bottom right with encoding. Top 2 max pooling means taking the maximum two values all the points in each channel and then concatenate into one vector representing global feature. "Tile" means repeating the global feature and concatenating to each point as extra channels.

Figure 4: Feature Visualization: each feature from low or high level is displayed on 2 point clouds from different categories. High-level activations are in yellow and low-level activations are in blue.

Figure 5: Different strategies induce different vector fields: (a) is the vector field which selects the corner as the origin of the distance function. (b) is the vector field which selects the middle as the origin. (c) is the linear combination of two vector fields with different origins. The combination coefficients depend on the distance to the origin at each point: v x = d(y 1 , x) v 1x -d(y 2 , x) v 2 x . { v i } represent the vector field with the origin y i and d(y i , x) represent the geodesic distance. The absolute value of combination coefficient for one vector field will descend to 0 as x approaches the origin to prevent the singularity at the origin.

Comparisons of overall accuracy (OA) and mean per-class accuracy (mA) on ModelNet40 as well as comparisons in instance average IoU (mIoU) and class average IoU (mcIoU) on ShapeNet Part. Models ranking first is colored in red and second in blue.

Table content: <table><tr><td/><td colspan="2">Modelnet40</td><td colspan="2">ShapeNet part</td></tr><tr><td>Method</td><td colspan="4">OA(%) mA(%) mIoU mcIoU</td></tr><tr><td>kd-net Klokov &amp; Lempitsky (2017)</td><td>91.8</td><td>88.5</td><td>82.3</td><td>77.4</td></tr><tr><td>pointnet Qi et al. (2017a)</td><td>89.2</td><td>86.2</td><td>83.7</td><td>80.4</td></tr><tr><td>SO-Net Li et al. (2018a)</td><td/><td>87.3</td><td>84.9</td><td>81.0</td></tr><tr><td>pointnet++ Qi et al. (2017b)</td><td>90.7</td><td>-</td><td>85.1</td><td>81.9</td></tr><tr><td>SpecGCN Wang et al. (2018a)</td><td>92.1</td><td>-</td><td>85.4</td><td>-</td></tr><tr><td>SpiderCNN Xu et al. (2018)</td><td>92.4</td><td>-</td><td>85.3</td><td>81.7</td></tr><tr><td>pointcnn Li et al. (2018b)</td><td>92.2</td><td>88.1</td><td>86.1</td><td>84.6</td></tr><tr><td>DGCNN Wang et al. (2018c)</td><td>92.2</td><td>90.2</td><td>85.1</td><td>82.3</td></tr><tr><td>Ours</td><td>92.7</td><td>90.2</td><td>85.8</td><td>83.3</td></tr><tr><td>4.2 RUBOSTNESS TEST</td><td/><td/><td/><td/></tr></table>

Table 2 shows that geometric convolution methods are close to the methods which do not need normal estimation. NPTC-net outperforms the best known geometric convolution method TangentConvXu et al. (2018). Vladimir G. Kim, Duygu Ceylan, I-Chao Shen, Mengyan Yan, Hao Su, Cewu Lu, Qixing Huang, Alla Sheffer, and Leonidas Guibas. A scalable active framework for region annotation in 3d shape collections. ACM Trans. Graph., 35(6):210:1-210:12, November 2016. ISSN 0730-0301. doi: 10.1145/2980179.2980238. URL http://doi.acm.org/10.1145/ 2980179.2980238. We implement the model with Tensorflow using SGD optimizer with an initial learning rate 0.1 for ModelNet40 and ADAM optimizer with an initial learning rate 0.002 for ShapeNet Part and S3DIS on a GTX TITAN Xp GPU. During the training procedure of classification, the data is augmented by random rotation, scaling and Gaussian perturbation on the coordinates of the points. During the training procedure of segmentation, the data is augmented by scaling and Gaussian perturbation on the coordinates of the points.

Table content: <table><tr><td colspan="4">Li Yi, Chris Zhang, Wenjie Luo, and Raquel Urtasun. Efficient convolutions for real-time semantic seg-</td></tr><tr><td colspan="4">mentation of 3d point clouds. In 2018 International Conference on 3D Vision (3DV), pp. 399-408.</td></tr><tr><td>IEEE, 2018.</td><td/><td/><td/></tr><tr><td>A APPENDIX</td><td/><td/><td/></tr><tr><td>A.1 IMPLEMENTATION DETAILS</td><td/><td/><td/></tr><tr><td colspan="4">Table 2: Comparisons of overall accuracy (OA) and mean per-class IoU (mIoU) on S3DIS. Models</td></tr><tr><td colspan="2">ranking first is colored in red and second in blue.</td><td/><td/></tr><tr><td>Convolution Type</td><td>Method</td><td colspan="2">OA(%) mIoU(%)</td></tr><tr><td>no convolution</td><td>pointnet Qi et al. (2017a)</td><td>78.8</td><td>41.3</td></tr><tr><td/><td>SegCloud Tchapmi et al. (2017)</td><td>-</td><td>48.9</td></tr><tr><td>3-d convolution</td><td>Eff3DConvZhang et al. (2018)</td><td>69.3</td><td>51.8</td></tr><tr><td/><td>ParamConvWang et al. (2018b)</td><td>-</td><td>58.3</td></tr><tr><td>geometric convolution</td><td>TangentConv Xu et al. (2018) Ours</td><td>82.5 83.7</td><td>52.8 54.0</td></tr><tr><td>5 CONCLUSION</td><td/><td/><td/></tr></table>

Comparisons of number of parameters and FLOPs for classification.

Table content: <table><tr><td/><td>method</td><td colspan="2">Parameters FLOPs(Inference)</td></tr><tr><td colspan="2">pointnet Qi et al. (2017a)</td><td>3.48M</td><td>14.70B</td></tr><tr><td colspan="2">pointnet++ Qi et al. (2017b)</td><td>1.48M</td><td>26.94B</td></tr><tr><td colspan="2">DGCNN Wang et al. (2018c)</td><td>1.84M</td><td>44.27B</td></tr><tr><td colspan="2">pointcnn Li et al. (2018b)</td><td>0.6M</td><td>25.30B</td></tr><tr><td/><td>Ours</td><td>1.29M</td><td>11.7B</td></tr><tr><td colspan="4">Table 4: Comparisons of training time of networks on ModelNet40</td></tr><tr><td>Method</td><td>Settings</td><td colspan="2">Accuracy and Training (+Pre-processing) time</td></tr><tr><td>PointNet++ Qi</td><td>adam, 1024 points</td><td/><td>90.7%, 6 hours</td></tr><tr><td>et al. (2017b)</td><td>adam, 5000 points</td><td/><td>91.9%, 20 hours</td></tr><tr><td>ours</td><td>adam, 2048 points SGD, 2048 points</td><td/><td>92.4%, 6h (+1.5h) 92.7%, 12h (+1.5h)</td></tr></table>

Peer review (iclr2020):
The paper introduces a new geometric convolution that can be applied to point clouds approximating a 2D manifold in R^3. Similar to previous work, the continuous mathematical description of the method involves a kernel that is a function on R^2, which is pushed to the tangent spaces of the manifold via a choice of frame u. A local neighbourhood around the kernel is parameterized by the tangent space via the exponential map and matched against the kernel. The frame u, which determines the orientation of the kernel, is chosen by first picking an origin and then setting u1 to the direction of steepest ascent of the function that measures geodesic distance to the origin. The other basis vector u2 is computed as u1 x n where n is the normal vector. In a practical implementation, the point cloud is voxelized in order to compute the distance function and it*s gradient. The gradient is then interpolated back to the point cloud. If I understood correctly, a convolution is then directly applied to the point cloud, though I could not find a description of how this is done. The problem of defining geometric convolutions on point clouds is interesting and relevant, and something like what is presented in this paper might work well. Indeed the experiments demonstrate that the method produces decent scores on modelnet and S3DIS. The method is not very fast, due to the voxelization preprocessing which is required, which at .5s precludes real-time applications. Also, as discussed below, there are some issues related to singularities in the vector fields u1,u2 that are not adequately discussed. My main concern, and the reason I have given a *weak reject* rating, is that the clarity and completeness of the paper is insufficient and I find the paper hard to follow (see below). I would actually like to see an improved version published, and if the authors can address the concerns I would increase my score. # Writing I find that the paper is hard to read because of the way it is structured, as well as numerous small mathematical and expository issues (discussed below) and missing information. The present paper builds on the PTC method of Schonsheck et al., but this method is not properly explained in the paper. PTC is mentioned in 1.1, but only described at a very high level. Since I had not read this paper before (I have now) the present paper was hard to follow on a first reading. Section 1.2 is a large sub-section of the related work section that actually discusses the proposed NPTC. I think it*s better not to spend so much of the related work section on this. Moreover, section 3.1.1. *General idea of NPTC*, contains another high level description, which is somewhat redundant (though at the same time, both sections leave lots of questions unanswered - see below). The following sections, 3.1.2 and 3.1.3 explain the computation of the distance function and the vector fields, but contain no clear explanation of the whole algorithm. Many important questions about how the method is actually implemented are left unanswered, even though the main contribution of this paper is at the implementation level rather than the theoretical level. - How is voxelization done? Count the number of points per voxel? How is the voxel size chosen? How do you make sure that you obtain a *narrow band* around the surface defined by the point cloud? What kind of datastructure do you use to store a sparse voxel grid? - How is the filter parameterized? In the theory, k is a function on R^2. How do we evaluate it at an arbitrary point in R^2? - How is convolution done? I think it is done on points not voxels, similar to eq. 4, but this is never stated in the paper. How do you approximate the integral over the tangent space in Eq 2, if eq 2 is what the conv is based on? I would remove section 2.1 where the notion of a connection is formally introduced. The reader will either know this concept, in which case it is unnecessary, or not, in which case the description is far too compact (one must read a textbook to really understand this notion). It may be better to include only a short intuitive introduction to parallel transport, refering the reader to other texts for mathematical definitions of basic notions like connections. The fact that the voxelization of the point cloud is sparse is only mentioned very late in the paper. For a while I was thinking the idea would be to construct a dense voxel grid, which would be extremely memory intensive. Also, the phrase *narrow-band* is often used with a very different meaning, as in a small part of the spectrum. It was not clear to me what this was referring to until halfway through the paper. Better to explain the general idea of the algorithm in the introduction. # Singularities I looked at the papers citing the main related work (the PTC paper by Schonscheck et al., 2018), and of the four listed in google scholar, one seems relevant in that it prominently cites Schonscheck et al. and claims to improve upon it, but this work is not cited in the present paper: Cohen, Weiler, Kicanaoglu, Welling, Gauge Equivalent Convolutional Networks and the Icosahedral CNN. This work highlights one potential downside of the PTC approach, which is that it is not possible to find a global frame u (called in w in their paper) without singularities on manifolds like the sphere. Moreover, the choice of frame is fundamentally arbitrary and should not affect the results. In the PTC approach, a certain choice of frame with singularities is made, which leads to filter orientations that are 1) essentially arbitrary, and 2) change smoothly in most places but abruptly near the singularities. The results are heavily dependent on the choice of frame. The present paper dismisses these issues by saying that *We remark that possible singularities will lead to no convolution operation at those points. These are isolated points on a closed manifold and do not effect experiment results.* However, this is not actually demonstrated in the paper, and one might reasonably believe that this problem affects more than a small finite set of points. Near a singularity (e.g. the poles of the sphere in fig 2d), nearby filters will be oriented very differently. If we draw a small circle around the singularity, the orientation of the filter changes 360 degrees as we travel around the circle. As a result, the meaning of the patterns in the output feature map is very different near the poles than it is near the equator. Nevertheless, the next layer will try to match these patterns with the same set of filters / perform weight sharing across different positions. In my opinion this issue should be more frankly discussed. Fortunately, in some applications with point clouds this issue can be avoided. For point clouds coming directly from a (RGB+)depth sensor, the manifold is essentially like a wrinkeled sheet (homeomorphic to a disk), and one can easily find vector fields / frames without singularities on such manifolds. (this is not necessarily true for point clouds that represent a whole scene, e.g. in SLAM). I think this is what is mentioned in paragraph 3 of 3.1.1. However, it is not clear to me if the frame used in this paper is without singularities even when it is possible to find such a frame. The reason is that the frame is defined in terms of the distance function rho to an arbitrary origin. If I understand correctly, one will always have a singularity at the origin. This could in principle easily be solved though by simply using the x and y direction of the camera plane as a frame (projecting it from R^3 to each tangent space). However, if the authors decide to go that route, one would also like to see a comparison to simply applying 2d convolutions to the RGB+D images. # Experiments The experiments on Modelnet40 show that, when compared with other point-cloud methods, the proposed method outperforms. I do not know if there are better point-based methods than those listed in the paper, but on the official Modelnet40 leaderboard (which is incomplete) there are several methods that score better (97%+). Since this difference could possibly be attributed to a loss of information due to the discretization into a point cloud, I still think these results are quite good. Similarly on S3DIS the method scores quite well, though does not reach state of the art. I could not find the architecture for the classification network, and only a high-level description of the segmentation architecture. More details on the training and evaluation procedures could be added for both experiments. # Misc Some more things I noticed below. Many of these are not serious problems, just things that can be improved / fixed. - p2: -- *Spatial mesh-based methods are more intuitive* - this is subjective -- f(v) where v is a tangent vector in T_xe M is not defined. One would expect f to be a function on the manifold. Typically one writes f(exp_x v) instead. -- script M is not defined (though it is intuitive that this is the manifold). Later in 2.1 it is written *Let M be a 2 dimensional differential manifold*. Later still (3.1) the notation is switched to P without notice. -- TxM is not defined. Later it is explained this is the tangent plane. Neither is g_x (it is obvious this should be the metric, but only if one knows differential geometry). -- *and do not effect experimental results* -> affect -- *singularities from a given vector field can be overcome ....* I don*t understand what this is saying. How can we avoid the issues with singularities? -- consider writing log instead of exp^{-1} -- *while uses tangent planes* -> using - p3: -- You have f(z) in the subscript of the indicator I_argmax ... -- In the explanation of pointnet it is not clear where there are any parameters in the kernel k if k(xi, xj) = delta(xi, xj) -- I don*t understand the explanation of edge convolution. If f(x_j) = 1 (for all j(?)) then k(xi, xj) = MLP(f(xi), f(xi) - f(xj)) would equal MLP(1, 0) which makes no sense. -- Description of figure 1: *are in parallel*: need to say along what curve they are parallel. If I understand correctly, they are only in parallel if they are attached to different points on a minimizing geodesic emanating from the origin. - p4: -- *embed in R^3* -> embedded -- In 2.1 it is explained that T_x M is the tangent plane, but you*ve already discussed T_x M several times before. -- A vector field is not just any assignment M -> TM. It is a section of TM, ie a map M -> TM that, when composed with the projection TM -> M, yields the identity on M. -- The interval *I* mentioned below eq 5 has not been defined. *I* was used as indicator function before. -- *X is the unique section of Gamma(TM)*. The concept of *section* has not been introduced. Moreover, one could say *section in Gamma(TM)* or *section of TM* but not *section of Gamma(TM)* since Gamma(TM) *is* the set of sections of TM. Probably best to say *unique vector field*. -- *there will be a geodesic connecting x0 and x1* - only true if M is connected. - p5: -- *how a distance functions are* -> function -- *easliy* -- below eq 6 *f(x) is a strictly positive function*, but f(x) does not appear in eq 6 -- in 3.1., script P has not been defined. I first thought it is just a new letter for M, but I think it is the point cloud? Needs to be made explicit. -- *Geodesic curve represents, in some snse, the shortest path*. This is false. A geodesic is a *straightest* curve, but a geodesic need not be distance minimizing in any sense. -- *ascend direction* -> ascent -- In the first paragraph of 3.1.1 it is not mentioned explicitly that y plays the role of an *origin*. This makes the last sentence confusing. -- *The value f(v) is computed by f(v) = f(z) where z in P is the closest point to v*. Firstly, this sentence is in the middle of a paragraph about the vector fields u1,u2, but seems unrelated. Secondly, what are v and z? I guess v is a point in M and z in P? Or is v a tangent vector? In that case, do you mean closest in the embedding space R^3? - p6: -- *consider point clouds in R^3*. This assumption was already made before, right? -- *it is not straightforwardly compute distance function* -> *straightforward to compute the distance function* -- *Here Lambda is chosen as certain point on the point cloud* -> *a certain point*. Also, Lambda was used before as a subset of Omega-bar (below eq 6), but here it is a point. I guess this point is the origin. In other places (earlier) you also refer to the origin, e.g. by y. Needs to be made consistent. -- *Show that the directly* - remove *the* -- *Finally, we interpolate the distance function from the voxels to point cloud* -> *the point cloud*. On first reading, this (page 6!) was the point where I realized (guessed) that you are going to define the convolution on the point cloud not voxel grid. This needs to be explained much earlier. -- *it is nature to* -> natural - p7 -- *in our implement* -> implementation -- *Appendix.* -> *Appendix A* or *the Appendix.* - p8 -- *Scene semantics segmentation* -> semantic