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

Chapter 7
A Graph Matching Approach to Symmetry
Detection and Analysis

Michael Chertok and Yosi Keller

Bar-Ilan University, Israel
{michael.chertok,yosi.keller}@gmail.com

Abstract. Spectral relaxation was shown to provide an efficient approach for
solving a gamut of computational problems, ranging from data mining to image reg-
istration. In this chapter we show that in the context of graph matching, spectral re-
laxation can be applied to the detection and analysis of symmetries in n- dimensions.
First, we cast symmetry detection of a set of points in

n as the self-alignment of
the set to itself. Thus, by representing an object by a set of points S

R

n ,sym-
metry is manifested by multiple self-alignments. Secondly, we formulate the align-
ment problem as a quadratic binary optimization problem, solved efficiently via
spectral relaxation. Thus, each eigenvalue corresponds to a potential self-alignment,
and eigenvalues with multiplicity greater than one correspond to symmetric self-
alignments. The corresponding eigenvectors reveal the point alignment and pave
the way for further analysis of the recovered symmetry. We apply our approach to
image analysis, by using local features to represent each image as a set of points.
Last, we improve the scheme's robustness by inducing geometrical constraints on
the spectral analysis results. Our approach is verified by extensive experiments and
was applied to two and three dimensional synthetic and real life images.

∈ R

1 Introduction

Symmetry is all around us. In nature it is commonly seen in living creatures such as
butterflies, in still life like flowers, and in the unseen world of molecules. Humans
have been inspired by nature's symmetry for thousand of years in countless fields.
In the fields of art and architecture, the scientific fields of mathematics and even
the humanitarian fields such as philosophy - symmetry is a prominent factor. From
airplanes to kitchen cups, symmetry ideas are copied from nature in many man-
made objects. The presence of visual symmetry in everyday life makes its detection
and analysis one of the fundamental tasks in computer vision. When dealing with
computer vision applications, the detection of symmetry is mainly used to reach
a more advanced level of recognition, like object detection or segmentation. It is
known that the human visual system is more prone to detect symmetric patterns in