“Symmetrization” by Mitra, Guibas and Pauly

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.

1. Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3, 617–625. Google ScholarDigital Library
2. Atallah, M. 1985. On symmetry detection. IEEE Trans. on Computers, 663–666. Google ScholarDigital Library
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.Google Scholar
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.Google Scholar
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. Google ScholarDigital Library
6. Cox, T., and Cox, M. 1994. Multidimensional Scaling. Chapman and Hall, London.Google Scholar
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. Google ScholarDigital Library
8. Faber, G. 1920. Ueber potentialtheorie und konforme abbildung. Sitzungsber. Bayer. Akad. Wiss. Math.-Naturwiss. Kl., 49–64.Google Scholar
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. Google ScholarDigital Library
10. Funkhouser, T., and Shilane, P. 2006. Partial matching of 3D shapes with priority-driven search. In Symposium on Geometry Processing, 131–142. Google ScholarDigital Library
11. Gal, R., and Cohen-Or, D. 2006. Salient geometric features for partial shape matching and similarity. ACM TOG 25, 1. Google ScholarDigital Library
12. Garland, M., and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In SIGGRAPH ’97, 209–216. Google ScholarDigital Library
13. Grunbaum, B. 1963. Measures of symmetry for convex sets. Proc. Symposium Pure Math. 7, 233–270.Google ScholarCross Ref
14. Hadwiger, H. 1957. Vorlesungen ueber Inhalt, Oberflaeche und Isoperimetrie. Springer.Google Scholar
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. Google ScholarCross Ref
16. Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph. 24, 3, 1134–1141. Google ScholarDigital Library
17. Kazhdan, M. M., Chazelle, B., Dobkin, D. P., Finkelstein, A., and Funkhouser, T. A. 2002. A reflective symmetry descriptor. In ECCV, 642–656. Google ScholarDigital Library
18. Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2004. Symmetry descriptors and 3d shape matching. In Sympos. on Geometry Processing, 116–125. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
21. Pauly, M., Keiser, R., and Gross, M. 2003. Multi-scale feature extraction on point-sampled models. In Proceedings of Eurographics, 281–289.Google Scholar
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. Google ScholarDigital Library
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. Google ScholarDigital Library
24. Schouten, A. 1951. Tensor analysis for physicists. Cambridge Univ. Press.Google Scholar
25. Simari, P., Kalogerakis, E., and Singh, K. 2006. Folding meshes: Hierarchical mesh segmentation based on planar symmetry. In Proc. Symposium on Geometry Processing. Google ScholarDigital Library
26. Thrun, S., and Wegbreit, B. 2005. Shape from symmetry. In Int. Conference on Computer Vision. Google ScholarDigital Library
27. Wolfson, H. J., and Rigoutsos, I. 1997. Geometric hashing: An overview. IEEE Comput. Sci. Eng. 4, 4, 10–21. Google ScholarDigital Library
28. Wolter, J., Woo, T., and Volz, R. 1985. Optimal algorithms for symmetry detection in two and three dimensions. The Visual Computer, 37–48.Google Scholar
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. Google ScholarDigital Library
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. Google ScholarDigital Library