A Graph Matching Approach to Symmetry Detection and Analysis - Computational Intelligence Paradigms in Advanced Pattern Classification - page 123

where is a scale factor. This binary quadratic optimization is known to be np -hard

[SM00], and its solution can be approximated by spectral relaxation

σ

Z T HZ
Z T Z ,

Z ∗ = arg max

Z

Z ∈ R . (13)

Thus, Z ∗ is given by the eigenvector corresponding to the largest eigenvalue λ 1 ,as

this maximizes Eq. 13. This approach can be considered as normalized cut cluster-
ing applied to the set of correspondences c i k j k N 1 N 2

. Namely, we assume that the

1

true correspondences c i k j k M

N 1 N 2 ) form a tightly connected cluster based
on the affinity measure in Eq. 12. In [CSS07] Cour and Shi proposed a doubly-
stochastic normalization of the affinity matrix H , and adding an affinity constraint
over the solution Z to enforce one-to-one matchings.
Given the relaxed solution Z ∗ , we apply the discretization procedure given in
[LH05] to derive an approximation Y to the binary vector Y ∗ . Note that since we are
interested in symmetry analysis, we expect to recover multiple solutions (eigenvec-
tors)

( M

1

Y i K

1 ,where K is the order of symmetry. In the following section we show
how to estimate K based on the eigenvalues of the affinity matrix H , and how to
recover the symmetry correspondences. We then compute the symmetry centers for
rotational symmetry, and axes of reflection for reflectional symmetry.

4 Spectral Symmetry Analysis

In this section we apply the spectral matching to symmetry analysis and derive the
spectral symmetry analysis scheme. We start in Section 4.1, by presenting a gen-
eral computational approach for the detection and analysis of symmetries of sets of
points in n-dimensional spaces. We then elaborate on the analysis of symmetry in
two-dimensional images in Section 4.2.

n

4.1 Spectral Symmetry Analysis of Sets in R

n , with a symmetry of order K , it follows by Section 2, that
there exists a set of symmetry transformations,

Given a set of points S ∈ R

,thatmap S to itself.
The main issue is how to detect these multiple transformations simultaneously. In
terms of numerical implementation, this implies that one has to look for a set local
solutions of the corresponding optimization problem. Most matching and alignment
schemes, such as RANSAC and ICP, lock on to a single optimal alignment, and it is
unclear how to modify them to search for multiple solutions.
Spectral relaxation provides an elegant solution to this issue. The multiple self-
alignments will be manifested by the multiple maxima of the binary formulation
in Eq. 11 and its corresponding relaxation in Eq. 13. The maxima of the Reigh-
ley quotient in Eq. 13 are the leading eigenvalues of the affinity matrix H ,and
the corresponding arguments are the corresponding eigenvectors. This beautiful

{ T C K } and { T D K }