Euclidean skeletons: overview
Skeleton (or medial axis) is one of the most studied and used concepts in pattern recognition and analysis. Since its introduction by H. Blum in the sixties, it has been the subject of hundreds of publications dealing with both practical and theoretical aspects. Indeed, despite the simplicity of its most common definition, as the set of all centers of maximal included balls, its use in real applications often raises difficult challenges.
These difficulties are mainly due to two distinct problems.
First, the nice properties of skeleton that can be proved in the continuous framework (uniqueness, thinness, homotopy equivalence, invariance w.r.t. isometries) do not all hold in discrete grids which are commonly used in image processing. Considerable effort has been devoted to design discrete skeletonization methods that aim at retrieving these properties, at least partially.
Second, even in the continuous framework the skeleton suffers from its sensitivity to small contour perturbations, in other words, its lack of stability. This difficulty can be expressed mathematically: the transformation which associates a shape to its skeleton is only semi-continuous. This fact, among others, explains why it is usually necessary to add a filtering step (or pruning step) to any method that aims at computing the skeleton.
These pages contain several contributions to the solution of these problems in discrete grids.
In [CCZ07], we propose a new definition and an algorithm for the discrete bisector function, which is an important tool for analyzing and filtering Euclidean skeletons. We also introduce a new thinning algorithm which produces homotopic discrete Euclidean skeletons. These algorithms, which are valid both in 2D and 3D, are integrated in a skeletonization method which is based on exact transformations, allows the filtering of skeletons, and is computationally efficient.
In [SCL09], we present the definition of the Exact Euclidean Medial Axis in Higher Resolution, which has the same properties as the medial axis but with a better thinness characteristic, against the price of rising resolution. We provide and prove an efficient algorithm to compute it.
In 2005, Chazal and Lieutier introduced the lambda-medial axis as a new concept for computing the medial axis of a shape subject to single parameter filtering. The lambda-medial axis is stable under small shape perturbations, as proved by these authors. In [CCT10], a discrete lambda-medial axis (DLMA) is introduced and compared with the recently introduced integer medial axis (GIMA). We show that DLMA provides measurably better results than GIMA, with regard to stability and sensibility to rotations. We give efficient algorithms to compute the DLMA, and we also introduce a variant of the DLMA which may be computed in linear-time.
In the 90s, several authors introduced the notion of a hierarchic family of 2D Euclidean skeletons, evolving smoothly under the control of a filtering parameter. We provide in [Cou11] a discrete framework which formalizes and generalizes this notion, in particular to higher dimensions. This framework allows us to propose a new skeletonization scheme and to prove several important properties, such as topology preservation and stability w.r.t. parameter changes.
Site info
© 2009-2010 ESIEE Dept. Info.