The propagating skeleton: a robust detail-preserving approach

Abstract

A skeleton is a centered geometric representation of a shapethat describes the shape in a simple and intuitive way, typically reducingthe dimension by at least one. Skeletons are useful in shape analysis andrecognition since they provide a framework for part decomposition, arestable under topology preserving deformation, and supply informationabout the topology and connectivity of the shape. The main drawbackto skeletonization algorithms is their sensitivity to small boundary per-turbations: noise on a shape boundary, such as pixelation, will producemany spurious branches within a skeleton. As a result, skeletonizationsoften require a second pruning step. In this article, we propose a new2D skeletonization algorithm that directly produces a clean skeleton fora shape, avoiding the creation of noisy branches. The approach propa-gates a circle inside the shape, maintaining neighborhood-based contactwith the boundary and bypassing boundary oscillations below a chosenthreshold. By explicitly modeling the scale of noise via two parame-ters that are shape-independent, the algorithm is robust to noise whilepreserving important shape details. Neither preprocessing of the shapeboundary nor pruning of the skeleton is required. Our method producesskeletons with fewer spurious branches than other state-of-the-art meth-ods, while outperforming them visually and according to error measuressuch as Hausdorff distance and symmetric difference, as evaluated on theMPEG-7 database (1033 images).