A Formal Classification of 3D Medial Axis Points and Their Local Geometry
|
Abstract—This paper proposes a novel hypergraph skeletal representation for 3D shape based on a formal derivation of the generic structure of its medial axis. By classifying each skeletal point by its order of contact, we show that, generically, the medial axis consists of five types of points, which are then organized into sheets, curves, and points: 1) sheets (manifolds with boundary) which are the locus of bitangent spheres with regular tangency A_1^2 (A_k^n notation means n distinct k{\hbox{-}}{\rm{fold}} tangencies of the sphere of contact, as explained in the text); two types of curves, 2) the intersection curve of three sheets and the locus of centers of tritangent spheres, A_1^3, and 3) the boundary of sheets, which are the locus of centers of spheres whose radius equals the larger principal curvature, i.e., higher order contact A_3 points; and two types of points, 4) centers of quad-tangent spheres, A_1^4, and 5) centers of spheres with one regular tangency and one higher order tangency, A_1A_3. The geometry of the 3D medial axis thus consists of sheets (A_1^2) bounded by one type of curve (A_3) on their free end, which corresponds to ridges on the surface, and attached to two other sheets at another type of curve (A_1^3), which support a generalized cylinder description. The A_3 curves can only end in A_1A_3 points where they must meet an A_1^3 curve. The A_1^3 curves meet together in fours at an A_1^4 point. This formal result leads to a compact representation for 3D shape, referred to as the medial axis hypergraph representation consisting of nodes (A_1^4 and A_1 A_3 points), links between pairs of nodes (A_1^3 and A_3 curves) and hyperlinks between groups of links (A_1^2 sheets). The description of the local geometry at nodes by itself is sufficient to capture qualitative aspects of shapes, in analogy to 2D. We derive a pointwise reconstruction formula to reconstruct a surface from this medial axis hypergraph together with the radius function. Thus, this information completely characterizes 3D shape and lays the theoretical foundation for its use in recognition, morphing, design, and manipulation of shapes.
[1] 238 N. Amenta, S. Choi, and R. Kolluri, 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.
[2] E.V. Anoshkina, A.G. Belyaev, O.G. Okunev, and T.L. Kunii, Ridges and Ravines: A Singularity Approach Int'l J. Shape Modeling, vol. 1, no. 1, 1994.
[3] D. Attali and A. Montanvert, Computing and Simplifying 2D and 3D Continuous Skeletons Computer Vision and Image Understanding, vol. 67, no. 3, pp. 261-273, 1997.
[4] J. August, K. Siddiqi, and S.W. Zucker, Fragment Grouping via the Principle of Perceptual Occlusion Proc. Int'l Conf. Pattern Recognition, pp. 1-8, 1996.
[5] A. Belyaev, E. Anoshkina, and T. Kunii, Ridges Ravines and Singularities Topological Modeling for Visualization, chapter 18, 1997.
[6] T. Binford, Generalized Cylinder Representation Encyclopedia of Artificial Intelligence, John Wiley and Sons, pp. 321-323, 1987.
[7] H. Blum, Biological Shape and Visual Science J. Theoretical Biology, no. 38, pp. 205-287, 1973.
[8] H. Blum and R. Nagel, Shape Description Using Weighted Symmetric Axis Features Pattern Recognition, vol. 10, no. 3, pp. 167-180, 1978.
[9] I.A. Bogaevsky, Metamorphoses of Singularities of Minimum Functions, and Bifurcations of Shock Waves of the Burgers Equation with Vanishing Viscosity St. Petersburg (Leningrad) Math. J., vol. 1, no. 4, pp. 807-823, 1990.
[10] G. Borgefors, I. Nyström, and G. Sanniti di Baja, Computing Skeletons in Three Dimensions Pattern Recognition, vol. 32, no. 7, pp. 1225-1236, July 1999.
[11] S. Bouix and K. Siddiqi, Divergence-Based Medial Surfaces Proc. Sixth European Conf. Computer Vision, vol. 1, pp. 603-618, June 2000.
[12] J.W. Bruce, P. Giblin, and C. Gibson, Symmetry Sets Proc. Royal Soc. Edinburgh, vol. 101A, pp. 163-186, 1985.
[13] J.W. Bruce, P. Giblin, and F. Tari, Ridges, Crests and Sub-Parabolic Lines of Evolving Surfaces Int'l J. Computer Vision, vol. 18, no. 3, pp. 195-210, 1996.
[14] J.W. Bruce and P.J. Giblin, Curves and Singularities: A Geometrical Introduction to Singularity Theory. Cambridge, U.K.: Cambridge Univ. Press, second ed., 1992.
[15] H. Choi, S. Choi, and H. Moon, Mathematical Theory of Medial Axis Pacific J. Math., vol. 181, no. 1, pp. 57-88, 1997.
[16] T.K. Dey and W. Zhao, Approximate Medial Axis as a Voronoi Subcomplex Proc. Seventh ACM Symp. Solid Modeling Applications, pp. 356-366, 2002.
[17] G. Elber and M.-S. Kim, Computing Rational Bisectors IEEE Computer Graphics and Applications, vol. 19, no. 6, Nov./Dec. 1999.
[18] F. Fol-Leymarie, 3D Shape Representation via Shock Flows PhD thesis, Division of Eng., Brown Univ., Providence, RI, 02912, Jan. 2003.
[19] J. Foley, A.V. Dam, S.K. Feiner, and J.F. Hughes, Computer Graphics Principles and Practice. Addison-Wesley, second ed., 1996.
[20] P. Giblin, Symmetry Sets and Medial Axes in Two and Three Dimensions The Math. of Surfaces IX, R. Cipolla and R. Martin, eds., Springer-Verlag, pp. 306-321, 2000.
[21] P.J. Giblin and B.B. Kimia, On the Local Form and Transitions of Symmetry Sets, and Medial Axes, and Shocks in 2D Technical Report LEMS-170, LEMS, Brown Univ., Apr. 1998. Int'l J. Computer Vision, to appear.
[22] P.J. Giblin and B.B. Kimia, On the Intrinsic Reconstruction of Shape from Its Symmetries Proc. IEEE Computer Soc. Conf. Computer Vision and Pattern Recognition, pp. 79-84, June 1999. IEEE Trans. Pattern Analysis and Machine Intelligence, to appear.
[23] P.J. Giblin and B.B. Kimia, On the Local Form and Transitions of Symmetry Sets, and Medial Axes, and Shocks in 2D Proc. Int'l Conf. Computer Vision, pp. 385-391, 1999.
[24] P.J. Giblin and B.B. Kimia, Transitions of the 3D Medial Axis under a One-Parameter Family of Deformations Proc. Seventh European Conf. Computer Vision, pp. 718-724, May 2002.
[25] P.J. Giblin and B.B. Kimia, On the Intrinsic Reconstruction of Shape from Its Symmetries IEEE Trans. Pattern Analysis and Machine Intelligence, 2003.
[26] J. Gomes and O. Faugeras, Reconciling Distance Functions and Level Sets J. Visual Comm. and Image Representation, vol. 11, pp. 209-223, 2000.
[27] P. Hallinan, G. Gordon, A. Yuille, P. Giblin, and D. Mumford, Two and Three Dimensional Patterns of the Face, Natick, Mass.: A.K. Peters, 1999.
[28] M. Hisada, A. Belyaev, and T. Kunii, A Skeleton-Based Approach for Detection of Perceptually Salient Features on Polygonal Surfaces Computer Graphics Forum, vol. 21, no. 4, pp. 1-12, 2002.
[29] Proc. Seveth Int'l Conf. Computer Vision, IEEE Press, Sept. 1999.
[30] I.R. Porteous, Geometric Differentiation. Cambridge Univ. Press, 1994.
[31] D.G. Kendall, Shape Manifolds, Procrustean Metrics and Complex Projective Spaces Bull. London Math. Soc., 16, pp. 81-121, 1984.
[32] B.B. Kimia, A.R. Tannenbaum, and S.W. Zucker, Shapes, Shocks, and Deformations, I: The Components of Shape and the Reaction-Diffusion Space Int'l J. Computer Vision, vol. 15, no. 3, pp. 189-224, 1995.
[33] L. Lam, S.W. Lee, and C.Y. Suen, “Thinning Methodologies: A Comprehensive Survey,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 14, pp. 869-885, 1992.
[34] F. Leymarie and B.B. Kimia, The Shock Scaffold for Representing 3D Shapes Proc. Int'l Workshop on Visual Form, C. Arcelli, L. Cordella, and G.S. di Baja, eds., pp. 216-228, May 2001.
[35] F. Leymarie and B.B. Kimia, Symmetry-Based Representation of 3D Data Proc. IEEE Int'l Conf. Image Processing, pp. 581-584, Oct. 2001.
[36] T. Liu and D. Geiger, Approximate Tree Matching and Shape Similarity Proc. Int'l Conf. Computer Vision, pp. 456-462, 1999.
[37] C. Ma and M. Sonka, A Fully Parallel 3D Thinning Algorithm and Its Applications Computer Vision and Image Understanding, vol. 64, no. 3, pp. 420-433, 1996.
[38] G. Malandain and S. Fernandez-Vidal, Euclidean Skeletons Image and Vision Computing, vol. 16, no. 5, pp. 317-327, Apr. 1998.
[39] D. Metaxas and D. Terzopoulos, Dynamic Deformation of Solid Primitives with Constraints Computer Graphics, vol. 26, no. 2, pp. 309-312, 1992.
[40] M.E. Mortensen, Geometric Modeling. Wiley, 1997.
[41] A. Okabe, B. Boots, K. Sugihara, and S.N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams Probability and Statistics, New York, New York: Wiley, second ed., 2000.
[42] A. Rangarajan, H. Chui, and E. Mjolsness, A New Distance Measure for Non-Rigid Image Matching Energy Minimization Methods in Computer Vision and Pattern Recognition, E. Hancock and M. Pelillo, eds., Springer, pp. 237-252, 1999.
[43] T.B. Sebastian, P.N. Klein, and B.B. Kimia, Recognition of Shapes by Editing Shock Graphs Proc. Eighth Int'l Conf. Computer Vision, pp. 755-762, July 2001.
[44] Image Analysis and Mathematical Morphology: Theoretical Advances. J. Serra, ed., London, England: Academic Press, vol. 2, 1988.
[45] D. Sharvit, J. Chan, H. Tek, and B.B. Kimia, Symmetry-Based Indexing of Image Databases J. Visual Comm. and Image Representation, vol. 9, no. 4, pp. 366-380, Dec. 1998.
[46] G. Taubin,“Estimation of planar curves, surfaces, and nonplanar space curves defined by implicit equations with applications to edge and range image segmentation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 11, pp. 1115-1137, Nov. 1991.
[47] H. Tek and B.B. Kimia, Boundary Smoothing via Symmetry Transforms J. Math. Imaging and Vision, vol. 14, no. 3, pp. 211-223, May 2001.
[48] J.-P. Thirion and A. Gourdon, Computing the Differential Characteristics of Isointensity Sufaces Computer Vision, Graphics, and Image Processing, pp. 190-202, 1995.
[49] M. Zerroug and R. Nevatia, Three-Dimensional 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.
Index Terms:
3D medial axis, skeleton, shocks, curve skeleton, order of contact, local form, medial topology, ridges, generalized axis.
Citation:
Peter Giblin, Benjamin B. Kimia, "A Formal Classification of 3D Medial Axis Points and Their Local Geometry," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 2, pp. 238-251, Jan. 2004, doi:10.1109/TPAMI.2004.1262192
Usage of this product signifies your acceptance of the
Terms of Use.
|
|
|
|
|
|
|
|
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb