A simple and robust thinning algorithm on cell complexes

Pierre Alliez, Lu Liu, Erin W. Chambers, David Letscher, Tao JuComputer Graphics Forum 2010 · DOI

TL;DR

This paper introduces a novel thinning algorithm for generating skeletons of 3D objects represented as cell complexes. Their key innovation is "medial persistence," a measure that quantifies how long a skeletal element persists during a thinning process, effectively capturing the object's shape features like tubes and plates. This approach leads to more robust and controllable skeletons compared to traditional methods, which are often sensitive to noise and boundary perturbations.

What Problem Does This Paper Address?

Skeletons are crucial for understanding and describing the shape of objects in computer graphics and vision, with applications ranging from object recognition to animation. A common method for generating these skeletons is "thinning," which iteratively removes parts of an object's boundary until only a thin core remains. However, traditional thinning algorithms, often applied to discrete grids (digital pictures), are highly sensitive to small changes in the object's boundary. This sensitivity can lead to "spurious" skeletal branches that don't accurately represent the object's global shape. While more robust methods exist, they are often computationally expensive. The authors aim to bridge this gap by developing a thinning algorithm that is both simple and robust, capable of capturing global shape features without excessive computational cost.

Methods

The core of the paper is a new thinning algorithm that operates on "cell complexes," a more structured representation of geometric objects than simple digital grids. Their algorithm is based on an iterative process of removing "simple pairs" of cells (a cell and its unique facet). The novelty lies in the introduction of medial persistence (MP), a measure computed during this iterative thinning.

MP quantifies how long a skeletal element (a cell) remains "isolated" (not a facet of a higher-dimensional cell) during the thinning process. They define two MP scores:

  • Mabs (absolute medial persistence): The absolute duration a cell remains isolated.
  • Mrel (relative medial persistence): The relative duration a cell remains isolated, normalized by its removal iteration.

The intuition is that cells corresponding to geometrically significant features (like the center of a tube or a plate) will persist longer during thinning. The algorithm proceeds in three steps:

  1. Thinning Pass 1: Compute MP scores for all cells.
  2. Clustering: Identify "medial cells" (cells with high MP scores) and group them.
  3. Thinning Pass 2: Re-run the thinning process, but this time, preserve the identified medial cells, ensuring topology is maintained.

This two-pass approach, guided by MP, allows for the generation of skeletons that are both topology-preserving and shape-descriptive.

Datasets

The paper uses a suite of 3D models for evaluation. These models are converted into cell complexes from triangular meshes. The authors do not introduce a new benchmark dataset but rather demonstrate their algorithm's performance on existing models, including a "Fish model" voxelized at different resolutions to test robustness to discretization levels.

Key Insights and Ideas

  • Medial Persistence as a Shape Descriptor: The core insight is that the duration a skeletal element persists during a topology-preserving thinning process directly correlates with the "anisotropic elongation" of the object's shape at that location. Cells persisting longer are indicative of features like tubes (1D elongation) or plates (2D elongation).
  • Dimension-Agnostic Significance: Medial persistence is formulated in a way that applies to cells of any dimension (points, edges, faces, etc.) within a cell complex, making it a unified measure for different types of skeletal features.
  • Robustness through Global Measure: By relying on a measure derived from the entire thinning process (rather than just local neighborhoods), the algorithm achieves robustness against boundary perturbations and varying discretization levels.
  • Controllable Skeleton Composition: The MP scores provide parameters that allow users to control the composition of the resulting skeleton (e.g., generating curve-only skeletons or surface-and-curve skeletons) by setting thresholds for MP values.

Key Results

  • Robustness: The algorithm produces skeletons that are stable under boundary perturbations and changes in model resolution, as demonstrated by comparing results on a clean hand model versus a noisy one, and on the Fish model at different voxelization levels (Figure 6 and 7).
  • Shape Capture: Medial persistence effectively highlights geometrically significant features. Faces with high MP scores correspond to plate-like parts, and edges with high MP scores correspond to tube-like parts of the object (Figure 4 and 8).
  • Comparison to Existing Methods: The paper shows that their MP-guided skeletons are more stable and less prone to spurious branches compared to traditional thinning algorithms on digital pictures (Figure 8). They also qualitatively compare their MP-guided skeletons to those generated by a Feature Distance measure, showing MP highlights anisotropy better, even in parts away from the object's center (Figure 5).
  • Controllability: The algorithm allows for flexible control over skeleton dimensionality, enabling the generation of curve-only or surface-and-curve skeletons by adjusting MP thresholds.

Limitations and Future Work

  • Grid Bias: The authors acknowledge that their current algorithm, which follows the grid structure of the cell complex, can be biased by grid orientation, potentially affecting MP scores. They are exploring distance-guided removal of simple pairs to mitigate this.
  • Arbitrary Ordering: The selection of witness facets for simple pairs is currently arbitrary. Further analysis on the effect of ordering is suggested.
  • Parallelization: The iterative and parallel nature of simple pair removals suggests potential for significant acceleration through parallel, hardware-accelerated implementations.
  • Continuous Formulation: The authors believe a continuous formulation of their discrete thinning and medial persistence measure exists and would be a promising direction for future research, potentially explaining the observed stability at increasing discretization levels.

Summary updated

BibTeX
@article{alliez2010simple,
  author = {Pierre Alliez and Lu Liu and Erin W. Chambers and David Letscher and Tao Ju},
  title = {{A simple and robust thinning algorithm on cell complexes}},
  journal = {Computer Graphics Forum},
  year = {2010},
  doi = {10.1111/j.1467-8659.2010.01814.x},
}
Figure