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

3.2. Co-Volume Spatial Discretization in 3D

A 3D digital image is given on a structure of voxels with a cubic shape, in
general. Since discrete values of image intensity I 0 are given in voxels and they
influence the model, we will relate spatially discrete approximations of the seg-
mentation function u also to the voxel structure; more precisely, to voxel centers.
In every discrete time step t n of the method (8) we have to evaluate the gradient
of the segmentation function at the previous step u n− 1 | . To that goal we put

the 3D tetrahedral grid into the voxel structure and take a piecewise linear rep-
resentation of the segmentation function on such a grid. Such an approach will
give a constant value of the gradient in tetrahedra (which is the main feature of the
co-volume [65, 16] and linear finite-element [62, 63, 64] methods in solving the
mean curvature flow in the level set formulation), allowing simple, clear, and fast
construction of a fully-discrete system of equations.
The formal construction of our co-volumes will be given in the next paragraph,
and we will see that the co-volume mesh corresponds back to the image voxel
structure, which is reasonable in image processing applications. On the other hand,
the construction of the co-volume mesh has to use a 3D tetrahedral finite-element
grid to which it is complementary. This will be possible using the following
approach. First, every cubic voxel is split into 6 pyramids with a vertex given
by the voxel center and base surfaces given by the voxel boundary faces. The
neighbouring pyramids of the neighbouring voxels are joined together to form an
octahedron that is then split into 4 tetrahedra using diagonals of the voxel boundary
face (see Figure 5). In such way we get our 3D tetrahedral grid . Two nodes of
every tetrahedron correspond to the centers of neighbouring voxels, and the further
two nodes correspond to the voxel boundary vertices; every tetrahedron intersects a
common face of neighbouring voxels. In our method, only the centers of the voxels
will represent degree-of-freedom nodes (DF nodes), i.e., solving the equation at
a new time step, we update the segmentation function only in these DF nodes.
Additional nodes of the tetrahedra will not represent degrees of freedom, and we
will call them non-degree-of-freedom nodes (NDF nodes), and they will be used
in piecewise linear representation of the segmentation function. Let a function u
be given by discrete values in the voxel centers, i.e., in DF nodes. Then in the
NDF nodes we take the average value of the neighbouring DF nodal values. By
such defined values in the NDF nodes a piecewise linear approximation u h of u
on the tetrahedral grid is built.
For the tetrahedral grid

|∇

T h , given by the previous construction, we construct
a co-volume (dual) mesh. We modify the approach given in [65, 16] in such a way
that our co-volume mesh will consist of cells p associated only with DF nodes p of
T h , say p =1 ,...,M . Since there will be one-to-one correspondence between co-
volumes and DF nodes, without any confusion, we use the same notation for them.
For each DF node p of

T h , let C p denote the set of all DF nodes q connected to the
node p by an edge. This edge will be denoted by σ pq and its length by h pq . Then