Biomedical Engineering Reference
In-Depth Information
10.5.2 Numerical Solution for the Level Set
Implementation of RAGS
As in the numerical solution for vector diffusion, a computational grid is re-
quired. Once the grid is chosen, the initial level sets
φ
(
x
,
t
)
=
0 can be defined
with the property that the zero level set corresponds to the initial contours of the
snake. The signed-distance transform can be used to build the initial level sets.
A brute-force Euclidean distance transform would be computationally infeasi-
ble. Practically, accuracy is required only near the initial contours, and discrete
values based on grid distance can suffice further away. A positive sign is given
to the points outside the contours, and a negative sign is applied to the points
inside.
As shown in (10.17), the snake evolves according to four forces that can be
categorized into three types based on the nature of their motions:
1. The first motion is of a smoothing and collapsing nature with speed propor-
tional to its curvature as shown in Fig. 10.1. It can be numerically approx-
imated using central differences, because the curvature is only dependent
on the contour. It is independent of time and spatial position.
2. The second is expanding or shrinking with a spatially constant speed, char-
acterized by
α
g
(
·
) in the normal direction of the curve. However, when the
constant term exists, the normals can collide with each other while evolv-
ing. Thus shocks, or corners, will form and once a shock has developed,
some information will be lost as it evolves. This means that shocks cause
irreversibility; information cannot be recovered by tracing 'backwards' in
time. Generally, no new information can be created while evolving, which
is referred to as an
entropy condition
. Central difference approximation
cannot be used to approximate the gradient in this case, as it suffers from
shocks where the entropy condition is invoked. An
upwind scheme
can be
used, as an entropy-satisfying scheme, that engages information upwind of
the direction of its propagation. In other words, in order to achieve a stable
numerical scheme, the numerical domain of dependence should contain
the mathematical domain of dependence. Thus, in order to approximate
the gradient of the constant term, it is important to first know which way
the speed function points, and whether it is negative or positive. Then we
can choose proper backward or forward difference approximations.
