Anisotropic diffusion

Last updated

In image processing and computer vision, anisotropic diffusion, also called Perona–Malik diffusion, is a technique aiming at reducing image noise without removing significant parts of the image content, typically edges, lines or other details that are important for the interpretation of the image. [1] [2] [3] Anisotropic diffusion resembles the process that creates a scale space, where an image generates a parameterized family of successively more and more blurred images based on a diffusion process. Each of the resulting images in this family are given as a convolution between the image and a 2D isotropic Gaussian filter, where the width of the filter increases with the parameter. This diffusion process is a linear and space-invariant transformation of the original image. Anisotropic diffusion is a generalization of this diffusion process: it produces a family of parameterized images, but each resulting image is a combination between the original image and a filter that depends on the local content of the original image. As a consequence, anisotropic diffusion is a non-linear and space-variant transformation of the original image.

Contents

In its original formulation, presented by Perona and Malik in 1987, [1] the space-variant filter is in fact isotropic but depends on the image content such that it approximates an impulse function close to edges and other structures that should be preserved in the image over the different levels of the resulting scale space. This formulation was referred to as anisotropic diffusion by Perona and Malik even though the locally adapted filter is isotropic, but it has also been referred to as inhomogeneous and nonlinear diffusion [4] or Perona-Malik diffusion [5] by other authors. A more general formulation allows the locally adapted filter to be truly anisotropic close to linear structures such as edges or lines: it has an orientation given by the structure such that it is elongated along the structure and narrow across. Such methods are referred to as shape-adapted smoothing [6] [7] or coherence enhancing diffusion. [8] As a consequence, the resulting images preserve linear structures while at the same time smoothing is made along these structures. Both these cases can be described by a generalization of the usual diffusion equation where the diffusion coefficient, instead of being a constant scalar, is a function of image position and assumes a matrix (or tensor) value (see structure tensor).

Although the resulting family of images can be described as a combination between the original image and space-variant filters, the locally adapted filter and its combination with the image do not have to be realized in practice. Anisotropic diffusion is normally implemented by means of an approximation of the generalized diffusion equation: each new image in the family is computed by applying this equation to the previous image. Consequently, anisotropic diffusion is an iterative process where a relatively simple set of computation are used to compute each successive image in the family and this process is continued until a sufficient degree of smoothing is obtained.

Formal definition

Formally, let denote a subset of the plane and be a family of gray scale images. is the input image. Then anisotropic diffusion is defined as

where denotes the Laplacian, denotes the gradient, is the divergence operator and is the diffusion coefficient.

For , the output image is available as , with larger producing blurrier images.

controls the rate of diffusion and is usually chosen as a function of the image gradient so as to preserve edges in the image. Pietro Perona and Jitendra Malik pioneered the idea of anisotropic diffusion in 1990 and proposed two functions for the diffusion coefficient:

and

the constant K controls the sensitivity to edges and is usually chosen experimentally or as a function of the noise in the image.

Motivation

Let denote the manifold of smooth images, then the diffusion equations presented above can be interpreted as the gradient descent equations for the minimization of the energy functional defined by

where is a real-valued function which is intimately related to the diffusion coefficient. Then for any compactly supported infinitely differentiable test function ,

where the last line follows from multidimensional integration by parts. Letting denote the gradient of E with respect to the inner product evaluated at I, this gives

Therefore, the gradient descent equations on the functional E are given by

Thus by letting the anisotropic diffusion equations are obtained.

Ill-Posedness problem

Diffusion coefficient, , which is proposed by Perona and Malik can be negative value when . From here, the system is restricted by one-dimension for simplicity. If flux function is defined as , where and , then the

Perona-Malik equation can be rewritten based on the flux function by

. Here, are denoted by first derivative of time, position, and second derivative of position, respectively.

Now, it is clear that plays a role in diffusion coefficient of linear heat equation. By calculating ,

.

If , diffusion coefficient becomes negative and it leads to backward diffusion that enhances contrasts of image intensity rather than smoothes them in image processing.

In terms of theoretical perspective, backward diffusion is not only physically unnatural, but also gives numerically unstable solutions which are very sensitive to parameter(). In addition, it is known that backward diffusion have numerous of solutions and this is called ill-posedness problem.

To avoid the problem, regularization is necessary and people have shown that spatial regularizations lead to converged and constant steady-state solution. [9]

Regularization

Modified Perona-Malik model [10] (that is also known as regularization of P-M equation) will be discussed in this section. In this approach, the unknown is convolved with a Gaussian inside the non-linearity to obtain the modified Perona-Malik equation

Where .

The well-posedness of the equation can be achieved by regularization but it also introduces blurring effect, which is the main drawback of regularization. A prior knowledge of noise level is required as the choice of regularization parameter depends on it.

Applications

Anisotropic diffusion can be used to remove noise from digital images without blurring edges. With a constant diffusion coefficient, the anisotropic diffusion equations reduce to the heat equation which is equivalent to Gaussian blurring. This is ideal for removing noise but also indiscriminately blurs edges too. When the diffusion coefficient is chosen as an edge seeking function, such as in Perona-Malik, the resulting equations encourage diffusion (hence smoothing) within regions and prohibit it across strong edges. Hence the edges can be preserved while removing noise from the image.

Along the same lines as noise removal, anisotropic diffusion can be used in edge detection algorithms. By running the diffusion with an edge seeking diffusion coefficient for a certain number of iterations, the image can be evolved towards a piecewise constant image with the boundaries between the constant components being detected as edges.

See also

Related Research Articles

Ficks laws of diffusion mathematical descriptions of molecular diffusion

Fick's laws of diffusion describe diffusion and were derived by Adolf Fick in 1855. They can be used to solve for the diffusion coefficient, D. Fick's first law can be used to derive his second law which in turn is identical to the diffusion equation.

Navier–Stokes equations Equations describing the motion of viscous fluid substances

In physics, the Navier–Stokes equations are a set of partial differential equations which describe the motion of viscous fluid substances, named after French engineer and physicist Claude-Louis Navier and Anglo-Irish physicist and mathematician George Gabriel Stokes.

Heat equation

In mathematics and physics, the heat equation is a certain partial differential equation. Solutions of the heat equation are sometimes known as caloric functions. The theory of the heat equation was first developed by Joseph Fourier in 1822 for the purpose of modeling how a quantity such as heat diffuses through a given region.

In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a function on Euclidean space. It is usually denoted by the symbols ∇·∇, 2 or Δ. In a Cartesian coordinate system, the Laplacian is given by the sum of second partial derivatives of the function with respect to each independent variable. In other coordinate systems, such as cylindrical and spherical coordinates, the Laplacian also has a useful form. Informally, the Laplacian Δf(p) of a function f at a point p measures by how much the average value of f over small spheres or balls centered at p deviates from f(p).

The primitive equations are a set of nonlinear differential equations that are used to approximate global atmospheric flow and are used in most atmospheric models. They consist of three main sets of balance equations:

  1. A continuity equation: Representing the conservation of mass.
  2. Conservation of momentum: Consisting of a form of the Navier–Stokes equations that describe hydrodynamical flow on the surface of a sphere under the assumption that vertical motion is much smaller than horizontal motion (hydrostasis) and that the fluid layer depth is small compared to the radius of the sphere
  3. A thermal energy equation: Relating the overall temperature of the system to heat sources and sinks

The diffusion equation is a parabolic partial differential equation. In physics, it describes the macroscopic behavior of many micro-particles in Brownian motion, resulting from the random movements and collisions of the particles. In mathematics, it is related to Markov processes, such as random walks, and applied in many other fields, such as materials science, information theory, and biophysics. The diffusion equation is a special case of convection–diffusion equation, when bulk velocity is zero.

Geometrical optics, or ray optics, is a model of optics that describes light propagation in terms of rays. The ray in geometric optics is an abstraction useful for approximating the paths along which light propagates under certain circumstances.

Helmholtz equation

In mathematics, the eigenvalue problem for the Laplace operator is known as the Helmholtz equation. It corresponds to the linear partial differential equation:

In mathematics and physics, the Christoffel symbols are an array of numbers describing a metric connection. The metric connection is a specialization of the affine connection to surfaces or other manifolds endowed with a metric, allowing distances to be measured on that surface. In differential geometry, an affine connection can be defined without reference to a metric, and many additional concepts follow: parallel transport, covariant derivatives, geodesics, etc. also do not require the concept of a metric. However, when a metric is available, these concepts can be directly tied to the "shape" of the manifold itself; that shape is determined by how the tangent space is attached to the cotangent space by the metric tensor. Abstractly, one would say that the manifold has an associated (orthonormal) frame bundle, with each "frame" being a possible choice of a coordinate frame. An invariant metric implies that the structure group of the frame bundle is the orthogonal group O(p, q). As a result, such a manifold is necessarily a (pseudo-)Riemannian manifold. The Christoffel symbols provide a concrete representation of the connection of (pseudo-)Riemannian geometry in terms of coordinates on the manifold. Additional concepts, such as parallel transport, geodesics, etc. can then be expressed in terms of Christoffel symbols.

The electromagnetic wave equation is a second-order partial differential equation that describes the propagation of electromagnetic waves through a medium or in a vacuum. It is a three-dimensional form of the wave equation. The homogeneous form of the equation, written in terms of either the electric field E or the magnetic field B, takes the form:

The topological derivative is, conceptually, a derivative of a shape functional with respect to infinitesimal changes in its topology, such as adding an infinitesimal hole or crack. When used in higher dimensions than one, the term topological gradient is also used to name the first-order term of the topological asymptotic expansion, dealing only with infinitesimal singular domain perturbations. It has applications in shape optimization, topology optimization, image processing and mechanical modeling.

Spinodal decomposition

Spinodal decomposition occurs when one thermodynamic phase spontaneously separates into two phases. Decomposition occurs in the absence of nucleation because certain fluctuations in the system reduce the free energy. As a result, the phase change occurs immediately. There is no waiting, as there typically is when there is a nucleation barrier.

Radiative transfer equation and diffusion theory for photon transport in biological tissue

Photon transport in biological tissue can be equivalently modeled numerically with Monte Carlo simulations or analytically by the radiative transfer equation (RTE). However, the RTE is difficult to solve without introducing approximations. A common approximation summarized here is the diffusion approximation. Overall, solutions to the diffusion equation for photon transport are more computationally efficient, but less accurate than Monte Carlo simulations.

The Cauchy momentum equation is a vector partial differential equation put forth by Cauchy that describes the non-relativistic momentum transport in any continuum.

Diffusion movement of molecules, atoms, or ions from a region of high concentration to a region of low concentration

Diffusion is the net movement of anything from a region of higher concentration to a region of lower concentration. Diffusion is driven by a gradient in concentration.

Mild-slope equation Combined effects of diffraction and refraction for water waves propagating over variable depth and with lateral boundaries

In fluid dynamics, the mild-slope equation describes the combined effects of diffraction and refraction for water waves propagating over bathymetry and due to lateral boundaries—like breakwaters and coastlines. It is an approximate model, deriving its name from being originally developed for wave propagation over mild slopes of the sea floor. The mild-slope equation is often used in coastal engineering to compute the wave-field changes near harbours and coasts.

In the finite element method for the numerical solution of elliptic partial differential equations, the stiffness matrix represents the system of linear equations that must be solved in order to ascertain an approximate solution to the differential equation.

Total variation denoising

In signal processing, total variation denoising, also known as total variation regularization, is a process, most often used in digital image processing, that has applications in noise removal. It is based on the principle that signals with excessive and possibly spurious detail have high total variation, that is, the integral of the absolute gradient of the signal is high. According to this principle, reducing the total variation of the signal subject to it being a close match to the original signal, removes unwanted detail whilst preserving important details such as edges. The concept was pioneered by Rudin, Osher, and Fatemi in 1992 and so is today known as the ROF model.

In scientific computation and simulation, the method of fundamental solutions (MFS) is a technique for solving partial differential equations based on using the fundamental solution as a basis function. The MFS was developed to overcome the major drawbacks in the boundary element method (BEM) which also uses the fundamental solution to satisfy the governing equation. Consequently, both the MFS and the BEM are of a boundary discretization numerical technique and reduce the computational complexity by one dimensionality and have particular edge over the domain-type numerical techniques such as the finite element and finite volume methods on the solution of infinite domain, thin-walled structures, and inverse problems.

In numerical mathematics, the boundary knot method (BKM) is proposed as an alternative boundary-type meshfree distance function collocation scheme.

References

  1. 1 2 Pietro Perona and Jitendra Malik (November 1987). "Scale-space and edge detection using anisotropic diffusion". Proceedings of IEEE Computer Society Workshop on Computer Vision. pp. 16–22.
  2. Pietro Perona and Jitendra Malik (July 1990). "Scale-space and edge detection using anisotropic diffusion" (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. 12 (7): 629–639. doi:10.1109/34.56205.
  3. Guillermo Sapiro (2001). Geometric partial differential equations and image analysis. Cambridge University Press. p. 223. ISBN   978-0-521-79075-8.
  4. Joachim Weickert (July 1997). "A Review of Nonlinear Diffusion Filtering". Scale-Space Theory in Computer Vision. Springer, LNCS 1252. pp. 1–28. doi:10.1007/3-540-63167-4.
  5. Bernd Jähne and Horst Haußecker (2000). Computer Vision and Applications, A Guide for Students and Practitioners. Academic Press. ISBN   978-0-13-085198-7.
  6. Lindeberg, T., Scale-Space Theory in Computer Vision, Kluwer Academic Publishers, 1994, ISBN   0-7923-9418-6, (chapter 15).
  7. Andres Almansa and Tony Lindeberg (2000). "Fingerprint Enhancement by Shape Adaptation of Scale-Space Operators with Automatic Scale-Selection". IEEE Transactions on Image Processing. 9 (12): 2027–2042. Bibcode:2000ITIP....9.2027L. doi:10.1109/83.887971. PMID   18262941.
  8. Weickert, J Anisotropic diffusion in image processing, Teuber Verlag, Stuttgart, 1998.
  9. Weickert, Joachim. "A review of nonlinear diffusion filtering." International Conference on Scale-Space Theories in Computer Vision. Springer, Berlin, Heidelberg, 1997
  10. Guidotti,P Some Anisotropic Diffusions,2009.