Graphics Reference
In-Depth Information
Stability of facial fiducial points and measurements under changes following facial expres-
sions is a fundamental issue for recognition. It has been demonstrated that geodesic distances
are almost preserved under many expressions (Bronstein et al., 2005). Experimental evidence
of this fact has been reported in Mpiperis et al. (2006), where the maximum change of 5% is
measured for the geodesic distances computed between the nose and the cheek of the same
subject under different expressions. Similar results are reported in Bronstein et al. (2007),
where the average standard deviation of the absolute distance error due to facial expressions
was measured in 5.89 mm and 12.03 mm, respectively, for the geodesic and Euclidean dis-
tance. Moreover, the pronasale (i.e., the nose tip) and the left and right endocanthion (i.e., the
points at the inner commissure of the left and right eye fissure) have been verified to be stable
with respect to face variations (Bronstein et al., 2005; Chang et al., 2005).
3.9.1 Extraction of Facial Stripes
In the proposed approach, computation of the geodesic distance on the piecewise planar mesh
is accomplished through the Dijkstra's algorithm (Cormen et al., 2001), and approximates the
actual geodesic distance between two surface points with the length of the shortest piecewise
linear path on mesh edges. In particular, considering a mesh as a graph
G
=
(
V
,
E
) with
the edge weights
w
(
e
),
w
(
e
)
E
, the Dijkstra's algorithm solves the
problem to find the
shortest path
from a
source vertex v
s
∈
>
0, for each edge
e
∈
V
to a
target vertex v
t
∈
V
.In
our specific case, the weight
w
(
e
ij
) of an edge
e
ij
=
v
j
) connecting vertices
v
i
and
v
j
,
is given by the linear length of the edge itself, that is,
w
(
e
ij
)
(
v
i
,
. It is worth noting
that the computation of geodesic distances on the mesh can be affected by the regularity of
the mesh. In fact, since the Djikstra's algorithm approximates the actual geodesic distances
through edge lengths, a nontriangular mesh (i.e., a mesh composed of general polygons) or
a nonregular mesh (i.e., a mesh composed of triangles of different sizes) makes the estimate
less accurate. So, a mesh should be preprocessed to triangularize and regularize its polygons,
thus making sufficiently accurate the computation of the geodesic distance using the Dijkstra's
approximation (Antini et al., 2005).
=|
v
i
−
v
j
|
Computer Implementation
A pseudo-code description of the Dijkstra's algorithm is reported in Figure 3.28. In this simple
implementation, vertices of the set
V
are stored in an ordinary
linked list
(or array), and
extract minimum from
V
is simply a linear search through all vertices in
V
. In this case,
it can be easily shown that if
are the number of vertices and edges in
V
and
E
, respectively, the algorithm runs with a worst case time complexity of
O
(
|
V
|
and
|
E
|
2
|
V
|
+|
E
|
)
=
2
) edges, Dijkstra's
algorithm can be implemented more efficiently by storing the graph in the form of
adjacency
lists
and using a
binary heap
as a priority queue to implement extracting minimum efficiently.
With a binary heap, the algorithm requires
O
((
V
2
O
(
|
|
). For
sparse graphs
, that is, graphs with far fewer than
O
(
|
V
|
|
E
|+|
V
|
)log
|
V
|
) time, which is dominated
by
O
(
), assuming the graph is connected. Since, meshes representing 3D faces are
sparse and connected, this latter optimized implementation of the algorithm can be used in
our case, thus reducing the overall time complexity in computing the geodesic distances to
the nose tip. A simplified description of the algorithm using a binary tree
V
-TREE, where the
|
E
|
log
|
V
|
