June 2000

BACK

Abstract

We present a discrete framework for 3D wave propagation to support morphological computations with an emphasis on the recovery of the medial axis of a 3D solid, a collection of surface patches, or a data set of unorganized points. The wave propagation is implemented on a discrete lattice, where initial surfaces are considered as sources of propagation. Three classes of discrete rays are designed to cover the propagation space with a minimal number of computations. These pencils of rays represent a ``compromise'' view between Huygens and Fermat principles. The 3D medial axis points mare then found at the collision of wavefronts. This method has linear time complexity in the number of nodes of the lattice used to discretize the propagation medium, i.e., it is independent of the topological complexity of the initial data. As such, it is highly efficient for the extraction of symmetries, as well as for implementing 3D morphological filters based on erosions and dilations, from large 3D data sets. The wave propagation scheme permits to implement the effect of various metrics including the Euclidean one.

Keywords: 3D morphology, skeletons, Euclidean Distance Transform, wave propagation, Eikonal, unorganized datasets, cellular automata.

Slides :

PDF presentation (compressed with zip)

PostScript presentation (compressed with gzip)

More details here ...

BACK

Last Updated: June 15, 2001