Null-Space Diffusion Sampling for Zero-Shot Point Cloud Completion

1 Introduction

The 3D point cloud is a widely-used 3D representation for various 3D vision tasks including scene understanding and autonomous driving. However, point clouds scanned from the real world are usually suffered unexpected degradation, which significantly causes the performance decrease of downstream applications. Hence, the point cloud completion methods which aim to restore the degraded observations have been widely studied recently. Most existing methods [Yuan et al., 2018; Liu et al., 2020; Pan et al., 2021] tackle this problem in a fully supervised paradigm, i.e., their methods require paired degraded-complete point clouds for training, which heavily restrict their generalization in real-world scenes with various degradation forms.

We attempt to solve the point cloud completion task in a zero-shot manner to overcome the paired data requirement. Our framework is inspired by the success of existing zero-shot works that leverage pre-trained generative models to solve the 2D image inpainting [Lugmayr et al., 2022; Wang et al., 2023c], which is the task related to point cloud completion in the 2D domain. The inpainting task aims at yielding a complete image ˆx from a masked observation y = Axgt, where xgt denotes the ground truth image and A is the linear operation matrix which can be known from the mask. However, directly extending 2D zero-shot inpainting methods to solve the 3D point cloud completion task suffers several crucial challenges: (i) Methods with pre-trained generative models struggle to balance the data consistency and realness, which problem is more severe for 3D point clouds. (ii) A point cloud is an unordered set, i.e., the permutations of the points cause no difference to the represented object geometry. Therefore, the linear operator can not be constructed in advance if the ground truth is unknown.

In this paper, we propose a novel zero-shot framework named Null-Space Diffusion Sampling (NSDS) for solving the point cloud completion task. Instead of adopting wellstudied generative models such as generative adversarial networks (GANs), our framework is implemented based on the emerging diffusion models due to they support explicit operation during the generation process. To address the challenge (i), we introduce the range-null space decomposition technique [Chen and Davies, 2020; Wang et al., 2023c; Wang et al., 2023a; Wang et al., 2023b; Yu et al., 2023] to analytically guarantee the data consistency and only refine the null-space content for generating desired completion results with realness. Combined with the explicit operation property of diffusion models, we dynamically estimate the linear matrix in specific steps during the reverse process to address the challenge (ii). Furthermore, we propose a tolerant loop mechanism to achieve better realness of completion results when facing more complicated degraded situations. Experiments on multiple point cloud completion datasets demonstrate that our zero-shot framework achieves competitive completion performance in various domains, which provides a promising new path for solving the completion task. The main contributions of this work can be summarized as follows:

• We propose a zero-shot point cloud completion framework named Null-Space Diffusion Sampling (NSDS), which generates completion results from degraded observations by only refining the null-space content during the reverse process of a pre-trained diffusion model.
• We propose an effective dynamical matrix estimation approach to overcome the problem that the analytical matrix is unavailable when degraded observation is only obtained in point cloud completion.
• We propose a tolerant loop mechanism to further improve the completion quality in complicated cases.
• Experiments demonstrate that the proposed framework achieves competitive completion performance to existing unsupervised or even supervised methods on multiple point cloud completion datasets, including PCN, GenRe, and our ShapeNet-Split.

2 RelatedWorks

2.1 Point Cloud Completion

Point Cloud Completion aims at predicting the missing part from partial scans. PCN [Yuan et al., 2018] is the pioneer learning-based work that proposes an Encoder-Decoder architecture to complete partial point cloud in a coarse-to-fine manner. Following PCN, several works [Tchapmi et al., 2019; Wen et al., 2020; Huang et al., 2020; Zhang et al., 2020; Xia et al., 2021; Pan et al., 2021; Wang et al., 2022] improve the Encoder-Decoder architecture to achieve better completion performance. To better preserve the geometry information from the partial point cloud, MSN [Liu et al., 2020] adopts Minimum Density Sampling to obtain a subset point cloud and build residual connections. Besides, GRNet [Xie et al., 2020] introduces a volumetric intermediate representation to preserve the structure and context of the input point cloud. Inspired by the great success of vision transformers [Dosovitskiy et al., 2020; Liu et al., 2021], SnowflakeNet [Xiang et al., 2021] and PoinTr [Yu et al., 2021] extend transformer architectures to point cloud completion. More recently, PDR [Lyu et al., 2022] proposes a diffusion-based method using a conditional DDPM to generate a coarse point and a refinement module to obtain the completed point clouds. However, most existing approaches are trained in a fully-supervised manner, which heavily relies on large-scale paired partial-complete point clouds as training data. To address this issue, Pcl2pcl [Chen et al., 2020] first proposes an unpaired point-based method, which trains two separate auto-encoders for reconstructing partial and complete point clouds respectively and maps the partial scans to complete point clouds by a GAN. The subsequent work [Wu et al., 2020] utilizes a conditional GAN to output multiple plausible complete point clouds from a partial scan. Following Pcl2pcl, Cycle4Completion [Wen et al., 2021] captures the bidirectional geometric correspondence between incomplete and complete point clouds to enhance the completion performance. Also, [Cai et al., 2022] learn a unified and structured latent space for unpaired point cloud completion. ShapeInversion [Zhang et al., 2021] applies GAN inversion to complete the partial point cloud which exploits the shape prior learned from a pre-trained GAN. Different from existing methods, we leverage a pre-trained point cloud diffusion model to complete a partial point cloud in a zero-shot manner.

2.2 Point Cloud DiffusionModels

Denoising diffusion models (DDMs) [Ho et al., 2020; Dhariwal and Nichol, 2021] have emerged as powerful image synthesis methods recently, which formulate the generation as a progressive sampling procedure from random Gaussian noises. Several works explore the effectiveness of DDMs in the more challenging 3D domain [Luo and Hu, 2021; Zhou et al., 2021; Zeng et al., 2022] and achieve promising point cloud synthesis performance. By utilizing the pretrained diffusion model as a powerful generative prior, our Null-space Diffusion Sampling framework successfully extends their methods to solve the completion task without requiring any fine-tuning. We note our framework is orthogonal to these works and can be further benefited from the development of point cloud DDMs.

3 Background

3.1 DiffusionModels

We adopt the point cloud diffusion model as the basic generative method, which follows the diffusion process defined in Denoising Diffusion Probabilistic Models (DDPM) [Ho et al., 2020], thus we give a brief review of DDPM here. The DDPM aims to generate a high-quality output x ∼ q(xgt) from a random Gaussian noise xT ∼ N(0, I), where q(xgt) represents the sample distribution in the training dataset and N represents the Gaussian distribution. The DDPM defines a T -step forward process to slowly adds random noises to training samples, and a T -step reverse process to generate desired outputs from random noises.

Concretely, the forward process yields the present state xt from the previous state xt-1:

where xt is the noised sample at time-step t, and βt is the predefined scale factor of noise value. To efficiently calculate xt from the x0, we can rewrite Eq. 1 using the reparameterization trick:

The reverse process aims at yielding the the previous state xt-1 from xt and x0 using the posterior distribution, which can be derived using Eq. 1 and Eq. 2:

where µt(xt, x0) = √ ¯αt-1βt 1-¯αt x0 + √αt(1-¯αt-1) 1-¯αt xt and σ2 t = 1-¯αt-1 1-¯αt βt. Furthermore, µt(xt, x0) can be reparameterized as 1 √αt (xt - βt √1-¯αt ϵt) by applying Eq. 2, where ϵt denotes the unknown noise added to xt. DDPM uses a neural network to predict the noise ϵθ(xt, t) for each time-step t. In the training stage, DDPM randomly selects a training sample x0, a noise ϵ, and a time-step t to optimize the network, and the simplified training objective L can be formulated as:

Finally, high-quality outputs are generated by the trained model from xT ∼ N(0, I) using the following sampling equation progressively:

3.2 Range-Null Space Decomposition

For the linear operator matrix A ∈ Rd×D which describes the degradation process y = Ax between a complete point cloud x ∈ RD×3 and its degradation y ∈ Rd×3 , we can solve the pseudo-inverse A† ∈ RD×d which satisfies AA†A ≡ A. A†A can be seen as the projected operator to decompose x into the range-space part and the null-space part of A:

A†Ax is the range-space part of A because AA†Ax ≡ Ax, and (I - A†A)x is the null-space part of A because A(I-A†A)x ≡ 0. By leveraging such range-null space decomposition, we introduce degraded observations as the constraints into unconditional diffusion generative models to address zero-shot point cloud completion.

4 Method

In this section, we detailed describe our proposed zero-shot point cloud completion framework named Null Space Diffusion Sampling (NSDS), which leverages the range-space decomposition technique to lead unconditional pre-trained point cloud diffusion models to generate desired completion results without any additional fine-tuning.

4.1 Refine Null-Space During Diffusion

The 3D point cloud degradation can be described as a linear process y = Axgt, where y ∈ Rd×3 is the observed degraded point cloud, xgt ∈ RD×3 is our completing target, where d < D, and A ∈ Rd×D is a sub-sampling matrix (consist of 0 or 1) which indicates the linear degraded operation. Considering we want to generate a point cloud x as the completing result, x is expected to conform to two constraints including the Consistency constraint Ax ≡ y and the Realness constraint x ∼ q(xgt), where q(xgt) represents the distribution of ground truth samples.

However, we can analytically construct a solution from x that satisfies the Consistency constraint: x can be decomposed as the range-space part A†Ax and the null-space part

(I -A†A)x as shown in Sec. 3.2. By replacing the rangespace part as A†y, we can directly construct ˆx = A†y+(IA†A)x that satisfies Aˆx ≡ y:

With ensuring the Consistency of ˆx, we resort to the pretrained diffusion model to generate a reasonable point cloud with Realness ˆx ∼ q(xgt) by only refining the null-space part (I - A†A)x.

Given a pre-trained point cloud diffusion model, we start with the state xt in the reverse process of a time-step t. We note that xt is naturally noisy and should not be expected to satisfy Axt ≡ y. Instead of constructing the solution from xt directly, we firstly estimate x0 from xt and the predicted noise ϵθ(xt, t) by using Eq. 2, which is denoted as x0|t:

Compared with noisy xt, x0|t is more relative to our final desired output. Thus we introduce the Consistency constraint to x0|t and the rectified ˆx0|t can be constructed by range-null space decomposition as:

Therefore, xt-1 is sampled according to Eq. 3 by replacing the estimated x0 as our constructed ˆx0|t:

To sum up, we apply range-null space decomposition on the estimated x0|t to construct ˆx0|t that conforms Consistency constraint Aˆx0|t ≡ y for each time-step t (Eq. 7), and only refine the null-space contents (I-A†A)x0|t to progressively generate a harmony output x0 that conforms Realness constraint x0 ∼ q(xgt) assisted by a pre-trained diffusion model, where x0 = ˆx0|1. Different from the regular sampling described in Eq. 5, our null-space sampling iterative applies Eq. 8, Eq. 9 and Eq. 10 to generate completing outputs.

4.2 Dynamic Matrix Estimation

As discussed above, Null-Space Diffusion can solve the zeroshot point cloud completion when knowing the linear operator matrix A in advance. We note that A is independent and easily constructed in many typical image restoration tasks such as inpainting, while A is highly relative to the unknown ground truth xgt in the point cloud completion task. As illustrated in Fig. 3, A is determined by xgt due to point cloud representations are unstructured, i.e., points in a specific cloud are unordered. Concretely, given a point cloud x ∈ RD×3 , which the i-th row presents the 3D coordinate of a point x[i] = (xi, yi, zi). If we swap coordinates of the points x[i] and x[j], the geometry of the object which x represented remains unchanged. Therefore, the analytical A is unavailable when the degraded y is only observed because the point y[i] can be mapped from the unknown j-th row of a uncertain xgt, and all possible ground truth clouds are equivalent.

Due to the analytical A being unavailable, we have to estimate an approximate linear operator matrix A for range-null space decomposition and zero-shot completion. Thanks to the explicit sampling operations in the diffusion models, we can approximately estimate the linear matrix between the observed y and the x0|t. Considering that x0|t is the estimation of x0 at time-step t and is more accurate when t decreases, we adopt a dynamic estimate strategy that continuously adjusts the matrix during the sampling process instead of using a fixed one. Specifically, we propose a simple but effective approach to obtain the linear matrix At∈Rd×D at the timestep t by searching the closest point pairs between y and x0|t:

where 0≤k<D. Therefore, we replace the A in Eq. 9 as our obtained At to construct the rectified ˆx0|t at the time-step t. Compared with using a fixed inaccurate linear matrix, leveraging our dynamically estimated At can effectively decrease the refinement difficulty of the null-space contents during the reverse process and stably generate harmonized results.

4.3 Tolerant Loop for Better Realness

Although the proposed Null-Space Diffusion Sampling framework maintains the Consistency of completion results through the whole reverse process, refining the null-space contents (I - A†t At)x0|t appropriately to generate harmonized output x0 with good Realness is still challenging, especially in complicated degraded cases. Hence we propose a tolerant loop mechanism to improve the Realness of completion results with the Consistency unaffected.

To implement the tolerant loop, three hyper-parameters including the loop start time-step L, the loop count N, and the null-space sampling interval K are designed to enhance the Realness of outputs in different aspects: Firstly, the loop start time-step L shortens the applied range of proposed nullspace sampling to the last L time-steps in the reverse process. This restriction is proposed due to the core calculations in null-space sampling including the construction of rectified ˆx0|t (Eq. 9) and the dynamic estimation of the matrix At (Eq. 11) are both relied on the estimate x0|t, which is more accurate when t is closer to 0. Hence proposed null-space sampling is only applied in the last L time-steps instead of the whole reverse process for the precise construction and estimation. Secondly, the loop count N is proposed to extend the completion process by repeating the last L sampling steps for N times, i.e., xL is the next state of x0 if the loop continues, where xL = √ ¯αLx0 + √1- ¯αLϵ according to the forward diffuse step (Eq. 2). Since the repeatedly forward diffuse steps bring bigger sampling space to the completion process and the null-space samplings adequately leverage the data prior contained in pre-trained diffusion models, the Realness of the completion outputs achieves significant improvement. Finally, the null-space sampling interval K is designed to properly balance the Consistency and Realness of the completion results, where such interval hyper-parameter means our null-space sampling is only applied every K time-steps while the regular sampling (Eq. 5) is adopted otherwise. We give two extreme settings to explain the effect of K. When K = 1, the null-space sampling is applied in every time-steps during the loop and the Consistency constraint is considered strictly. When K > L, the regular sampling is always applied and the pre-trained diffusion model generates outputs with Realness unconditionally. For complicated cases whose

Algorithm 1 Null-Space Diffusion Sampling.

Input: Degraded observation y ∈ Rd×3

Output: Completion result x0 ∈ RD×3 1: xT ∼N(0, I) 2: for t = T, ...,L+1 do 3: ϵ ∼N(0, I) 4: xt-1 = 1 √αt (xt - βt √1-¯αt ϵθ(xt, t)) + σtϵ 5: end for 6: // Tolerant loop 7: for n = 1, ...,N do 8: for t = L, ..., 1 do 9: ϵ ∼ N(0, I) if t > 1, else ϵ = 0 10: if (t - 1)%K == 0 then 11: x0|t = 1 √αt (xt - √1 - ¯αtϵθ(xt, t)) 12: // Dynamic matrix estimation 13: At = 0d×D 14: for i = 1, ..., d do 15: j = argmin k ||y[i] - x0|t[k]||22 16: At[i, j] = 1 17: end for 18: // Null-space sampling 19: ˆx0|t = A†t y + (I - A†t At)x0|t 20: xt-1 = √ ¯αt-1βt 1-¯αt ˆx0|t + √αt(1-¯αt-1) 1-¯αt xt +σtϵ 21: else 22: // Regular sampling 23: xt-1 = 1 √αt (xt - βt √1-¯αt ϵθ(xt, t)) + σtϵ 24: end if 25: end for 26: if n < N then 27: ϵ ∼ N (0, I) 28: xL = √ ¯αLx0 + √1 - ¯αLϵ 29: end if 30: end for 31: return x0

A†t y and (I-A†t At)x0|t is obviously disharmony before the progressive refinement, we can set a proper k to make the reverse process is more tolerant in the aspect of Consistency.

Fig. 2 and Algo. 1 show the overview and the detailed process of the proposed Null-Space Diffusion Sampling framework with the tolerant loop mechanism respectively.

5 Experiments

5.1 Setups

Evaluation Metrics. We evaluate the completion performance by computing the Chamfer Distance (CD) between the predicted completion results and the ground truth point clouds following previous methods [Tchapmi et al., 2019; Pan et al., 2021]. Since CD is sensitive to outliers, we additionally use F1 score which is defined as the harmonic mean between precision and recall following [Chen et al., 2020]. To evaluate the uniformity of the predicted complete point cloud, we use Minimum Matching Distance-Earth Mover's Distance (EMD). To remove the effect of the shape scale, we normalize each point cloud into a unit sphere with radius = 1.

Implementation Details. In all experiments, our NSDS framework adopts the pre-trained Point-Voxel Diffusion (PVD) [Zhou et al., 2021] as the basic diffusion generative model, which is trained on the ShapeNet. Due to the PVD only providing pre-trained models for car, chair, and airplane categories with a resolution of 2048, we conduct all experiments on these three categories and set the resolution of the predicted completion results to 2048. For hyper-parameters assigned in the tolerant loop mechanism, we set the loop count N = 20, the loop start time-step L = 100, and the null-space sampling interval K = 10. We implement all the supervised methods with settings described in [Pan et al., 2021] and utilize the official implementation of the unsupervised Pcl2pcl [Chen et al., 2020] for comparison.

5.2 Point Cloud Completion on ShapeNet

Datasets. To verify the effectiveness of our zero-shot NSDS framework under different degraded situations, we conduct point cloud completion experiments on three datasets derived from ShapeNet [Chang et al., 2015] benchmark with varying forms of degradation. The first dataset is a widely used benchmark PCN [Yuan et al., 2018], which is the subset derived from the ShapeNet dataset. For each category, PCN reserves 150 partial point clouds for testing. The second dataset is provided by GenRe [Zhang et al., 2018]. We select renderings of each shape in ShapeNet from 5 random views and sample 600 points obtained from the provided depth images as the partial inputs. Since most of the point cloud completion methods are trained by paired partial-complete point clouds generated from virtual cameras, we construct a dataset derived from ShapeNet with an unseen degradation form, namely ShapeNet-Split. Concretely, we split the point clouds from x, y, z axis respectively, and randomly remove a quarter or a half part of the points. For each category, we select 1800 degraded point clouds for testing.

Baselines. We compared our NSDS framework with other supervised completion methods including PCN [Yuan et al., 2018], TopNet [Tchapmi et al., 2019], MSN [Liu et al., 2020], ECG [Pan, 2020], CRN [Wang et al., 2020], VRCNet [Pan et al., 2021] and unsupervised completion method Pcl2pcl [Chen et al., 2020].

Quantitative comparison. We report the point cloud completion results of the proposed NSDS framework and other supervised/unsupervised completion methods on the three datasets including PCN, GenRe, and ShapeNet-Split in Tab. 1. For supervised methods, the completion difficulty on GenRe and ShapeNet-Split is obviously higher than PCN, which is caused by the degradation forms in PCN are similar to their training set while the degradation forms in GenRe and ShapeNet-Split are relatively different or unseen. Hence, supervised methods achieve superior performance on all metrics than unsupervised methods including ours. On the contrary, NSDS surprisingly achieves comparable performance to many supervised methods, especially on the F1 score, which indicates that our framework can solve the point cloud completion task in a unified degraded process with ignoring the variation of degradation forms. For unsupervised methods, NSDS consistently outperforms Pcl2pcl in CD/F1 metrics on all datasets by a large margin. We emphasize that NSDS can be easily implemented based on an off-the-shelf pre-trained diffusion model without extra training, thus the competitive experimental results reveal that our framework provides a promising novel path for point cloud completion.

Visual Comparison. We further provide the visual comparison results in Fig. 6 to demonstrate the outstanding property of our framework: the Consistency constraints of our generated completion results are theoretically guaranteed, which is crucial to complete partial inputs in complicated degraded situations. Compared to our framework, these methods tend to generate uniform and symmetric completion outputs due to the full supervision or careful design, resulting in higher metric results, especially on PCN and GenRe datasets. However, their methods consider less to the Consistency constraint between degraded and completion clouds and might generate undesirable results when facing unseen degraded situations.

5.3 Point Cloud Completion on Real-world Scans

We also conduct experiments on real-world scans fromMatterPort3D [Chang et al., 2017] and KITTI [Geiger et al., 2012]. Compared to the virtual scans from ShapeNet, realworld scans suffer more complicated degradation situations. Since the real-world scans have no ground truth provided, we give visual completion results in Fig. 4, which reveal our NSDS framework could complete degraded point clouds with generalization capability.

5.4 Multiple Valid Completion Outputs

Since our NSDS solves point cloud completion by utilizing a pre-trained diffusion generative model, our framework could predict multiple reasonable completion results by changing the initial noise when the degraded observations are extremely incomplete. As shown in Fig. 5, our NSDS framework is able to generate multiple valid outputs that conform to the degraded inputs. However, the metric results are significantly different for various valid completion results, which indicates that our performance might be underestimated.

5.5 Ablation Study

Dynamic Matrix Estimation. We study the effectiveness of the proposed dynamic matrix estimation in this section. As illustrated in Fig. 3, the analytical A is unknown in the 3D point cloud completion task. To demonstrate the necessity of dynamically estimating the approximate At from y and x0|t, we construct a baseline that leverages a fixed, randomly sampled matrix Ar during the reverse process, and the ablation results on PCN dataset are shown in Tab. 2. The completion performance of our framework significantly decreases when adopting the Ar. Compared to our estimated At, the randomly sampled Ar is extremely inaccurate which frequently maps a point xt[i] in the generated cloud to a remote observed point y[j] in the reserve process, leading to severe conflicts between adjacent sampling steps, which obviously injures the Realness of the final outputs.

Tolerant Loop. In this section, we construct ablation experiments to demonstrate the effectiveness of the proposed tolerant loop mechanism by changing the number of loop count N as shown in Tab. 3. When N = 1, the tolerant loop is actually not employed, and the Realness of the outputs are inadequate. With the increase of N, the extended diffusion process brings larger sampling space to generate a well prior, and the extended sampling process refines the null-space content more for generating high-quality results with better Realness. However, the time cost increases correspondingly with the N being larger, and we finally set N = 20 to balance the time cost and the completion performance.

6 Discussion

We propose a novel Null-Space Diffusion Sampling (NSDS) framework employed on pre-trained point cloud diffusion models for solving the point cloud completion task in a zeroshot way. Experimental results demonstrate that our framework can complete the point clouds in various degraded situations. Without requiring the collection of paired degradedcomplete data for any extra training, our method is practical for various downstream applications when only adopting an off-the-shelf point cloud diffusion model. One potential limitation of NSDS is our completion performance is highly determined by the generative capacity of the pre-trained model, and we believe our framework can achieve better results when stronger diffusion models are available.

An interesting direction for future works is to complete the degraded point clouds under various multi-modal constraints, e.g., text descriptions, reference images, or videos for target objects, which has been verified feasible in image domain.

Contribution Statement

Xinhua Cheng and Nan Zhang contribute to this work equally. Jian Zhang is the corresponding author.

Acknowledgements

This work was supported in part by Shenzhen Research Project under Grant JCYJ20220531093215035.