Probably Approximately Symmetric: Fast Rigid Symmetry Detection With Global Guarantees

Simple item page
dc.contributor.authorKorman, Simonen_US
dc.contributor.authorLitman, Roeeen_US
dc.contributor.authorAvidan, Shaien_US
dc.contributor.authorBronstein, Alexen_US
dc.contributor.editorDeussen, Oliver and Zhang, Hao (Richard)en_US
dc.date.accessioned2015-03-02T19:44:44Z
dc.date.available2015-03-02T19:44:44Z
dc.date.issued2015en_US
dc.description.abstractWe 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.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.en_US
dc.description.number1en_US
dc.description.sectionheadersArticlesen_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume34en_US
dc.identifier.urihttps://doi.org/10.1111/cgf.12454en_US
dc.publisherCopyright © 2015 The Eurographics Association and John Wiley & Sons Ltd.en_US
dc.titleProbably Approximately Symmetric: Fast Rigid Symmetry Detection With Global Guaranteesen_US
Files
Collections
34-Issue 1