|
Published Articles >> Table of Contents >> Abstract
February 2007 (Vol. 29, No. 2)
pp. 313-330
The Medial Scaffold of 3D Unorganized Point Clouds
Frederic F. Leymarie
Benjamin B. Kimia
Full Article Text:
   
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TPAMI.2007.44
Send link to a friend
| Abstract |
|
We introduce the notion of the medial scaffold, a hierarchical organization of the medial axis of a 3D shape in the form of a graph constructed from special medial curves connecting special medial points. A key advantage of the scaffold is that it captures the qualitative aspects of shape in a hierarchical and tightly condensed representation. We propose an efficient and exact method for computing the medial scaffold based on a notion of propagation along the scaffold itself, starting from initial sources of the flow and constructing the scaffold during the propagation. We examine this method specifically in the context of an unorganized cloud of points in 3D, e.g., as obtained from laser range finders, which typically involve hundreds of thousands of points, but the ideas are generalizable to data arising from geometrically described surface patches. The computational bottleneck in the propagation-based scheme is in finding the initial sources of the flow. We thus present several ideas to avoid the unnecessary consideration of pairs of points which cannot possibly form a medial point source, such as the "visibility” of a point from another given a third point and the interaction of clusters of points. An application of using the medial scaffold for the representation of point samplings of real-life objects is also illustrated.
|
 References
|
[1] N. Amenta and M. Bern, “Surface Reconstruction by Voronoi Filter,” Discrete and Computational Geometry, vol. 22, pp. 481-504, 1999.
[2] N. Amenta et al., “The Power Crust, Unions of Balls, and the Medial Axis Transform,” Int'l J. Computational Geometry and Its Applications, vol. 19, nos. 2-3, pp. 127-153, 2001.
[3] D. Attali and J.-D. Boissonnat, “A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces,” Proc. Seventh ACM Symp. Solid Modeling and Applications, pp. 139-146, 2002.
[4] A. Balliccioni, Coordonnes Barycentriques et Géométrie; Applications: Tetraedre, Surfaces et Lignes Remarquables Associes. Claude Hermant, 1964.
[5] C. Barber et al., “The Quickhull Algorithm for Convex Hulls,” ACM Trans. Math. Software, vol. 22, no. 4, pp. 469-483, 1996.
[6] G. Barequet et al., “RSVP: A Geometric Toolkit for Controlled Repair of Solid Models,” IEEE Trans. Visualization and Computer Graphics, vol. 4, no. 2, pp. 162-177, Apr.-June 1998.
[7] C. Berge, Hypergraphs. Combinatorics of Finite Sets, vol. 45. North-Holland, 1989.
[8] T. Binford, “Generalized Cylinder Representation,” Encyclopedia of Artificial Intelligence, pp. 321-323, 1987.
[9] M. Blane et al., “The 3L Algorithm for Fitting Implicit Polynomial Curves and Surfaces to Data,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 3, pp. 298-313, Mar. 2000.
[10] H. Blum, “Biological Shape and Visual Science,” J. Theoretical Biology, vol. 38, pp. 205-287, 1973.
[11] H. Blum and R. Nagel, “Shape Description Using Weighted Symmetric Axis Features,” Pattern Recognition, vol. 10, no. 3, pp.167-180, 1978.
[12] W. Boehm and H. Prautzsch, Geometric Concepts for Geometric Design. A.K. Peters, 1994.
[13] G. Borgefors et al., “Computing Skeletons in 3D,” Pattern Recognition, vol. 32, no. 7, pp. 1225-1236, July 1999.
[14] M.-C. Chang et al., “3D Shape Registration Using Regularized Medial Scaffolds,” Proc. Second Int'l Symp. 3D Data Processing, Visualization and Transmission, pp. 987-994, 2004.
[15] F. Chazal et al., “A Sampling Theory for Compacts in Euclidean Spaces,” Proc. 22nd ACM Ann. Symp. Computational Geometry, pp.319-326, 2006.
[16] T. Culver et al., “Exact Computation of the Medial Axis of a Polyhedron,” Computer Aided Geometric Design, vol. 21, no. 1, pp.65-98, 2004.
[17] L. Devroye, Lecture Notes on Bucket Algorithms. Birkhauser, 1986.
[18] G. Elber and M.-S. Kim, “Computing Rational Bisectors,” IEEE Computer Graphics and Applications, vol. 19, no. 6, pp. 76-81, 1999.
[19] P. Giblin and B. Kimia, “Transitions of the 3D ${\cal MA}$ under a 1-Parameter Family of Deformations,” Lecture Notes in Computer Science, no. 2351, pp. 719-734, 2002.
[20] P. Giblin and B. Kimia, “On the Intrinsic Reconstruction of Shape from Its Symmetries,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 7, pp. 895-911, July 2003.
[21] P. Giblin and B. Kimia, “On the Local Form and Transitions of Symmetry Sets,” Int'l J. Computer Vision, vol. 54, no. 1-3, pp. 143-157, 2003.
[22] P. Giblin and B. Kimia, “A Formal Classification of 3D Medial Axis Points and Their Local Geometry,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 2, pp. 238-251, Feb. 2004.
[23] P. Halliman et al., Two- and Three-Dimensional Patterns of the Face. A.K. Peters, 1999.
[24] M. Hilaga et al., “Topology Matching for Fully Automatic Similarity Estimation of 3D Shapes,” Proc. ACM SIGGRAPH, pp.203-212, 2001.
[25] C. Hoffmann, “How to Construct the Skeleton of CSG Objects,” The Math. of Surfaces IV, pp. 421-438, Oxford Univ. Press, 1994.
[26] B. Kimia et al., “Shapes, Shocks, and Deformations,” Int'l J. Computer Vision, vol. 15, no. 3, pp. 189-224, 1995.
[27] M. Levoy et al., “The Digital Michelangelo Project,” Proc. ACM SIGGRAPH, pp. 131-144, 2000.
[28] F. Leymarie, “Three-Dimensional Shape Representation,” PhD thesis, Brown Univ., 2003.
[29] F. Leymarie et al., “The SHAPE Lab,” Computing Archaeology for Understanding the Past, pp. 78-89, Archaeopress, 2001.
[30] F. Leymarie et al., “Towards Surface Regularization via ${\cal MA}$ Transitions,” Proc. Int'l Conf. Pattern Recognition, vol. 3, pp. 123-126, 2004.
[31] F. Leymarie and B. Kimia, “Computation of the Shock Scaffold,” Proc. Conf. Computer Vision and Pattern Recognition, vol. 1, pp. 821-827, 2003.
[32] F. Leymarie and B. Kimia, “From the Infinitely Large to the Infinitely Small,” Medial Representations: Mathematics, Algorithms and Applications, chapter 11. Kluwer Academic, 2007.
[33] M. Leyton, Symmetry, Causality, Mind. MIT Press, 1992.
[34] M. Leyton, “A Generative Theory of Shape,” Lecture Notes in Computer Science, no. 2145, 2001.
[35] G. Malandain and S. Fernandez-Vidal, “Euclidean Skeletons,” Image and Vision Computing, vol. 16, no. 5, pp. 317-327, 1998.
[36] D. Mumford, “Mathematical Theories of Shape,” Proc. Geometric Methods in Computer Vision Conf., vol. 1570, pp. 2-10, 1991.
[37] A. Okabe et al., “Spatial Tessellations: Concepts and Applications of Voronoi Diagrams,” Probability and Statistics Series, second ed. Wiley, 2000.
[38] N. Patrikalakis and T. Maekawa, Shape Interrogation for CAD and Manufacturing. Springer, 2002.
[39] M. Peternell, “Geometric Properties of Bisector Surfaces,” Graphical Models and Image Processing, vol. 62, no. 3, pp. 202-236, May 2000.
[40] T. Sebastian et al., “Recognition of Shapes by Editing Their Shock Graphs,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 5, pp. 550-571, May 2004.
[41] J. Serra, Image Analysis and Mathematical Morphology, vol. 1. Academic Press, 1982.
[42] E. Sherbrooke et al., “An Algorithm for the ${\cal MA}$ Transform of 3D Polyhedral Solids,” IEEE Trans. Visualization and Computer Graphics, vol. 2, no. 1, pp. 44-61, Jan.-Mar. 1996.
[43] E. Sherbrooke et al., “Differential and Topological Properties of ${\cal MA}$ Transforms,” Graphical Models and Image Processing, vol. 58, no. 6, pp. 574-592, 1996.
[44] J. Shewchuk, “Lecture Notes on Geometric Robustness,” technical report, Dept. of Electrical Eng. and Computer Science, Univ of California at Berkeley, 1999.
[45] K. Siddiqi et al., “Hamilton–Jacobi Skeletons,” Int'l J. Computer Vision, vol. 48, no. 3, pp. 215-231, 2002.
[46] K. Siddiqi and B. Kimia, “A Shock Grammar for Recognition,” Proc. Conf. Computer Vision and Pattern Recognition, pp. 507-513, 1996.
[47] D. Siersma, “Voronoi Diagrams and Morse Theory,” Geometry in Present Day Science, World Scientific, 1999.
[48] M. Smid, “Closest-Point Problems,” Handbook of Computational Geometry, pp. 877-935, Elsevier, 2000.
[49] H. Sundar et al., “Skeleton Based Shape Matching,” Proc. IEEE Int'l Conf. Shape Modeling and Applications, pp. 130-142, 2003.
[50] H. Tek and B. Kimia, “Curve Evolution, Wave Propagation, and Mathematical Morphology,” Computational Imaging and Vision, vol. 12, pp. 115-126, 1998.
[51] H. Tek and B. Kimia, “Boundary Smoothing via Symmetry Transforms,” J. Math. Imaging and Vision, vol. 14, no. 3, pp. 211-223, 2001.
[52] H. Tek and B. Kimia, “Symmetry Maps of Free-Form Curve Segments,” Int'l J. Computer Vision, vol. 54, nos. 1-3, pp. 35-81, 2003.
[53] D. Terzopoulos and D. Metaxas, “Dynamic 3D Models with Local and Global Deformations: Deformable Superquadrics,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 7, pp.703-714, July 1991.
[54] A. Verroust and F. Lazarus, “Extracting Skeletal Curves from 3D Scattered Data,” The Visual Computer, vol. 16, no. 1, pp. 15-25, 2000.
[55] L. Wade and R. Parent, “Automated Generation of Control Skeletons for Use in Animation,” The Visual Computer, vol. 18, no. 2, pp. 97-110, 2002.
[56] F.-E. Wolter, “Cut Locus and ${\cal MA}$ in Global Shape Interrogation and Representation,” Technical Report 92-2, Dept. of Ocean Eng., Design Lab, Massachusetts Inst. of Tech nology, Jan. 1992.
[57] F.-E. Wolter and K.-I. Friese, “Local and Global Geometric Methods for Analysis, Interrogation, Reconstruction, Modification and Design of Shape” Proc. Conf. Graphics Int'l, pp. 137-151, 2000.
[58] M. Zerroug and R. Nevatia, “3D Descriptions Based on the Analysis of the Invariant and Quasi-Invariant Properties of Some Curved-Axis Generalized Cylinders,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 3, pp. 237-253, Mar. 1996.
|
 Additional Information
|
Index Terms- 3D shape understanding, object representation, geometric algorithms, 3D medial axis, shock graphs, flow singularities, 3D bucketing, visibility constraints.
Citation:
Frederic F. Leymarie, Benjamin B. Kimia,
"The Medial Scaffold of 3D Unorganized Point Clouds,"
IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 29,
no. 2,
pp. 313-330,
Feb.,
2007
|
|
RSS Feed