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

property, allows to recover multiple assignments, simultaneously, and independently
by computing the eigendecomposition of H .
Such an example is given in Fig. 4, where the four self alignments are manifested
by four dominant eigenvalues. Note, that the largest eigenvalue corresponds to the
identity transform, that maps each point to itself. Hence, given the set of interest
points S

n , we apply the spectral alignment algorithm in Section 3.3 and compute
the eigen-decomposition

∈ R

K
1 of Eq. 13. The overall number of symmetry axes
is given by the number of large eigenvalues K , and the correspondence maps

{ ψ , λ } i i

K
1

{ C i }

are derived by the discretized binary eigenvectors .

As the spectral alignment matches Euclidean distances between points, it can be
used to compute multiple non-parametric alignments. This implies that we do not
have to predefine which symmetry type to analyze; those that do exist, will be de-
tected. But, this also implies that the scheme might detect erroneous self-alignments,
which are unrelated to the symmetry. This phenomenon would become evident dur-
ing the analysis of symmetric sets embedded in clutter. The problem is resolved in
the next section, by incorporating the geometrical constraints of the symmetry trans-
forms, discussed in Section 2. This allows us to prune the erroneous self-alignments.

{ ψ i }

4.1.1 Perfect Symmetry and Spectral Degeneracy

When analyzing perfectly symmetric sets of points, multiple alignments might be
manifested by the same eigenvalue, and the corresponding eigenvector becomes de-
generate. Each eigenvectors is then a linear combination of several assignments.
This phenomenon, never occurs with data sources other then synthetic sets of
points. For instance, in images, the feature points detectors have a certain subpixel
accuracy, and corresponding feature points do not create perfect symmetries. This
applies to synthetic images and even more so, to real images and three-dimensional
objects that are never perfectly symmetric.
In order to generalize our approach to perfectly symmetric sets of points, we
propose adding Gaussian random noise N

to the non zero elements of the
affinity matrix. This breaks down the perfect symmetry, if it exists, and does not
influence the analysis of regular data. In order to retain the symmetricity of the
affinity matrix we add a symmetric pattern of noise. As the non zeros affinities are

( 0 , σ n )

of O 10 − 1 for a well chosen value of

10 − 3 .

=

σ in Eq. 12, we used σ n

4.2 Spectral Symmetry Analysis of Images

2 . As such, the spectral
matching scheme can not be used, as it applies to sets of points. Hence, we turn to
image modeling by means of local features, as discussed in Section 3.2. This allows
us to represent the input image as a set of salient points. The rotation invariance of
the detectors, guaranties that corresponding symmetric points would be detected as
salient points simultaneously. We then present in Section 4.2.2 a scheme for pruning
erroneous spectral alignments, and identifying valid matchings as C K or D K .Last,

2 is a scalar or vector function defined over

An image I ∈ R R