| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
On the Intrinsic Reconstruction of Shape from Its Symmetries
July 2003 (vol. 25 no. 7)
pp. 895-911
Abstract—The main question we address is: What is the minimal information required to generate closed, nonintersecting planar boundaries? For this paper, we restrict “shape” to this meaning. More precisely, we examine whether the medial axis, together with dynamics, can serve as a language to design shapes and to effect shape changes, e.g., for modeling, to generate a morph sequence, etc. We represent the medial axis together with a direction of flow along the axis as the shock graph and examine the reconstruction of shape along each of the three types of medial axis points, (labeled A_1^2, A_1^3, A_3; see below for the A notation) and the associated six types of shock points. First, we show that the tangent and curvature of the medial axis and the speed and acceleration of the shock with respect to time of propagation, i.e., first and second order geometric and dynamic properties, are sufficient to determine the boundary tangent and curvature at corresponding points of the boundary. This implies that a rather coarse sampling of the symmetry axis, its tangent, curvature, speed, and acceleration is sufficient to regenerate accurately a local neighborhood of shape at regular axis points (A_1^2). We also show how higher order differential properties of the axis can be related to the higher-order differential properties of the boundary of the same order. Second, we examine the reconstruction of shape at branch points (A_1^3) where three regular branches are joined. We show that the three pairs of geometry (that is, curvature) and dynamics (that is, acceleration) must satisfy certain constraints. Finally, we derive similar results for the end points of shock branches (A_3 points). These formulas completely specify the local reconstruction of a shape from its shock-graph or medial axis and the conditions required to form a coherent shape from the medial axis.
[1] 895 H. Blum, Biological Shape and Visual Science J. Theoretical Biology, vol. 38, pp. 205-287, 1973.[2] H. Blum and R.N. Nagel, Shape Description Using Weighted Symmetric Axis Features Pattern Recognition, vol. 10, pp. 167-180, 1978.[3] T. Fletcher, S. Pizer, A. Thall, and A. Gash, Shape Modeling and Image Visualization in 3D with M-Rep Object Models Technical Report TR01-004, Dept. of Computer Science, Univ. of North Carolina, 2001.[4] D. Fritsch, S. Pizer, L. Yu, and V. Johnson, E. Chaney, Localization and Segmentation of Medical Image Objects Using Deformable Shape Loci Information Processing in Medical Imaging, vol. 1230, pp. 127-140, 1997.[5] 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. [6] 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.[7] P.J. Giblin and B.B. Kimia, On the Local Form of Symmetry Sets, and Medial Axes, and Shocks in 3D Proc. IEEE CS Conf. Computer Vision and Pattern Recognition, pp. 566-573, June 2000.[8] T. Igarashi, Teddy: A 3D Free-Form Drawing System Personal Comm., www.mtl.t.u-tokyo.ac.jptakeo, 1998.[9] B.B. Kimia, J. Chan, D. Bertrand, S. Coe, Z. Roadhouse, and H. Tek, A Shock-Based Approach for Indexing of Image Databases Using Shape Proc. SPIE's Multimedia Storage and Archiving Systems II, vol. 3229, pp. 288-302, Nov. 1997.[10] S.T.M. Teichmann, Assisted Articulation of Closed Polygonal Models Proc. SIGGRAPH, 1998.[11] S. Pizer, D. Fritsch, V. Johnson, and E. Chaney, Segmentation, Registration, and Measurement of Shape Variation via Image Object Shape IEEE Trans. Medical Imaging, 2000.[12] S.M. Pizer, P.T. Fletcher, Y. Fridman, D.S. Fritsch, A.G. Gash, J.M. Glotzer, S. Joshi, A. Thall, G. Tracton, P. Yushkevich, and E.L. Chaney, Deformable M-Reps for 3D Medical Image Segmentation Medical Image Analysis, 2000.[13] R. Plankers and P. Fua, Tracking and Modeling People in Video Sequences Computer Vision and Image Understanding, vol. 81, no. 3, 2001.[14] 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.[15] D. Shaked and A. Bruckstein, The Curve Axis Computer Vision and IU vol. 63, no. 2, pp. 367-379, Mar. 1996.[16] 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.[17] J. Shen and D. Thalmann, Interactive Shape Design Using Metaballs and Splines Proc. Implicit Surfaces, 1995.[18] J. Shen and D. Thalmann, Fast Realistic Human Body Deformation for Animation and VR Applications Computer Graphics Int'l, pp. 166-174, 1996.[19] K. Siddiqi and B.B. Kimia, A Shock Grammar for Recognition Proc. Conf. Computer Vision and Pattern Recognition, pp. 507-513, 1996.[20] K. Siddiqi, B.B. Kimia, A.R. Tannenbaunm, and S.W. Zucker, On the Psychophysics of the Shape Triangle Vision Research, vol. 41, no. 9, pp. 1153-1178, 2001.[21] K. Siddiqi, K.J. Tresness, and B.B. Kimia, Parts of Visual Form: Ecological and Psychophysical Aspects Perception, vol. 25, pp. 399-424, 1996.[22] H. Tek, The Role of Symmetry Maps in Representing Objects in Images PhD dissertation, Division of Eng., Brown Univ., Providence, RI, July 1999.[23] R.C. Zeleznik, K. Herndon, and J.F. Hughes, SKETCH: An Interface for Sketching 3D Scenes Proc. SIGGRAPH Computer Graphics '96, pp. 163-170, Aug. 1996.[24] S.W. Zucker, K. Siddiqi, B.B. Kimia, and A. Tannenbaum, Categorical Features in Shape Perception Proc. Assoc. Research in Vision and Opthalmology Conf., May 1999.[25] K. Siddiqi, A. Shokoufandeh, S. Dickinson, and S. Zucker, Shock Graphs and Shape Matching Int'l J. Computer Vision, vol. 35, no. 1, pp. 13-32, Nov. 1999.[26] M. Pelillo, K. Siddiqi, and S.W. Zucker, “Matching Hierarchical Structures Using Association Graphs,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 21, no. 11, pp. 1105-1120, 1999.[27] D. Siersma, Properties of Conflict Sets in the Plane Geometry and Topology of Caustics, S. Janeczko and V.M. Zakalyukin, eds., vol. 50, pp. 267-276, 1999.
Index Terms:
Shape, reconstruction, shape modeling, symmetry set, shocks, medial axis, medial geometry, shock dynamics.
Citation:
Peter J. Giblin, Benjamin B. Kimia, "On the Intrinsic Reconstruction of Shape from Its Symmetries," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 7, pp. 895-911, July 2003, doi:10.1109/TPAMI.2003.1206518
Usage of this product signifies your acceptance of the
Terms of Use.
|
|
|
|
|
|
|
|
