24-04-2014, 12:17 PM
Multigrid Anisotropic Diffusion
Multigrid Anisotropic.pdf (Size: 249 KB / Downloads: 13)
Abstract
A multigrid anisotropic diffusion algorithm for im-
age processing is presented. The multigrid implementation pro-
vides 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 coarse-
to-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 re-
sults 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 segmen-
tation [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.
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 prob-
lem, nonlinear problems, and time-dependent problems. Here,
we apply the multigrid technique to a nonlinear problem:
anisotropic diffusion of digital images.
Relaxation
The choice of the relaxation method for the discrete
anisotropic diffusion problem is important in both the
traditional and multigrid solutions. The Jacobi (6) and
Gauss–Seidel (7) iterates have been introduced. Because
the solutions at each grid point (at each pixel site) are
replaced simultaneously with the Jacobi approach, oscillatory
behavior can occur and convergence rates can be reduced. The
Gauss–Seidel approach can be utilized, but, unlike the Jacobi
iterates, the Gauss-Seidel iterates are affected by the order of
replacement. For the anisotropic diffusion problem, streaking
artifacts have been observed when sequential updating is used.
This can be alleviated by utilizing a red-black update scheme
on each row, and a zebra scheme on the columns [7]. Simply
stated, the grid sites at even columns and even rows are
computed, then those with odd rows and odd columns, then
odd rows and even columns, and finally even rows with odd
columns. This Gauss–Seidel update scheme is used for all
results produced in Section V.