July 2000

BACK

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 are 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.

SHAPE Slides :

• Presented June 27th., by F. Leymarie :
    
  • PDF file compressed (gzip)

ERRATUM :

There was an error at printing of figure 4, on page 359 :

• Figure (d) should be moved to replace (c), and figure (d) should be replaced by the following one:
    
  • GIF image of medial axis of a closed-end cylinder.
      
  • PDF file compressed (gzip) with Figure 4 as it should appear in the Proceedings.

Paper is published in :

• Mathematical Morphology and its Applications to Image and Signal Processing,
  edited by John Goutsias, Luc Vincent & Dan Bloomberg,
  Kluwer Academic Publishers, Computational Imaging and Vision series, vol. 18, 2000, 445 pages.
• Paper appears on pages 351-360.
• ISBN: 0-7923-7862-8

Links:

• Official ISMM'00 web site: www.parc.xerox.com/parc/ismm2000/
• Kluwer academic publishers: www.wkap.nl

BACK