PaperlayerView exact revision on arXiv

Source-linked AI summary

3D Point Cloud Denoising using Graph Laplacian Regularization of a Low Dimensional Manifold Model

Jin Zeng, Gene Cheung, Michael Ng, Jiahao Pang, Cheng Yang

arXiv:1803.07252v2cs.CV

TL;DR

Noisy acquisition makes 3D point-cloud denoising necessary, while extending low-dimensional manifold methods from ordered image patches to unstructured surface patches is difficult. The paper addresses this with a graph Laplacian regularizer, noise-robust patch similarity, and collaborative patch denoising. Experiments report better objective performance and structural-detail preservation than existing schemes, with GLR offering the best performance despite relatively high complexity.

  • Problem

    3D point clouds are inherently noisy, and image-based low-dimensional manifold dimension computation does not directly apply to unstructured surface patches.

  • Method

    The method collaboratively denoises self-similar surface patches using a low-dimensional manifold prior approximated by a patch-based graph Laplacian regularizer.

  • Results

    The proposal outperforms existing schemes and preserves structural details better, while GLR provides the best performance despite relatively high complexity.

  • Takeaways & Limitations

    Graph Laplacian regularization enables low-dimensional manifold denoising for discrete point-cloud patches while preserving visually salient structure.

Abstract

from arXiv · show

3D point cloud - a new signal representation of volumetric objects - is a discrete collection of triples marking exterior object surface locations in 3D space. Conventional imperfect acquisition processes of 3D point cloud - e.g., stereo-matching from multiple viewpoint images or depth data acquired directly from active light sensors - imply non-negligible noise in the data. In this paper, we adopt a previously proposed low-dimensional manifold model for the surface patches in the point cloud and seek self-similar patches to denoise them simultaneously using the patch manifold prior. Due to discrete observations of the patches on the manifold, we approximate the manifold dimension computation defined in the continuous domain with a patch-based graph Laplacian regularizer and propose a new discrete patch distance measure to quantify the similarity between two same-sized surface patches for graph construction that is robust to noise. We show that our graph Laplacian regularizer has a natural graph spectral interpretation, and has desirable numerical stability properties via eigenanalysis. Extensive simulation results show that our proposed denoising scheme can outperform state-of-the-art methods in objective metrics and can better preserve visually salient structural features like edges.

I. INTRODUCTION

3D point clouds are noisy, and existing denoising methods face trade-offs between smoothing, feature preservation, and computational cost. The paper extends a low-dimensional manifold prior to unstructured surface patches using graph Laplacian regularization.

  • 3D point clouds acquired from depth sensors, scanners, or multiview stereo are inherently noisy.
  • MLS- and LOP-based methods are often criticized for over-smoothing, while sparsity-based methods can over-smooth or over-sharpen at high noise levels.
  • Non-local methods better preserve fine shape features under high noise, but existing approaches can be computationally impractical.
  • The low-dimensional manifold model treats similar patches as samples from a low-dimensional manifold, but extending it from images to point clouds is non-trivial.
  • The proposed method uses graph Laplacian regularization to avoid explicit manifold coordinate functions and reduce the iteration burden caused by asymmetric systems.
  • An efficient noise-robust patch similarity measure supports graph construction, while the method provides graph spectral interpretation and numerical stability analysis.
  • The proposed scheme outperforms state-of-the-art methods in objective metrics and better preserves salient features such as edges.

A. Surface Patch

The paper represents a point cloud through translated local surface patches assumed to lie on a low-dimensional manifold. It formulates denoising by minimizing manifold dimension, then approximates the continuous computation with a graph Laplacian regularizer for discrete observations.

  • Surface Patch: Patch centers are selected from the point cloud, and the union of patches is required to cover the entire point cloud.
  • Surface Patch: A surface patch is the set of k nearest neighbors of a selected center point under Euclidean distance.
  • Surface Patch: Each patch contains k points in R^3, and translated coordinates place its center at the origin for similarity evaluation.
  • Patch Manifold: The patch manifold is assumed to be a low-dimensional smooth manifold embedded in R^(3k).
  • Patch Manifold: The LDMM prior favors solutions whose patches minimize patch-manifold dimension, balanced against a fidelity term in a MAP objective.
  • Patch Manifold: Manifold dimension varies with patch geometry: planar patches have lower dimension than patches containing corners.
  • Manifold Dimension Computation: Continuous dimension computation uses manifold coordinate functions and their gradients, but the observed patches are discrete and finite.
  • Manifold Dimension Computation: PIM requires globally ordered patch coordinates, which surface patches lack because point clouds are unstructured.

B. Dimension Discretization with GLR

The paper constructs a patch graph and uses its combinatorial graph Laplacian to discretize the continuous manifold-dimension regularizer. Under sampling and neighborhood conditions, the discrete regularizer converges to the continuous functional, especially when the manifold dimension is low.

  • Graph construction: The method constructs a graph whose vertices are observed surface patches and whose edges connect patches using weighted patch distances.The graph is an r-neighborhood graph with r = ϵC_r and normalization based on patch degrees.
  • Graph Laplacian regularizer: The symmetric adjacency matrix A and degree matrix D define the combinatorial Laplacian L = D − A.The graph weights populate A, while D contains the corresponding weighted degrees.
  • Graph Laplacian regularizer: Sampling manifold coordinate functions at the patches yields vectors α_i, whose quadratic forms α_i^⊤Lα_i define the graph Laplacian regularizer.This regularizer replaces the continuous gradient-based functional with a graph-based quantity.
  • Convergence: As the number of samples increases and the neighborhood shrinks, the graph regularizer approaches its continuous limit.The theorem requires conditions on ϵ, M, and the coordinate functions; low manifold dimension supports accurate approximation in high-dimensional embeddings.
  • Convergence: The manifold dimension can therefore be approximated from coordinate functions and the constructed graph Laplacian.The theorem is specifically derived for the combinatorial Laplacian, not the normalized Laplacian.

C. From Global Coordinate Ordering to Local Correspondence

The paper removes the need for globally ordered patch coordinates by reformulating the regularizer through local correspondences between connected patches. This makes the manifold-dimension computation depend directly on pairwise patch geometry and graph weights.

  • Global coordinate ordering: The original graph construction requires globally ordered patch coordinates so that the coordinate functions and patch similarities can be defined.This ordering requirement is identified as a remaining obstacle after the initial graph-based approximation.
  • Local correspondence: The regularization term can instead be computed from local pairwise correspondences between connected patches.The reformulation avoids relying on a global ordering of all patches.
  • Local correspondence: The modified manifold-dimension formula eliminates the coordinate functions α_i from the graph Laplacian regularizer.Because the edge weights also depend on the patch distance d_mn, the dimension can be computed once local correspondences determine d_mn.
  • Local correspondence: For each connected patch pair, corresponding points form a subgraph whose weighted Laplacian captures the pairwise geometric contribution.The subgraph is built from concatenated patch coordinates and local point correspondences, then pair contributions are summed into the final regularizer.
  • Local correspondence: The resulting construction uses patch-pair geometry rather than a global coordinate ordering to obtain the overall point-domain graph Laplacian.The formulation operates on the 3D coordinates of the connected patch pairs.

D. Objective Formulation with GLR Prior

The GLR prior is incorporated into a denoising objective by measuring self-similarity between centered surface patches through continuous-surface distances. The distance uses local reference planes and alternating surface normals to define a symmetric patch comparison.

  • D. Objective Formulation with GLR Prior: The objective is reformulated with a graph-Laplacian prior built from patch-pair contributions.The patch-domain terms combine as tr(P^⊤L_pP), linking the prior to the denoised patch coordinates.
  • D. Objective Formulation with GLR Prior: The denoised patch matrix P is linked to the point samples U through a sampling matrix S and a centering matrix C.S selects k-point patches from the point cloud, while C centers the extracted patches before optimization.
  • V. ALGORITHM DEVELOPMENT: The algorithm develops a patch distance measure, an implementation procedure, and analyses of numerical stability and efficient solution under GLR.The section frames these components as the remaining steps for constructing and solving the denoising objective.
  • A. Patch Distance Measure: For continuous surfaces, patch distance is defined by integrating surface separation over a local neighborhood around the patch center.The comparison is based on interpolated surfaces rather than direct pointwise Euclidean matching.
  • 1) Distance Measure in Continuous Domain:: Each patch is represented relative to a reference plane tangent at its center and perpendicular to that patch’s surface normal.The resulting function gives the perpendicular distance from a reference-plane point to the corresponding surface.
  • 1) Distance Measure in Continuous Domain:: Because centered patches share an origin but generally have different normals, the two surface-distance functions are defined on corresponding local neighborhoods.Patch centers coincide after centering, while their surface normals may differ.
  • 1) Distance Measure in Continuous Domain:: The patch distance uses local neighborhoods and alternates the reference plane between the two patch normals.The reference-plane choice changes the distance, so both orientations are used in the comparison.

2) Distance Measure with Discrete Point Observation:

The method measures similarity between discrete surface patches by matching points through projections onto reference planes rather than relying only on direct point positions. It uses PCA-based surface normals, nearest-neighbor correspondence, and symmetric directional distances to construct the final patch distance.

  • The distance from patch m to patch n is computed by projecting points onto the plane perpendicular to patch m’s normal and matching corresponding projected locations.
  • PCA estimates each patch’s surface normal as the covariance matrix eigenvector associated with its smallest eigenvalue.
  • When exact projected correspondences are absent, the method replaces them with the nearest point according to projection distance.
  • The reverse directional distance uses patch n’s reference plane and matches its projected points to the closest projections in patch m.
  • The final patch distance combines the two directional distances into a symmetric measure.

3) Planar Interpolation:

The planar interpolation procedure extends projection-based patch correspondence when nearest-neighbor replacement is insufficient. It limits graph construction to nearby patches and uses these correspondences to build the point-domain graph Laplacian.

  • Nearest-neighbor replacement is used below threshold τ, while larger separations trigger planar interpolation.
  • For interpolation, three nearby points form a plane and the target point is projected along the normal vector onto that plane.
  • Projection-based correspondence is more noise-robust than position-based modified Hausdorff matching because it connects points along the underlying planar structure.
  • Patch pairs connect corresponding points using nearest projected locations, with interpolation weights assigned from distances to the three plane-defining points.
  • The search is restricted to the K-nearest patch centers, after which local correspondences generate the point-domain graph Laplacian Lp.
  • Algorithm 1 alternates patch sampling, neighborhood formation, patch-graph connections, point correspondences, and Laplacian construction from noisy input toward a denoised output.

C. Denoising Algorithm

GLR approximately solves its non-convex objective by alternating between updating the patch graph Laplacian and optimizing the point coordinates. For fixed graph structure, the solution has a graph-spectral interpretation as coordinate-wise low-pass filtering.

  • Because Lp depends on the patches, the optimization is non-convex and is solved by alternating updates of Lp and the denoised point cloud U.
  • For fixed Lp, the x-, y-, and z-coordinates are optimized separately through linear systems, defining the GLR algorithm.
  • The coordinate-wise optimization assumes the union of all patches covers the point cloud and uses kM > N.
  • The solution uses an eigen-decomposition of L + µI, whose eigenvectors form the graph Fourier basis and whose eigenvalues represent graph frequencies.
  • The inverse spectral weights 1/(λ_i^µ + µ) attenuate higher graph frequencies more strongly than lower frequencies.
  • Thus, GLR denoising can be interpreted as graph spectral low-pass filtering of the point-cloud coordinates.

E. Numerical Stability via Eigen-Analysis

Eigen-analysis bounds the graph system’s spectrum and condition number, supporting stable solution of the GLR linear equations when graph degrees are sufficiently small. The section also outlines computational complexity and the evaluation setup.

  • E. Numerical Stability via Eigen-Analysis: With edge weights bounded by 1, Gershgorin analysis bounds the largest eigenvalue of Lp by 2ρmax.
  • E. Numerical Stability via Eigen-Analysis: Eigenvalue interlacing and the µI shift ensure that L + µI is positive definite with smallest eigenvalue at least µ.
  • E. Numerical Stability via Eigen-Analysis: The condition-number bound implies a stable linear system for sufficiently small ρmax, solvable efficiently with preconditioned conjugate gradient methods.
  • Complexity and Evaluation: The algorithm’s complexity is governed by patch-based graph construction and iterative solution of the coordinate linear systems.
  • Complexity and Evaluation: Complexity can be reduced by adjusting patch-center sampling density, patch-graph neighborhood size, and patch size.
  • Complexity and Evaluation: The evaluation compares GLR with APSS, RIMLS, AWLOP, NLD, MRPCA, and LR using MSE, SNR, and MCD metrics.

B. Parameter Tuning

Parameter tuning balances denoising quality against runtime by selecting the search-window and patch sizes, then evaluates GLR against competing methods on eight models. GLR achieves the strongest average objective and visual results across tested noise levels, while preserving structural features.

  • Parameter selection: K = 16 balances performance and runtime because larger search ranges improve results but converge beyond K = 16.Larger K connects patches more often, but runtime increases.
  • Parameter selection: k = 30 provides the best results because smaller patches miss salient features, whereas larger patches increase manifold dimension.The selected patch size also improves edge-aware similarity estimation.
  • Objective comparison: GLR achieves the best average MSE, SNR, and MCD at every tested noise level.Against the second-best scheme, GLR gains 0.009, 0.008, and 0.009 MSE for σ = 0.02, 0.03, and 0.04, respectively.
  • Visual comparison: GLR preserves planes, folds, and corners without over-smoothing or generating extra features in the visual comparisons.The iterative result converges quickly, and the recovered structures retain sharp edges.
  • Visual comparison: Local and sparsity-based competitors show characteristic failures, including over-smoothing, residual noise, uneven planes, or extra surfaces.APSS and RIMLS over-smooth, AWLOP retains noisy features, and MRPCA can generate extra surface.

C. Generalization to ShapeNetCore Dataset

Evaluation on 100 ShapeNetCore models tests whether parameters learned on eight earlier models generalize across object categories and noise levels. GLR provides the best quantitative and visual results, preserving salient rifle features while avoiding LR’s over-smoothing.

  • Dataset and protocol: The ShapeNetCore evaluation uses 100 models from 10 categories, with approximately 30,000 sampled points per model.Gaussian noise is added at σ = 0.02, 0.03, and 0.04.
  • Quantitative results: GLR provides the best MSE, SNR, and MCD results on ShapeNetCore, while patch-based LR ranks second.The same GLR parameter setting learned previously is used for this dataset.
  • Visual results: GLR and LR best preserve the rifle shape under high noise, but LR over-smooths and loses fine details that GLR retains.The comparison supports the effectiveness of patch-similarity-based filtering.
  • Complexity: GLR has relatively high computational complexity but provides the best denoising performance, making it favorable when accuracy requirements are high.APSS, RIMLS, and NLD have the lowest complexity, while MRPCA and GLR have similar complexity.
  • Complexity: Runtime comparisons are not directly suitable for complexity ranking because the methods use different programming languages.The authors report that NLD takes more than ten times APSS’s runtime despite similar complexity.

APPENDIX A

Appendix A establishes convergence of the graph-based quantity under manifold, density, smoothness, and weighting assumptions. It identifies the quantity with a weighted Laplace–Beltrami operator and obtains point-wise convergence by weakening uniform convergence.

  • The analysis assumes a Riemannian manifold with boundary, vertex density h(p), κ-Hölder functions α_i, κ ≥ 3, and a specified graph-weight parameter.
  • S∆(α_i) is induced by the 2(1−γ)-th weighted Laplace–Beltrami operator on M.
  • Under uniformly distributed vertices, the normalization uses the manifold volume |M|.
  • The implementation sets γ = 0.5, following the referenced setting, and thereby obtains the corresponding specialized form of S∆(α_i).
  • The convergence in (11) follows by weakening the uniform convergence in (42) to point-wise convergence.
Loading 1803.07252v2…