A level set model[30,29] specifies a surface as a
level set (iso-surface) of a scalar volumetric
function,
, where
is the range
of the surface model. Thus, a surface
is
There are two different approaches to defining a deformable surface
from a level set of a volumetric function as described in
Equation (9). Either one can think of
as
a static function and change the iso-value
or
alternatively fix
and let the volumetric function
dynamically change in time, i.e.
. Following
the second approach, we can mathematically express the dynamic model
as
There are a variety of options for the curvature smoothing terms in
Equation (13), and the question of efficient, effective
higher-order smoothing terms is the subject of on-going
research[29]. For the work presented in this paper
the smoothing term uses the mean curvature
of the level set
to form a vector in the direction of the surface normal
:
Level set models have a number of practical and theoretical
advantages over conventional surface models, especially in the context
of deformation and segmentation. Level set models are
topologically flexible; they easily represent complicated surface
shapes that can, form holes, split to form multiple objects, or merge
with other objects to form a single structure. These models can
incorporate many (millions) of degrees of freedom, and therefore they
can accommodate complex shapes.
Indeed, the shapes formed by the level sets of
are restricted only by the resolution of the sampling. Thus,
there is no need to re-parameterize the model as it undergoes
significant changes in shape.
The solutions to the partial differential equations described above are computed using finite differences on a discrete grid. The use of a grid and discrete time steps raises a number of numerical and computational issues that are important to the implementation. However, it is outside of the scope of this paper to give a detailed mathematical description of such a numerical implementation. Rather we shall give a short outline below and refer to the actual source code which is publicly available1.
Equation (12) to (15) can be solved using finite forward differences if one
uses the up-wind scheme, proposed by Osher and Sethian [30],
to compute the spatial derivatives. This up-wind scheme produces the
motion of level-set models over the entire range of the embedding, i.e.,
for all values of in Equation (10). However, this
method requires updating every voxel in the volume for each iteration.,
which means that the computation time increases as a function of the volume,
rather than the surface area, of the model. Because segmentation requires
only a single model, the calculation of solutions over the entire range of
iso-values is an unnecessary computational burden.
This problem can be avoided by the use of narrow-band methods, which compute solutions only in a narrow band of voxels that surround the level set of interest [24].In previous work [25] we described an alternative numerical algorithm, called the sparse-field method, that computes the geometry of only a small subset of points in the range and requires a fraction of the computation time required by previous algorithms. We have shown two advantages to this method. The first is a significant improvement in computation times. The second is increased accuracy when fitting models to forcing functions that are defined to sub-voxel accuracy.
Figure 3. Level set models represent curves and surfaces implicitly using grey scale images. For example an ellipse is represented as the level set of an image (top). To change the shape of the ellipse we modify the grey scale values of the image by solving a PDE (bottom).