Distance-ordered homotopic thinning: A skeletonization algorithm for 3D digital images

A technique called distance-ordered homotopic thinning (DOHT) for skeletonizing 3D binary images is presented. DOHT produces skeletons that are homotopic, thin, and medial. This is achieved by sequentially deleting points in ascending distance order until no more can be safely deleted. A point can be safely deleted only if doing so preserves topology, Distance information is provided by the chamfer distance transform, an integer approximation to the Euclidean distance transform. Two variations of DOHT are presented that arise from using different rules for preserving points. The first uses explicit rules for preserving the ends of medial axes or edges of medial surfaces, and the second preserves the centers of maximal halls identified from the chamfer distance transform. By thresholding the centers according to their distance values, the user can control the scale of features represented in the skeleton. Results are presented for real and synthetic 2D and 3D data. (C) 1998 Academic Press.