“Partial and approximate symmetry detection for 3D geometry” by Mitra, Guibas and Pauly

“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.

1. Alliez, P., Cohen-Steiner, D., Devillers, O., Levy, B., and Desbrun, M. 2003. Anisotropic polygonal remeshing. ACM TOG 22, 3, 485–493. Google ScholarDigital 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.Google ScholarDigital 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.Google Scholar
4. Amenta, N., and Bern, M. 1998. Surface reconstruction by voronoi filtering. In Symposium on Computational Geometry, 39–48. Google ScholarDigital 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.Google ScholarCross Ref
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. Google ScholarDigital Library
7. Atallah, M. 1985. On symmetry detection. IEEE Trans. on Computers 34, 7, 663–666.Google ScholarDigital Library
8. Boissonnat, J. D., and Oudot, S. 2003. Provably good surface sampling and approximation. In Symposium on Geometry Processing, 9–18. Google ScholarDigital Library
9. Cohen-Steiner, D., and Morvan, J.-M. 2003. Restricted delaunay triangulations and normal cycle. In Symposium on Computational Geometry, 312–321. Google ScholarDigital Library
10. Comaniciu, D., and Meer, P. 2002. Mean shift: A robust approach toward feature space analysis. IEEE PAMI 24, 603–609. Google ScholarDigital Library
11. Cox, T., and Cox, M. 1994. Multidimensional Scaling. Chapman and Hall, London.Google Scholar
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. Google ScholarDigital Library
13. Gal, R., and Cohen-Or, D. 2006. Salient geometric features for partial shape matching and similarity. vol. 25(1), to appear. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital Library
16. Hough, P. 1959. Machine analysis of bubble chamber pictures. In International Conference on High Energy Accelerators and Instrumentation.Google Scholar
17. James, D. L., and Twigg, C. D. 2005. Skinning mesh animations. ACM TOG 24, 3, 399–407. Google ScholarDigital 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. Google ScholarDigital Library
19. Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2004. Symmetry descriptors and 3d shape matching. In Symposium on Geometry Processing, 116–125. Google ScholarDigital Library
20. Klein, F. 1893. Vergleichende betrachtungen ber neuere geometrische forschungen. Mathematische Annalen 43.Google Scholar
21. 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
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. Google ScholarDigital Library
23. Loy, G., and Eklundh, J. 2006. Detecting symmetry and symmetric constellations of features. In Proceedings of ECCV, to appear.Google Scholar
24. Magnus, W., Karrass, A., and Solitar, D. 2004. Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations. Dover.Google Scholar
25. Manay, S., Hong, B.-W., Yezzi, A. J., and Soatto, S. 2004. Integral invariant signatures. In Proceedings of ECCV, 87–99.Google Scholar
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. Google ScholarDigital Library
27. Motwani, R., and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press. Google ScholarDigital Library
28. Raab, M., and Steger, A. 1998. “balls into bins” — A simple and tight analysis. Lecture Notes in Computer Science. Google ScholarDigital Library
29. Rusinkiewicz, S., and Levoy, M. 2001. Efficient variants of the icp algorithm. In 3DIM, 145–152.Google Scholar
30. Sun, C., and Sherrah, J. 1997. 3d symmetry detection using the extended gaussian image. IEEE PAMI 19. Google ScholarDigital Library
31. Thompson, D. W. 1961. On Growth and Form. Cambridge.Google Scholar
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. Google ScholarDigital Library
33. Wolter, J., Woo, T., and Volz, R. 1985. Optimal algorithms for symmetry detection in two and three dimensions. The Visual Computer.Google Scholar
34. Zabrodsky, H., Peleg, S., and Avnir, D. 1995. Symmetry as a continuous feature. IEEE PAMI 17. Google ScholarDigital Library