Probably Approximately Symmetric: Fast 3D Symmetry Detection with Global Guarantees
Simon Korman*, Roee Litman*, Shai Avidan, Alex Bronstein
School of Electrical Engineering, Tel-Aviv University
[Abstract] [Paper] [Code] [Supplementary Material]
[Abstract] [Paper] [Code] [Supplementary Material]
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 sub-linear 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.