A simple and robust thinning algorithm on cell complexes

L. Liu, E. W. Chambers, D. Letscher, T. Ju

Research output: Contribution to journalArticlepeer-review

55 Scopus citations


Thinning is a commonly used approach for computing skeleton descriptors. Traditional thinning algorithms often have a simple, iterative structure, yet producing skeletons that are overly sensitive to boundary perturbations. We present a novel thinning algorithm, operating on objects represented as cell complexes, that preserves the simplicity of typical thinning algorithms but generates skeletons that more robustly capture global shape features. Our key insight is formulating a skeleton significance measure, called medial persistence, which identify skeleton geometry at various dimensions (e.g., curves or surfaces) that represent object parts with different anisotropic elongations (e.g., tubes or plates). The measure is generally defined in any dimensions, and can be easily computed using a single thinning pass. Guided by medial persistence, our algorithm produces a family of topology and shape preserving skeletons whose shape and composition can be flexible controlled by desired level of medial persistence.

Original languageEnglish
Pages (from-to)2253-2260
Number of pages8
JournalComputer Graphics Forum
Issue number7
StatePublished - Sep 2010


Dive into the research topics of 'A simple and robust thinning algorithm on cell complexes'. Together they form a unique fingerprint.

Cite this