Symmetry Detection
Motivation
• Compression
• Reconstruction
• Classification
• Analysis
• Alignment
• Matching
• Etc.
1
Definition
A collection of:
points/lines/curves/triangles/surfaces/volumes,
has reflective symmetry w.r.t. some plane p if
the reflection Refp through p fixes the
collection.
p p
Definition
A collection of:
points/lines/curves/triangles/surfaces/volumes,
has rotational symmetry of order k w.r.t.
some axis p if the rotation Rotpk by an angle
of 360o/k about p fixes the collection.
p p
k=4 k=2
2
Outline
• Geometry based approaches
• Geometry/descriptor based approaches
• Descriptor based approaches
Discrete Symmetry
String matching
A
C B
A A S=ABACABAC
B C
A
3
Discrete (Rotational) Symmetry
Search for non-trivial repeating patterns in
concatanation (S_ S·S):
S·S= A B A C A B A C A B A C A B A C
ABACABAC
A ABACABAC
C B ABACABAC
ABACABAC
ABACABAC S
A A ABACABAC
ABACABAC
B C ABACABAC
A
Discrete (Reflective) Symmetry
Search for non-trivial repeating patterns in
concatanation (St_ S·S):
S·S= A B A C A B A C A B A C A B A C
CABACABA
A CABACABA
C B CABACABA
CABACABA
CABACABA St
A A CABACABA
CABACABA
B C CABACABA
A
4
Discrete (Reflective) Symmetry
Search for non-trivial repeating patterns in
concatanation (St_ S·S):
S·S= A B A C A B A C A B A C A B A C
CABACABA
A CABACABA
C B CABACABA
CABACABA
CABACABA St
A A CABACABA
CABACABA
B C CABACABA
A
Outline
• Geometry based approaches
• Geometry/descriptor based approaches
• Descriptor based approaches
5
Points on a Circle
Sort by angle and compute angle
α between adjacent points
β
α
S=ααβχβ
Generate string from
β ordered list of angles
IEEE, 1985. Atallah
The Visual Computer, 1985. Wolter et al.
χ Information Processing Letters, 1986. Highnam
Points on a Circle
Rotational Symmetry
S·S= α α β χ β α α β χ Find rotational and reflective
α α β χ ββ symmetries of string:
ααβχβ
ααβχβ S
ααβχβ
ααβχβ
Reflective Symmetry
S·S= α α β χ β α α β χ
β χ β α αβ
βχβαα
βχβαα St
βχβαα
βχβαα
6
Points in 2D
asdf
Discussion
Pro:
• Evaluates all symmetries
Cons:
• Only perfect symmetry
• Does not generalize to 3D
Continuous Measure of Symmetry No
Identifies All Symmetries Yes
3D No
7
Symmetry Distance
Measure of symmetry as distance to nearest
symmetric model:
Initial model Nearest 3-fold Symmetry Distance
symmetric
IWVF, 1994. Zabrodsky et al.
IEEE, 1995. Zabrodsky et al.
Symmetry Distance
Nearest symmetric model can be obtained by
folding:
IWVF, 1994. Zabrodsky et al.
IEEE, 1995. Zabrodsky et al.
8
Symmetry Distance
Needs establishment of correspondences
IWVF, 1994. Zabrodsky et al.
IEEE, 1995. Zabrodsky et al.
Discussion
Pro:
• A continuous measure of symmetry
• Generalizes to 3D
Cons:
• Does not identify potential symmetries
• Depends on establishing of correspondences
Continuous Measure of Symmetry Yes
Identifies All Symmetries No
3D Yes
9
Outline
• Geometry based approaches
• Geometry/descriptor based approaches
• Descriptor based approaches
Approach
Leverage shape descriptor to obtain a
structured shape representation: 2D Shape
• Correspondences become implicit
Descriptor
3D Shape Descriptor Descriptor
10
PCA
PCA of a 3D model gives an ellipsoid:
IEEE TENCON, 1996. O’Mara et al.
IEEE, 1997. Sun et al.
Symmetry of the Ellipsoid
Planes of reflective symmetry of an ellipsoid
are perpendicular to principal axes
IEEE TENCON, 1996. O’Mara et al.
IEEE, 1997. Sun et al.
11
Symmetry of the Ellipsoid
Axes of rotational symmetry of an ellipsoid:
• Are principal axes
• Only occur if the other two axes have the
same length (when orderg 2)
IEEE TENCON, 1996. O’Mara et al.
IEEE, 1997. Sun et al.
Computing Symmetry with PCA
1. Compute the principal axes of a model
2. Identify candidate axes/planes of
symmetry
3. Evaluate quality of candidates by
comparing the shape descriptor (SD) of
initial models with the SDs of the
rotations/reflections.
IEEE TENCON, 1996. O’Mara et al.
IEEE, 1997. Sun et al.
12
Discussion
Pros:
• A continuous measure of symmetry
• Generalizes to 3D
• Addresses the correspondence issue
Con:
• Evaluates each symmetry type independently
Continuous Measure of Symmetry Yes
Evaluates All Symmetries No
3D Yes
Outline
• Geometry based approaches
• Geometry/descriptor based approaches
• Descriptor based approaches
13
Approach
Leverage shape descriptor to obtain a
structured shape representation: 2D Shape
• Possibility for efficient exhaustive
symmetry detection
Descriptor
3D Shape Descriptor Descriptor
Observation
Sub-string based symmetry detection is
efficient but is binary.
Sub-string matching is O(n),
S·S=with
ABA CABACABACABAC
n=|S|
A ABACABAC
ABACABAC
C B ABACABAC
ABACABAC
A A ABACABAC S
ABACABAC
B C ABACABAC
A ABACABAC
14
Circular Function Descriptors
Replace discrete matching of circular string
with correlation of circular function
Correlation is O(b log(b)),
Shape Descriptor
(SD) with |SD|=O(b)
2π
Sym( SD, α ) = SD(t − α ) SD(t ) dt
0 PRL, 1995. Sun
RTI, 1999. Sun et al.
2D Function Descriptors
Generalize to 2D functions by looking at
circular restrictions
SD
Correlation is O(b2 log(b)),
with |SD|=O(b2)
scale factor scale factor scale factor
Sym(SD, γ ) = r1 Sym( , γ ) + r2 Sym( , γ ) + r3 Sym( , γ ) + ...
ECCV, 2002. Kazhdan et al.
15
Spherical Function Descriptors
Use spherical harmonics and Wigner-D
transform to perform rotational correlation.
Correlation is O(b4),
Shape Descriptor
(SD) with |SD|=O(b2)
Sym( SD, R ) = SD( R (t )) R(t ) dt
Sphere
3D Function Descriptors
Generalize to 3D functions by looking at
spherical restrictions
SD
Correlation is O(b4),
with |SD|=O(b3)
scale factor scale factor scale factor
Sym(SD, R) = r1 Sym( , R) + r2 Sym( , R) + r3 Sym( , R) + ...
ECCV, 2002. Kazhdan et al.
16
Summary
• Use shape descriptors for efficiency and
simplicity
• Generalize fast sub-string matching to FFT
• Extend FFT to FST
Sub-String Symmetry PCA FFT FST
Distance
Continuous Measure of Symmetry No Yes Yes Yes Yes
Identifies all Symmetries Yes No No Yes Yes
3D No Yes Yes No Yes
17