# Probably Approximately Symmetric:
Fast 3D Symmetry Detection with Global Guarantees

[Abstract]
[Paper]
[Code]
[Supplementary Material]

* Equal contributors

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.

### (to appear at Computer Graphics Forum 2014)

[pdf]

[zip (37 KB)]

[pdf]

E O F