3D Shape Representation via Shock Flows

Frederic Leymarie leymarie at lems.brown.edu
Fri Jan 24 18:38:26 PST 2003

My thesis is now available on-line:


We address the problem of representing 3D shapes when partial and unorganized data
is obtained as an input, such as clouds of point samples
on the surface of a face, statue, solid, etc., of regular or arbitrary complexity (free-form),
as is commonly produced by photogrammetry, laser
scanners, computerized tomography, and so on. Our starting point is the medial axis (MA)
representation which has been explored mainly for
2D problems since the 1960's in pattern recognition and image analysis. The MA makes
explicit certain symmetries of an object, corresponding
to the shocks of waves initiated at the input samples, but is itself difficult to directly use f
or recognition tasks and applications. Based on
previous work on the 2D problem, we propose a new representation in 3D which is
derived from the MA, producing a graph we call the shock
scaffold. The nodes of this graph are defined to be certain singularities of the shock
flow along the MA. This graph can represent exactly the MA
--- and the original inputs --- or approximate it, leading to a hierarchical description of shapes.

We develop accurate and efficient algorithms to compute for 3D unorganized
clouds of points the shock scaffold, and thus the MA, as well as
its close cousin the Voronoi diagram. One computational method relies on
clustering and visibility constraints, while the other simulates
wavefront propagation on a 3D grid. We then propose a method of splitting
the shock scaffold in two sub-graphs, one of which is related to the (a
priori unknown) surface of the object under scrutiny. This allows us to simplify
the shock scaffold making more explicit coarse scale object
symmetries, while at the same time providing an original method for the surface
interpolation of complex datasets. In the last part of this talk,
we address extensions of the shock scaffold by studying the case where the
inputs are given as collections of unorganized polygons.

Frederic FOL LEYMARIE, R&D Project leader, SHAPE Lab.
Brown University, Division of Engineering, LEMS, Box D
182-4 Hope Street, Providence, Rhode Island 02912, U.S.A.
Tel: +1.401.863.2760, Alternate Voice: x2177, Fax: x9039
mailto:leymarie at lems.brown.edu , http://www.lems.brown.edu/~leymarie

The compgeom mailing lists: see
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.

More information about the Compgeom-announce mailing list