PARALLEL CO-VOLUME SUBJECTIVE SURFACE METHOD FOR 3D MEDICAL IMAGE SEGMENTATION - Deformable Models - page 130

control volumes are constructed as elements of a dual (complementary) grid to a
finite-element triangulation (tetrahedral grid in the 3D case). Then the nonlinear
quantities in PDEs, as an absolute value of the solution gradient in Eq. (2), are
evaluated using piecewise linear representation of the solution on a tetrahedral
grid thus employing the methodology of the linear finite-element method. The
finite-volume methodology brings in the naturally discrete minimum-maximum
principle. The piecewise linear representation (reconstruction) of the segmentation
function on the finite-element grid yields a fast and simple evaluation of nonlin-
earities. Implicit, i.e., nonlinear time discretization and co-volume techniques, for
solution of the level set equations were first introduced in [65]. The implicit time
stepping as in [65], although unconditionally stable, leads to solution of a non-
linear system in every discrete time update. On the other hand, the semi-implicit
scheme leads in every time step to solution of a linear algebraic system that is
much more efficient. Using explicit time stepping, stability is often achieved only
under severe time step restriction. Since in nonlinear diffusion problems (like the
level set equations or the subjective surface method) the coefficients depend on
the solution itself and thus must be recomputed in every discrete time update, an
overall computational time for an explicit scheme can be tremendous. From such
a point of view, the semi-implicit method seems to be optimal regarding stability
and computational efficiency.
In the next subsections we discuss the semi-implicit 3D co-volume method.
We present the method formally in discretization of Eq. (1), although we always
use its ε -regularization (2) with a specific ε> 0. The notation is simpler in case
of (1), and it will be clear where the ε -regularization appears in the numerical
scheme.

3.1. Semi-Implicit Time Discretization

We first choose a uniformdiscrete time step τ and a variance σ of the smoothing
kernel G σ . We then replace the time derivative in (1) by backward difference. The
nonlinear terms of the equation are treated from the previous time step while the
linear ones are considered on the current time level, whichmeans semi-implicitness
of the time discretization. By such an approach we get our semi-discrete in a time
scheme:
Let τ and σ be fixed numbers, I 0 be a given image, and u 0 a given initial segmen-
tation function. Then, for every discrete time moment t n = nτ , n =1 ,...N,we
look for a function u n , the solution of the equation

= ∇ . g 0

.

u n u n− 1 u n 1 − ∇

(8)

|∇ u n− 1 | τ |∇ u n− 1 |