Probably approximately symmetric: Fast rigid symmetry detection with global guarantees
Korman S, Litman R, Avidan S, Bronstein AM. 2015. Probably approximately symmetric: Fast rigid symmetry detection with global guarantees. Computer Graphics Forum. 34(1), 2–13.
Download (ext.)
Journal Article
| Published
| English
Scopus indexed
Author
Korman, Simon;
Litman, Roee;
Avidan, Shai;
Bronstein, Alex M.ISTA 

Abstract
We present a fast algorithm for global rigid symmetry detection with approximation guarantees. The algorithm is guaranteed to find the best approximate symmetry of a given shape, to within a user-specified threshold, with very high probability. Our method uses a carefully designed sampling of the transformation space, where each transformation is efficiently evaluated using a sublinear algorithm. We prove that the density of the sampling depends on the total variation of the shape, allowing us to derive formal bounds on the algorithm's complexity and approximation quality. We further investigate different volumetric shape representations (in the form of truncated distance transforms), and in such a way control the total variation of the shape and hence the sampling density and the runtime of the algorithm. A comprehensive set of experiments assesses the proposed method, including an evaluation on the eight categories of the COSEG data set. This is the first large-scale evaluation of any symmetry detection technique that we are aware of.
Publishing Year
Date Published
2015-02-01
Journal Title
Computer Graphics Forum
Publisher
Wiley
Volume
34
Issue
1
Page
2-13
ISSN
eISSN
IST-REx-ID
Cite this
Korman S, Litman R, Avidan S, Bronstein AM. Probably approximately symmetric: Fast rigid symmetry detection with global guarantees. Computer Graphics Forum. 2015;34(1):2-13. doi:10.1111/cgf.12454
Korman, S., Litman, R., Avidan, S., & Bronstein, A. M. (2015). Probably approximately symmetric: Fast rigid symmetry detection with global guarantees. Computer Graphics Forum. Wiley. https://doi.org/10.1111/cgf.12454
Korman, Simon, Roee Litman, Shai Avidan, and Alex M. Bronstein. “Probably Approximately Symmetric: Fast Rigid Symmetry Detection with Global Guarantees.” Computer Graphics Forum. Wiley, 2015. https://doi.org/10.1111/cgf.12454.
S. Korman, R. Litman, S. Avidan, and A. M. Bronstein, “Probably approximately symmetric: Fast rigid symmetry detection with global guarantees,” Computer Graphics Forum, vol. 34, no. 1. Wiley, pp. 2–13, 2015.
Korman S, Litman R, Avidan S, Bronstein AM. 2015. Probably approximately symmetric: Fast rigid symmetry detection with global guarantees. Computer Graphics Forum. 34(1), 2–13.
Korman, Simon, et al. “Probably Approximately Symmetric: Fast Rigid Symmetry Detection with Global Guarantees.” Computer Graphics Forum, vol. 34, no. 1, Wiley, 2015, pp. 2–13, doi:10.1111/cgf.12454.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level

Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1403.6637