Automatic Generation of Curve Skeletons Using Fast
  Marching Methods

Understanding shape is of great importance in pattern analysis and machine intelligence. The medial axis (MA) or skeleton has been introduced as a generic and compact representation of a shape while maintaining its topology. Skeletonization aims at reducing the dimensionality of a shape such that it can be represented with less information than the original one. For example, the skeleton of a 2D shape is a set of medial curves or centerlines, while that of a 3D object is a set of medial surfaces. It has been found that reducing the dimensionality of the skeleton describing general shapes from medial surfaces to a set of medial curves or (CS) is of utmost importance in several applications such as 3D path planning, character animation, object recognition, shape matching, shape retrieval, and 3D gait analysis.

The aim of this project is to automatically extract CS of 3D articulated objects that are centered, connected, one-voxel width, less sensitive to boundary noise, and efficiently handle objects with arbitrary number of loops.
Research Team
Aly A. Farag CVIP Director farag@cvip.uofl.edu
M. Sabry Hassouna Research Assistant msabry@cvip.uofl.edu
Methods

In this project, we present an original framework for inferring stable discrete curve skeletons for elongated and articulated objects using partial differential equation (PDE). The proposed method works as follows: a curve skeleton point is selected automatically as the point of global maximum Euclidean distance from the boundary, and is considered a point source (PS) that transmits two wave fronts of different speeds that evolve over time and traverse the object domain. The motion of the front is governed by a nonlinear PDE whose solution is computed efficiently using the higher accuracy fast marching methods (HAFMM). Initially, the (PS) transmits a moderate speed wave to explore the object domain and to extract its topological information. Then, it transmits a new front whose speed is proportional to a nonlinear function of the minimum Euclidean distance field of the object. As a consequence, the CS of the object intersects the propagating fronts at those points of maximum positive curvature, which are identified by solving an ordinary differential equation using an efficient numerical scheme. The proposed method is robust, fully automatic, computationally efficient, and computes CS that are centered, connected, one voxel width, and less sensitive to boundary noise.
 

Results
   
   
   
   
   
 
   
 
   
   
 
   

Movies
Extraction of Curve Skeletons of Various Objects of Different Complexity

Publications

M. Sabry Hassouna and A.A. Farag, "Robust Centerline Extraction Framework Using Level Sets," Proc. of IEEE Conference on Computer Vision and Pattern Recognition (CVPR'05), San Diego, CA, USA June 20-26, 2005.

Acknowledgement / Sponsors
We would like to thank the University of Louisville for its sponsorship.