Automatic Generation of Curve Skeleton using Fast Marching Methods

Introduction:

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.

Goal:

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

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:

sample output

sample output

sample output

sample output

sample output

sample output

sample output

sample output

sample output

sample output

sample output

sample output

sample output

sample output

sample output

sample output

Research Team:

Publications:

  1. 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:

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


News