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

presented. The latter approach paves the way for the proposed Spectral Symmetry
Analysis (SSA) algorithm presented in Section 4.

3.1 Previous Work in Symmetry Detection and Analysis

Symmetry has been thoroughly studied in literature from theoretical, algorithmic,
and applicative perspectives. Theoretical analysis of symmetry can be found in
[Mil72, Wey52]. The algorithmic approaches to its detection can be divided into
several categories, the first of which consists of intensity-based schemes that com-
pute numerical moments of image patches. For instance, detection of vertical re-
flectional symmetry using a one-dimensional odd-even decomposition is presented
in [Che01]. The authors assume that the symmetry axis is vertical and thus scans
each horizontal line in the image. Each such line is treated as a one-dimensional
signal that is normalized and decomposed into odd and even parts. From odd and
even parts, the algorithm constructs a target function that achieves its maximum at
the point of mirror symmetry of the one-dimensional signal. When the image has
a vertical symmetry axis, all symmetry points of the different horizontal lines lie
along a vertical line in the image.
A method that estimates the relative rotation of two patterns using the Zernike
moments is suggested in [KK99]. This problem is closely related to the problem of
detecting rotational symmetry in images. Given two patterns, where one pattern is
a rotated replica of the other pattern, the Zernike moments of the two images will
have the same magnitude and some phase differential. The phase differential can be
used to estimate the relative rotation of the two images.
In order to detect large symmetric objects, such schemes require an exhaustive
search over all potential symmetry axes and locations in the image, requiring exces-
sive computation even for small images. An efficient search algorithm for detecting
areas with high local reflectional symmetry that is based on a local symmetry op-
erator is presented in [KG98]. It defines a two-dimensional reflectional symmetry
measure as a function of four parameters x , y ,

θ ,and r ,where x and y are the center

of the examined area, r is its radius, and θ is the angle of the reflection axis. Ex-

amining all possible values of x , y , r ,and is computational prohibitive; therefore,

the algorithm formulates the search as a global optimization problem and uses a
probabilistic genetic algorithm to find the optimal solution efficiently.
A different class of intensity-based algorithms [DG04, KS06, Luc04] utilizes the
Fourier transform to detect global symmetric patterns in images. The unitarity of
the Fourier transform preserves the symmetry of images in the Fourier domain: a
symmetric object in the intensity domain, will also be symmetric in the Fourier do-
main. Derrode et al. [DG04] analyze the symmetries of real objects by computing
the Analytic Fourier-Mellin transform (AFMT). The input image is interpolated on
a polar grid in the spatial domain before computing the FFT, resulting in a polar
Fourier representation. Lucchese [Luc04] provides an elegant approach to analyz-
ing the angular properties of an image, without computing its polar DFT. An angular
histogram is computed by detecting and binning the pointwise zero crossings of the

θ