• Download the manuscript: click here    
   
• A pictorial tour through the thesis : click here    
   
• Results from the Spring-Summer of 2002 : click here    
   
• List of publications linked to this work.
   

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

Keywords: 3D shape representation, medial axis, Voronoi diagram, maximal contact spheres and shocks, directed graphs (digraphs), shock scaffold hierarchy (5 levels), wave propagation, eikonal equation, Euclidean distance maps, Lagrangian versus Eulerian computations, deterministic cellular automata, Huygens versus Fermat's optical principles, visibility constraints, unorganized generators, point clouds, polygonal clouds, quadrics, quartics, octics, Groebner bases and hybrid elimination methods, surface interpolation and meshing, ribs and ridges.

Results :

• http://www.lems.brown.edu/vision/researchAreas/Shocks3D/ResultsApril02/

List of Publications linked to this work:

1. F. F. Leymarie and B. B. Kimia, "From the Infinitely Large to the Infinitely Small," Ch. 11 in "Medial Representations --- Mathematics, Algorithms and Applications," K. Siddiqi and S. M. Pizer, eds., Kluwer Academic, 2007.
2. F. F. Leymarie and B. B. Kimia, "The Medial Scaffold of 3D Unorganised Point Clouds," IEEE Transactions on Pattern Analysis and Machine Intelligence (IEEE-PAMI), vol. 29, no. 2, pp. 313-330, February 2007. 
3. F. F. Leymarie, "Aesthetic Computing and Shape," Ch. 14, pp. 259-288 in "Aesthetic Computing," P. Fishwick, ed., MIT Press, April 2006. (Review of book in JVLC, 2007.)
4. M.-C. Chang, F.F. Leymarie and B.B. Kimia, "3D Shape Registration using Regularized Medial Scaffolds," 2nd International Symposium on 3D Data Processing, Visualization, and Transmission (3DPVT), pp. 987-994,  Thessaloniki, Greece, Sept. 2004.
5. F. F. Leymarie, B. B. Kimia and P. J. Giblin, "Towards Surface Regularization via Medial Axis Transitions," 17th International Conference on Pattern Recognition (ICPR'04), Vol. 3, pp. 123-126, Cambridge, U.K., August 2004.
6. F. F. Leymarie and B. B. Kimia, "Computation of the Shock Scaffold for Unorganized Point Clouds in 3D," IEEE Proceedings of the Conference on Computer Vision and Pattern Recognition (CVPR'03), Vol. 1, pp. 821-827, Madison, Wisconsin, USA, June 2003.
7. Frederic Fol Leymarie, "Three-Dimensional Shape Representation via Shock Flows," PhD thesis, Brown University, May 2003. 
8. B. Kimia and F. Leymarie, "Symmetry-based Representation of Volumetric Imaging", invited paper at the IEEE International Conference on Image Processing (ICIP01), vol. 2, pp. 581-584, October 2001.
9. F. Leymarie and B. Kimia, "The Shock Scaffold for Representing 3D Shape", Proc. of 4th International Workshop on Visual Form (IWVF4). Published in "Visual Form 2001", Lecture Notes in Computer Science (LNCS 2059), Springer-Verlag, pp. 216-229, May 2001.
10. F. Leymarie and B. Kimia, "Discrete 3D Wave Propagation for Computing Morphological Operations from Surface Patches and Unorganized Points", International Symp. on Math. Morpho. (ISMM), Palo Alto. Kluwer Academic, Comp. Imaging & Vision Series, vol.18, pp.351-360, June 2000.
11. H. Tek, F. Leymarie and B. Kimia, "Interpenetrating Waves and Multiple Generation Shocks via the CEDT". In "Advances in Visual Form Analysis", World Scientific, pp. 582-593, 1997.