Graphics Reference
In-Depth Information
Algorithm
: Geodesic distance computation
Given a set of vertices
V
and a source vertex
v
s
:
1.
Set
v
.distance
=+∞
for every vertex
v
∈
V
;
2.
Set
v
s
.distance
=
0 and insert
v
s
in V-TREE;
3.
Take the vertex
v
, which has smallest
v
.distance in
V
-TREE, and remove it from
V
-TREE;
4.
For each vertex
u
adjacent to
v
,if
v
.distance
+|
(
v
,
u
)
|
<
u
.distance,
update
u
.distance
=
v
.distance
+|
(
v
,
u
)
|
and insert (or reinsert)
u
to
V
-TREE;
5.
Repeat Step 3 and 4 until
V
-TREE is empty.
Figure 3.29
Algorithm to operatively compute the geodesic distance from a source vertex of the mesh
v
s
to all the other vertices
V
of the mesh. The use of a binary tree
V
-TREE, where the vertices are sorted
in ascendant order of distance attribute from the source vertex permits to optimize the time complexity
3.9.2 Computing Relationships between Facial Stripes
Once values of the normalized geodesic distance are computed for every surface point, iso-
geodesic stripes can be identified. For this purpose, the range of the normalized geodesic
distance values is quantized into
n
intervals
c
1
,...,
c
n
. Accordingly,
n
stripes concentric with
respect to the nose tip, are identified on the 3D surface, the
i
th stripe corresponding to the
set of surface points for which the value of the normalized geodesic distance falls within the
limits of interval
c
i
.
Figure 3.31
b
shows the projection on the XY plane of the pairs of iso-geodesic stripes of
the three subjects in Figure 3.31
a
, thus evidencing the shape variations of the stripes. As an
example, Figure 3.35 shows the first nine iso-geodesic stripes identified on the face scans of
two individuals.
Results of the analysis of the deformation that non-neutral facial expressions induce in
the shape of the iso-geodesic stripes, as is detailed in Berretti et al. (2010), motivate the
decomposition of the facial stripes into three parts,
upper left
(UL),
upper right
(UR) and
lower
(L), with respect to the coordinates of the nose tip (see Figure 3.31
b
). In general, under
the effect of non-neutral facial expressions, the region around the mouth is subject to larger
deformations than the other regions of the face. Furthermore, decomposition of the upper
part into the upper left and upper right allows the face representation model to better deal
with slight asymmetries of the face that constitute a characterizing trait of some individuals.
This subdivision resulted necessary in improving the performance of the approach in the case
v
1
2
v
6
6
1
1
v
2
3
1
v
5
2
1
1
v
4
5
v
3
Figure 3.30
An edge-weighted directed graph
