Biomedical Engineering Reference
In-Depth Information
1. Initialize the value of
F
ext
at all the grid points adjacent to the interface
φ
−
1
(0) using the bicubic interpolation algorithm discussed in Section 4.2.3.
Place all those grid points in the accepted set
A
. Add all grid points adjacent
to a point in the set
A
into the set
T
, and the remainder of the grid points
are placed in the set
D
.
2. Take the grid point
x
i
,
j
with the smallest value of
|
φ
i
,
j
|
from the set
T
and
place it in set
A
. Solve Eq. 4.34 for
F
ext
i
,
j
at this
x
i
,
j
. Take all neighbors of
x
i
,
j
which are in
D
, and place them in
T
.
3. Repeat step 2 while
T
=∅
.
Similar to the comments made in the previous section, the velocity extension
method also can avoid the cost of the heap sort by taking the first-in-first-out
strategy. Therefore, the computational cost for the velocity extension is the same
as for reinitialization,
O
(
N
).
4.2.6 Narrow Band Methods
There is another technique frequently used in level set methods that deserves
attention. While it is not an essential part of the level set method it is useful in
that it can significantly reduce the computational cost.
As noted earlier, switching from a parametric representation to the implicit
representation used in the level set method also increased the computational
cost. For example, if an evolving curve in the plane can be modeled with
O
(
N
)
points, then the corresponding level set representation would require
O
(
N
2
)
points, due to the higher dimension of the level set function. However, most
of that increased computational cost is spent computing the evolution of
φ
in
regions far from the
φ
=
0 interface of interest.
It was observed in [19] that it is not necessary to compute the evolution
of
φ
everywhere, but only in the neighborhood of the
φ
=
0 interface. This
observation effectively reduces the computation back to
O
(
N
). This technique
is called a narrow-band level set method, and was significantly refined in [2].
Basically, the evolution equation of
φ
is computed on a dynamically determined
set of grid points where
φ
is small.
Not all applications will benefit from a narrow band implementation; it de-
pends heavily on the cost of computing
F
, which can easily overwhelm the cost
