Euclidean Skeletons of Digital Image and Volume Data in Linear Time by the Integer Medial Axis Transform

Wim H. Hesselink*, Jos B.T.M. Roerdink

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

84 Citations (Scopus)
343 Downloads (Pure)

Abstract

A general algorithm for computing euclidean skeletons of 2D and 3D data sets in linear time is presented. These skeletons are defined in terms of a new concept, called the integer medial axis (IMA) transform. We prove a number of fundamental properties of the IMA skeleton and compare these with properties of the centers of maximal disks (CMD) skeleton. Several pruning methods for IMA skeletons are introduced (constant, linear, and square-root pruning) and their properties studied. The algorithm for computing the IMA skeleton is based upon the feature transform using a modification of a linear-time algorithm for euclidean distance transforms. The skeletonization algorithm has a time complexity that is linear in the number of input points and can be easily parallelized. We present experimental results for several data sets, looking at skeleton quality, memory usage, and Computation time, both for 2D images and 3D volumes.

Original languageEnglish
Pages (from-to)2204-2217
Number of pages14
JournalIeee transactions on pattern analysis and machine intelligence
Volume30
Issue number12
DOIs
Publication statusPublished - Dec-2008

Keywords

  • Feature transform
  • integer medial axis
  • euclidean skeletonization
  • integer perpendicular bisector
  • BINARY IMAGES
  • DISTANCE MAPS
  • ALGORITHM
  • REPRESENTATION
  • DIMENSIONS

Cite this