Niloy J. Mitra
Leonidas J. Guibas
Mark Pauly
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.
Supplemental Material
- Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. ACM Trans. Graph. 24, 3, 617--625. Google Scholar
Digital Library
- Atallah, M. 1985. On symmetry detection. IEEE Trans. on Computers, 663--666. Google ScholarDigital Library
- 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
- 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
- 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
- Cox, T., and Cox, M. 1994. Multidimensional Scaling. Chapman and Hall, London.Google Scholar
- 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
- Faber, G. 1920. Ueber potentialtheorie und konforme abbildung. Sitzungsber. Bayer. Akad. Wiss. Math.-Naturwiss. Kl., 49--64.Google Scholar
- 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
- 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
- Gal, R., and Cohen-Or, D. 2006. Salient geometric features for partial shape matching and similarity. ACM TOG 25, 1. Google ScholarDigital Library
- Garland, M., and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In SIGGRAPH '97, 209--216. Google ScholarDigital Library
- Grunbaum, B. 1963. Measures of symmetry for convex sets. Proc. Symposium Pure Math. 7, 233--270.Google ScholarCross Ref
- Hadwiger, H. 1957. Vorlesungen ueber Inhalt, Oberflaeche und Isoperimetrie. Springer.Google Scholar
- 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
- 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
- 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
- Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2004. Symmetry descriptors and 3d shape matching. In Sympos. on Geometry Processing, 116--125. Google ScholarDigital Library
- 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
- 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
- Pauly, M., Keiser, R., and Gross, M. 2003. Multi-scale feature extraction on point-sampled models. In Proceedings of Eurographics, 281--289.Google Scholar
- 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
- 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
- Schouten, A. 1951. Tensor analysis for physicists. Cambridge Univ. Press.Google Scholar
- 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
- Thrun, S., and Wegbreit, B. 2005. Shape from symmetry. In Int. Conference on Computer Vision. Google ScholarDigital Library
- Wolfson, H. J., and Rigoutsos, I. 1997. Geometric hashing: An overview. IEEE Comput. Sci. Eng. 4, 4, 10--21. Google ScholarDigital Library
- 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
- 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
- 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
Index Terms
- Symmetrization
Recommendations
A planar-reflective symmetry transform for 3D shapes
SIGGRAPH '06: ACM SIGGRAPH 2006 PapersSymmetry is an important cue for many applications, including object alignment, recognition, and segmentation. In this paper, we describe a planar reflective symmetry transform (PRST) that captures a continuous measure of the reflectional symmetry of a ...
Symmetrization
SIGGRAPH '07: ACM SIGGRAPH 2007 papersWe 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 ...
Symmetrization of 2D Polygonal Shapes Using Mixed-Integer Programming
AbstractSymmetry widely exists in nature and man-made shapes, but it is unavoidably distorted during the process of growth, design, digitalization, and reconstruction steps. To enhance symmetry, traditional methods follow the detect-then-...
Highlights- An effective method for the symmetrization of general shapes represented as 2D polygons.
Comments