Anisotropic diffusion

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

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[edit]

Formally, let  \Omega \subset \mathbb{R}^2 denote a subset of the plane and  I(\cdot,t): \Omega \rightarrow \mathbb{R} be a family of gray scale images, then anisotropic diffusion is defined as

 \frac{\partial I}{\partial t} = \mathrm{div} \left( c(x,y,t) \nabla I \right)= \nabla c \cdot \nabla I + c(x,y,t) \Delta I

where  \Delta denotes the Laplacian,  \nabla denotes the gradient,  \mathrm{div}(\dots) is the divergence operator and  c(x,y,t) is the diffusion coefficient.  c(x,y,t) 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:

 c\left(\|\nabla I\|\right) = e^{-\left(\|\nabla I\| / K\right)^2}

and

 c\left(\| \nabla I\| \right) = \frac{1}{1 + \left(\frac{\|\nabla I\|}{K}\right)^2}

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

Motivation[edit]

Let  M 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  E: M \rightarrow \mathbb{R} defined by

 E[I] = \frac{1}{2} \int_{\Omega} g\left( \| \nabla I(x)\|^2 \right)\, dx

where  g:\mathbb{R} \rightarrow \mathbb{R} is a real-valued function which we will see is intimately related to the diffusion coefficient. Then for any compactly supported infinitely differentiable test function  h , we have

 \begin{align}
\left.\frac{d}{dt} \right|_{t=0} E[I + th] &= \frac{d}{dt} \big|_{t=0}\frac{1}{2} \int_{\Omega} g\left( \| \nabla (I+th)(x)\|^2 \right)\, dx \\
                                   &= \int_{\Omega} g'\left(\| \nabla I(x)\|^2 \right) \nabla I \cdot \nabla h\, dx  \\
                                   &= -\int_{\Omega} \mathrm{div}(g'\left( \| \nabla I(x)\|^2 \right) \nabla I)  h\, dx
\end{align}

where the last line follow from multidimensional integration by parts. Letting  \nabla E_I denote the gradient of E with respect to the  L^2(\Omega, \mathbb{R}) inner product evaluated at I, this gives

 \nabla E_I = - \mathrm{div}(g'\left( \| \nabla I(x)\|^2 \right) \nabla I)

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

 \frac{\partial I}{\partial t} = - \nabla E_I =  \mathrm{div}(g'\left( \| \nabla I(x)\|^2 \right) \nabla I)

Thus by letting  c = g' we obtain the anisotropic diffusion equations.

Regularization[edit]

Modified Perona-Malik model[9] (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

 \frac{\partial I}{\partial t}=\mathrm{div} \left(c(|DG_{\sigma} * I|)\nabla I \right)

Where  G_{\sigma}=C{\sigma}^{-\left(1/2\right)}exp\left(-|x|^2/4{\sigma}\right).

The well-posedness of the equation can be achieved by regularization but it also introduce 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[edit]

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 and 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[edit]

External links[edit]

  • Mathematica PeronaMalikFilter function.
  • IDL nonlinear anisotropic diffusion package(edge enhancing and coherence enhancing): [1]

References[edit]

  1. ^ a b 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". 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 0-13-085198-1. 
  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. doi:10.1109/83.887971. PMID 18262941. 
  8. ^ Weickert, J Anisotropic diffusion in image processing, Teuber Verlag, Stuttgart, 1998.
  9. ^ Guidotti,P Some Anisotropic Diffusions,2009.