Recent Advances in the Level Set Method - Biomedical Image Analysis - page 223

to the accepted set, A , only the immediately adjacent grid points require the
approximate value of φ to be updated. Let F min and F max be the minimum and
maximum values of the speed function F . For the more general ordered upwind
method, all the tentative points in a radius of xF max / F min around x must be
updated. If the new approximate value for φ is smaller, this new value is used.
This is to account for the possible highest speed direction which could allow
the point x to influence grid points within this radius before the immediately
adjacent grid points. The formulation for computing the approximation for φ at
these tentative points uses the same type of one-sided discretization as used in
the fast marching method to follow the characteristics from x .
As an example of the use of the ordered upwind method, the geodesic dis-
tance from the origin on the manifold z =

3

4 sin(3 π x ) sin(3 π y ) is computed on

1
2 ,

1 1

2 ,

1

the square [ −

2 ] × [ − 2 ]inthe x - y plane. The resulting distance isocontours

are shown in Fig. 4.12

4.3.2 Improved Velocity Extensions

The velocity extension method currently in common usage was described in
Section 4.2.5, and can be attributed to [3]. However, as noted in [23], the velocity
extension characteristics are not supposed to be the straight line extensions that
are currently constructed. While it is true that ∇ F ·∇ φ = 0 should hold at the
initial interface, it does not necessarily hold off the interface.
As an example of what can happen with the current velocity extension
method, consider the example of an interface consisting of two circles, with
the left circle having speed 1, and the right circle having speed 2 (see Fig. 4.13).
The current velocity extension method is such that the left half-plane will have
F = 1, and the right half-plane will have F = 2, with the break indicated by the
dashed line in Fig. 4.13. The evolution makes a clear error when the right circle
expands to the dividing line. Once the circle crosses that line, the velocity ex-
tension incorrectly changes the speed from 2 to 1. By noting the gap between
successive contours, it is clear that the right-hand circle has slowed down on the
left side. The reason that the velocity extension in Fig. 4.13 failed is because the
characteristics of the problem were not respected. Once the interface crossed
the center line, the velocity came from the left circle, while the characteris-
tics came from the right circle. Ultimately, this happened because the velocity
extension was done independent of, and prior to, the actual evolution.