article

Partial and approximate symmetry detection for 3D geometry

Authors:

Niloy J. Mitra,

Leonidas J. Guibas,

Mark PaulyAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 25, Issue 3

Pages 560 - 568

https://doi.org/10.1145/1141911.1141924

Published: 01 July 2006 Publication History

Abstract

"Symmetry is a complexity-reducing concept [...]; seek it every-where." - Alan J. PerlisMany natural and man-made objects exhibit significant symmetries or contain repeated substructures. This paper presents a new algorithm that processes geometric models and efficiently discovers and extracts a compact representation of their Euclidean symmetries. These symmetries can be partial, approximate, or both. The method is based on matching simple local shape signatures in pairs and using these matches to accumulate evidence for symmetries in an appropriate transformation space. A clustering stage extracts potential significant symmetries of the object, followed by a verification step. Based on a statistical sampling analysis, we provide theoretical guarantees on the success rate of our algorithm. The extracted symmetry graph representation captures important high-level information about the structure of a geometric model which in turn enables a large set of further processing operations, including shape compression, segmentation, consistent editing, symmetrization, indexing for retrieval, etc.

Supplementary Material

JPG File (p560-mitra-high.jpg)

Download
12.27 KB

JPG File (p560-mitra-low.jpg)

Download
9.90 KB

Low Resolution (p560-mitra-high.mov)

Download
24.15 MB

Low Resolution (p560-mitra-low.mov)

Download
9.73 MB

References

[1]

Alliez, P., Cohen-Steiner, D., Devillers, O., Levy, B., and Desbrun, M. 2003. Anisotropic polygonal remeshing. ACM TOG 22, 3, 485--493.

Digital Library

[2]

Alt, H., Mehlhorn, K., Wagener, H., and Welzl, E. 1988. Congruence, similarity and symmetries of geometric objects. Discrete Comput. Geom. 3, 237--256.

Digital Library

[3]

Amato, N. M., Bayazit, O. B., Dale, L. K., Jones, C., and Vallejo, D. 2000. Choosing good distance metrics and local planners for probabilistic roadmap methods. In IEEE Trans. on Robotics and Automation, 442--447.

[4]

Amenta, N., and Bern, M. 1998. Surface reconstruction by voronoi filtering. In Symposium on Computational Geometry, 39--48.

Digital Library

[5]

Arias-Castro, E., Donoho, D. L., and Huo, X. 2006. Adaptive multiscale detection of filamentary structures in a background of uniform random points. Annals of Statistics 34, 1.

[6]

Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., and Wu, A. Y. 1998. An optimal algorithm for approximate nearest neighbor searching. In Journal of the ACM, vol. 45, 891--923.

Digital Library

[7]

Atallah, M. 1985. On symmetry detection. IEEE Trans. on Computers 34, 7, 663--666.

Digital Library

[8]

Boissonnat, J. D., and Oudot, S. 2003. Provably good surface sampling and approximation. In Symposium on Geometry Processing, 9--18.

Digital Library

[9]

Cohen-Steiner, D., and Morvan, J.-M. 2003. Restricted delaunay triangulations and normal cycle. In Symposium on Computational Geometry, 312--321.

Digital Library

[10]

Comaniciu, D., and Meer, P. 2002. Mean shift: A robust approach toward feature space analysis. IEEE PAMI 24, 603--609.

Digital Library

[11]

Cox, T., and Cox, M. 1994. Multidimensional Scaling. Chapman and Hall, London.

[12]

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, vol. 24, 381--395.

Digital Library

[13]

Gal, R., and Cohen-Or, D. 2006. Salient geometric features for partial shape matching and similarity. vol. 25(1), to appear.

Digital Library

[14]

Gonnet, G. 1981. Expected length of the longest probe sequence in hash code searching. In Journal of the Association for Computing Machinery, 289--304.

Digital Library

[15]

Hofer, M., Pottmann, H., and Ravani, B. 2004. From curve design algorithms to the design of rigid body motions. In The Visual Computer, 279--297.

Digital Library

[16]

Hough, P. 1959. Machine analysis of bubble chamber pictures. In International Conference on High Energy Accelerators and Instrumentation.

[17]

James, D. L., and Twigg, C. D. 2005. Skinning mesh animations. ACM TOG 24, 3, 399--407.

Digital Library

[18]

Kazhdan, M. M., Chazelle, B., Dobkin, D. P., Finkel-Stein, A., and Funkhouser, T. A. 2002. A reflective symmetry descriptor. In Proceedings of ECCV, 642--656.

Digital Library

[19]

Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2004. Symmetry descriptors and 3d shape matching. In Symposium on Geometry Processing, 116--125.

Digital Library

[20]

Klein, F. 1893. Vergleichende betrachtungen ber neuere geometrische forschungen. Mathematische Annalen 43.

[21]

Lamdan, Y., and Wolfson, H. J. 1988. Geometric hashing: A general and efficient model-based recognition scheme. In Proceedings of ICCV, 238--249.

[22]

Liu, Y., Collins, R., and Tsin, Y. 2004. A computational model for periodic pattern perception based on frieze and wall-paper groups. In IEEE PAMI, 354--371.

Digital Library

[23]

Loy, G., and Eklundh, J. 2006. Detecting symmetry and symmetric constellations of features. In Proceedings of ECCV, to appear.

[24]

Magnus, W., Karrass, A., and Solitar, D. 2004. Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations. Dover.

[25]

Manay, S., Hong, B.-W., Yezzi, A. J., and Soatto, S. 2004. Integral invariant signatures. In Proceedings of ECCV, 87--99.

[26]

Mitra, N. J., Gelfand, N., Pottmann, H., and Guibas, L. 2004. Registration of point cloud data from a geometric optimization perspective. In Symposium on Geometry Processing, 23--32.

Digital Library

[27]

Motwani, R., and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press.

Digital Library

[28]

Raab, M., and Steger, A. 1998. "balls into bins" --- A simple and tight analysis. Lecture Notes in Computer Science.

Digital Library

[29]

Rusinkiewicz, S., and Levoy, M. 2001. Efficient variants of the icp algorithm. In 3DIM, 145--152.

[30]

Sun, C., and Sherrah, J. 1997. 3d symmetry detection using the extended gaussian image. IEEE PAMI 19.

Digital Library

[31]

Thompson, D. W. 1961. On Growth and Form. Cambridge.

[32]

Tuzel, O., Subbarao, R., and Meer, P. 2005. Simultaneous multiple 3d motion estimation via mode finding on lie groups. In Proceedings of ICCV, vol. 1, 18--25.

Digital Library

[33]

Wolter, J., Woo, T., and Volz, R. 1985. Optimal algorithms for symmetry detection in two and three dimensions. The Visual Computer.

[34]

Zabrodsky, H., Peleg, S., and Avnir, D. 1995. Symmetry as a continuous feature. IEEE PAMI 17.

Digital Library

Cited By

Valarezo Añazco EGuerrero SRivera Lopez POh JRyu GKim T(2024)Deep Learning-Based Ensemble Approach for Autonomous Object Manipulation with an Anthropomorphic Soft Robot HandElectronics10.3390/electronics1302037913:2(379)Online publication date: 17-Jan-2024
https://doi.org/10.3390/electronics13020379
Gözütok U(2024)Computing affine equivalences and symmetries of trigonometric curves in arbitrary dimensionHacettepe Journal of Mathematics and Statistics10.15672/hujms.127766553:3(637-651)Online publication date: 27-Jun-2024
https://doi.org/10.15672/hujms.1277665
Zhu ZNan LXie HChen HWang JWei MQin J(2024)CSDN: Cross-Modal Shape-Transfer Dual-Refinement Network for Point Cloud CompletionIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.323606130:7(3545-3563)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3236061
Show More Cited By

Index Terms

Partial and approximate symmetry detection for 3D geometry
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Partial and approximate symmetry detection for 3D geometry
SIGGRAPH '06: ACM SIGGRAPH 2006 Papers

"Symmetry is a complexity-reducing concept [...]; seek it every-where." - Alan J. PerlisMany natural and man-made objects exhibit significant symmetries or contain repeated substructures. This paper presents a new algorithm that processes geometric ...
A Reflective Symmetry Descriptor for 3D Models

Computing reflective symmetries of 2D and 3D shapes is a classical problem in computer vision and computational geometry. Most prior work has focused on finding the main axes of symmetry, or determining that none exists. In this paper we introduce a new ...
Symmetry in 3D Geometry: Extraction and Applications

The concept of symmetry has received significant attention in computer graphics and computer vision research in recent years. Numerous methods have been proposed to find, extract, encode and exploit geometric symmetries and high-level structural ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 25, Issue 3

July 2006

742 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1141911

Issue’s Table of Contents

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2006

Published in TOG Volume 25, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

456
Total Citations
View Citations
3,117
Total Downloads

Downloads (Last 12 months)129
Downloads (Last 6 weeks)11

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Valarezo Añazco EGuerrero SRivera Lopez POh JRyu GKim T(2024)Deep Learning-Based Ensemble Approach for Autonomous Object Manipulation with an Anthropomorphic Soft Robot HandElectronics10.3390/electronics1302037913:2(379)Online publication date: 17-Jan-2024
https://doi.org/10.3390/electronics13020379
Gözütok U(2024)Computing affine equivalences and symmetries of trigonometric curves in arbitrary dimensionHacettepe Journal of Mathematics and Statistics10.15672/hujms.127766553:3(637-651)Online publication date: 27-Jun-2024
https://doi.org/10.15672/hujms.1277665
Zhu ZNan LXie HChen HWang JWei MQin J(2024)CSDN: Cross-Modal Shape-Transfer Dual-Refinement Network for Point Cloud CompletionIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.323606130:7(3545-3563)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3236061
Zhuang ZZhi ZHan TChen YChen JWang CCheng MZhang XQin NMa L(2024)A Survey of Point Cloud CompletionIEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing10.1109/JSTARS.2024.336247617(5691-5711)Online publication date: 2024
https://doi.org/10.1109/JSTARS.2024.3362476
Caballero RPiękos PFeron ESchmidhuber J(2024)Utilizing a Malfunctioning 3D Printer by Modeling Its Dynamics with Machine Learning2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10611304(15562-15569)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10611304
Figueiredo LIvson PCeles W(2024)Unsupervised method for identifying shape instances on 3D CAD modelsComputers and Graphics10.1016/j.cag.2023.08.018116:C(228-238)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1016/j.cag.2023.08.018
Zhao XChen YYang CFang L(2024)FuseNet: a multi-modal feature fusion network for 3D shape classificationThe Visual Computer10.1007/s00371-024-03581-2Online publication date: 26-Jul-2024
https://doi.org/10.1007/s00371-024-03581-2
Nagar R(2024)Robust extrinsic symmetry estimation in 3D point cloudsThe Visual Computer10.1007/s00371-024-03313-6Online publication date: 15-Mar-2024
https://doi.org/10.1007/s00371-024-03313-6
Podgorelec DLukač LŽalik B(2023)Reflection Symmetry Detection in Earth Observation DataSensors10.3390/s2317742623:17(7426)Online publication date: 25-Aug-2023
https://doi.org/10.3390/s23177426
Cao ZZhang WWen XDong ZLiu YXiao XYang BWilliams BChen YNeville J(2023)KT-NetProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i1.25101(286-294)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i1.25101
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents