01-12-2012, 02:34 PM
Multigrid Anisotropic Diffusion
1Multigrid.pdf (Size: 249 KB / Downloads: 24)
Abstract
A multigrid anisotropic diffusion algorithm for image
processing is presented. The multigrid implementation provides
an efficient hierarchical relaxation method that facilitates
the application of anisotropic diffusion to time-critical processes.
Through a multigrid V-cycle, the anisotropic diffusion equations
are successively transferred to coarser grids and used in a coarseto-
fine error correction scheme. When a coarse grid with a trivial
solution is reached, the coarse grid estimates of the residual
error can be propagated to the original grid and used to refine
the solution. The main benefits of the multigrid approach are
rapid intraregion smoothing and reduction of artifacts due to the
elimination of low-frequency error. In the paper, the theory of
multigrid anisotropic diffusion is developed. Then, the intergrid
transfer functions, relaxation techniques, diffusion coefficients,
and boundary conditions are discussed. The analysis includes
the examination of the storage requirements, the computational
cost, and the solution quality. Finally, experimental results are
reported that demonstrate the effectiveness of the multigrid
approach.
INTRODUCTION
ANISOTROPIC diffusion has been widely applied as a
mechanism for intraregion smoothing of images. The results
of anisotropic diffusion can be used to obtain an enhanced
image [14] or as a precursor to higher-level processing such
as shape description [15], edge detection [4], image segmentation
[3], and object identification and tracking [8]. Although
attractive in terms of edge localization and the ability to control
scale, anisotropic diffusion may lead to the creation of false
edges and false regions, among other ill effects. As with any
diffusion technique, processing high-resolution imagery via
anisotropic diffusion usually requires a significant number of
iterations, precluding real-time processing. Depending upon
the realization of the diffusion process, high-frequency error,
or noise, can be rapidly eliminated. Even when a well-posed
formation of anisotropic diffusion is given, limited relaxation
can lead to undesirable artifacts due to low-frequency error.
The multigrid approach alleviates the computational cost of
the diffusion process and reduces the processing artifacts that
can be associated with a reasonable number of iterations.
MULTIGRID ANISOTROPIC DIFFUSION
The Multigrid Approach
The marriage between multigrid methods and problems
defined by partial differential equations has been profitable.
The multigrid approach has been extended from simple finite
difference problems to include finite element/volume problem,
nonlinear problems, and time-dependent problems. Here,
we apply the multigrid technique to a nonlinear problem:
anisotropic diffusion of digital images.
Multigrid V-Cycle
To this point, only two-level correction methods have been
introduced. One may notice that computation of the error at
a coarse level has the same form as the original problem. So,
it is logical to repeat this correction process and compute the
error at the next coarse level to correct the error estimate itself.
This process can be continued recursively until a level with
an exact solution is reached. Finally, the error corrections can
be propagated back to the original resolution. This is called
the multigrid V-cycle, as the algorithm starts with an initial
estimate, telescopes down to the coarsest grid, and then returns
in order to the finest grid [7]. The so-called full multigrid Vcycle
starts with the exact solution at the coarsest grid and then
performs a succession of nested V-cycles to obtain a solution
at the finest grid. Full multigrid is valuable when no informed
initial estimate is available. Because the anisotropic diffusion
problem here relies on an initial estimate (the initial image),
the full multigrid V-cycle is not appropriate, and the V-cycle
method is utilized.