Variational Surface Approximation and Model Selection

Bao Li, Ruwen Schnabel, Shiyao Jin, Reinhard KleinComputer Graphics Forum 2009 · DOI

TL;DR

This paper introduces a novel algorithm that jointly optimizes surface partitioning and primitive selection for approximating complex 3D shapes. By integrating model selection into variational surface approximation, it automatically determines the optimal number and types of simple geometric primitives (like planes, spheres, cylinders) needed for a concise and accurate representation, overcoming limitations of previous methods that required manual input or focused on only one aspect of the problem.

What Problem Does This Paper Address?

Representing complex 3D surfaces with a collection of simple geometric primitives (like planes, spheres, cylinders) is a fundamental problem in computer graphics with applications in areas like 3D model compression, remeshing, and reverse engineering. The challenge lies in three interconnected sub-problems:

  1. Partitioning: How to divide the input surface into regions.
  2. Primitive Type Selection: What type of primitive best represents each region.
  3. Model Selection: How many primitives to use to achieve a good balance between representation complexity and approximation error, avoiding overfitting.

Previous methods often tackled these problems in isolation. Variational Surface Approximation (VSA) methods excel at finding optimal partitions and fitting primitives but typically require the user to specify the number of primitives beforehand. On the other hand, model selection techniques can automatically determine the number and type of primitives but often neglect the crucial partitioning aspect, especially for complex, non-range-image data. This paper aims to bridge this gap by proposing a unified approach that jointly optimizes all three aspects.

Methods

The core contribution is a novel algorithm that combines Variational Surface Approximation (VSA) with model selection in a joint global optimization framework. The algorithm iteratively refines a set of "shape hypotheses," where each hypothesis consists of a primitive and its corresponding surface region.

The process involves:

  1. Initial Hypothesis Generation: A set of initial shape hypotheses is generated using a RANSAC (Random Sample Consensus) approach. This method is robust to noise and can detect various primitive types (planes, spheres, cylinders, cones, tori).
  2. Iterative Refinement: The algorithm enters a nested loop structure:
  3. Model Selection: For each hypothesis, a model selection procedure (based on the Minimum Description Length - MDL criterion) is used to find the best subset of other hypotheses that, along with the current one, best approximate the surface. This step balances the cost of describing the data (residuals) with the cost of describing the model (parameters).
  4. Partitioning: A variational shape approximation algorithm (similar to Lloyd's algorithm) is then used to refine the surface partitions for the selected hypotheses. This step ensures that the primitives align with the underlying surface geometry and its anisotropy.
  5. Convergence: The process continues until the set of selected proxies stabilizes, meaning the approximation quality and the set of chosen primitives no longer significantly change.

The paper formalizes the cost function using the MDL criterion, which includes terms for the residual error (how well primitives fit the data) and the complexity of the primitives themselves. The algorithm is designed to avoid local minima by maintaining a set of hypotheses throughout the refinement process, rather than committing to a single solution too early.

Datasets

The paper evaluates its method on several publicly available 3D models:

  • Rolling stage
  • Bunny
  • Horse
  • Fertility
  • Rocker-arm
  • Neptune

These models are used to compare the proposed method against existing VSA approaches and to demonstrate the effect of different parameter settings. No new datasets were introduced.

Key Insights and Ideas

  • Joint Optimization is Key: The most significant insight is that simultaneously optimizing surface partitioning, primitive type selection, and the number of primitives leads to superior results compared to methods that address these aspects independently.
  • Model Selection for Automatic Complexity Control: Integrating model selection (specifically MDL) provides a principled way to automatically balance the trade-off between representation complexity and approximation error, eliminating the need for manual specification of the number of primitives.
  • RANSAC for Robust Initialization: Using RANSAC for initial hypothesis generation is crucial for providing a diverse and robust starting point, especially for noisy or complex input data.
  • Iterative Refinement to Avoid Local Minima: Maintaining a set of candidate hypotheses and iteratively refining them helps the algorithm escape local optima and find better global solutions.
  • Exploiting Anisotropy: Like VSA, the partitioning step respects the anisotropy of the input surface, leading to more natural and efficient representations.

Key Results

  • Improved Approximation Quality: The proposed method consistently achieves comparable or significantly lower approximation errors than traditional VSA methods, especially on complex models with symmetries. For instance, on the horse model, VSA's error was 2.5 times higher.
  • Automatic Primitive Count: The method automatically determines the number of primitives, which is shown to be effective in finding the "turning point" where adding more primitives yields diminishing returns (as illustrated in Figure 6).
  • Consistent Primitive Assignment: The algorithm assigns proxy types consistently, even in the presence of noise, due to the model selection trade-off.
  • Better Symmetry Recovery: Qualitative results show that the method better recovers symmetries in the input models (e.g., in the head area of the bunny model).
  • Efficiency: While the method is computationally intensive, optimizations like pruning unused proxies and shared refinement of hypotheses reduce the number of iterations required.

Limitations and Future Work

  • Runtime Performance: The authors acknowledge that the current runtime performance is a limitation, with computations taking up to 5 hours on the tested models.
  • Future Work:
    • Performance Optimizations: Further research is planned to improve the algorithm's speed.
  • Applications: The authors intend to evaluate the method's utility in applications like compression and symmetry detection.
  • Parameter Sensitivity: While the paper discusses parameter settings, further exploration of their impact and potential automatic tuning could be beneficial.

Summary updated

BibTeX
@article{li2009variational,
  author = {Bao Li and Ruwen Schnabel and Shiyao Jin and Reinhard Klein},
  title = {{Variational Surface Approximation and Model Selection}},
  journal = {Computer Graphics Forum},
  year = {2009},
  doi = {10.1111/j.1467-8659.2009.01577.x},
}
Figure