Graphics Reference
In-Depth Information
3.5.3 Reparametrization Estimation by Using Dynamic Programming
Given two shapes
q
1
and
q
2
, the idea is to estimate a nonlinear function
γ
that reparametrizes
q
2
so as to match both shapes closely, we want to solve for
1
0
˙
2
d
t
γ
=
ˆ
arg min
γ
∈
q
1
(
t
)
−
γ
(
t
)
q
2
(
γ
(
t
)
(3.8)
is the set of all reparametrizations. We can solve a discrete approximation of this problem
using dynamic programming (DP). A necessary condition for applying DP to such problems is
that the cost function is additive in time
t
. To decompose the problem into several subproblems,
define a partial cost function:
t
s
˙
2
d
E
(
s
,
t
;
γ
)
=
q
1
(
τ
)
−
γ
(
τ
)
q
2
(
γ
(
τ
)
τ
(3.9)
so the original cost function is simply
E
(0
,
1;
γ
).
γ
is seen as a graph from (0
,
0) to (1
,
1) in
2
such that the slope of this graph is always strictly between 0 and 90 degrees.
Our goal is to find an optimal path from (0
R
2
, corresponding to (
t
,
0) to (1
,
1) in
R
,γ
(
t
)) that
minimizes the cost function.
To use a numerical approach, the domain [0
,
1]
×
[0
,
1] is replaced with a finite grid and
we restrict over search to that grid. The grid
G
n
×
G
n
is formed by uniform partition of
G
n
as
G
n
={
1
/
n
,
2
/
n
,...,
(
n
−
1)
/
n
,
1
}
. The search will be done over the set of all restrictions of
γ
to this grid. The total cost associated with the path is the sum of the costs associated with
its linear segments. On an
n
n
grid, there are only a finite number of paths, even less when
we impose the slope constraint. Actually the path is never vertical or horizontal. However, this
number of paths grows exponentially with
n
and we can not possibly search over all possible
paths in an exhaustive fashion. Instead, the DP finds the optimal path in
O
(
n
2
) time.
Denote a point on the grid (
i
×
/
n
,
j
/
n
)by(
i
,
j
). Certain nodes are not allowed to go to (
i
,
j
)
because of the slope constraint. Denote by
N
ij
the set of nodes that are allowed to go to (
i
,
j
).
For instance
N
(
i
,
j
)
={
(
k
,
l
)
/
0
≤
k
<
i
;
l
<
j
≤
n
}
is a valid set. Let
L
(
k
,
l
;
i
,
j
) denote a
straight line joining the nodes (
k
N
ij
this is a line with slope strictly
between 0 and 90 degrees. This sets up the iterative optimization problem:
,
l
) and (
i
,
j
); for (
k
,
l
)
∈
(
k
l
)
,
=
arg min
(
k
,
l
)
∈
N
ij
E
(
k
/
n
,
l
/
n
;
L
(
k
,
l
;
i
,
j
))
,
(3.10)
with E as defined in Equation 3.9. Define the minimum energy of reaching the point (
i
,
j
), in
an iterative fashion as
E
(
k
l
n
;
L
(
k
l
;
i
H
(
k
l
)
H
(
i
,
j
)
=
/
n
,
/
,
,
j
))
+
,
,
with
H
(0
,
0)
=
0
.
(3.11)
This subproblem is solved sequentially for each node (
i
,
j
), starting from (1
,
1) and increas-
ing
i
,
j
till one reaches the node (
n
,
n
). Tracing the path that results in the energy
H
(
n
,
n
)
provides a discrete version of the optimal
γ
.
