Graphics Reference
In-Depth Information
can be made more efficient if we organize the gallery elements in the form of a hierarchical
database, that is, a tree, where the comparisons are performed only at the nodes. To construct
such a shape tree, we need to be able to cluster similar shapes, and that is the problem we
study next.
Let
[0 0 ]
S
denotes the set of facial shapes. Consider the problem of clustering n shapes
[0 0 ] )into k clusters. A general approach is to form clusters in such a way that they
minimize total “within-cluster” variance. Let a configuration C consists of clusters denoted by
C 1 ,
(in
S
μ i s be the mean shapes in C i s and n i s be the sizes of C i s. There are
several cost functions used for clustering, for example, the sum of traces of covariances within
clusters. However, the computation of means
C 2 ,...,
C k , and let
μ i s of large shape clusters, and therefore their
variances, is computationally expensive, especially when they are updated at every iteration.
As a solution, a variation called pairwise clustering is used. (Hofmann and Buhmann, 1997),
where the variance of a cluster is replaced by a scaled sum of distances (squared) between its
elements as follows:
S a
S b ) 2
k
2
n i
.
d s ( S a
Q ( C )
=
,
(3.20)
i = 1
C i
b < a b C i
We seek configurations that minimize Q , i.e., C =
argmin Q ( C ). Notice that the metric
used is the arithmetic mean d a . We will minimize the clustering cost using a Markov chain
search process on the configuration space. The basic idea is to start with a configuration of
k clusters and to reduce Q by rearranging shapes amongst the clusters. The rearrangement
is performed in a stochastic fashion using two kinds of moves. These moves are performed
with probability proportional to the negative exponential of the Q -value of the resulting
configuration. The two types of moves are as follows: (1) Move a shape : Here we select
a shape randomly and reassign it to another cluster. Let Q ( i )
j
be the clustering cost when a
shape
θ j is reassigned to the cluster C i keeping all other clusters fixed. If
θ j is not a singleton,
that is, not the only element in its cluster, then the transfer of
θ j to cluster C i is performed
exp( Q ( i j / T )
i = 1 exp( Q ( i )
j
with probability: P M ( j
,
i ; T )
=
i
=
1
,
2
,...,
k . Here T plays a role similar to
/ T )
temperature in simulated annealing. If
θ j is a singleton, then moving it is not allowed in order
to fix the number of clusters at k .(2). Swap two shapes : Here we select two shapes randomly
from two different clusters and swap them. Let Q (1) and Q (2) be the Q -values of the original
configuration (before swapping) and the new configuration (after swapping), respectively.
Then, swapping is performed with probability: P S ( T )
exp( Q (2)
/ T )
T ) .
To seek global optimization, we have adopted a simulated annealing approach. Although
simulated annealing and the random nature of the search help in avoiding local minima, the
convergence to a global minimum is difficult to establish. Algorithm 7 illustrates the steps of
the clustering algorithm.
It is important to note that once the pairwise distances are computed, they are not com-
puted again in the iterations. Secondly, unlike k -mean clustering, the mean shapes are never
calculated in this clustering. The algorithms for computing Karcher mean and clustering
can be applied repeatedly for organizing a large database of human faces into a hierarchy
that allows efficient searches during biometrics. Among the 466 faces used as gallery in the
FRGCv2 experimentation, we propose to organize the 410 faces that have corresponding face
in the probe.
=
i = 1 exp(
Q ( i )
/
 
Search WWH ::




Custom Search