PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Resampling of 3D Point Clouds via Graphs

Siheng Chen, Dong Tian, Chen Feng, Anthony Vetro, Jelena Kovačević

arXiv:1702.06397v1cs.CV

TL;DR

Large-scale point clouds make storage and downstream processing costly, while uniform resampling may not preserve application-specific information. The paper develops graph-based randomized resampling that optimizes feature reconstruction and evaluates it across visualization, registration, and shape modeling. The reported applications validate the methods’ effectiveness and efficiency, with geometric invariance guaranteed by the framework.

  • Problem

    Large point clouds make storage and subsequent processing inefficient, while resampling must preserve application-dependent features such as contours and key points.

  • Method

    The paper models point clouds with graphs, defines feature-based reconstruction error, derives an optimal randomized sampling distribution, and instantiates it with graph filters.

  • Results

    The proposed methods validate their effectiveness and efficiency in large-scale visualization, accurate registration, and robust shape modeling.

  • Takeaways & Limitations

    Application-dependent graph-filter resampling can reduce point-cloud scale while preserving targeted information for visualization, registration, and surface reconstruction.

Abstract

from arXiv · show

To reduce cost in storing, processing and visualizing a large-scale point cloud, we consider a randomized resampling strategy to select a representative subset of points while preserving application-dependent features. The proposed strategy is based on graphs, which can represent underlying surfaces and lend themselves well to efficient computation. We use a general feature-extraction operator to represent application-dependent features and propose a general reconstruction error to evaluate the quality of resampling. We obtain a general form of optimal resampling distribution by minimizing the reconstruction error. The proposed optimal resampling distribution is guaranteed to be shift, rotation and scale-invariant in the 3D space. We next specify the feature-extraction operator to be a graph filter and study specific resampling strategies based on all-pass, low-pass, high-pass graph filtering and graph filter banks. We finally apply the proposed methods to three applications: large-scale visualization, accurate registration and robust shape modeling. The empirical performance validates the effectiveness and efficiency of the proposed resampling methods.

I. INTRODUCTION

The paper frames large-scale point-cloud resampling as an application-dependent signal-processing problem, replacing heuristic uniform selection with graph-based randomized sampling. Its framework targets cheaper downstream processing while preserving selected features.

  • Motivation: Large point clouds create storage and processing challenges, motivating representative subset selection for tasks such as registration and contour detection.The paper notes that scans may contain billions of points and that real-time systems can generate millions per second.
  • Proposed framework: The proposed randomized strategy samples points from a non-uniform distribution designed to preserve application-dependent information while reducing computation.Graphs capture local and global point-cloud structure, while randomized sampling avoids costly sequential nonconvex optimization.
  • Proposed framework: A general feature-extraction framework quantifies reconstruction error, derives its exact mean square error, and obtains an optimal resampling distribution.The resulting distribution is guaranteed to be shift-, rotation-, and scale-invariant.
  • Graph-filter strategies: Graph filtering instantiates the framework through all-pass, low-pass, and high-pass strategies, plus graph filter banks for feature enhancement.The paper studies these strategies on simulated and real data.
  • Applications: Applications cover large-scale visualization, accurate registration, and robust shape modeling, with reported effectiveness and efficiency across the three tasks.High-pass sampling highlights contours and extracts registration key points, while low-pass sampling supports noise-robust surface reconstruction.
  • Contributions: The paper contributes a theoretical resampling framework with exact error analysis, an optimal distribution, graph-filter feature extraction, and empirical studies.It positions resampling as a theoretical signal-processing problem rather than a purely heuristic preprocessing step.

B. Graph Signal Processing for Point Clouds

The paper represents point clouds as graphs whose nodes carry coordinate or attribute signals, then applies graph signal-processing operations to capture geometry and frequency structure.

  • Graph representation: General graphs provide flexible point-cloud representations because they encode local geometry without the connectivity restrictions of polygon meshes.The resulting graph is intended as a discrete representation of the underlying surface and can be constructed efficiently with tree data structures.
  • Graph construction: An adjacency matrix connects nearby points when their distance is below a threshold, with edge weights determined by point similarity.The weighted degree reflects local point density.
  • Graph signals: Point-cloud attributes, including coordinates, colors, and textures, become graph signals indexed by graph nodes.The paper distinguishes 3D coordinates from other attributes while treating both as signal data.
  • Graph filtering: Graph filtering maps an input graph signal to an output signal through a graph shift operator and polynomial filter.The filter output is y = h(A)s, where coefficients control powers of the shift operator.
  • Graph frequencies: Graph Fourier analysis orders eigenvectors by graph frequency, from lowest variation to highest variation.The graph Fourier basis expands signals into frequency components that can be recombined by the inverse transform.

III. RESAMPLING BASED ON FEATURE EXTRACTION

The paper formulates feature-preserving resampling by measuring reconstruction loss after random sampling and optimizing the sampling distribution. Normalization and worst-case rotation handling provide geometric invariance.

  • Feature-extraction formulation: A feature-extraction operator maps a point cloud to application-specific features such as edges, key points, and flatness.The abstract operator is later implemented with graph filters.
  • Reconstruction error: The evaluation metric measures feature information lost when sampled features are reconstructed using a simple interpolation operator.Lower reconstruction error indicates that resampling preserves features more closely.
  • Optimization: The sampling distribution is optimized by minimizing the expected reconstruction error over independently drawn samples.The framework derives an exact mean square error for this objective.
  • Geometric invariance: For invariant feature operators, the evaluation metric and resulting resampling strategy remain unchanged under shifts, rotations, and scaling.The paper explicitly connects feature-operator invariance to resampling-strategy invariance.
  • Geometric invariance: Recentering coordinates and normalizing their magnitude address shift and scale variance before resampling.The normalization constant controls the trade-off between coordinate and other-attribute contributions.
  • Geometric invariance: For rotation-variant operators, a worst-case reconstruction metric over admissible coordinate rotations yields a rotation-invariant strategy.The coordinate spectral norm is constrained because rotations preserve it.

B. Optimal Resampling Distribution

The optimal sampling distribution assigns higher probability to points whose extracted features have larger magnitude. For rotation-variant linear operators, feature magnitude combines coordinate and other-attribute contributions.

  • Rotation-invariant operators: For rotation-invariant feature extraction, the optimal resampling distribution is proportional to each point’s feature magnitude.Points with larger feature responses receive higher selection probability.
  • Rotation-variant operators: For rotation-variant linear feature extraction, the optimal distribution is likewise proportional to feature magnitude under the normalized coordinate scale.The feature contribution comes from both 3D coordinates and other attributes.

IV. RESAMPLING BASED ON GRAPH FILTERING

The paper designs graph filters in vertex or spectral domains to extract features for point-cloud resampling. Filter coefficients control local averaging across graph neighborhoods and determine frequency-selective responses.

  • Graph-filter design: Graph filters extract point-cloud features by applying a linear operator to graph signals.The paper derives optimal resampling distributions by substituting graph-filter feature operators into the general framework.
  • Invariance: Graph-filter feature operators are scale-variant because graph filtering is linear, while shift and rotation behavior depends on the graph shift operator and coefficients.The paper notes that coordinate normalization can address scale variation.
  • Graph-filter design: In the vertex domain, each graph-filter output averages attributes from points within L hops.The coefficient h_ℓ specifies the contribution from neighbors ℓ hops away.
  • Graph-filter design: In the spectral domain, filter coefficients fit a desired graph-spectrum distribution across graph frequencies.The graph Fourier basis and eigenvalues define the frequency-domain response.

A. All-pass Graph Filtering

All-pass filtering preserves the original point attributes, yielding uniform resampling when overall geometry is the target. High-pass filtering instead measures local geometric innovation, enabling contour-sensitive sampling that is invariant under the intended transformations.

  • All-pass filtering: With all-pass filtering, h(A)=I and the extracted features are the original point attributes.This setting assumes the point cloud is trustworthy, uniformly sampled, and noise-free.
  • All-pass filtering: Uniform resampling is optimal for preserving overall geometry when only 3D coordinates are retained under all-pass filtering.The feature-extraction matrix is the identity and every point has the same resampling probability.
  • High-pass filtering: High-pass graph filtering defines local variation from how poorly a point’s coordinates are approximated by its neighbors.Large local variation indicates that a point breaks the neighboring trend and may be a contour point.
  • Invariance: Using a transition matrix as the graph shift operator makes the proposed local variation shift-invariant, while the general local variation is rotation-invariant but may be shift-variant.The transition matrix satisfies A1=1, supporting shift invariance without recentering.
  • High-pass filtering: The Haar-like high-pass filter attenuates low graph frequencies and amplifies high graph frequencies.Its response is h_HH(λ_i)=1−λ_i.
  • Contour detection: The proposed local variation satisfies the paper’s simple geometric contour examples and detects contours more effectively than pairwise-difference variation.Pairwise differences assign equal variation to points across cube faces, whereas Haar-like high-pass variation identifies contour structure in simulated and real objects.

C. Low-pass Graph Filtering

Low-pass graph filtering captures the rough shape of a point cloud while reducing sampling noise. This is motivated by the smoothness of neighboring 3D coordinates on the constructed graph.

  • Low-pass graph filtering captures the rough shape of a point cloud and reduces sampling noise during resampling.The paper relates this behavior to classical low-pass filtering of smooth signals.
  • The 3D coordinates are naturally smooth on the graph because adjacent points have similar spatial coordinates.
  • Low-pass resampling is designed for noisy point clouds whose application-dependent information is associated with their broad geometric structure.

1) Ideal low-pass graph filter:

The ideal low-pass graph filter projects point-cloud coordinates onto a bandlimited subspace, with larger bandwidths retaining progressively more shape detail. The paper also describes efficient computation and evaluates low-pass resampling for noisy fitness-ball shape modeling.

  • 1) Ideal low-pass graph filter:: An ideal low-pass graph filter removes graph frequencies above bandwidth b while passing lower frequencies unchanged.It projects an input graph signal onto a bandlimited subspace.
  • 1) Ideal low-pass graph filter:: Increasing bandwidth improves the bandlimited approximation of a teapot, from rough structure at 10 frequencies to visible details at 500.The main spectral energy is concentrated in the low-pass band.
  • 1) Ideal low-pass graph filter:: The ideal low-pass strategy uses graph-frequency information represented through the rows of V(b) to determine resampling probabilities.The corresponding computation involves leverage scores based on the truncated eigendecomposition.
  • 1) Ideal low-pass graph filter:: Randomized leverage-score approximation can reduce the stated computational cost from O(Nb^2) to O(Nb log(N)).Graph partitioning into subgraphs is another proposed way to leverage computation.
  • 2) Haar-like low-pass graph filter:: The Haar-like low-pass filter averages each point with neighboring attributes to provide a smooth output.Its response amplifies low frequencies and attenuates high frequencies.
  • 2) Haar-like low-pass graph filter:: Low-pass graph filtering produces robust fitness-ball shape modeling for noisy point clouds compared with noisy and uniformly sampled alternatives.The evaluation compares fitted spheres using radius and center estimates, with relative error defined against ground truth.

D. Graph Filter Banks

Graph filter banks separate a 3D point cloud into subbands, resample each component with a filter-specific strategy, and synthesize a reconstructed surface. The section also reports that high-pass resampling improves sofa registration while using fewer points.

  • Graph filter banks: Filter banks analyze a 3D point cloud in multiple subbands and synthesize its components for surface reconstruction.Different resampling operators preserve different point-cloud components.
  • Graph filter banks: Each subband uses a specific graph filter, with its sample count controlled by the sampling ratio α.The system can use original points or graph-filtered points during synthesis.
  • Graph filter banks: The reconstruction objective creates a rate-distortion tradeoff: more sampled points reduce reconstruction error but require more encoded bits.Fewer points reduce encoding cost while increasing reconstruction error.
  • Accurate registration: The sofa experiment registers overlapping scans with ICP, recovering the overall structure while leaving some detailed mismatch.The sofa cloud contains 1,204,055 points, and the registration task inverts an intentional shift and rotation.
  • Accurate registration: High-pass graph filtering emphasizes contours and key points for efficient registration of large-scale point clouds.The application compares uniform resampling with high-pass graph-filter-based resampling.
  • Accurate registration: High-pass graph-filter-based resampling uses 20-times fewer points and achieves better registration results than using all points.The reported comparison concerns shift and rotation errors as well as registration accuracy.

APPENDIX

The appendix proves the resampling-error results by separating bias and variance and evaluating the variance contributions element by element. It then combines these terms to obtain the stated bound.

  • Proof variants: The appendix also distinguishes nonweighted and reweighted versions of the resampling result.Separate proof passages introduce each version.
  • Proof structure: The proof decomposes the error into bias and variance terms.The first term is identified as bias and the second as variance.
  • Proof structure: The bias term is zero, so the proof focuses on bounding the variance term.The appendix then analyzes each element of the variance expression.
  • Variance bound: The variance analysis evaluates individual cross terms before combining all elements to obtain the stated result.The final combination yields equation (8).

D. Proof of Theorem 3

The proof derives the optimal resampling strategy by formulating a constrained optimization problem, constructing its Lagrangian, and applying stationarity and complementary slackness. It concludes that the optimal sampling probability is proportional to a feature-dependent norm.

  • Optimization derivation: The optimal resampling strategy is obtained by solving a constrained optimization problem.The proof introduces the corresponding Lagrange function.
  • Optimization derivation: Differentiating the Lagrangian with respect to π_i and setting the derivative to zero provides the stationarity condition.The proof then applies complementary slackness.
  • Optimization derivation: Complementary slackness reduces the solution to a proportionality between π_i and the feature-row norm.For the stated case, π_i ∝ ∥f_i(X)∥2.
  • Reweighted formulation: A corresponding derivation is given for the reweighted formulation, using rows of F and F X_o in the optimization.The proof repeats the Lagrangian and stationarity steps for the reweighted case.

F. Proof of Theorem 5

The proof establishes rotational and shift invariance of the local variation used by the resampling strategy. Rotation invariance follows from orthonormality, while shift invariance is analyzed by adding a common translation.

  • Rotational invariance: For a rotated point cloud X R, the proof evaluates the local variation after applying the rotation matrix.The rotation matrix is specified as R ∈ R3×3.
  • Rotational invariance: The rotational calculation uses the fact that every rotation matrix R is orthonormal.This property supplies the equality used in the proof.
  • Shift invariance: For a shifted point cloud X + 1a^T, the proof evaluates the corresponding local variation after adding the common shift a.The shift is represented as a ∈ R3.
Loading 1702.06397v1…