Multi-scale Feature Extraction on Point-sampled Surfaces

Mark Pauly, Richard Keiser, Markus H. GrossComputer Graphics Forum 2003 · DOI

TL;DR

This paper introduces a novel multi-scale approach for automatically detecting and extracting "line-type" features (like edges and ridges) from unstructured point clouds representing 3D surfaces. By analyzing surface variation at different neighborhood sizes, their method becomes robust to noise and can identify features that might be missed by single-scale techniques, paving the way for more intuitive 3D shape analysis and artistic rendering.

What Problem Does This Paper Address?

In computer graphics and related fields, representing 3D objects using only a collection of points (point clouds) is becoming increasingly common, especially with modern scanning technologies. These point clouds lack explicit connectivity or topological information, making it challenging to identify important geometric features like edges, ridges, or boundaries. Traditional feature extraction methods often rely on explicit surface representations (like meshes) or struggle with noisy data. This paper tackles the problem of reliably extracting these crucial "line-type" features directly from raw point clouds, even when the data is noisy or lacks a clear structure, enabling better understanding and visualization of 3D shapes.

Methods

The core of this paper lies in a multi-scale feature extraction pipeline. Here's a breakdown of the key techniques:

  • Multi-scale Surface Variation: Instead of traditional scale-space methods that convolve signals with Gaussian kernels, this approach uses the size of local neighborhoods around each point as a discrete scale parameter. For each point, they compute a covariance matrix of its k-nearest neighbors. The smallest eigenvalue of this matrix, relative to the sum of all eigenvalues, quantifies "surface variation" – essentially, how much the surface bends or curves locally. By analyzing this variation across different neighborhood sizes (scales), they can identify features that are persistent across scales.
  • Hysteresis Thresholding: To select feature points, they employ hysteresis thresholding. This involves using two thresholds: a lower one to discard points with very low variation and an upper one to confidently select feature points. Points falling between these thresholds are used to bridge gaps, ensuring continuity.
  • Minimum Spanning Graph (MSG): After selecting feature points, they construct a Minimum Spanning Graph (MSG) to connect them. The edge costs in this graph balance the feature weights (derived from surface variation) with Euclidean distance, ensuring that connected points are both likely to be features and geometrically close.
  • Pruning and Closing Cycles: The initial MSG often contains short, noisy branches. They use a bottom-up pruning method to remove these artifacts. Additionally, they introduce a mechanism to close cycles in the graph, allowing for the detection of closed feature loops (like boundaries).
  • Active Contour Models (Snakes): To smooth the jagged feature lines obtained from the MSG, they employ "snakes" – energy-minimizing splines. These snakes are guided by internal forces (to maintain smoothness) and external forces (to stay close to the underlying surface variation), providing explicit control over the smoothness and accuracy of the extracted features.
  • Non-photorealistic Rendering: The extracted feature lines are then used to generate artistic line drawings. They use a point-based rendering technique where feature lines are converted into "feature surfels." The splat radii and intensity of these surfels are modulated by the scale and surface variation, creating visually intuitive line drawings.

Datasets

The paper evaluates their method on several publicly available models:

  • Max Planck model (bust)
  • Bunny model
  • Dinosaur head model
  • Dragon model
  • Igea model
  • Cat model

These models represent a range of complexities and sampling densities, including a noisy laser range scan to demonstrate robustness. No new benchmarks are introduced; the focus is on evaluating the method's performance on existing datasets.

Key Insights and Ideas

  • Neighborhood Size as Scale: The most significant insight is using the size of local neighborhoods as a discrete scale parameter for feature analysis. This elegantly sidesteps the complexities of traditional continuous scale-space methods for discrete point clouds.
  • Robustness through Multi-scale Analysis: Analyzing features at multiple scales makes the detection process inherently more robust to noise. Features that appear as noise at one scale might be persistent and clearly identifiable at another.
  • Surface Variation as a Feature Indicator: The paper demonstrates that a simple statistical measure like surface variation, derived from local covariance, is a powerful indicator of feature presence, particularly for line-type features.
  • Bridging the Gap between Geometry and Semantics: By extracting features directly from raw geometry, the method provides a bridge to higher-level semantic understanding or artistic interpretation of 3D shapes.
  • Artistic Control through Parameters: The multi-scale approach, combined with parameters for hysteresis thresholding, MSG construction, and snake smoothing, offers significant user control over the feature extraction and visualization process.

Key Results

  • Robust Feature Extraction: The method successfully extracts features from noisy point clouds (demonstrated with a laser scan), outperforming single-scale approaches.
  • Efficient Pipeline: The authors provide timing data showing that the multi-scale classification is the most computationally intensive part, but the overall pipeline is efficient enough for interactive feedback loops (excluding the classification step).
  • High-Quality Line Drawings: The system generates visually appealing, artistic line drawings from point clouds, leveraging the extracted feature information to control line width and intensity.
  • Versatility: The extracted features can be used for various applications beyond visualization, such as meshing, segmentation, and anisotropic fairing.

Limitations and Future Work

  • Semi-Automatic Nature: While the method aims for semi-automatic operation, users still need to adjust thresholding parameters to achieve satisfactory results, especially for artistic rendering.
  • Focus on Line-Type Features: The current method is primarily designed for "line-type" features. Extending it to detect other types of features (e.g., corners, regions) might require modifications.
  • Future Work: The authors suggest several avenues:
  • Incorporating more semantic information or parameterized feature models for more advanced extraction.
  • Exploring the distribution of eigenvectors over scale for additional insights, particularly for applications like surface reconstruction.
  • Further investigation into how to automatically select the optimal scale for feature detection.

Summary updated

BibTeX
@article{pauly2003multi,
  author = {Mark Pauly and Richard Keiser and Markus H. Gross},
  title = {{Multi-scale Feature Extraction on Point-sampled Surfaces}},
  journal = {Computer Graphics Forum},
  year = {2003},
  doi = {10.1111/1467-8659.00675},
}
Figure