Euclidean skeletons of 3D data sets in linear time by the integer medial axis transform

Wim H. Hesselink; Menno Visser; Jos B.T.M. Roerdink

Euclidean skeletons of 3D data sets in linear time by the integer medial axis transform

Wim H. Hesselink, Menno Visser, Jos B.T.M. Roerdink

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

243 Downloads (Pure)

Abstract

A general algorithm for computing Euclidean skeletons of 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. The algorithm is based upon the computation of 3D feature transforms, using a modification of an algorithm for Euclidean distance transforms. The skeletonization algorithm has a time complexity which is linear in the amount of voxels, and can be easily parallelized. The relation of the IMA skeleton to the usual definition in terms of centers of maximal disks is discussed.

Original language	English
Title of host publication	MATHEMATICAL MORPHOLOGY: 40 YEARS ON
Editors	C Ronse, L Najman, E Decenciere
Place of Publication	DORDRECHT
Publisher	Springer
Pages	259-268
Number of pages	10
ISBN (Print)	1-4020-3442-3
Publication status	Published - 2005
Event	7th International Symposium on Mathematical Morphology - , France Duration: 18-Apr-2005 → 20-Apr-2005

Publication series

Name	Computational Imaging and Vision
Publisher	SPRINGER
Volume	30

Other

Other	7th International Symposium on Mathematical Morphology
Country	France
Period	18/04/2005 → 20/04/2005

Keywords

feature transform
integer medial axis
3-D Euclidean skeletonization
DISTANCE TRANSFORM
BINARY IMAGES
ALGORITHM
DIMENSIONS
MAPS

Access to Document

2005CompImagVisHesselink.pdfFinal publisher's version, 389 KB

Cite this

@inproceedings{6773705d5d6e4a85a2d7e53750862bd7,

title = "Euclidean skeletons of 3D data sets in linear time by the integer medial axis transform",

abstract = "A general algorithm for computing Euclidean skeletons of 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. The algorithm is based upon the computation of 3D feature transforms, using a modification of an algorithm for Euclidean distance transforms. The skeletonization algorithm has a time complexity which is linear in the amount of voxels, and can be easily parallelized. The relation of the IMA skeleton to the usual definition in terms of centers of maximal disks is discussed.",

keywords = "feature transform, integer medial axis, 3-D Euclidean skeletonization, DISTANCE TRANSFORM, BINARY IMAGES, ALGORITHM, DIMENSIONS, MAPS",

author = "Hesselink, {Wim H.} and Menno Visser and Roerdink, {Jos B.T.M.}",

note = "Relation: http://www.rug.nl/informatica/organisatie/overorganisatie/iwi Rights: University of Groningen, Research Institute for Mathematics and Computing Science (IWI); 7th International Symposium on Mathematical Morphology ; Conference date: 18-04-2005 Through 20-04-2005",

year = "2005",

language = "English",

isbn = "1-4020-3442-3",

series = "Computational Imaging and Vision",

publisher = "Springer",

pages = "259--268",

editor = "C Ronse and L Najman and E Decenciere",

booktitle = "MATHEMATICAL MORPHOLOGY: 40 YEARS ON",

}

Hesselink, WH, Visser, M & Roerdink, JBTM 2005, Euclidean skeletons of 3D data sets in linear time by the integer medial axis transform. in C Ronse, L Najman & E Decenciere (eds), MATHEMATICAL MORPHOLOGY: 40 YEARS ON. Computational Imaging and Vision, vol. 30, Springer, DORDRECHT, pp. 259-268, 7th International Symposium on Mathematical Morphology, France, 18/04/2005.

Euclidean skeletons of 3D data sets in linear time by the integer medial axis transform. / Hesselink, Wim H.; Visser, Menno; Roerdink, Jos B.T.M.

MATHEMATICAL MORPHOLOGY: 40 YEARS ON. ed. / C Ronse; L Najman; E Decenciere. DORDRECHT : Springer, 2005. p. 259-268 (Computational Imaging and Vision; Vol. 30).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Euclidean skeletons of 3D data sets in linear time by the integer medial axis transform

AU - Hesselink, Wim H.

AU - Visser, Menno

AU - Roerdink, Jos B.T.M.

N1 - Relation: http://www.rug.nl/informatica/organisatie/overorganisatie/iwi Rights: University of Groningen, Research Institute for Mathematics and Computing Science (IWI)

PY - 2005

Y1 - 2005

N2 - A general algorithm for computing Euclidean skeletons of 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. The algorithm is based upon the computation of 3D feature transforms, using a modification of an algorithm for Euclidean distance transforms. The skeletonization algorithm has a time complexity which is linear in the amount of voxels, and can be easily parallelized. The relation of the IMA skeleton to the usual definition in terms of centers of maximal disks is discussed.

AB - A general algorithm for computing Euclidean skeletons of 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. The algorithm is based upon the computation of 3D feature transforms, using a modification of an algorithm for Euclidean distance transforms. The skeletonization algorithm has a time complexity which is linear in the amount of voxels, and can be easily parallelized. The relation of the IMA skeleton to the usual definition in terms of centers of maximal disks is discussed.

KW - feature transform

KW - integer medial axis

KW - 3-D Euclidean skeletonization

KW - DISTANCE TRANSFORM

KW - BINARY IMAGES

KW - ALGORITHM

KW - DIMENSIONS

KW - MAPS

M3 - Conference contribution

SN - 1-4020-3442-3

T3 - Computational Imaging and Vision

SP - 259

EP - 268

BT - MATHEMATICAL MORPHOLOGY: 40 YEARS ON

A2 - Ronse, C

A2 - Najman, L

A2 - Decenciere, E

PB - Springer

CY - DORDRECHT

T2 - 7th International Symposium on Mathematical Morphology

Y2 - 18 April 2005 through 20 April 2005

ER -