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

[MCUP02], as shown in Fig. 2b. The ellipses in the figure represent the second mo-
ment matrix of the detected regions. In contrast, non-structured object are better
characterized by affine adapted Hessian-like detectors as depicted in Fig. 2a.
The common solution is to use multiple descriptors simultaneously [NZ06]. In
the context of symmetry detection in contrast to object recognition, the local fea-
tures are all extracted from the same image. Hence, one can assume that symmetric
points within the same image, would respond well to the same type of local detec-
tor/descriptor. This allows us to use one detector-descriptor pair at a time.

Spectral Matching of Sets of Points in R n

3.3

x j N 2
1

n , such that S 1 = x i N 1

Given two sets of points in R and S 2 = ,where

1

= c i k j k N 1 x k j ∈ R

n , k

= 1 , 2, we aim to find a correspondence map C , such that c i k j k

1

implies that the point x i k ∈ S 1 corresponds to the point x j k ∈ S 2 . Figure 3 presents

an example of two sets being matched. Spectral point matching was first presented
in the seminal work of Scott and Longuet-Higgins [SLH91], who aligned point-sets
by performing singular value decomposition on a point association weight matrix.
In this work we follow a different formulation proposed by Berg et al. [BBM05]
and its spectral relaxation introduced by Leordeanu et al. in [LH05]. We start by
formulating a binary quadratic optimization problem, where the binary vector Y

∈

, represents all possible assignments of a point x i k ∈

{ 0 , 1 } S 1 to the points in set S 2 .

The assignment problem is then given by:

Y T HY ,

Y ∗ = arg max

Y

Y ∈{ 0 , 1 } (11)

Fig. 3 Toy example for matching two sets of points

( , )

where H is an affinity matrix, such that H k 1 k 1 is the affinity between the match-

ings c i k 1 j k 1 and c i k 2 j k 2 . H ( k 1 , k 1 ) → 1 implies that both matchings are consistent, and

H ( k 1 , k 1 ) → 0 , implies that the matchings are contradictory. In practice, we use

exp x j k 2 2

d x i k 1 ,

x i k 2 d x j k 1 ,

1
σ

H ( k 1 , k 1 )= − − (12)