Wave Propagation: Cellular automata & Distance Transforms

Initial assumptions:

• we have a uniform (isotropic) discrete grid representing the 3D space
• the grid is of finite size (say NxNxN)
• the underlying metric is Euclidean

In other words: "We have a bounded section of an equidistantly sampled Euclidean space of dimension D=3."

In an attempt to address problems of previous approaches as well as going further ahead in designing a powerful process for shape description and representation we propose a "new" approach for dealing with symmetry elicitation in 3D.

What we are aiming at:

• Elicitation of medial axes, locally performed but retaining the global shape properties.
• Accurate loci in space-time, where time is taken for Euclidean distance.
• Explicit characterization of medial axes features.
• A process permitting to deal both with sparse and dense data sets, within the same framework.
• A process for shape which can be naturally be extended to compute other symmetries or shape properties, such as:
  • mid-chord loci
  • full SymSet
• A process physically plausible, which can tackle shape problems in other fields than visual perception, such as:
  • computation of caustics of light rays
  • crack propagation and fatigue in material engineering analysis
  • visibility computations in computer graphics for rendering light and sound propagations
  • simulation of wave propagations through particle systems ...
• A process dealing in a similar way with human-made, curved or "natural" objects.

The solution: Huygen's principle revisited

Let Phi(q0,t) be the wavefront of the point q0 after time t. For every point q of this front, consider the wavefront after time s: Phi(q,s).

Then, the wavefront of the point q0 after time s+t, Phi(q0, s+t), will be the envelope of the fronts Phi(q,s), such that q in Phi(q0,t).

In this formulation, one can replace the "point" q0 by a curve, surface, or in general, by a closed set.

Furthermore, the 3D space can be replaced by any smooth manifold, and the propagation of light can be replaced by the propagation of any disturbance transmitting itself "locally".

We can also replace the metric from Euclidean to a Riemannian, and model anisotropic "shape" properties (of the medium, or space).

The difficulty, is to translate this principle in a discrete world relying upon a lattice, such as the X-Y-Z grid made of voxels, traditionally used in image processing.

We have developed such a "discrete" method relying upon a 3D grid. We call it 3D-CADT for:

3D Cellular Automata based on (Euclidean) Distance Transforms.

In this approach, we simulate propagation of information by the use of a class of cellular automata "oriented" in the direction of the wavefront. Equivalently, these automata rely upon the metric characteristic of the underlying space (the "indicatrix"). For Euclidean 3D space, this is a sphere or directions.

The resultant ray system, is the system of normals to a surface in Euclidean space. In the ngb. of a smooth surface, its normals form a smooth fibration, until at some distance from the surface, various normals may begin to intersect one another.

Historical note: These "singularities" were first investigated by Archimedes (caustics of light rays, around 300 B.C.).

Some examples

1 - A point and a plane generate a paraboloid surface

2 - An open cylinder generates a stick axis

3 - Intersection of a paraboloid & a plane : medial axis with a A1³ medial curve

Computation of 3D shocks

3D shocks have been proposed by Kimia.These are based on curvature properties of a level hypersurface, £, in a 4D space which represents the evolution of a 3D object under a wave propagation (or under a motion defined by a so-called "reaction-diffusion" PDE).

Next ....

From discrete to "smooth" medial axes traces.

From medial axes traces to 3D shock computations.

Dimensional reduction: from medial sheets to curves.

Computing other 3D symmetries.

Page created by Frederic Leymarie, 1998.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu