Niloy J. Mitra
Leonidas J. Guibas
Mark Pauly
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.
Supplemental Material
- Alliez, P., Cohen-Steiner, D., Devillers, O., Levy, B., and Desbrun, M. 2003. Anisotropic polygonal remeshing. ACM TOG 22, 3, 485--493. Google Scholar
Digital Library
- Alt, H., Mehlhorn, K., Wagener, H., and Welzl, E. 1988. Congruence, similarity and symmetries of geometric objects. Discrete Comput. Geom. 3, 237--256.Google ScholarDigital Library
- 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.Google Scholar
- Amenta, N., and Bern, M. 1998. Surface reconstruction by voronoi filtering. In Symposium on Computational Geometry, 39--48. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Atallah, M. 1985. On symmetry detection. IEEE Trans. on Computers 34, 7, 663--666.Google ScholarDigital Library
- Boissonnat, J. D., and Oudot, S. 2003. Provably good surface sampling and approximation. In Symposium on Geometry Processing, 9--18. Google ScholarDigital Library
- Cohen-Steiner, D., and Morvan, J.-M. 2003. Restricted delaunay triangulations and normal cycle. In Symposium on Computational Geometry, 312--321. Google ScholarDigital Library
- Comaniciu, D., and Meer, P. 2002. Mean shift: A robust approach toward feature space analysis. IEEE PAMI 24, 603--609. Google ScholarDigital Library
- Cox, T., and Cox, M. 1994. Multidimensional Scaling. Chapman and Hall, London.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, vol. 24, 381--395. Google ScholarDigital Library
- Gal, R., and Cohen-Or, D. 2006. Salient geometric features for partial shape matching and similarity. vol. 25(1), to appear. Google ScholarDigital Library
- Gonnet, G. 1981. Expected length of the longest probe sequence in hash code searching. In Journal of the Association for Computing Machinery, 289--304. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Hough, P. 1959. Machine analysis of bubble chamber pictures. In International Conference on High Energy Accelerators and Instrumentation.Google Scholar
- James, D. L., and Twigg, C. D. 2005. Skinning mesh animations. ACM TOG 24, 3, 399--407. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2004. Symmetry descriptors and 3d shape matching. In Symposium on Geometry Processing, 116--125. Google ScholarDigital Library
- Klein, F. 1893. Vergleichende betrachtungen ber neuere geometrische forschungen. Mathematische Annalen 43.Google Scholar
- Lamdan, Y., and Wolfson, H. J. 1988. Geometric hashing: A general and efficient model-based recognition scheme. In Proceedings of ICCV, 238--249.Google Scholar
- 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. Google ScholarDigital Library
- Loy, G., and Eklundh, J. 2006. Detecting symmetry and symmetric constellations of features. In Proceedings of ECCV, to appear.Google Scholar
- Magnus, W., Karrass, A., and Solitar, D. 2004. Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations. Dover.Google Scholar
- Manay, S., Hong, B.-W., Yezzi, A. J., and Soatto, S. 2004. Integral invariant signatures. In Proceedings of ECCV, 87--99.Google Scholar
- 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. Google ScholarDigital Library
- Motwani, R., and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press. Google ScholarDigital Library
- Raab, M., and Steger, A. 1998. "balls into bins" --- A simple and tight analysis. Lecture Notes in Computer Science. Google ScholarDigital Library
- Rusinkiewicz, S., and Levoy, M. 2001. Efficient variants of the icp algorithm. In 3DIM, 145--152.Google Scholar
- Sun, C., and Sherrah, J. 1997. 3d symmetry detection using the extended gaussian image. IEEE PAMI 19. Google ScholarDigital Library
- Thompson, D. W. 1961. On Growth and Form. Cambridge.Google Scholar
- 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. Google ScholarDigital Library
- Wolter, J., Woo, T., and Volz, R. 1985. Optimal algorithms for symmetry detection in two and three dimensions. The Visual Computer.Google Scholar
- Zabrodsky, H., Peleg, S., and Avnir, D. 1995. Symmetry as a continuous feature. IEEE PAMI 17. Google ScholarDigital Library
Index Terms
- Partial and approximate symmetry detection for 3D geometry
Recommendations
Partial and approximate symmetry detection for 3D geometry
"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 ...
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 ...
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 ...
Comments