Fast medial axis extraction algorithm on tubular large 3D data by randomized erosion

Topological abstraction of complex and highly branching three- dimen-sional structures to a tree-like skeleton enables sophisticated object recognition and analysis in 3D image data sets. Skeletonization is a costly procedure, mostly not applicable with huge data sets, e.g. computed tomography studies from lungs or liver. Information about the hierarchical topology of vessel trees would be highly desirable in these cases. A fast morphological thinning approach for skeletonization of tubular structures and objects with arbitrary shape was developed. This algorithm increases hit-rate during surface erosion applying minimal constraints to generality, providing performance suitable for thinning of huge datasets. Time consuming neighbourhood checking is solved by the use of fast indexing lookup tables, yielding homogenous erosion of any shape. Results show accurate centreline extraction without any offset introduced by digital sampling of objects with even diameter. The algorithm proved to be robust and fast, meeting the requirements of computer aided diagnosis in modern radiology.