TL;DR
FAST (Fourier Accelerated Symmetry Transform) is a training-free, geometric framework that detects multiple reflection symmetries in 3D shapes in just a few milliseconds. By representing geometric votes as a signal in the spherical-harmonic domain and applying the Funk-Hecke theorem, it achieves state-of-the-art accuracy while running over 100× faster than previous GPU-based methods.
What Problem Does This Paper Address?
Reflection symmetry is a cornerstone of 3D shape analysis, essential for tasks like object recognition and reconstruction. However, detecting these symmetries—especially when an object has multiple planes of symmetry or is corrupted by noise—is computationally grueling.
Traditional "voting" methods (similar to a Hough Transform) work by having pairs of points on a surface "vote" for a potential symmetry plane. The problem is the search space: a plane in 3D is defined by its orientation and its offset from the origin. Searching this 3D space is slow. While recent deep learning approaches have tried to solve this, they often struggle with generalization or require massive amounts of labeled training data. The authors of this paper sought a purely geometric, training-free method that doesn't sacrifice speed for accuracy.
Methods
The authors introduce FAST, which follows a "propose-and-verify" strategy. The pipeline consists of several clever optimizations:
- Search Space Reduction: The authors exploit the fact that any global reflection plane must pass through the shape's centroid. By centering the shape, they eliminate the need to search for plane offsets, reducing the search space from 3D to 2D (just plane orientations on the projective sphere $RP^2$).
- Geometric Pair Voting & Witnessing: Pairs of surface points suggest candidate planes. To filter out "garbage" votes, FAST uses "witness points"—randomly sampled points that check if the suggested plane actually reflects the local geometry correctly before the vote is counted.
- Harmonic Field Computation: This is the core innovation. Instead of accumulating votes in a clunky discrete grid, FAST treats the votes as a continuous signal on a sphere.
- The Funk-Hecke Shortcut: Smoothing this signal (to find the strongest peaks) is usually expensive. FAST uses the Funk-Hecke theorem, the spherical equivalent of the Fourier convolution theorem. This allows them to perform Gaussian smoothing as a simple multiplication in the spherical-harmonic domain. This mathematical trick decouples the complexity from the number of directions being searched, allowing for incredibly dense sampling at a fraction of the cost.
Datasets
The researchers evaluated FAST on two main benchmarks:
- PRS (Planar Reflective Symmetry): A standard benchmark containing 750 test shapes, mostly common objects with 1–3 symmetry planes.
- ANALYTIC (New): Introduced in this paper, this benchmark consists of 120 procedurally generated, highly symmetric polyhedra (like prisms and Platonic solids) with 3–15 exact reflection planes. This was designed to test the limits of multi-plane detection.
Key Insights and Ideas
- Spectral Acceleration is a Game Changer: By moving the voting process into the spherical-harmonic domain, the authors turned a heavy computational burden into a light one. The complexity drops from $O(N_u L^2)$ to $O(L^3 + N_u)$, where $L$ is the bandlimit and $N_u$ is the number of directions.
- Centroid Consistency: Simply assuming the plane passes through the centroid is a powerful prior that drastically simplifies the geometry without losing much real-world applicability for global symmetry.
- Continuous vs. Discrete: By using a continuous harmonic field rather than a discrete histogram, FAST can perform precise sub-grid refinement of symmetry planes, leading to much lower angular errors.
Key Results
FAST sets a new bar for both speed and accuracy in 3D symmetry detection:
- Speed: It achieves GPU inference in under 4 ms per shape. As shown in Figure 1, this makes it over 100× faster than the next-best GPU baseline (E3Sym) and orders of magnitude faster than traditional CPU methods.
- Accuracy: It achieved the highest $F_1$ scores on both benchmarks (0.861 on PRS and 0.947 on ANALYTIC).
- Robustness: The method remains highly effective even under significant geometric noise (up to 5% RMS displacement).
Qualitatively, FAST is able to recover complex symmetry sets for shapes like tetrahedrons and octahedrons even when the surfaces are heavily distorted by noise.
Limitations and Future Work
- Global Symmetry Only: Because the method relies on the centroid-passing assumption, it is designed for global reflection symmetry. It would likely need significant modification to detect partial or local symmetries where the plane does not pass through the object's center of mass.
- Reflection Focus: The current work focuses strictly on reflection. Extending this harmonic approach to detect rotational symmetries or other transformation groups is a logical next step suggested by the authors.
Summary updated