Namespaces
Variants
Actions

Difference between revisions of "Edge detection"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (AUTOMATIC EDIT (latexlist): Replaced 6 formulas out of 6 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
 
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 6 formulas, 6 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|done}}
 
An early processing stage in image processing and computer vision, aimed at detecting and characterizing discontinuities in the image domain.
 
An early processing stage in image processing and computer vision, aimed at detecting and characterizing discontinuities in the image domain.
  
Line 5: Line 13:
 
A non-trivial aspect of edge-based analysis of image data, however, concerns what should be meant by a discontinuity in image brightness. Real-world image data are inherently discrete, and for a function defined on a discrete domain, there is no natural notion of  "discontinuity" , and there is no inherent way to judge what are the edges in a given discrete image.
 
A non-trivial aspect of edge-based analysis of image data, however, concerns what should be meant by a discontinuity in image brightness. Real-world image data are inherently discrete, and for a function defined on a discrete domain, there is no natural notion of  "discontinuity" , and there is no inherent way to judge what are the edges in a given discrete image.
  
An early approach to edge detection involved the convolution of the image <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120040/e1200401.png" /> by a Gaussian kernel <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120040/e1200402.png" />, followed by the detection of zero-crossings in the Laplacian response [[#References|[a1]]] (cf. also [[Scale-space theory|Scale-space theory]]). However, such edge curves satisfying
+
An early approach to edge detection involved the convolution of the image $f$ by a Gaussian kernel $g ( . ; t )$, followed by the detection of zero-crossings in the Laplacian response [[#References|[a1]]] (cf. also [[Scale-space theory|Scale-space theory]]). However, such edge curves satisfying
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120040/e1200403.png" /></td> </tr></table>
+
\begin{equation*} \nabla ^ { 2 } ( g (. ; t ) ^ { * } f ( . ) ) = 0 \end{equation*}
  
 
give rise to false edges and have poor localization at curved edges.
 
give rise to false edges and have poor localization at curved edges.
Line 17: Line 25:
 
ii) the third-order directional derivative in the gradient direction is negative.
 
ii) the third-order directional derivative in the gradient direction is negative.
  
In terms of partial derivatives, for a two-dimensional image <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120040/e1200404.png" /> this edge definition can be written as
+
In terms of partial derivatives, for a two-dimensional image $L : \mathbf{R} \rightarrow \mathbf{R}$ this edge definition can be written as
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120040/e1200405.png" /></td> </tr></table>
+
\begin{equation*} \left\{ \begin{array} { l } { L _ { x } ^ { 2 } L _ { x x } + 2 L _ { x } L _ { y } L _ { x y } + L _ { y } ^ { 2 } L _ { y y } = 0, } \\ { L _ { x } ^ { 3 } L _ { x x x } + 3 L _ { x } ^ { 2 } L _ { y } L _ { x x y } + 3 L _ { x } L _ { y } ^ { 2 } L _ { x y y }  + L _ { y } ^ { 3 } L _ { y y y } &lt; 0. } \end{array} \right. \end{equation*}
  
Again, the computation of discrete derivative approximations is preceded by smoothing the image <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e120/e120040/e1200406.png" /> with a Gaussian kernel, and the choice of different standard deviations of the Gaussian kernel gives rise to edges at different scales (see [[Scale-space theory|Scale-space theory]] or [[#References|[a5]]]). While other choices of linear smoothing kernels have also been advocated, their shapes can often be well approximated by Gaussians [[#References|[a3]]], [[#References|[a6]]], [[#References|[a7]]].
+
Again, the computation of discrete derivative approximations is preceded by smoothing the image $f$ with a Gaussian kernel, and the choice of different standard deviations of the Gaussian kernel gives rise to edges at different scales (see [[Scale-space theory|Scale-space theory]] or [[#References|[a5]]]). While other choices of linear smoothing kernels have also been advocated, their shapes can often be well approximated by Gaussians [[#References|[a3]]], [[#References|[a6]]], [[#References|[a7]]].
  
 
Other approaches to edge detection involve the thresholding of edge strength measures, the computation of intensity derivatives from local least squares fitting, and functional minimization (see also [[#References|[a8]]]).
 
Other approaches to edge detection involve the thresholding of edge strength measures, the computation of intensity derivatives from local least squares fitting, and functional minimization (see also [[#References|[a8]]]).
Line 28: Line 36:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D. Marr,  E. Hildreth,  "Theory of edge detection"  ''Proc. R. Soc. London'' , '''207'''  (1980)  pp. 187–217</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.M. Haralick,  "Digital step edges from zero-crossings of second directional derivatives"  ''IEEE Trans. Pattern Anal. Machine Intell.'' , '''6'''  (1984)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Canny,  "A computational approach to edge detection"  ''IEEE Trans. Pattern Anal. Machine Intell.'' , '''8''' :  6  (1986)  pp. 679–698</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A.F. Korn,  "Toward a symbolic representation of intensity changes in images"  ''IEEE Trans. Pattern Anal. Machine Intell.'' , '''10''' :  5  (1988)  pp. 610–625</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  T. Lindeberg,  "Edge detection and ridge detection with automatic scale selection"  ''Internat. J. Computer Vision'' , '''30''' :  2  (1998)  pp. 117–154</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  V. Torre,  T.A. Poggio,  "On edge detection"  ''IEEE Trans. Pattern Anal. Machine Intell.'' , '''8''' :  2  (1980)  pp. 147–163</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  R. Deriche,  "Using Canny's criteria to derive a recursively implemented optimal edge detector"  ''Internat. J. Computer Vision'' , '''1'''  (1987)  pp. 167–187</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  R. Jain,  et al.,  "Machine vision" , McGraw-Hill  (1995)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  P. Perona,  J. Malik,  "Scale-space and edge detection using anisotropic diffusion"  ''IEEE Trans. Pattern Anal. Machine Intell.'' , '''12''' :  7  (1990)  pp. 629–639</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  "Geometry-driven diffusion in computer vision"  B.M. ter Haar Romeny (ed.) , Kluwer Acad. Publ.  (1994)</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  D. Marr,  E. Hildreth,  "Theory of edge detection"  ''Proc. R. Soc. London'' , '''207'''  (1980)  pp. 187–217</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  R.M. Haralick,  "Digital step edges from zero-crossings of second directional derivatives"  ''IEEE Trans. Pattern Anal. Machine Intell.'' , '''6'''  (1984)</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  J. Canny,  "A computational approach to edge detection"  ''IEEE Trans. Pattern Anal. Machine Intell.'' , '''8''' :  6  (1986)  pp. 679–698</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  A.F. Korn,  "Toward a symbolic representation of intensity changes in images"  ''IEEE Trans. Pattern Anal. Machine Intell.'' , '''10''' :  5  (1988)  pp. 610–625</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  T. Lindeberg,  "Edge detection and ridge detection with automatic scale selection"  ''Internat. J. Computer Vision'' , '''30''' :  2  (1998)  pp. 117–154</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  V. Torre,  T.A. Poggio,  "On edge detection"  ''IEEE Trans. Pattern Anal. Machine Intell.'' , '''8''' :  2  (1980)  pp. 147–163</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  R. Deriche,  "Using Canny's criteria to derive a recursively implemented optimal edge detector"  ''Internat. J. Computer Vision'' , '''1'''  (1987)  pp. 167–187</td></tr><tr><td valign="top">[a8]</td> <td valign="top">  R. Jain,  et al.,  "Machine vision" , McGraw-Hill  (1995)</td></tr><tr><td valign="top">[a9]</td> <td valign="top">  P. Perona,  J. Malik,  "Scale-space and edge detection using anisotropic diffusion"  ''IEEE Trans. Pattern Anal. Machine Intell.'' , '''12''' :  7  (1990)  pp. 629–639</td></tr><tr><td valign="top">[a10]</td> <td valign="top">  "Geometry-driven diffusion in computer vision"  B.M. ter Haar Romeny (ed.) , Kluwer Acad. Publ.  (1994)</td></tr></table>

Latest revision as of 15:31, 1 July 2020

An early processing stage in image processing and computer vision, aimed at detecting and characterizing discontinuities in the image domain.

The importance of edge detection for early machine vision is usually motivated from the observation that under rather general assumptions about the image formation process, a discontinuity in image brightness can be assumed to correspond to a discontinuity in either depth, surface orientation, reflectance, or illumination. In this respect, edges in the image domain constitute a strong link to physical properties of the world. A representation of image information in terms of edges is also compact in the sense that the two-dimensional image pattern is represented by a set of one-dimensional curves. For these reasons, edges have been used as main features in a large number of computer vision algorithms.

A non-trivial aspect of edge-based analysis of image data, however, concerns what should be meant by a discontinuity in image brightness. Real-world image data are inherently discrete, and for a function defined on a discrete domain, there is no natural notion of "discontinuity" , and there is no inherent way to judge what are the edges in a given discrete image.

An early approach to edge detection involved the convolution of the image $f$ by a Gaussian kernel $g ( . ; t )$, followed by the detection of zero-crossings in the Laplacian response [a1] (cf. also Scale-space theory). However, such edge curves satisfying

\begin{equation*} \nabla ^ { 2 } ( g (. ; t ) ^ { * } f ( . ) ) = 0 \end{equation*}

give rise to false edges and have poor localization at curved edges.

A more refined approach is the notion of non-maximum suppression [a2], [a3], [a4], where edges are defined as points at which the gradient magnitude assumes a local maximum in the gradient direction. In differential-geometric terms, such edge points can be characterized as points at which [a5]:

i) the second-order directional derivative in the gradient direction is zero; and

ii) the third-order directional derivative in the gradient direction is negative.

In terms of partial derivatives, for a two-dimensional image $L : \mathbf{R} \rightarrow \mathbf{R}$ this edge definition can be written as

\begin{equation*} \left\{ \begin{array} { l } { L _ { x } ^ { 2 } L _ { x x } + 2 L _ { x } L _ { y } L _ { x y } + L _ { y } ^ { 2 } L _ { y y } = 0, } \\ { L _ { x } ^ { 3 } L _ { x x x } + 3 L _ { x } ^ { 2 } L _ { y } L _ { x x y } + 3 L _ { x } L _ { y } ^ { 2 } L _ { x y y } + L _ { y } ^ { 3 } L _ { y y y } < 0. } \end{array} \right. \end{equation*}

Again, the computation of discrete derivative approximations is preceded by smoothing the image $f$ with a Gaussian kernel, and the choice of different standard deviations of the Gaussian kernel gives rise to edges at different scales (see Scale-space theory or [a5]). While other choices of linear smoothing kernels have also been advocated, their shapes can often be well approximated by Gaussians [a3], [a6], [a7].

Other approaches to edge detection involve the thresholding of edge strength measures, the computation of intensity derivatives from local least squares fitting, and functional minimization (see also [a8]).

A subject which has been given large attention during the 1990s is the replacement of the linear smoothing operation by a non-linear smoothing step, with the goal of avoiding smoothing across object boundaries [a9], [a10].

References

[a1] D. Marr, E. Hildreth, "Theory of edge detection" Proc. R. Soc. London , 207 (1980) pp. 187–217
[a2] R.M. Haralick, "Digital step edges from zero-crossings of second directional derivatives" IEEE Trans. Pattern Anal. Machine Intell. , 6 (1984)
[a3] J. Canny, "A computational approach to edge detection" IEEE Trans. Pattern Anal. Machine Intell. , 8 : 6 (1986) pp. 679–698
[a4] A.F. Korn, "Toward a symbolic representation of intensity changes in images" IEEE Trans. Pattern Anal. Machine Intell. , 10 : 5 (1988) pp. 610–625
[a5] T. Lindeberg, "Edge detection and ridge detection with automatic scale selection" Internat. J. Computer Vision , 30 : 2 (1998) pp. 117–154
[a6] V. Torre, T.A. Poggio, "On edge detection" IEEE Trans. Pattern Anal. Machine Intell. , 8 : 2 (1980) pp. 147–163
[a7] R. Deriche, "Using Canny's criteria to derive a recursively implemented optimal edge detector" Internat. J. Computer Vision , 1 (1987) pp. 167–187
[a8] R. Jain, et al., "Machine vision" , McGraw-Hill (1995)
[a9] P. Perona, J. Malik, "Scale-space and edge detection using anisotropic diffusion" IEEE Trans. Pattern Anal. Machine Intell. , 12 : 7 (1990) pp. 629–639
[a10] "Geometry-driven diffusion in computer vision" B.M. ter Haar Romeny (ed.) , Kluwer Acad. Publ. (1994)
How to Cite This Entry:
Edge detection. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Edge_detection&oldid=49936
This article was adapted from an original article by Tony Lindeberg (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article