Graphics Reference
In-Depth Information
Algorithm 7
Statistical shape clustering
For
n
shapes and
k
clusters, initialize by randomly distributing
n
shapes among
k
clusters.
Set a high initial temperature
T
.
1. Compute pairwise geodesic distances between all
n
shapes. This requires
n
(
n
−
1)
/
2
geodesic computations.
2. With equal probabilities pick one of the two moves:
Move a shape
: Pick a shape
θ
j
randomly. If it is not a singleton in its cluster,
then compute
Q
(
i
)
j
for all
i
=
1
,
2
,...,
k
. Compute the probability
P
M
(
j
,
i
;
T
) for all
θ
j
to a cluster chosen according to the probability
P
M
.
Swap two shapes
: Select two clusters randomly, and select a shape from each. Compute
the probability
P
S
(
T
) and swap the two shapes according to that probability.
i
=
1
,...,
k
and re-assign
3. Update the temperature using
T
=
T
/β
and return to Step 2. We have used
β
=
1
.
0001.
Figure 3.23 shows a hierarchical organization of these shapes all the way up to the top. At
the bottom level (level D in the figure), these 410 are gathered into 29 clusters. Computing
the means of each of these clusters, we obtain faces that are to be clustered at the next level
(level C in the Figure 3.23). Repeating the clustering on the mean faces at level C, we obtain
the next level (level B) containing 3 mean faces representing the clusters of the previous level.
In level A, we just calculate the mean of the three mean faces in level B. This face represents
the coarsest face along the tree.
If we follow a path from top to bottom of the tree, we can see the shapes getting more
detailed structurally and leading up to individual faces, as illustrated in Figure 3.24.
Another example, we start with approximately 500 nose scans corresponding to 50 distinct
subjects. These noses form the bottom layer of the hierarchy, called level E in Figure 3.25.
Then, we compute Karcher mean shapes for each person to obtain shapes at level D. These
shapes are further clustered together and a Karcher mean is computed for each cluster. These
mean shapes form the level C of the hierarchy. Repeating this idea a few times, we reach the
top of the tree. If we follow a path from top to bottom of the tree, we can see the shapes getting
more detailed structurally and leading up to individual faces, as illustrated in Figure 3.26.
3.9 The Iso-geodesic Stripes
One main difficulty in extracting
facial curves
from the surface of 3D face scans is related to the
presence of noise. In fact, in addition to the intrinsic noise components as a result of acquisition
devices and surface characteristics that can be smoothed through some preprocessing, other
sources of noise can contribute to alter the extraction of facial curves from the acquired
data. For example, in the approach proposed by Samir et al. (2006), the
iso-depth curves
extracted from the face are greatly influenced by the misalignment of 3D scans with respect
to a common 3D cartesian reference system, whereas in Samir et al. (2009) the
iso-geodesic
curves
are sensitive to the noise in computing the geodesic distances between points of the
surface and a reference point of the face. As a consequence, the shape of these facial curves
can be largely influenced by the noise, and the effect of these variations can be amplified by
