{'fraction_non_alphanumeric': 0.025973530645714938, 'fraction_numerical': 0.010869979785651627, 'mean_word_length': 4.733654056418106, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
GASCN: Graph Attention Shape Completion Network

Shape completion, the problem of inferring the complete geometry of an object given a partial point cloud, is an important problem in robotics and computer vision. This paper proposes the Graph Attention Shape Completion Network (GASCN), a novel neural network model that solves this problem. This model combines a graph-based model for encoding local point cloud information with an MLP-based architecture for encoding global information. For each completed point, our model infers the normal and extent of the local surface patch which is used to produce dense yet precise shape completions. We report experiments that demonstrate that GASCN outperforms standard shape completion methods on a standard benchmark drawn from the Shapenet dataset.


Introduction
It is often desirable to be able to infer the geometry of objects in a scene based on a small number of sensor measurements. This is known as the shape completion problem where the system infers the complete geometry of an object based on a partially observed point cloud, such as that produced by a depth sensor. In particular, shape completion could be useful in the context of robotic manipulation where a robotic system could use the inferred geometry of the objects in a scene to create geometric plans that solve desired tasks. Compared to other approaches to scene reconstruction that estimate the pose of specific objects, a critical advantage of shape completion methods is that they can be used to infer the geometry of novel objects, not just a closed set of previously modeled objects.
There are two main types of approaches to shape completion: one based on the point cloud representation and the second based on voxel grids or signed distance functions. Point clouds are a convenient choice because they can be created easily from the output of depth sensors or LIDAR and several methods use point cloud represenations [36,35,8,17]. However, these methods are all limited by the fact that they cannot use 3D convolutions because the point cloud representation does not explicitly encode information about the local connectivity of each point. An alternative is to create shape completion algorithms based on a voxel grid or signed distance function (SDF) representation [22,12,24]. Here, we can use 3D convolutions to obtain higher shape completion accuracy, as in GRNet [32]. However, the memory requirements for voxel grids or SDFs are cubic in the resolution of the grid and therefore it severely limits the resolution at which the method can be applied.
In contrast to the methods above, this paper proposes GASCN, a shape completion approach that operates on a graph rather than a point cloud or voxel grid. Since converting a point cloud into a mesh can itself be challenging, we use a graph attention approach [26] where each point in the cloud is associated with a unique graph that connects it with its neighbors. Another key element of our approach is a densification step that converts a coarse reconstruction into a fine reconstruction by deforming a fine 2D grid to each coarse point via a learned surface normal and variance. The novel features of our approach relative to prior shape completion work are the following: 1. Our encoder utilizes the graph attention layer to encode local context information for further combination with the global structure information whereas prior work on shape completion typically uses a Point-Net [20] encoder or 3D convolutions on voxels [31]. This enables us to take point cloud input while still encoding using graph convolutions.
2. Our decoder contains a novel densification procedure that maps a dense planar grid to a local region around each point in a coarse shape completion. This enables us to produce a dense completion while keeping the network complexity manageable.
We compare our model with several other recent approaches from the literature [35,36,25] and find that it outperforms on a standard shape completion baseline task. arXiv:2201.07937v1 [cs.CV] 20 Jan 2022

Related Work
The problem of inferring 3D structures from RGB and depth camera images has been studied for decades. A classic but powerful non-learning method uses the Iterative Closest Point (ICP) [1] algorithm to align a template model from a large dataset with the observed point cloud. BEOs [3] constructs a new representation space with VBPCA [2] basis, where the best corresponding point to the partial input could be found. Some other works [21,10,16] deform the template model to synthesize shapes that are more consistent with the observations. These methods are often sensitive to noise and require large datasets as well as expensive computation time.
Recent learning-based approaches complete the 3D structure with a parameterized model, often a deep neural network, directly from the observation. It allows a fast inference and great generalization. Some datasets like ShapeNet [5] and YCB [4] enable learning on sufficient examples to generate visually compelling shapes. The most common structure for a shape completion network consists of an encoder that maps the partial observation to a latent vector and a decoder that produces the complete 3D shape given the latent vector. The learning method differs based on the different representation methods of a 3D object.
Voxel-based methods [24,31,12] voxelize point clouds into binary voxels, where 3D convolutional neural networks can be applied. Recently, GRnet [32] proposed a novel gridding mechanism to encode the neighbors' information into the vertices of each voxel. These methods are often computation expensive and limited to quantization effects due to the voxel representation.
PointNet [20] is a pioneer in using the MLP-based approach to learn point clouds. It combined pointwise multilayer perceptrons with a max-pooling aggregation function to achieve invariance to permutation and robustness to perturbation. After PointNet, FoldingNet [35] proposed a folding-based decoder that deforms a 2D grid onto the 3D surface of a point cloud. Following previous works, PCN [36] proposed the coarse-to-fine procedure to densify the point cloud. AtlasNet [8] and MSN [17] generated a collection of parametric surface elements based on Fold-ingNet's decoder. Besides, some work [15,30] combined MLPs with GANs [7], and some [22] integrated it with reinforcement learning. However, these approaches just aggregated the global information from the whole point cloud without focusing on the local information of each point's neighbors, and neither did they take the various local properties of different points into account during the generation process.
Compared with MLP-based approaches, graph-based methods could extract local information of each point. Most recent graph-based convolution methods [14,11,26] operated on groups of spatially close neighbors. ECC [23] is the first one to apply graph convolutions to point cloud classification. After that, DGCNN [29] proposed a more generalized edge convolution method with dynamic graph updates to encode the local neighborhood information for point clouds. Inspired by DGCNN, DCG [27] introduced this method to point cloud completion following a coarseto-fine fashion. However, the edge convolution is computationally expensive in large graphs. After Graph Attention Network [26], GAC [28] inherited its ideas and applied attention mechanism to the point cloud segmentation area. To the best of our knowledge, we are the first to directly combine the graph-level local information with the global structure information in the encoder as well as utilize surface normals to incorporate pointwise local properties for shape completion. Figure 1 below is an overview of our network, which follows an encoder-decoder architecture. It takes a partial point cloud with a variable number of points as input, p input and generates a complete dense point cloud as output, p f inal .

Method
The encoder ( Figure 2) uses a graph attention network (GAT) [26] to reason about the local geometry of the input cloud and MLPs to reason about global geometry.
GAT [26] is used to learn the graph-level local information and MLPs are used to encode the global information. Following a coarse-to-dense procedure, our decoder first decodes a sparse point cloud P c and then samples each point's neighbors to densify P c . To make the densifying process flexible and adaptive to different local geometries, we decode surface normals and the scale factor σ by our normal decoder and sigma decoder to adjust the orientation and the size of each point's neighborhood.

Encoder
Since each region of a point cloud could have different geometries, all the global information without the local information would result in averaging over all point features and thus undermining the completions. In order to solve it, our encoder is built on the graph representation of partial point clouds. We encode each node feature with its neighbors' information, its mapped Cartesian feature, and two different types of global vectors to maximize the utilization of local information and global information.  features corresponding to each point, where D is the dimension of the node features. Each node feature is initial-

Build Graph for Point Cloud
..,m ⊆ G for all nodes as k-nearest neighbor [19] graphs from node features H by connecting the corresponding point p i with its k-nearest spatial neighbors. Besides, the subgraphs include self-loops to preserve each node's own information.
As a result, the whole graph for the point cloud comprises m directed subgraphs and each point is assigned as the destination node of a subgraph. Each of them seems like a patch on the surface of a 3D object, similar to the kernel window in 2D convolution.

Local Convolution: GAT
Although points in the point cloud are independent, there must exist certain hidden relationships to maintain the local surface geometry. GAT [26] provides an attentive mechanism to learn it. Given the graph G and point features H of a partial point cloud, we apply the GAT layer to aggregate each node's neighborhood information.
First, we conduct a linear transformation for the embedding feature h i of the node i with a shared learnable weight Figure 2: Graph-based Encoder of GASCN model. It encodes each node feature with its neighbors' information F graph by graph attention layer, its mapped Cartesian feature F cart by point-wise MLP, and two types of global vectors, g graph and g cart , extracted from the max-pooling operation.
matrix W and then compute a pair-wise unnormalized attention score e ij with a learnable vector a between the two neighbors i and j (|| is the concatenation operation).
After that, our network normalizes the attention score on each node's neighbors and aggregates the embeddings from neighbors with the normalized attention score, and applies a nonlinear activation function.
The final result is denoted as F graph which is an m × d matrix, where m is the number of points and d is the feature dimension. The process above maps each node feature from a 3-dimension xyz coordinate to a d-dimension vector that contains the information of its neighbors through the graph attention layer.

Global Information
The global structure information is critical in point cloud generation, which could be used to distinguish different objects. We extract two different types of global information, the global graph vector g graph and the global Cartesian vector g cart . The global graph vector g graph is given by where max-pooling operation concatenates the maximum value among each feature dimension of F graph to construct the permutation-invariant global vector g graph . We define the pointwise MLPs in PointNet [20] as M θ : R d1 → R d2 . It maps each point feature from d 1 -dimension into a new d 2 -dimension space using a nonlinear function M with the shared learnable weights θ. The second global vector is aggregated by: After that, two different feature matrices, F graph and F cart , are concatenated into an augmented feature matrix F , while two global vectors g graph and g cart are concatenated together to produce the augmented global vectorḡ. We concatenateḡ to each row ofF to get our final feature matrix F f inal . So far, each node feature is encoded with information of its neighbors, its mapped Cartesian feature, and two types of global vectors. Finally, we extract the final latent vector g f inal by:

Decoder
Regarding the various local properties of different points during the generation process, our decoder first generates coarse points, each coarse point's surface normal, and its corresponding scale factor σ, as shown in Figure 3. It then samples coarse points' neighbors with adaptive 3D grid points and utilizes both surface normals and coarse points to determine the rotation and the translation, respectively.

Coarse Point Cloud and Surface Normal
The coarse output P c is a preliminary generated complete shape with sparse points. Following previous work [36], we use three fully connected layers with nonlinear activation functions to decode the g f inal to P c , as shown at the top of Figure 3.
In order to densify completions, some pointwise attributes are needed to generate neighbors. Surface normal is a good option which contains the local orientation of a surface. To decode surface normals, we first build a graph by connecting each coarse point with its nearest neighbors and apply one graph convolution layer [14] to aggregate the neighbor information into C local . In the meantime, the global vector g f inal and coarse points P c are mapped respectively by two different MLPs into G map and C map . The surface normal is generated by where the N imd is the normal internal embedding. The whole process above is shown in Figure 3. Figure 3: Decoder Architecture. The coarse points decoder consists of three fully connected layers. The normal decoder takes as inputs the mapped coarse point coordinate C map , its neighbors' information C local , and the mapped global vector G map . The sigma decoder takes as inputs the normal internal embedding N imd , C local , C map , and G map , and then applies three pointwise MLP layers to output pointwise-attentive sigmas.

Calculate Neighbors by Surface Normals in Coarse Point Cloud
Given a point p = (p x , p y , p z ) and its normal n = (n x , n y , n z ), how could we sample its neighbor points? Neither sampling X, Y, Z randomly [17] from a distribution that would make the output look noisy and the model hard to train, nor utilize a fixed grid which is inflexible; we instead mesh an adaptive grid to obtain a set of 3D Cartesian coordinates for each coarse point. Our procedure has four steps: sampling, scaling, rotation, and translation.

Obtain neighbors by meshing grid:
(X, Y ) = M eshgrid(l, l); Z = 0 (11) (X, Y, Z) is a set of vertices of a square grid of size l, centered at the origin with surface normal oriented along Z-axis, forming a plane in 3D space. 2. Scale X, Y with σ: Each point has a specific scale factor σ that is learned from the neural network, which we will discuss in Sec-tion 3.2.3. After the scaling, different points are associated with planes of different sizes accordingly. Figure 4: After the scale and rotation, we align the initial 3D-grid neighbors' surface normal along the decoded N ormal. This process enables our generated grid points to match local surfaces with different orientations and geometries. (Blue dots are neighbors, the green line indicates the normal direction, and the red dot is the center.) 3. Rotate the samples to make their surface normals align along the surface normals we generated, as shown in Figure 4: where the k is the rotation axis, z axis is the unit vector along Z-axis, × is the cross product, θ is the rotation angle. If k is a zero vector, no rotation is needed. We use Rodrigues' Rotation Formula to transform the axis-angle representation to a rotation matrix R. 4. Translate the center of the samples to point p. The samples are centered at the origin (0, 0, 0) previously, and we add the generated point's coordinate (p x , p y , p z ) to each sample's coordinate to complete the translation.
After applying the operations to each point of P c , we fuse each point's local surface information with its coordinate to densify the point cloud.

Scale Factor σ
σ is the scale factor learned from our sigma network shown in Figure 3 to scale the samples. For each point in P c , there is a σ corresponding to it. It makes the neighbor generation be flexible and attentive. Using a table as an instance, the corner points or edge points may have smaller σ, while points on a flat plane should have a larger σ since they have more confidence in sampling neighbors with a wider grid. In our work, σ is pointwise attentive and learned by

Deformation and Refinement
So far, our network generates a dense set of points, P d . In order to deform the 3D-grid points and ensure robust performance, each point is concatenated with the corresponding coarse point, which serves as its positional embedding. We then map the feature to a high-dimension space and project them back to 3D space by three points-wise MLPs and Leaky-Relu activation function [33]. We intuitively denote the improved dense point clouds as fine point clouds, P f , which marks the end of our forward propagation.

Loss
Since the point cloud is an unordered set, we use the permutation-invariance loss, Chamfer Distance (CD) [6], to measure the distance between our output and the ground truth. CD (16) calculates the average closest point distance between two sets of point clouds. It has two terms to force the output to be closed to as well as cover the ground truth.
Our network generates two outputs: Coarse points P c , fine points P f , and each output corresponds to a CD loss with respect to the ground truth. Loss = CD loss (P c , P gt ) + α CD loss (P f , P gt ) (17) where α is a hyperparameter and P gt are ground truth points.

Experiments
This section describes our dataset and the training process first, and then compares our methods with several strong baselines. Afterward, we present the ablation study results, followed by experiment on real-sensor data. Following previous works [36,25,32], Chamfer Distance serves as our quantitative evaluation metric for baseline comparison and ablation study.

Datasets and Implementation Details
ShapeNet PCN. The ShapeNet dataset [5] for point cloud completion is derived from PCN [36], consisting 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 randomly sampling 8 camera poses to capture 8 depth images for each CAD model and backing-projecting the 2.5D depth images to 3D, and thus own a variant number of points.

Airplane Cabinet
Car Chair Lamp Sofa  ShapeNet Bottle. We built a small dataset for ablation study and our future work in manipulator grasping following ShapeNet PCN. It contains 498 bottle-shaped objects such as water bottles, jars, spray bottles, etc. Each object is also used to generate eight partial observations with a flexible number of points and one ground truth point cloud with 9,216 points. 80% of the models are used for training, 10% for evaluation and 10% for testing.
YCB Dataset. It consists of objects of daily life with different shapes, sizes, and textures. The dataset provides mesh models and RGB-D scans of the objects.
We select the following setting based on our implementations and dataset. During constructing the graph representation of the point cloud, each point is connected with its 20 neighbors. KDTree [18] was used for fast retrieval of nearest neighbors. We first generate a coarse point cloud with 1,024 points and link each point with its 5 nearest neighbors. A 4 × 4 grid initialized with l equals to 0.1 is used to sample 16 neighbors for each coarse point. As a result, our model consumes an input with a variable number of points and generates the coarse output with 1,024 points and fine output with 16,384 points. We trained the networks for 200 epochs with a decaying learning rate initialized at 10 −4 and Adam optimizer [13], with a batch size of 32 on Four

Baselines and Performance Comparison
Here, we compare our model against four baselines that work on point cloud completion.
1. FoldingNet: It encodes each point's neighbor information by flattening the covariance matrix and proposed a folding-based decoder that deforms a 2D fixed grid onto the 3D surface of a point cloud [35].
2. TopNet: It proposes a decoder following a hierarchical rooted tree structure to generate points [25].
Quantitative results in Table 1 and Table 2 indicate our method could achieve better performance over all eight categories while still maintain a reasonable number of parameters. As shown in Figure 5, our completion results could recover a more detailed geometry than others. It proves the advantage of our proposed method that extracts both the local information and the global structure information from the observations and the strength of generating various local geometries.

Ablation Study
In order to investigate our encoder and decoder's performance separately, we train four different neural networks for the ablation study on the ShapeNet Bottle. A 3×3 grid is used to generate 9,216 points. We evaluate the performance on the validation dataset every 20 epochs during training.  As shown in Figure 6, both our encoder and decoder converge fast and outperform PCN's encoder and decoder. Without GAT in the encoder, the performance is decreased by 8%; without surface normals and scale factor σ, the performance is decreased by 10%. It further indicates our encoder's benefit, which combines local information with global information, and our decoder's power, which utilizes surface normals and adaptive grid sizes.
We also investigated using multiple GAT layers to encode local information, while the test results show no improvement but the deterioration of the performance. We speculate the main reason is that two graph attention layers allow each point to communicate with more neighbors, Figure 7: Experimental results on YCB objects, showing completions for a mustard bottle and a banana, respectively. We extract the point clouds (second column) from the raw depth images (first column), and feed them into the model to generate the completions (third column). The ground truth meshes are shown in the last column.
which will lead it to lose the property of local convolution, and hence be difficult to learn efficiently with the attention mechanism.

Experiment on Sensory Data
We test our model on YCB objects with a reasonable reconstructed mesh (70 in total), as shown in Figure 7. We first build a small simulation dataset using the same strategy mentioned in ShapeNet Bottle. After training our model for 150 epochs, we test it on sensory point clouds extracted from raw registered depth images. Our model achieves an average chamfer distance of 9.9834 × 10 −3 on depth images of the first camera view of each object from the YCB dataset. It is worth noting that the real sensor data is nosier and occasionally suffers from missing geometry features compared to the simulated data.

Nearest Neighbor Distance for Each Point
Since Chamfer Distance only provides the average performance for the whole point cloud [34], to analyze our results in detail, we illustrate each point's nearest neighbor distance to the ground truth in Figure 8. The generated points are rendered by their closest distances to the ground truth. As it suggests, each point maintains a relatively small distance to the closest point in the ground truth.

Generalization Ability
When testing on the ShapeNet Bottle dataset, we found some interesting results. Figure 9 shows our generation process for a shampoo bottle and a coke can with a straw. There is no straw-like object but some shampoo bottles in the training dataset, and our network could still reason out the geometry of the straw, though it resembles the shampoo header to some degree. This phenomenon shows that our model could predict a reasonable shape for the unseen part of the input point cloud, which indicates the generalization ability of our proposed method.

Partial
Coarse Fine Ground Truth Figure 9: Illustration of Generalization Ability of GASCN: first, we take a partial point cloud as input and output coarse point clouds, and then do the coarse-to-fine refinement. The top row and the bottom row show the generation process of a shampoo bottle and a coke can with a straw, respectively. Though there is no straw in our training data, our model generates a similar geometry for the unseen part of the partial observation during testing.

Point Cloud Registration
Many tasks in robotics could benefit from dense complete point clouds. We illustrate its advantage on the point cloud registration. Specifically, we ran ICP [1] for two different partial observations from one object and compared its results with their corresponding complete fine points. Our experiment indicated that our generated complete points have fewer errors since they have significant overlaps compared to the partial observations. It is worth noting that our model could enormously increase the utilization of observations in many downstream tasks, especially where both the completions and surface normals are needed.

Conclusion
In this work, we studied how to infer the complete 3D geometry from an incomplete observation. Our motivation is to combine local information with global information in our encoder and take the pointwise local property into account during our generation. To achieve the target, we utilized the graph attention layer for encoding local context information and utilized MLPs and max-pooling to aggregate the global structure information. To decode the latent vector properly, we inversed the process of calculating surface normal from points and utilized adaptive 3D grids to obtain neighbors. In our future work, we will investigate combining shape completion with grasp pose detection [9] in robotics.