{'fraction_non_alphanumeric': 0.03609913793103448, 'fraction_numerical': 0.012021821120689655, 'mean_word_length': 4.8946010321556175, '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': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
PU-EVA: An Edge Vector based Approximation Solution for Flexible-scale Point Cloud Upsampling

High-quality point clouds have practical significance for point-based rendering, semantic understanding, and surface reconstruction. Upsampling sparse, noisy and nonuniform point clouds for a denser and more regular approximation of target objects is a desirable but challenging task. Most existing methods duplicate point features for upsampling, constraining the upsampling scales at a fixed rate. In this work, the flexible upsampling rates are achieved via edge vector based affine combinations, and a novel design of Edge Vector based Approximation for Flexible-scale Point clouds Upsampling (PU-EVA) is proposed. The edge vector based approximation encodes the neighboring connectivity via affine combinations based on edge vectors, and restricts the approximation error within the second-order term of Taylor's Expansion. The EVA upsampling decouples the upsampling scales with network architecture, achieving the flexible upsampling rates in one-time training. Qualitative and quantitative evaluations demonstrate that the proposed PU-EVA outperforms the state-of-the-art in terms of proximity-to-surface, distribution uniformity, and geometric details preservation.


Introduction
With increasing capability of acquiring point clouds as a direct approximation of an object or scene surface from 3D scanning sensors, typical applications processing raw points are prevailing, such as point-based semantic understanding [3,10,31,32,34], point clouds rendering [4,14] and surface reconstruction [22,36], etc. Hence, the quality of input points is critical for the digital designs. However, a couple of varying artifacts, including occlusion, light  [42], (b) 3PU [40], (c) PU-GAN [17] and (d) our PU-EVA. Note that our PU-EVA with edge vector based approximation generates points more uniform with fine-grained details, compared to other state-of-the-arts. reflection, surface materials, sensor resolutions and viewing angles, hinder high-quality practical acquisition of point clouds. It is desirable to upsample raw point clouds for a better description of an underlying surface, by converting the sparse, noisy, and non-uniform points into the dense, regular and uniform ones.
The success of image super-resolution [16,21,30,33,38] in 2D computer vision inspires the corresponding techniques for point clouds upsampling. Nevertheless, the intrinsic irregularity of point clouds makes effective implementations for image interpolations not applicable in 3D world. Based on this, different criteria should also be considered for point clouds upsampling. First, the upsampled points should lie on or be close to the underlying surfaces of target objects. Next, the upsampled results should distribute uniformly, instead of being clustered together. Last, the generated points should preserve geometric details of the target objects.
The previous works often upsample points by simply duplicating point features and disentangling them in positions via a set of MLPs [17,40,42]. The strategy may lead the generated points cluster around original ones and loss geometric details of the target objects. To overcome these issues, we are motivated to develop an upsampling strategy by considering the geometric information of the underlying surface. To capture veracious neighboring connectivity, a similarity matrix constructed by edge vectors is devised. Here, the edges depict the connections between a center point to the neighboring points, by following the concept of EdgeConv [35]. The edge vectors are the oriented edges pointing from the center point, encoding features from both of the connecting points. The significance of edge vectors to the upsampling point are endowed in the similarity matrix, and an edge vector based affine combination is formed to implement their contributions to upsampling. According to the linear approximation theorem originally proposed by [26], the approximation error of affine combinations in local neighborhood can be formulated as a high-order term mathematically. By applying the theorem in our case, a second-order term of Taylor's Expansion is derived as the approximation error of the proposed method, which encourages the data-driven upsampling network converging under such an approximation. Moreover, the upsampling unit is designed to learn all possible neighboring connectivity from the edge vectors, making the upsampling rate flexible in one-time training. To implement the motivations, we propose a novel design of Edge Vector based Approximation for Flexible-scale Point clouds Upsampling (PU-EVA). To sum up, the contributions of the proposed PU-EVA are listed as below: 1. The proposed PU-EVA achieves a flexible upsampling scale in one-time end-to-end training, making the upsampling rate decoupled with the network architecture; 2. The edge vector based approximation upsample new points by endowing geometric information of the target objects, which benefits the upsampling performance in sharp regions and areas with fine-grained details; 3. The proposed edge vector based affine combinations restrict the approximation error within a second-order term of Taylor's Expansion, encouraging the datadriven network converging under such an approximation.

Related work 2.1. Optimization-based upsampling methods
One of the earliest optimization-based methods generates a set of triangles for the sample points by using three-dimensional Voronoi diagram and Delaunay triangulation [2]. A parametric-free method of point resampling and surface approximation is developed by using a locally optimal projection operator (LOP) in [20]. However, the LOP-based methods require surface smoothness, giving rise to performance struggling around sharp edges and corners. To this end, an edge-aware point clouds resampling (EAR) method uses implicit models to preserve sharp features, by resampling points away from edges and upsampling them progressively to approach the edge singularities [12], whereas the performance of EAR heavily depends on the given normal values and parameter tuning. For point clouds completion and consolidation, a new representation of associating surface points with inner points to reside on the extracted meso-skeletons is proposed, and the optimization is conducted under global geometry constraints from the meso-skeletons [37]. The method recovers regions with holes successfully though, it is sensitive to noise and outliers. Overall, the piece-wise smoothness assumption of optimization-based upsampling methods makes the finegrained patterns missing, causing the performance of this category of methods limited.

Learning-based upsampling methods
Inspired by data-driven approaches and their promising results, taking advantages of deep learning techniques to model the complex geometries has been brought to attention thus far. PU-Net [42], as the first learning-based point upsampling network, learns geometry semantics of point patches based on the framework of PointNet++ [23], and expands the learned multi-scale features to upsample a given point cloud. EC-Net [41] utilizes an edge-aware technique to process point clouds and simultaneously recovers 3D point coordinates and point-to-edge distances by a joint loss. 3PU [40] proposes a progressive upsampling network using different number of neighbors in subsequent upsampling units. PU-GAN [17] is a generative adversarial network (GAN) [9] based point cloud upsampling network. It focuses on boosting the quantitative performance of upsampled point clouds by constructing an up-down-up expansion unit, a self-attention unit as well as a compound loss. PUGeo-Net [27], as the first geometry-centric network, proposes to upsample points by learning the first and second fundamental forms of the local geometry under the supervision of normals. CAD-PU [19] proposes geometrically intuitive surrogates to improve the quality of the surface approximation for upsampled point clouds, by realizing the curvature-adaptive feature expansion. Dis-PU [18] Ground truth points disentangles the upsampling task by formulating two cascaded sub-networks, a dense generator and a spatial refiner. The dense generator infers a coarse output describing the underlying surface roughly, and the spatial refiner adjusts the point locations via the predicted offsets for a fine upsampling result. PU-GCN [25] proposes a Graph Convolutional Networks (GCN) based network by combining a feature extraction module Inception DenseGCN to capture multi-scale information and a point cloud upsampling module NodeShuffle to encode local point information. The proposed NodeShuffle can also be incorporated into other upsampling pipelines for performance improving.
One of the main limitations of these learning-based upsampling methods is that the upsampling rate is fixed during each training, limiting their applications to the realworld upsampling tasks. MAPU-Net [26] handles an arbitrary upsampling factor in one-time training for the first time, by learning unified and sorted interpolation weights and normal-guided displacements in terms of the proposed linear approximation theorem. A self-attention-based refinement module is further devised to circumvent the normal estimation, driving the upsampling results to approach the underlying surface [28]. Meta-PU [39] also supports the arbitrary scales upsampling by using meta learning to predict the weights of the network and change behavior for each scale factor dynamically. Our proposed upsampling strategy decouples the upsampling rate with network architecture, with an edge vector based approximation solution to generate new points by encoding neighboring connectivity, achieving the flexible upsampling rates in one-time training.

Proposed method
In this section, we present an end-to-end data-driven framework for point clouds upsampling, dubbed Edge Vector based Approximation for Flexible-scale Point clouds Up-sampling (PU-EVA). As shown in Figure 3, the proposed PU-EVA consists three elements: dense feature extraction, edge vector based approximation upsampling, and coordinate reconstruction. The detailed architecture is explained below.

Dense feature extraction
Given an input sparse point cloud P , where N is the number of points. The objective is to generate dense points approximating the underlying surface, where R is the upsampling rate 1 . As show in Figure 2 (b), consider a small vicinity N K (p i ) ⊆ P, the red point denotes the center point p i , and the yellow points indicate K nearest neighbors p i,k .
In dense feature extraction, a dense dynamic feature extraction method in [40] is applied on each vicinity N K (p i ) ⊆ P, by adopting the EdgeConv [35] as a basic block. In essence, four dense blocks are employed for extraction. To leverage features of different layers, skip-connections are applied within and between the dense blocks. Within the dense block, three convolutional layers are skip-connected, the output features are passed to all subsequent layers, and a max-pooling layer is employed at the end for input order invariant; between the dense blocks, the features produced by each block are fed to all following blocks. In this way, the point feature of N × C are extracted from the sparse input P, where C stands for the number of dimensions. The enriched geometric features with long-range and non-local information from multiple scales are embedded in the obtained point feature V for further edge vector based operations.

Edge vector based approximation upsampling
The Edge Vector based Approximation (EVA) is put forward in the vicinity N K (p i ) for upsampling, as illustrated in Figure 2 (c). A similarity matrix S determines the significance of edge vectors to the upsampling point. Specifically, the edge vector ∆F i,k with respect to K neighbor points are defined as, where p i and v i are point coordinates and point features of the center point, p i,k and v i,k are point coordinates and Estimate the coordinate error  point features of K neighbor points, and d i,k is the Euclidean distance between the center point and the neighbors. Similarly, the edge vector ∆F i,r is obtained based on R anchor points. Here, R anchors points are selected from K neighbor points, implying that R is no bigger than K. The correlations between the edge vectors ∆F i,k and ∆F i,r form the elements of similarity matrix S with dimension N × R × K.
As shown in Figure 3, the 1×1 convolutional operators φ(·) and ψ(·) (described as "Conv") map the edge vectors into high dimensional feature space as, where C 1 and C 2 are in different number of dimensions. The correlations among edge vectors are attained via a softmax function as, where w k normalized by the softmax function f (·) encodes the significance of edge vectors to the upsampled point p r by computing the local correlations, as demonstrated in different color of arrows in Figure 2 (c).
To endow all possible neighboring connectivity from the edge vectors for upsampling, the R anchor points are selected randomly from K neighbor points in each iteration. Although R is smaller than K, the random selection guarantees the overall information in the local neighborhood are learned by the network during iteration. The number of generated points can be set as R times of the original points in the inference stage. As a result, the dimension of the similarity matrix N × R × K depends on the local selection only, which decouples with the network architecture. The upsampling rate R is an arbitrary positive integer smaller than K. Furthermore, the local feature l mapped by convolution ψ(·) based on the edge vector ∆F i,r is max-pooled and tiled up as l to preserve rich local geometric patterns, which encourages new points describing sharp regions and areas with fine-grained details better.
By obtaining the similarity matrix S, the correlations among edge vectors can be considered as the coefficients w k of point based affine combinations, The edge vector based affine combinations of local neighborhood approximate the underlying surface across the target object. Theoretically, the approximation error can be accumulated across the curved surface iteratively. Referring to the linear approximation theorem [26], the error can be expressed explicitly as a high-order term. Based on this, we derive the approximation error of the proposed edge vector based affine combination as a second-order term of Taylor's Expansion. The error estimation encourages the datadriven network converging under such an approximation. The mathematical reasoning is elaborated below. Assume that the vicinity N K (p i ) is local smoothness at point p i . According to the implicit function theorem [11], the vicinity satisfies f (p i,k ) = 0, ∀p i,k ∈ N K (p i ), where f (·) is a smooth implicit function. If the partial derivative ∂f ∂p z exists, the local curved surface can be expressed explicitly by a height function F : R 2 → R : p z = F (p x , p y ). Theoretically, given p x r and p y r , p z r on the curved surface can be obtained via the height function F (·).
However, the analytical solution on a curved surface is too computational expensive to acquire. The corresponding numerical solution can be approximated via Taylor's Expansion at any point p j in local neighborhood as, A linear function F a (·) can be defined as, As a result, Eq. 7 can be expressed as, p z on the curved surface is approximated by the corresponding point on the tangent plane. Considering the involved gradients calculation is complex, referring to [26], any point can be constructed by the existing points p x i,k and p y i,k in the two-dimensional local region as, with non-negative coefficients w k . By substituting Eq. 10 into Eq. 9, p z r on the curved surface is further approximated as, Since p j is a given point in local neighborhood, F p x j , p y j and ∇F p x j , p y j in Eq. 8 can be treated as the constants, thus, p z r can be further approximated as, To this end, the generated points p r residing on the curved surface are approximated by the edge vector based affine combination as, where the edge vectors are constructed by the given sparse points, and the approximation error is restricted within a second-order error term of Taylor's Expansion O(∆ 2 ). Overall, the approximated P R can be written as, with the coefficients decided by Eq. 5.

Coordinate reconstruction
The output of edge vector based affine combinations concatenates with the expanded feature l , yielding a concatenated feature F con for coordinate reconstruction, as demonstrated in the bottom of Figure 3, Under the guidance of concatenated feature F con enriched by the expanded local feature l with more information from sharp regions and areas with fine-grained details, the coordinate error is estimated by a series of MLPs. As explained in Section 3.2, the approximation error can be considered as the second-order term of Taylor's Expansion O(∆ 2 ), which encourages the upsampling network converging. Thereby, the desirable parameters of upsampling network are obtained as long as the supervision signals are fidelity to the ground truth. The coordinate error estimation network E utilizes MLPs under the supervision of ground , to regress the approximated P R towards the final output coordinates of point clouds P R , with the involved loss functions articulated below.
Modified Chamfer Distance (CD) loss in [1,40] measures the similarity between the upsampled point clouds P R and the ground truth Q, which is, where the operator · 2 2 stands for the squared Euclidean norm, and function ξ(d) = d, d ≤ δ, 0, otherwise, filters outliers above a specified threshold. CD loss facilitates the produced points lying on or being closer to the underlying surface.
Uniform loss adopted in [17] are defined as, where U imbalance considers the non-local distribution uniformity by evaluating the deviation of |S j | fromn, The point subsets {S j |j = 1 . . . M } are cropped by a ball query of radius r d in seed points, and the seed points are picked by Farthest Point Sampling (FPS) from P R .n is the expected number of points in S j . U clutter takes account of the local uniformity as, d w,k indicates the distance between each point p w in S j and its nearest neighbor p w,k , andd is the expected pointto-neighbor distance. The proposed PU-EVA network is trained by minimizing the joint loss function in an end-to-end fashion: where θ denotes the parameters in our PU-EVA network, α and β balance the CD loss and the uniform loss, and γ indicates the multiplier of weight decay.

Experiments
In this section, several experiments are conducted to compare our method with state-of-the-art point upsampling methods quantitatively and qualitatively, and various aspects of our model are evaluated.

Experimental setup 4.1.1 Data preparation
We train all these upsampling methods based on a benchmark dataset mentioned in [17] for fair comparison, where 147 objects covering a rich variety of shapes are collected. By following [17], the same 120 objects are used for training, and the remaining are used for testing. For quantitative comparison, the referenced ground truth point distribution Q of 8,192 points on the patch is sampled from original meshes by Poisson disk sampling [6]. In the training stage, the input spare point clouds P are randomly selected from Q on-the-fly. In the testing stage, 6× points are randomly selected from ground truth first, then 4× points are further sampled by FPS [7]. Data augmentation techniques are also applied to rotate, shift and scale data randomly to avoid over-fitting. Throughout the experiments, we train PU-EVA for 300 epochs with a mini batch size 32 on GPU NVIDIA 2080Ti. All models converge before the maximum epochs.

Network configurations
In the dense feature extraction unit, four dense blocks based on EdgeConv are employed. To leverage the features of different layers, skip-connections are applied within and between the dense blocks. Concretely, within the dense block, three convolutional layers of output channels 24 are skipconnected, the output features are passed to all subsequent layers, and a max-pooling layer is employed at the end; between the dense blocks, the features produced by each block are fed to all following blocks, resulting in the output channels of 120, 240, 360, and 480, sequentially.
In the EVA upsampling unit, K and R are set as 12 and 6 to obtain the neighbor points and the anchor points, empirically. C 1 and C 2 are set as 240 and 480, respectively. l is max-pooled into dimension of N × 1 × 480 before tiling by the upsampling rate (R = 6) to expand as l of N × 6 × 480. The output of P R N × 6 × 3 is then concatenated with the expanded l to get features F con with dimension N × 6 × (480 + 3) for coordinates reconstruction.
In the coordinate reconstruction unit, the error estimation module utilizes three fully connect layers (MLPs) of output channels 256, 128, and 64, followed by the last coordinate regression layer of output dimension RN × 3. All the convolutional layers and fully connected layers in the network are followed by the ReLU activation function, except for the last coordinate regression layer.

Evaluation metrics
Four evaluation metrics are employed for quantitative comparison of proximity-to-surface and distribution uniformity. To measure the deviations between upsampled points and ground truth, three commonly used metrics Chamfer Distance (CD), Hausdorff Distance (HD) [5,29], and point-tosurface distance (P2F) are adopted to evaluate the upsampling performance.
For L CD , δ in function ξ is set as 100. For L uni , we first use FPS to pick M seed points in P R and avails a ball query of radius r d to crop each seed for point subset {S j | j = 1 . . . M } to evaluate P R during training. M is chosen as 1,000, and the actual mesh of testing model is used to find S j geodesically instead of cropping S j by ball   query. According to r d = √ p, p is set as 0.4%, 0.6%, 0.8%, 1.0%, and 1.2%, respectively. α, β and γ are set as 150, 10, and 1 empirically. In the implementation, All these metrics are compared over the whole point clouds, and the smaller values indicate the better upsampling quality. Table 1 summarizes quantitative comparison of the proposed PU-EVA and other state-of-the-arts, i.e., EAR [13], PU-Net [40], 3PU [40] and PU-GAN [17], in terms of proximity-to-surface. The comparison is based on 4× upsampling, various input resolutions are evaluated, containing sparse points (256), medium points (2,048), and dense  points (4,096), respectively. PU-EVA achieves the best performance with the lowest deviations from surface consistently, which means points generated from our method are closer to the ground truth. Besides, the upsampling rates of PU-Net [40] and PU-GAN [17] are tangled with the network architectures, with features expanded by replication and rearrangement, neglecting the complex geometric information contained in the latent object surface. Although 3PU [40] shows a competitive capability to deal with flexible upsampling rates, the training process is complicated and more subsets are required for a higher upsampling rate, which is required to be in powers of 2. Table 2 reports quantitative comparison of points distribution uniformity for different p. We compare with optimization based EAR [13] and three deep learning based   methods, i.e., PU-Net [40], 3PU [40] and PU-GAN [17]. The uniformity of our results stays the lowest for all different p, indicating that PU-EVA obtains the best distribution uniformity compared to state-of-the-arts over varying scales. Furthermore, the performance of EAR [13] heavily depends on normal values and parameter tuning.

Qualitative results
The visual comparison of point clouds upsampling and surface reconstruction (using [15]) is shown in Figure 4, in which (a) is 2,048 random input points, (b) is the ground truth points uniformly-sampled from the original meshes of testing models, (c-f) are state-of-the-art methods PU- Net [40], 3PU [40] and PU-GAN [17], and (d) is our PU-EVA. The expanded features of PU-Net [40] are too similar to the inputs, which affects the upsampling quality, as shown in Figure 4 (c). Comparing with (c-e), the proposed PU-EVA produces more uniform point clouds with less noise. According to the blown-up views of upsampled results, PU-EVA renders fine-grained details better, e.g. ox's ear (top) and statue's leg (bottom). The reconstructed surfaces are smoother with less wrinkles or bulges while maintain the complex structures of the original shape. Figure 5 illustrates the upsampling results of the proposed PU-EVA with various upsampling rate, in which (a) is 2,048 random input points, (b) is 8,192 ground truth points, (c-f) are the upsampling results of R = 2, R = 6, R = 7, and R = 8, respectively. Note that all the upsampling results are obtained in one-time training with R = 4, and the upsampling results of rates bigger than the training rate still create point clouds fidelity to the ground truth. The proposed PU-EVA interpolates new points based on edge vectors to decouple the upsampling rate with the network architecture, making it to be a flexible-scale upsampling method.

Ablation study
To justify the approximation error is within the secondorder term of Taylor's Expansion, the performances of PU-EVA with and without it are compared. The comparison is based on 4× upsampling rate, various input resolutions are evaluated, containing sparse points (256), medium points (2,048), and dense points (4,096), respectively. The quantitative results are shown in Table 4. The upsampling results of PU-EVA with the second-order error of Taylor's Expansion declines both CD and HD, indicating its ability to drive upsampling points approaching the underlying surface. Nevertheless, please note that even without the second-order error term, the network still accomplishes comparable upsampling performance.
To explore the efficacy of the proposed EVA upsampling unit, we conduct ablation study to compare with different upsampling units. Specifically, direct point feature duplication upsampling, and the best upsampling unit in PU-GCN [24], named NodeShuffle, are adopted for com-parison. The direct point feature duplication follows the network architecture of the Feature Expansion module in PU-Net [42], while keeps rest of network the same as PU-EVA. Table 5 summarizes quantitative comparison in terms of surface deviations. According to all three metrics, the proposed EVA upsampling unit achieves the best performance with the lowest deviation from surface consistently across the input point resolutions, convincing our upsampling unit encourages points to approximate the underlying surface better. Besides, we visualize the upsampling results of EVA upsampling and NodeShuffle in [24]. As shown in the blown-up views in Figure 8, EVA upsampling unit achieves better upsampling results in term of fine-grained details.

Robustness test
Robustness against varying levels of input noise. We evaluate the robustness of proposed PU-EVA by comparing with the state-of-the-art method, PU-GAN [17], against varying levels of input noise. Figure 6 and Table 3  Compared with PU-GAN [17] upsampled point clouds, the proposed PU-EVA generates points approximating surfaces better, especially in the cases with heavier noise contamination. Furthermore, with the additive Gaussian noise levels escalating, the proposed PU-EVA shows the robustness of the upsampling result.
Robustness against varying sizes of input. Figure 7 illustrates the upsampling results with respect to varying sizes of input. We sample four sets of test samples, as shown in the upper row, which are 4,096, 2,048, 1,024, and 512 points, respectively. The bottom row shows the corresponding 4× upsampled outputs. We can witness that even for the sparsest input points in the rightmost column, the proposed PU-EVA acquires desirable performance.

Real-scanned LiDAR results
The upsampling results of PU-EVA on LiDAR-scanned street scenes from Kitti [8] is provided in Figure 9. Visualization results show that the proposed PU-EVA recovers the sparse and non-uniform input to obtain sharper object shapes of pedestrian and cyclist, etc.

Failure case
Although our method handles the fine-grained details well, such as the ox's ear and the statue's leg shown in Figure 4, there are still some very challenging cases making the upsampled results fail to approximate the complex geometries accurately. The blown-up views of Figure 10 visualize details of the failure case, the possible explanation is the edge vector based affine combination method tends to over fill the local neighborhood, with the characteristics inherited from the intrinsic mechanism.

Conclusion
This work is motivated to embed enriched geometric information of the underlying surface for point clouds upsampling. To this end, we first construct a similarity matrix to encode the correlations of edge vectors in local neighborhood, and propose PU-EVA to implement the significance of edge vectors for upsampling. By analyzing the linear approximation theorem, we identify the error of the edge vector based approximation are under control and verify the feasibility of the proposed network PU-EVA. Qualitative and quantitative evaluations demonstrate that the proposed PU-EVA outperforms the state-of-the-arts by generating smoother and more uniform dense point clouds maintaining more fine-grained details. In future research, we are interested in incorporating the upsampling results to bolster the performance of downstream works.