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 voor dit werk

OnderzoeksoutputAcademicpeer review

97 Citaten (Scopus)
501 Downloads (Pure)

Samenvatting

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.

Originele taal-2English
Pagina's (van-tot)2204-2217
Aantal pagina's14
TijdschriftIEEE Transactions on Pattern Analysis and Machine Intelligence
Volume30
Nummer van het tijdschrift12
DOI's
StatusPublished - dec.-2008

Vingerafdruk

Duik in de onderzoeksthema's van 'Euclidean Skeletons of Digital Image and Volume Data in Linear Time by the Integer Medial Axis Transform'. Samen vormen ze een unieke vingerafdruk.

Citeer dit