Description
Nonlinear diffusion methods have been proved to be powerful methods in the
processing of 2D and 3D images. They allow for example a denoising and
smoothing of image intensities while retaining and enhancing edges.
Such an image smoothing can be understood as a
successive coarsening while certain structures are retained
on a fine scale -- an approach which is closely related to the major techniques in image
compression.
Finite Element methods are widespread to discretize and appropriately implement the diffusion based
models.
In various areas of scientific computing adaptive Finite Element methods have been incorporated to
substantially reduce the required degrees of freedom while conserving the approximation quality of the numerical
solution.
As time evolves, a successive coarsening in areas of smooth image intensity is near at hand.
The cost of the numerical algorithm, the storage requirements, and the transmission
time on computer networks scale with this complexity in terms of actual degrees of
freedom.
These efficiency perspectives have first been studied by Bänsch and Mikula,
who presented an adaptive Finite Element method. This method is based on simplicial grids generated by bisection and
then again successively coarsened in the diffusion process.
The major shortcoming of their approach is the enormous memory requirement for
the data structures describing the adaptive grid and the sparse matrices used in the
linear solver in each implicit time. Therefore, large 3D images -- as they are
widespread in medical imaging -- are difficult to manage.
We present a method that avoids these shortcomings and comes along with
minimal storage requirements. The ingredients of out method are:
|
adaptive quad-- and octrees, with accompanying piecewise bilinear, respectively trilinear Finite Element spaces
are procedurally handled only,
|
error indicators on grid nodes and a suitable threshold value implicitly
describe the adaptive grid (no explicit adaptive grid structure is required), and by
invoking a certain saturation condition for the nodal indicators, we ensure
robustness and one level transitions only on the resulting adaptive grid,
|
the adaptive Finite Element space is defined as an implicitly constrained
discrete space on the full grid,
|
and instead of dealing with explicitly stored sparse matrices, the linear
solver in each time-step uses "on--the--fly" matrix multiplication
based on efficient grid traversals.
| |
We assume the images to have dimension 
in each direction for some number
|
|
To define the adaptive grid we prescribe a boolean valued
stopping criterion on each coarse element. This stopping criterion tells any
depth-first traversal routine whether to stop on this level or to descent
further in the hierarchy. If we define an error indicator 
we obtain such a
criterion by testing this error indicator with a threshold.
It is obvious that hanging nodes in the grid may occur. By enforcing a saturation condition on the stopping criterion, we ensure that only one-level transitions occur.
Saturation condition. Error indicator values on the nodes of an Element E are always greater or equal to the values on the child nodes of E.
|
|
Since we now have to deal with grids that contain only one level transitions, we can adjust the corresponding numerics in a simple way to keep the approximations continuous. The only configurations that appear are depicted below.
|
|
A resulting hierarchcal implicitely defined adaptive grid may then look like
|
|
From left to right several timesteps of the selective image smoothing on implicitly defined adaptive grids are shown. Click on the image to load an animation. |
|
Nonlinear diffusion has been applied to a 3D medical dataset containing more than 16 million unknowns. Depicted is a transparent isosurface visualization of the dataset. Click no the image to load a movie of the rotating 'glass head'. |
|
|
|
Results of a brain segmentation in 3D with tangential smoothing on the above dataset. The segment boundaries are defined by gradient threshold criterion. Click on the image to load a movie of the rotatnig 'segmented head'. |
|
Anisotropic nonlinear Diffusion on implicitely defined adaptive grids. Click on the image to load an animation. The movie shows the evolution of the noisy image on the right, whereas the corresponding grids are shown on the left. The number of unknowns is significantly reduced during the evolution. |
|
