Graphics Reference
In-Depth Information
Algorithm 1
Dynamic programming algorithm for optimal reparametrization estimation
Input
: Discrete version of
q
1
and
q
2
,
N
ij
: set of nodes that are allowed to go to (
i
,
j
)
Output
: Discrete version of
γ
E n by n matrix initialized by zeros;
for
i
1
to
n
do
E(1,i)=1;
end
for
i
←
1
to
n
do
E(i,1)=1;
end
E(1,1)=0;
for
i
←
←
2
to
n
do
←
for
j
2
to
n
do
for
Num
←
1
to
length
(
N
ij
)
do
k = i - Nbrs(Num,1);
l=j-Nbrs(Num,2);
if
((
l
>
0)&(
k
>
0))
then
k
i
l
j
n
);
=
,
+
FunctionE
(
q
1
,
q
2
,
n
,
n
,
n
,
H
c
(
Num
)
H
(
k
l
)
else
H
c
(
Num
)
=
C
;
end
H
(
i
,
j
)
=
min
(
H
c
)
end
end
end
Algorithm 1 summarizes the dynamic pogramming algorithm for optimal reparametrization
estimation. In this algorithm, C is a large positive number, function
E
is a subroutine that
computes
E
(
k
l
n
;
L
(
k
l
;
i
/
,
/
,
,
j
)), and Nbrs is a list of sites used to define
N
ij
. In practice,
one often restricts to a smaller subset to seek a computational step sped up. The next effect
is that the number of possible values for the slope along the path are further restricted (see
Figure 3.9).
An example of this idea is shown in Figures 3.10 and 3.11. The optimal matching using
dynamic programming for the two curves corresponding to the open and the closed mouth is
illustrated in Figure 3.11
b
and it highlights the elastic nature of this framework. For the left
curve, the mouth is open and for the right curve, it is closed. Still the feature points (upper and
bottom lips) match each other well. Figure 3.11
d
shows the geodesic path between the two
curves in the shape space
n
and this evolution looks very natural under the elastic matching.
The middle panel in the top row shows the optimal matching for the two curves obtained
using the dynamic programming, and this highlights the elastic nature of this framework. For
the left curve, the mouth is open and for the right curve, it is closed. Still the feature points
(upper and bottom lips) match each other very well. The bottom row shows the geodesic
path between the two curves in the shape space
S
S
and this evolution looks very natural
