GRNet: Gridding Residual Network for Dense Point Cloud Completion

Estimating the complete 3D point cloud from an incomplete one is a key problem in many vision and robotics applications. Mainstream methods (e.g., PCN and TopNet) use Multi-layer Perceptrons (MLPs) to directly process point clouds, which may cause the loss of details because the structural and context of point clouds are not fully considered. To solve this problem, we introduce 3D grids as intermediate representations to regularize unordered point clouds. We therefore propose a novel Gridding Residual Network (GRNet) for point cloud completion. In particular, we devise two novel differentiable layers, named Gridding and Gridding Reverse, to convert between point clouds and 3D grids without losing structural information. We also present the differentiable Cubic Feature Sampling layer to extract features of neighboring points, which preserves context information. In addition, we design a new loss function, namely Gridding Loss, to calculate the L1 distance between the 3D grids of the predicted and ground truth point clouds, which is helpful to recover details. Experimental results indicate that the proposed GRNet performs favorably against state-of-the-art methods on the ShapeNet, Completion3D, and KITTI benchmarks.


Introduction
With the rapid development of 3D acquisition technologies, 3D sensors (e.g., Li-DARs) are becoming increasingly available and affordable. As a commonly used format, point clouds are the preferred representation for describing the 3D shape of an object. Complete 3D shapes are required in many applications, including semantic segmentation and SLAM [1]. However, due to limited sensor resolution and occlusion, highly sparse and incomplete point clouds can be acquired, which causes loss in geometric and semantic information. Consequently, recovering the complete point clouds from partial observations, named point cloud completion, is very important for practical applications. In the recent few years, convolutional neural networks (CNNs) have been applied to 2D images and 3D voxels. Since the convolution can not be directly applied to point clouds due to their irregularity and unorderedness, most of the existing methods [2,3,4,5,6,7,8] voxelize the point cloud into binary voxels, where 3D convolutional neural networks can be applied. However, the voxelization operation leads to an irreversible loss of geometric information. Other approaches [9,10,11] use the Multi-Layer Perceptrons (MLPs) to process point clouds directly. However, these approaches use max pooling to aggregate information across points in a global or hierarchical manner, which do not fully consider the connectivity across points and the context of neighboring points. More recently, several attempts [12,13] have been made to incorporate graph convolutional networks (GCN) [14] to build local graphs in the neighborhood of each point in the point cloud. However, constructing the graph relies on the K-nearest neighbor (KNN) algorithm, which is sensitive to the point cloud density [15].
Several attempts in point cloud segmentation have been made to capture spatial relationships in point clouds through more general convolution operations. SPLATNet [16] and InterpConv [17] perform convolution on high-dimensional lattices and 3D cubes interpolated from neighboring points, respectively. However, both of them are based on a strong assumption that the 3D coordinates of the output points are the same as the input points and thus can not be used for 3D point completion.
To address the issues mentioned above, we introduce 3D grids as intermediate representations to regularize unordered point clouds, which explicitly preserves the structural and context of point clouds. Consequently, we propose a novel Gridding Residual Network (GRNet) for point cloud completion, as shown in Figure 1. Besides 3D CNN and MLP, we devise three differentiable layers: Gridding, Gridding Reverse, and Cubic Feature Sampling. In Gridding, for each point of the point cloud, eight vertices of the 3D grid cell that the point lies in are first weighted using an interpolation function that explicitly measures the geometric relations of the point cloud. Then, a 3D convolutional neural network (3D CNN) with skip connections is adopted to learn context-aware and spatially-aware features, which allows the network to complete missing parts of the incomplete point cloud. Next, Gridding Reverse converts the output 3D grid to a coarse point cloud by replacing each 3D grid cell with a new point whose coordinate is the weighted sum of the eight vertices of the 3D grid cell. The following Cubic Feature Sampling extracts features for each point in the coarse point cloud by concatenating the features of the corresponding eight vertices of the 3D grid cell that the point lies in. The coarse point cloud and the features are forwarded to an MLP to obtain the final completed point cloud.
Existing methods adopt Chamfer Distance in PSGN [18] as the loss function to train the neural networks. This loss function penalizes the prediction deviating from the ground-truth. However, there is no guarantee that the predicted point clouds follow the geometric layout of objects, and the networks tend to output a mean shape that minimizes the distance [19,20]. Some recent works [19,20,21,22,23] attempt to solve the unorderness while preserving fine-grained details by projecting the 3D point cloud to an image, which is then supervised by the corresponding ground truth masks. However, the projection requires extrinsic camera parameters, which are challenging to estimate in most scenarios [24]. To solve the unorderedness of point clouds, we propose Gridding Loss, which calculates the L1 distance between the generated points and ground truth by representing them in regular 3D grids with the proposed Gridding layer.
The contributions can be summarized as follows: -

Related Work
According to the network architecture used in point cloud completion and reconstruction, existing networks can be roughly categorized into MLP-based, graphbased, and convolution-based networks.
MLP-based Networks. Pioneered by PointNet [25], several works use MLP for point cloud processing [26,27] and reconstruction [9,10] because of its simplicity and strong representation ability. These methods model each point independently using several Multi-layer Perceptrons and then aggregate a global feature using a symmetric function (e.g., Max Pooling). However, the geometric relationships among 3D points are not fully considered. PointNet++ [28] and TopNet [11] incorporate a hierarchical architecture to consider the geometric structure. To relief the structure loss caused by MLP, AtlasNet [29] and MSN [30] recover the complete point cloud of an object by estimating a collection of parametric surface elements.
Graph-based Networks. By considering each point in a point cloud as a vertex of a graph, graph-based networks generate directed edges for the graph based on the neighbors of each point. In these methods, convolution is usually operated on spatial neighbors, and pooling is used to produce a new coarse graph by aggregating information from each point's neighbors. Compared with MLP-based methods, graph-based networks take local geometric structures into account.
In DGCNN [12], a graph is constructed in the feature space and dynamically updated after each layer of the network. Further, LDGCNN [31] removes the transformation network and link the hierarchical features from different layers in DGCNN to improve its performance and reduce the model size. Inspired by DGCNN, Hassani and Haley [32] introduce the multi-scale graph-based network to learn point and shape features for self-supervised classification and reconstruction. DCG [13] also follows DGCNN to encode additional local connection into a feature vector and progressively evolves from coarse to fine point clouds.
Convolution-based Networks. Early works [2,3,33] usually apply 3D convolutional neural networks (CNNs) build upon the volumetric representation of 3D point clouds. However, converting point clouds into 3D volumes introduces a quantization effect that discards some details of the data [34] and is not suitable for representing fine-grained information. To the best of our knowledge, no work directly applies CNNs on irregular point clouds for shape completion. In point cloud understanding, several works [17,35,36,37,38] develop CNNs operating on discrete 3D grids that are transformed from point clouds. Hua et al. [35] define convolutional kernels on regular 3D grids, where the points are assigned with the same weights when falling into the same grid. PointCNN [38] achieves permutation invariance through a χ-conv transformation. Besides CNNs on discrete space, several methods [8,15,16,39,40,41,42,43] define convolutional kernels on continuous space. Thomas et al. [15] propose both rigid and deformable kernel point convolution (KPConv) operators for 3D point clouds using a set of learnable kernel points. Compared with graph-based networks, convolution-based networks are more efficient and robust to point cloud density [17].

Overview
The proposed GRNet aims to recover the complete point cloud from an incomplete one in a coarse-to-fine fashion. It consists of five components, including Gridding (Section 3.2), 3D Convolutional Neural Network (Section 3.3), Gridding Reverse (Section 3.4), Cubic Feature Sampling (Section 3.5), and Multi-layer Perceptron (Section 3.6), as shown in Figure 1. Given an incomplete point cloud P as input, Gridding is first used to obtain a 3D grid G =< V, W >, where V and W are the vertex set and value set of G, respectively. Then, W is fed to a 3D CNN, whose output is W . Next, Gridding Reverse produces a coarse point cloud P c from the 3D grid G =< V, W >. Subsequently, Cubic Feature Sampling generates features F c for the coarse point cloud P c . Finally, MLP takes the coarse point cloud P c and the corresponding features F c as input to produce the final completed point cloud P f .

Gridding
2D and 3D convolutions have been developed to process regularly arranged data such as images and voxel grids. However, it is challenging to directly apply standard 2D and 3D convolutions to unordered and irregular point clouds. Several methods [2,3,8,33] convert point clouds into 3D voxels and then apply 3D convolutions to them. However, the voxelization process leads to an irreversible loss of geometric information. Recent methods [9,11] adopt Multi-layer Perceptrons (MLPs) to directly operate on point clouds and aggregate information across points with max pooling. However, MLP-based methods may lose local context information because the connectivity and layouts of points are not fully considered. Recent studies also indicate that simply applying MLPs to point clouds cannot always work in practice [17,39].
In this paper, we introduce 3D grids as intermediate representations to regularize point clouds and further propose a differentiable Gridding layer, which converts an unordered and irregular point cloud n is the number of points in P , and N is the resolution of the 3D grid G. As shown in Figure 1 (b), we define a cell as a cubic consisting of eight vertices.
of the 3D grid cell G, we define the neighboring points N (v i ) as points that lie in the adjacent 8 cells of this vertex. The point However, this voxelization process introduces a quantization effect that discards some details of an object. In addition, voxelization is not differentiable and thus can not be applied to point cloud reconstruction. As illustrated in Figure 1 (b), given a vertex v i and its neighboring points p ∈ N (v i ), the proposed Gridding layer computes the corresponding value w i of this vertex v i as denotes the sum operation. Tile creates a new tensor of size 16384 × 3 by replicating the "Coarse Point Cloud" 8 times.
where |N (v i )| is the number of neighboring points of v i . Specially, we define

3D Convolutional Neural Network
The 3D Convolutional Neural Network (3D CNN) with skip connections aims to complete the missing parts of the incomplete point cloud. It follows the idea of a 3D encoder-decoder with U-net connections [44,45]. Given W as input, the 3D CNN can be formulated as and w i ∈ R. As shown in Figure 2, the encoder of the 3D CNN has four 3D convolutional layers, each of which has a bank of 4 3 filters with padding of 2, followed by batch normalization, leaky ReLU activation, and a max pooling layer with a kernel size of 2 3 . The numbers of output channels of convolutional layers are 32, 64, 128, 256, respectively. The encoder is finally followed by two fully connected layers with dimensions of 2048 and 16384. The decoder consists of four transposed convolutional layers, each of which has a bank of 4 3 filters with padding of 2 and stride of 1, followed by a batch normalization layer and a ReLU activation.

Gridding Reverse
As illustrated in Figure 1 (c), we propose Gridding Reverse to generate the coarse be the index set of vertices of the i−th 3D grid cell. Gridding Reverse generates one point coordinate p c i for this grid cell by a weighted combination of eight vertices coordinates {v θ |θ ∈ Θ i } and the corresponding values {w θ |θ ∈ Θ i } in this cell, which is computed as Specially, we ignore the point p c i for this cell if θ∈Θ i w θ = 0.

Cubic Feature Sampling
MLP-based methods (e.g., PCN) are unable to take the context of neighboring points into account due to no local spatial connectivity across points. These methods use max-pooling to aggregate information globally, which may lose local context information.
To overcome this issue, we present Cubic Feature Sampling to aggregate fea- for the coarse point cloud P c , which is helpful for the following MLP to recover the details of point clouds, as shown in Figure 1 denotes the features of eight vertices of the i-th 3D gird cell where p c i lies in. In GRNet, Cubic Feature Sampling extracts the point features from feature maps generated by the first three transposed convolutional layers in 3D CNN. To reduce the redundancy of these features and generate a fixed number of points, we randomly sample 2, 048 points from the coarse point cloud P c . Consequently, it produces a feature map of size 2048 × 1792.

Multi-layer Perceptron
The Multi-layer Perceptron (MLP) is used to recover the details from the coarse point cloud by learning residual offsets between the coordinates of points in the coarse and final completed point cloud. It takes the coarse point cloud P c and the corresponding features F c as input, and outputs the final completed point where p f i ∈ R 3 and k is the number of points in the final completed point cloud P f . Tile creates a new tensor of size rk × 3 by replicating P c r times.
In GRNet, r is set to 8. The MLP consists of four fully connected layers with dimensions of 1792, 448, 112, and 24, respectively. The output of MLP is reshaped to 16384 × 3, which corresponds to the offsets of the coordinates of 16, 384 points.

Gridding Loss
Existing methods adopt Chamfer Distance [18] as the loss function to train the neural networks. This loss function penalizes the prediction deviating from the ground-truth. However, it can not guarantee that the predicted points follow the geometric layout of the object. Therefore the networks tend to output a mean shape that minimizes the distance, which causes the loss of the object's details [19,20].
Due to the unorderedness of point clouds, it is difficult to directly apply binary cross-entropy like voxels or L1/L2 loss like images. With the proposed Gridding, we can convert unordered point clouds into regular 3D grids ( Figure  1 (e)). Therefore, we design a new loss function based on Gridding, namely Gridding Loss, which is defined as the L1 distance between value sets of the two 3D grids. Let G pred =< V pred , W pred > and G gt =< V gt , W gt > be the 3D grids obtained by Gridding the predicted and ground truth point clouds, respectively, where W pred ∈ R N 3 G , W gt ∈ R N 3 G , and N G is the resolution of the two 3D grids. The Gridding Loss can be defined as

Datasets
ShapeNet. The ShapeNet dataset [46] for point cloud completion is derived from PCN [9], which consists of 30,974 3D models from 8 categories. The ground truth point clouds containing 16,384 points are uniformly sampled on mesh surfaces. The partial point clouds are generated by back-projecting 2.5D depth maps into 3D. For a fair comparison, we use the same train/val/test splits as PCN.
Completion3D. The Completion3D benchmark [11] is composed of 28,974 and 800 samples for training and validation, respectively. Different from the ShapeNet dataset generated by PCN, there are only 2,048 points in the ground truth point clouds.
KITTI. The KITTI dataset [47] is composed of a sequence of real-world Velodyne LiDAR scans, also derived from PCN [9]. For each frame, the car objects are extracted according to the 3D bounding boxes, which results in 2,401 partial point clouds. The partial point clouds in KITTI are highly sparse and do not have complete point clouds as ground truth.

Evaluation Metrics
be a reconstructed point set being evaluated, where n T and n R are the numbers of points of T and R, respectively. In our experiments, we use both Chamfer Distance and F-Score as quantitative evaluation metrics. Chamfer Distance. Follow PSGN [18] and TopNet [11], the distance between T and R are defined as  F-Score. As pointed out in [48], Chamfer Distance may sometimes be misleading. As suggested in [48], we take F-Score as an extra metric to evaluate the performance of point completion results, which can be defined as following where P (d) and R(d) denote the precision and recall for a distance threshold d, respectively.

Implementation Details
We implement our network using PyTorch [49] and CUDA 1 . All models are optimized with an Adam optimizer [50] with β 1 = 0.9 and β 2 = 0.999. We train the network with a batch size of 32 on two NVIDIA TITAN Xp GPUs. The initial learning rate is set to 1e − 4 and decayed by 2 after 50 epochs. The optimization is set to stop after 150 epochs.

Shape Completion on ShapeNet
To compare the performance of GRNet with other state-of-the-art methods, we conduct experiments on the ShapeNet dataset. AtlasNet [29] generates a point cloud with a set of parametric surface elements. To compare with other methods fairly, we sample 16,384 points from the generated primitive surface elements. PCN [9] completes the partial point cloud with a stacked version of PointNet [25], which directly outputs the coordinates of 16,384 points. FoldingNet [51]  is a baseline method adopted in PCN [9], which deforms a 128 × 128 2D grid into 3D point cloud. TopNet [11] incorporates a decoder following a hierarchical rooted tree structure to consider the topology of point clouds. Due to the scalable architecture of TopNet, it can easily generate 16,384 points by setting the number of nodes and the size of feature embedding. A very recent method MSN [30] generates dense point cloud containing 8,192 points in a coarse-to-fine fashion. To generate 16,384 points, we combine the generated points of 2 times forward propagation.
Quantitative results in Tables 2 and 1 indicate that GRNet outperforms all competitive methods in terms of Chamfer Distance and F-Score@1%. Figure 3 shows the qualitative results for point completion on ShapeNet, which indicates that the proposed method recovers better details of objects (e.g., chairs and lamps) than the other methods.

Shape Completion on Completion3D
Using the model with the lowest Chamfer Distance (CD) on the validation set, we recover the complete point clouds for 1,184 objects in the Completion3D testing set. Then, random subsampling is applied to the generated point clouds to obtain 2,048 points for benchmark evaluation. According to the online leaderboard 2 , as shown in Table 3, the overall CD for the proposed GRNet is 10.64, which remarkably outperforms state-of-the-art methods and ranks first on this benchmark.

Shape Completion on KITTI
To evaluate the performance of the proposed method on real-world LiDAR scans, we test GRNet on the KITTI dataset for completing sparse point clouds of cars. Unlike ShapeNet generated by back-projected from 2.5D images, point clouds from LiDAR scans can be highly sparse, which are much sparser than those in ShapeNet.
We fine-tuned all competitive methods on ShapeNetCars (the cars from ShapeNet) except PCN that directly uses released output for evaluation. During testing, each point cloud is transformed into the bounding box's coordinates and transformed back to the world frame after completion. The models trained specifically on cars are able to incorporate prior knowledge of the object class.
Since there are no complete ground truth point clouds for KITTI, we use Consistency and Uniformity to evaluate the performance of all competitive methods. Consistency in PCN [9] is the average CD between the output of the same car instance in n f consecutive frames. Let R j ti be the output for the j-th car instance at time t i . The Consistency for the j-th car can be calculated as Following PU-GAN [52], we adopt Uniformity to evaluate the distribution uniformity of the completed point clouds, which can be formulated as where S i (i = 1, 2, . . . , M ) is a point subset cropped from a patch of the output R using the farthest sampling and ball query of radius √ p. The term U imbalance and U clutter account for the global and local distribution uniformity, respectively. wheren = p|R| is the expected number of points in S i .
where d i,j represents the distance to the nearest neighbor for the j-th point in [52]. Table 9 shows the completion results for cars in the LiDAR scans from the KITTI dataset. Experimental results indicate that GRNet outperforms other competitive methods in terms of Consistency and Uniformity. Benefited from Gridding and Gridding Reverse, GRNet is more sensitive to the spatial structure of the input points, which leads to better consistency between the two consecutive frames. As shown in Figure 4, the cars are barely recognizable due to incompleteness of the input data. In contrast, the completed point clouds provide more geometric information. In addition, the qualitative results also demonstrate the proposed method generates more reasonable shape completion.

Ablation Study
The performance improvement of GRNet should be attributed to three key components, including Gridding, Cubic Feature Sampling, and Gridding Loss. To demonstrate the effectiveness of each component in the proposed method, we evaluate the performance with different parameters. Gridding. Table 5 shows the results of different resolutions of 3D grids generated by Gridding. The F-Score of final completed point clouds increases with the 3D grids' resolutions. However, the numbers of parameters and the backward time also increases. To archive a balance between effect and efficiency, we choose the resolution of size 64 3 for Gridding in GRNet. Cubic Feature Sampling. To quantitatively evaluate the effect of Cubic Feature Sampling, we compare the performance without Cubic Feature Sampling and with different feature maps fed into it. The experimental results presented in Table 6 indicate that Cubic Feature Sampling improves the point cloud completion results significantly. In addition, with more feature maps are fed, the completion quality becomes better without a significant increase in the numbers of parameters and backward time. Gridding Loss. We further validate the effects of Gridding Loss, as shown in Table 7. There is a decrease in terms of both CD and F-Score when removing Gridding Loss. When increasing the resolution of 3D grids from 64 3 to 128 3 , there are 25.9% and 5.4% improvements in CD and F-Score, respectively.

Conclusion
In this paper, we study how to recover the complete 3D point cloud from an incomplete one. The main motivation of this work is to enable the convolutions on 3D point clouds while preserving their structural and context information.
To this aim, we introduce 3D grids as intermediate representations to regularize unordered point clouds. We then propose a novel Gridding Residual Network (GRNet) for point cloud completion, which contains three novel differentiable layers: Gridding, Gridding Reverse, and Cubic Feature Sampling, as well as a new Gridding Loss. Extensive comparisons are conducted on the ShapeNet, Com-pletion3D, and KITTI benchmarks, which indicate that the proposed GRNet performs favorably against state-of-the-art methods.
A More Explanations on Gridding, Gridding Reverse, and Cubic Feature Sampling

A.1 Gridding
According to the main paper, given a vertex v i and its neighboring points p ∈ N (v i ). The proposed Gridding layer computes the corresponding value w i of this vertex v i as where |N (v i )| is the number of neighboring points of v i and w(v i , p) is defined as Based on Equations 17 and 18, the partial derivative with respect to x can be calculated as follows where x and x v i are the x-coordinates of the point p and vertex v i , respectively. Similarly, the partial derivative with respect to y and z can be calculated as follows where y and y v i are the y-coordinates of the point p and vertex v i , respectively. z and z v i are the z-coordinates of the point p and vertex v i , respectively.

A.2 Gridding Reverse
Point Coordinates Normalization. Gridding Reverse generates point p c i = (x c i , y c i , z c i ) for the i-th grid cell by a weighted combination of eight vertices {v θ |θ ∈ Θ i } and the corresponding values {w θ |θ ∈ Θ i } in this cell, which is calculated as where θ∈Θ i w θ = 0 and Θ i = {θ i j } 8 j=1 represents the index set of vertices of this 3D grid cell. Let (x v θ , y v θ , z v θ ) be the coordinate of the vertex v θ , where

B Additional Quantitative Results on ShapeNet
According to the main paper, the Chamfer Distance is with L2 norm. However, PCN [9] adopts the Chamfer Distance with L1 norm as an evaluation metric, which can be formulated as follows where is the reconstructed point set being evaluated. n T and n R are the numbers of points of T and R, respectively. Table 8 shows the results of point cloud completion using the Chamfer Distance calculated with Equation 34. The values of PCN are exactly the same as Table 4 in the original paper 3 .

C Additional Quantitative Results on KITTI
PCN [9] uses the Fidelity Distance (FD) and Minimal Matching Distance (MMD) as evaluation metrics for KITTI. FD is the average distance from each point in the input to its nearest neighbor in the output, which can be defined as follows   where I denotes the input point cloud. MMD is the Chamfer Distance (CD) between the output and the car point cloud from ShapeNet that is the closest to the output point cloud in terms of CD. The Fidelity and MMD on KITTI of the compared methods are shown in Table 9. However, both FD and MMD are not suitable metrics for KITTI. As shown in Figure 5, real-world LiDAR scans usually contain clutters which should be removed in the recovered point cloud. MSN [30] incorporates the minimum density sampling (MDS) to preserve the structure of the input point cloud. Although MSN outperforms other methods in terms of FD, the clutters in the input point cloud are also preserved. MMD measures how much the output resembles the cars in ShapeNet. However, cars from ShapeNet cannot cover all types of cars in the real world.

D Additional Ablation Studies
Number of Sampling Points. Gridding Reverse generates a coarse point cloud from a 3D grid. We randomly sample 2,048 points from the coarse point cloud to generate a point cloud containing a fixed number of points for the following MLP. Table 10 shows the Chamfer Distance (CD) and F-Score@1% with different numbers of points sampled.
Experimental results indicate that sampling 2,048 points from the coarse point clouds archives the best performance in terms of CD and F-Score. The Table 9. Results of point cloud completion on KITTI compared using Fidelity Distance (CD) and Minimal Matching Distance (MMD) computed on 16,384 points. Note that both FD and MMD are with L2 norm. The best results are highlighted in bold.

E More Qualitative Comparisons
In this section, we provide more visual comparisons with the state-of-the-art methods [9,29,51,11,30] for point cloud completion on ShapeNet [46].