Biomedical Engineering Reference
In-Depth Information
A
Which path
is shorter?
B
Figure 4.11: Illustration of the difficulty with anisotropic speed functions.
Which path is optimal depends on the speed and direction.
To illustrate the difference, consider the problem of finding the fastest route
between two cities. If the problem were isotropic, then it would mean that you
will travel at the same speed regardless of the direction you are traveling. The
solution is therefore simple: a straight line path between the two cities. However,
in reality, there are roads, bridges, rivers, mountains, and other assorted terrain
features that can influence the choice of the path. When on a road, the speed
function depends heavily on the direction to be traveled, with the highest speed
along the road and the slowest speed off the road.
The example of the road highlights one of the key technical issues that had to
be addressed in this paper. In the isotropic case, when computing an estimate for
the value of φ ( x ), it is sufficient to only check immediately neighboring points.
In the anisotropic case, this is not the case. When standing at a point on the road,
one must check not only the immediate neighborhood, but must also check far
down the road to see if a shorter path along the road would be possible. This
comparison is illustrated in Fig. 4.11, where the shortest path arriving at point B
may not be directly from nearby points, but may come from far away points along
directions which are faster. The key observation in [129] was the identification
of how far away one must check to assure locating the shortest path.
More specifically, the ordered upwind method solves equations of the form
F ( φ, x ) φ = 1 ,
(4.39)
with the additional assumption that F ( φ, x ) > 0 is convex. The case where F
is non-convex is significantly more challenging and remains an open problem.
The algorithm for the ordered upwind method is similar to the fast marching
method described in Section 4.2.3, with only step 3 requiring modification. In
the fast marching method, when a point x is moved from the tentative set, T ,
Search WWH ::




Custom Search