Download Fast Marching Methods - Parallel Implementation and Analysis

to this case, based on rotation and symmetry of the domain. By evaluating:
Ti,j − Ti−1,j
≥0
∆x
Ti,j − Ti,j−1
=
≥0
∆y
Ti+1,j − Ti,j
≥0
∆x
Ti,j+1 − Ti,j
=
≥ 0,
∆y
−x
Di,j
Ti,j =
+x
Di,j
Ti,j =
−y
Di,j
Ti,j
+y
Di,j
Ti,j
and plugging them in equation (1.24), we obtain:
q
2
2
−y
−x
max Di,j
T, 0 + max Di,j
T, 0 =
q
1
−y 2
−x 2
Di,j
T + Di,j
T =
,
Fi,j
which is the quadratic equation that we need to solve:
s
2 2
1
Ti,j − Ti,j−1
Ti,j − Ti−1,j
.
+
=
∆x
∆y
Fi,j
During the algorithm execution, this computation is done many times for each
node in the domain, until convergence is achieved. Basically, the value at the grid
point Ti,j can be computed exactly using only T at its neighbors, i.e. Ti±1,j and
Ti,j±1. We consider T to be computed exactly, if and only if the new T is smaller
than the old one.
Remark 1.22. Since during the algorithm execution, at each iteration, we recompute T at every point of the domain, we have a lot of useless computations (T is
changing only at a few grid points). The algorithm is not taking this shortcut into
consideration.
To illustrate the Rouy-Tourin algorithm, we consider a rectangular domain, with
the boundary condition imposed in two opposite corners. In the initialization step,
if Xi,j ∈ Γ (a point where we can approximate the initial curve), then T (Xi,j ) = 0,
otherwise T (Xi,j ) = ∞. For exemplification purposes, Figure 1.8 shows the stages
of the algorithm for a particular case. At each iteration of the algorithm, we solve
the local Eikonal equation at all the points of the domain. Note how T changes
25