Symmetrization

ABSTRACT

We present a symmetrization algorithm for geometric objects. Our algorithm enhances approximate symmetries of a model while minimally altering its shape. Symmetrizing deformations are formulated as an optimization process that couples the spatial domain with a transformation configuration space, where symmetries can be expressed more naturally and compactly as parametrized point-pair mappings. We derive closed-form solution for the optimal symmetry transformations, given a set of corresponding sample pairs. The resulting optimal displacement vectors are used to drive a constrained deformation model that pulls the shape towards symmetry. We show how our algorithm successfully symmetrizes both the geometry and the discretization of complex 2D and 3D shapes and discuss various applications of such symmetrizing deformations.

REFERENCES

• 1: Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3, 617--625.
• 2: Atallah, M. 1985. On symmetry detection. IEEE Trans. on Computers, 663--666.
• 3: Attali, D., Boissonnat, J., and Edelsbrunner, H. 2004. Stability and computation of the medial axis --- a state-of-the-art report. Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration.
• 4: Blum, H. 1967. A transformation for extracting descriptors of shape. In Models for the Perception of Speech and Visual Forms, MIT Press, 362--380.
• 5: Botsch, M., Pauly, M., Gross, M., and Kobbelt, L. 2006. Primo: Coupled prisms for intuitive surface modeling. In Proc. Symposium on Geometry Processing, 11--22.
• 6: Cox, T., and Cox, M. 1994. Multidimensional Scaling. Chapman and Hall, London.
• 7: Eggert, D. W., Lorusso, A., and Fisher, R. B. 1997. Estimating 3-d rigid body transformations: a comparison of four major algorithms. In Mach. Vision Appl., vol. 9(5-6), 272--290.
• 8: Faber, G. 1920. Ueber potentialtheorie und konforme abbildung. Sitzungsber. Bayer. Akad. Wiss. Math.-Naturwiss. Kl., 49--64.
• 9: Fischler, M. A., and Bolles, R. C. 1981. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. In Comm. of the ACM, 381--395.
• 10: Funkhouser, T., and Shilane, P. 2006. Partial matching of 3D shapes with priority-driven search. In Symposium on Geometry Processing, 131--142.
• 11: Gal, R., and Cohen-Or, D. 2006. Salient geometric features for partial shape matching and similarity. ACM TOG 25, 1.
• 12: Garland, M., and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In SIGGRAPH '97, 209--216.
• 13: Grunbaum, B. 1963. Measures of symmetry for convex sets. Proc. Symposium Pure Math. 7, 233--270.
• 14: Hadwiger, H. 1957. Vorlesungen ueber Inhalt, Oberflaeche und Isoperimetrie. Springer.
• 15: Hofer, M., Pottmann, H., and Ravani, B. 2004. From curve design algorithms to the design of rigid body motions. The Visual Computer, 279--297.
• 16: Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph. 24, 3, 1134--1141.
• 17: Kazhdan, M. M., Chazelle, B., Dobkin, D. P., Finkelstein, A., and Funkhouser, T. A. 2002. A reflective symmetry descriptor. In ECCV, 642--656.
• 18: Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2004. Symmetry descriptors and 3d shape matching. In Sympos. on Geometry Processing, 116--125.
• 19: Martinet, A., Soler, C., Holzschuch, N., and Sillion, F. 2006. Accurate detection of symmetries in 3d shapes. ACM Trans. Graph. 25, 2, 439--464.
• 20: Mitra, N. J., Guibas, L. J., and Pauly, M. 2006. Partial and approximate symmetry detection for 3d geometry. ACM Trans. Graph. 25, 3, 560--568.
• 21: Pauly, M., Keiser, R., and Gross, M. 2003. Multi-scale feature extraction on point-sampled models. In Proceedings of Eurographics, 281--289.
• 22: Pauly, M., Mitra, N. J., Giesen, J., Gross, M., and Guibas, L. 2005. Example-based 3d scan completion. In Symposium on Geometry Processing, 23--32.
• 23: Podolak, J., Shilane, P., Golovinskiy, A., Rusinkiewicz, S., and Funkhouser, T. 2006. A planar-reflective symmetry transform for 3d shapes. ACM Trans. Graph. 25, 3, 549--559.
• 24: Schouten, A. 1951. Tensor analysis for physicists. Cambridge Univ. Press.
• 25: Simari, P., Kalogerakis, E., and Singh, K. 2006. Folding meshes: Hierarchical mesh segmentation based on planar symmetry. In Proc. Symposium on Geometry Processing.
• 26: Thrun, S., and Wegbreit, B. 2005. Shape from symmetry. In Int. Conference on Computer Vision.
• 27: Wolfson, H. J., and Rigoutsos, I. 1997. Geometric hashing: An overview. IEEE Comput. Sci. Eng. 4, 4, 10--21.
• 28: Wolter, J., Woo, T., and Volz, R. 1985. Optimal algorithms for symmetry detection in two and three dimensions. The Visual Computer, 37--48.
• 29: Zabrodsky, H., and Weinshall, D. 1997. Using bilateral symmetry to improve 3D reconstruction from image sequences. Computer Vision and Image Understanding: CVIU 67, 1, 48--57.
• 30: Zabrodsky, H., Peleg, S., and Avnir, D. 1995. Symmetry as a continuous feature. IEEE Transactions on Pattern Analysis and Machine Intelligence 17, 12, 1154--1166.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Keywords:
correspondence, matching, shape analysis, shape optimization, symmetry