View source for Edge detection

{{Short description|Image processing method}}
{{FeatureDetectionCompVisNavbox}}

'''Edge detection''' includes a variety of [[mathematical]] methods that aim at identifying '''''edges''''', defined as [[curve]]s in a [[digital image]] at which the [[luminous intensity|image brightness]] changes sharply or, more formally, has [[Discontinuity (mathematics)|discontinuities]]. The same problem of finding discontinuities in one-dimensional signals is known as ''[[step detection]]'' and the problem of finding signal discontinuities over time is known as ''[[change detection]]''. Edge detection is a fundamental tool in [[image processing]], [[machine vision]] and [[computer vision]], particularly in the areas of [[feature detection (computer vision)|feature detection]] and [[feature extraction]].<ref>{{cite book|last=Umbaugh|first=Scott E|title=Digital image processing and analysis : human and computer vision applications with CVIPtools|year=2010|publisher=CRC Press|location=Boca Raton, FL|isbn=978-1-4398-0205-2|edition=2nd}}</ref>

== Motivations ==
[[File:Ääretuvastuse näide.png|thumb|500px|[[Canny edge detection]] applied to a photograph]]
The purpose of detecting sharp changes in image brightness is to capture important events and changes in properties of the world.
It can be shown that under rather general assumptions for an image formation model, discontinuities in image brightness are likely to correspond to:<ref>H.G. Barrow and J.M. Tenenbaum (1981) "Interpreting line drawings as three-dimensional surfaces", Artificial Intelligence, vol 17, issues 1–3, pages 75–116.</ref><ref name=lin95>{{SpringerEOM| title=Edge detection | id=Edge_detection | oldid=17883 | first=Tony | last=Lindeberg }}</ref>
* discontinuities in depth,
* discontinuities in surface orientation,
* changes in material properties and
* variations in scene illumination.
In the ideal case, the result of applying an edge detector to an image may lead to a set of connected curves that indicate the boundaries of objects, the boundaries of surface markings as well as curves that correspond to discontinuities in surface orientation.
Thus, applying an edge detection algorithm to an image may significantly reduce the amount of data to be processed and may therefore filter out information that may be regarded as less relevant, while preserving the important structural properties of an image.
If the edge detection step is successful, the subsequent task of interpreting the information contents in the original image may therefore be substantially simplified.
However, it is not always possible to obtain such ideal edges from real life images of moderate complexity.

Edges extracted from non-trivial images are often hampered by ''fragmentation'', meaning that the edge curves are not connected, missing edge segments as well as ''false edges'' not corresponding to interesting phenomena in the image – thus complicating the subsequent task of interpreting the image data.<ref name=lin98>[http://kth.diva-portal.org/smash/record.jsf?pid=diva2%3A452310&dswid=386 T. Lindeberg (1998) "Edge detection and ridge detection with automatic scale selection", International Journal of Computer Vision, 30, 2, pages 117–154.]</ref>

Edge detection is one of the fundamental steps in image processing, image analysis, image pattern recognition, and computer vision techniques.

== Edge properties ==

The edges extracted from a two-dimensional image of a three-dimensional scene can be classified as either viewpoint dependent or viewpoint independent.
A ''viewpoint independent edge'' typically reflects inherent properties of the three-dimensional objects, such as surface markings and surface shape.
A ''viewpoint dependent edge'' may change as the viewpoint changes, and typically reflects the geometry of the scene, such as objects occluding one another.

A typical edge might for instance be the border between a block of red color and a block of yellow. In contrast a '''[[line (mathematics)|line]]''' (as can be extracted by a [[ridge detection|ridge detector]]) can be a small number of [[pixel]]s of a different color on an otherwise unchanging background. For a line, there may therefore usually be one edge on each side of the line.

== A simple edge model ==
Although certain literature has considered the detection of ideal step edges, the edges obtained from natural images are usually not at all ideal step edges. Instead they are normally affected by one or several of the following effects:
* focal blur caused by a finite [[depth-of-field]] and finite [[point spread function]].
* [[penumbra|penumbral blur]] caused by shadows created by light sources of non-zero radius.
* [[shading]] at a smooth object
A number of researchers have used a Gaussian smoothed step edge (an [[error function]]) as the simplest extension of the ideal step edge model for modeling the effects of edge blur in practical applications.<ref name=lin98/><ref>W. Zhang and F. Bergholm (1997) "[https://link.springer.com/article/10.1023/A:1007923307644 Multi-scale blur estimation and edge type classification for scene analysis]", International Journal of Computer Vision, vol 24, issue 3, Pages: 219–250.</ref>
Thus, a one-dimensional image <math>f</math> that has exactly one edge placed at <math>x = 0</math> may be modeled as:

:<math>f(x) = \frac{I_r - I_\ell}{2} \left( \operatorname{erf}\left(\frac{x}{\sqrt{2}\sigma}\right) + 1\right) + I_\ell.</math>

At the left side of the edge, the intensity is <math>I_\ell = \lim_{x \rightarrow -\infty} f(x)</math>, and right of the edge it is
<math>I_r = \lim_{x \rightarrow \infty} f(x)</math>. The scale parameter <math>\sigma</math> is called the blur scale of the edge. Ideally this scale parameter should be adjusted based on the quality of image to avoid destroying true edges of the image.{{citation needed|date=September 2015}}

== Difficulty ==

Outside of images with simple objects or featuring well-controlled lighting, edge detection is not a trivial task, since it can be difficult to determine what threshold should be used to define an edge between two pixels.<ref name=lin98/> For example, in the following one-dimensional signal, most would intuitively say there is an edge between the 4th and 5th pixels:

{| style="border:0; margin:0.5em auto"
|-
| style="border:1px solid #000; padding:5px 10px;" | 5
| style="border:1px solid #000; padding:5px 10px;" | 7
| style="border:1px solid #000; padding:5px 10px;" | 6
| style="border:1px solid #000; padding:5px 10px;" | 4
| style="border:1px solid #000; padding:5px" | 152
| style="border:1px solid #000; padding:5px" | 148
| style="border:1px solid #000; padding:5px" | 149
|- style="height:30px"
| style="background:#050505" |

| style="background:#070707" |

| style="background:#060606" |

| style="background:#040404" |

| style="background:#989898" |

| style="background:#949494" |

| style="background:#959595" |
|}

However, if the intensity difference between the 4th and the 5th pixels were smaller, it would not be as easy to say that there should be an edge in the corresponding region. Similarly, if the intensity differences between the adjacent neighboring pixels were higher, one could argue that more than one edge should be considered to exist, or even none at all.

{| style="border:0; margin:0.5em auto"
|-
| style="border:1px solid #000; padding:5px 10px;" | 5
| style="border:1px solid #000; padding:5px 10px;" | 7
| style="border:1px solid #000; padding:5px 10px;" | 6
| style="border:1px solid #000; padding:5px 10px;" | 61
| style="border:1px solid #000; padding:5px" | 113
| style="border:1px solid #000; padding:5px" | 148
| style="border:1px solid #000; padding:5px" | 149
|- style="height:30px"
| style="background:#050505" |

| style="background:#070707" |

| style="background:#060606" |

| style="background:#3d3d3d" |

| style="background:#717171" |

| style="background:#949494" |

| style="background:#959595" |
|}

== Approaches ==
There are many methods for edge detection, but most of them can be grouped into two categories, search-based and [[Zero crossing|zero-crossing]] based.
The search-based methods detect edges by first computing a measure of edge strength, usually a [[first-order derivative expression]] such as the gradient magnitude, and then searching for local directional maxima of the gradient magnitude using a computed estimate of the local orientation of the edge, usually the gradient direction.
The zero-crossing based methods search for zero crossings in a [[second-order derivative expression]] computed from the image in order to find edges, usually the zero-crossings of the [[Laplacian]] or the zero-crossings of a non-linear differential expression. As a pre-processing step to edge detection, a smoothing stage, typically [[Gaussian smoothing]], is almost always applied (see also [[noise reduction]]).

The edge detection methods that have been published mainly differ in the types of smoothing filters that are applied and the way the measures of edge strength are computed. As many edge detection methods rely on the computation of image gradients, they also differ in the types of filters used for computing gradient estimates in the ''x''- and ''y''-directions.

A survey of a number of different edge detection methods can be found in (Ziou and Tabbone 1998);<ref>D. Ziou and S. Tabbone (1998) "[https://web.archive.org/web/20191008173716/https://pdfs.semanticscholar.org/587a/acc01a4c33f0fe7fb172f5db785f40522b57.pdf Edge detection techniques: An overview]", International Journal of Pattern Recognition and Image Analysis, 8(4):537–559, 1998</ref> see also the encyclopedia articles on edge detection in ''Encyclopedia of Mathematics''<ref name=lin95/> and Encyclopedia of Computer Science and Engineering.<ref>[http://mrw.interscience.wiley.com/emrw/9780470050118/ecse/article/ecse603/current/abstract J. M. Park and Y. Lu (2008) "Edge detection in grayscale, color, and range images", in B. W. Wah (editor)  Encyclopedia of Computer Science and Engineering, doi 10.1002/9780470050118.ecse603]</ref>

=== Canny ===
{{main|Canny edge detector}}
[[John Canny]] considered the mathematical problem of deriving an optimal smoothing filter, given the criteria of detection, localization and minimizing multiple responses to a single edge.<ref>J. Canny (1986) "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.420.3300&rep=rep1&type=pdf A computational approach to edge detection]", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol 8, pages 679–714.</ref> He showed that the optimal filter, given these assumptions, is a sum of four exponential terms. He also showed that this filter can be well approximated by first-order derivatives of Gaussians.
Canny also introduced the notion of non-maximum suppression, which means that, given the presmoothing filters, edge points are defined as points where the gradient magnitude assumes a local maximum in the gradient direction.
Looking for the zero crossing of the 2nd derivative along the gradient direction was first proposed by [[Haralick]].<ref>
R. Haralick, (1984) "[http://haralick-org.torahcode.us/journals/04767475.pdf Digital step edges from zero crossing of second directional derivatives]", IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(1):58–68.
</ref>
It took less than two decades to find a modern geometric variational meaning for that operator, that links it to the [[Marr–Hildreth algorithm|Marr–Hildreth]] (zero crossing of the Laplacian) edge detector.
That observation was presented by [[Ron Kimmel]] and [[Alfred Bruckstein]].<ref>{{Cite web |url=https://www.cs.technion.ac.il/~ron/PAPERS/laplacian_ijcv2003.pdf |title=R. Kimmel and A.M. Bruckstein (2003) "On regularized Laplacian zero crossings and other optimal edge integrators", ''International Journal of Computer Vision'', 53(3) pages 225–243. |access-date=2019-09-15 |archive-date=2021-03-08 |archive-url=https://web.archive.org/web/20210308012954/https://www.cs.technion.ac.il/~ron/PAPERS/laplacian_ijcv2003.pdf |url-status=dead }}</ref>

Although his work was done in the early days of computer vision, the [[Canny edge detector]] (including its variations) is still a state-of-the-art edge detector.<ref>[[Linda Shapiro|Shapiro L. G.]] & Stockman G. C. (2001) Computer Vision. London etc.: Prentice Hall, Page 326.</ref> Edge detectors that perform better than the Canny usually require longer computation times or a greater number of parameters.

=== Kovalevsky ===
[[Vladimir Antonovich Kovalevsky|Vladimir A. Kovalevsky]]<ref>Kovalevsky, V., Image Processing with Cellular Topology, Springer 2021, ISBN 978-981-16-5771-9, pp. 113-138</ref> has suggested a quite different approach. He uses a preprocessing of the image with the Sigma filter<ref> Lee, J.-S., Digital image smoothing and the sigma filter. Computer Vision, Graphics, and Information Processing. 1983, 24(2): 255-69 </ref> and with a special filter for the dilution of the ramps. This method uses no brightness of the image but only the intensities of the color channels which is important for detecting an edge between two adjacent pixels of equal brightness but different colors. The method scans the image two times: first along the horizontal lines and second along the vertical columns. In each horizontal line six consequent adjacent pixels are considered and five color difference between each two adjacent pixels are calculated. Each color difference is the sum of absolute differences of the intensities of the color channels Red, Green, and Blue of the corresponding adjacent pixels. If this sum is greater than a given threshold, then the sign of the color difference is set equal to the sign of the difference of the green intensities. If the green difference is zero, then the sign of the color difference is set equal to the sign of the difference of the red intensities. If, however, both the green and the red differences are zero, then the sign of the color difference is set equal to the sign of the blue difference which in this case cannot be zero since the sum is greater than the threshold. 
Certain conditions for the values and signs of the five color differences are specified in such way that if the conditions are fulfilled, then a short vertical stroke is put between the third and the fourth of the six pixels as the label of the edge.
Similar calculations are performed for the vertical columns. In this case a short horizontal stroke is put between the third and the fourth of the six subsequent pixels. The vertical and horizontal strokes (being the one-dimensional cells of an abstract cell complex corresponding to the image) mostly compose a connected sequence representing the edge.
This method is robust and very fast and, what is more important, it can detect edges between adjacent pixels of equal brightness’s if the color difference between these pixels is greater than the threshold.

The Canny–Deriche detector was derived from similar mathematical criteria as the Canny edge detector, although starting from a discrete viewpoint and then leading to a set of recursive filters for image smoothing instead of [[exponential filter]]s or Gaussian filters.<ref>R. Deriche (1987) ''Using Canny's criteria to derive an optimal edge detector recursively implemented'', Int. J. Computer Vision, vol 1, pages 167–187.</ref>

The [[Edge detection#Differential|differential edge detector]] described below can be seen as a reformulation of Canny's method from the viewpoint of differential invariants computed from a [[scale space representation]] leading to a number of advantages in terms of both theoretical analysis and sub-pixel implementation. In that aspect, [[Log Gabor filter]] have been shown to be a good choice to extract boundaries in natural scenes.<ref>Sylvain Fischer, Rafael Redondo, Laurent Perrinet, Gabriel Cristobal. [https://link.springer.com/content/pdf/10.1155/2007/90727.pdf Sparse approximation of images inspired from the functional architecture of the primary visual areas]. EURASIP Journal on Advances in Signal Processing, special issue on Image Perception, 2007</ref>

=== Other first-order methods ===
Different gradient operators can be applied to estimate image gradients from the input image or a smoothed version of it. The simplest approach is to use central differences:

:<math>
\begin{align}
L_x(x, y) & = -\frac 1 2 L(x-1, y) + 0 \cdot L(x, y) + \frac 1 2 \cdot L(x+1, y) \\[8pt]
L_y(x, y) & = -\frac1 2 L(x, y-1) + 0 \cdot L(x, y) + \frac 1 2 \cdot L(x, y+1),
\end{align}
</math>

corresponding to the application of the following filter masks to the image data:

:<math>
L_y = \begin{bmatrix}
+1/2 & 0 & -1/2
\end{bmatrix} L
\quad \text{and} \quad
L_x = \begin{bmatrix}
+1/2 \\
0 \\
-1/2
\end{bmatrix} L.
</math>

The well-known and earlier [[Sobel operator]] is based on the following filters:

:<math>
L_y = \begin{bmatrix}
+1 & 0 & -1 \\
+2 & 0 & -2 \\
+1 & 0 & -1
\end{bmatrix} L
\quad \text{and} \quad
L_x = \begin{bmatrix}
+1 & +2 & +1  \\
0 & 0 & 0 \\
-1 & -2 & -1
\end{bmatrix} L.
</math>

Given such estimates of first-order [[image derivative]]s, the gradient magnitude is then computed as:

:<math>|\nabla L| = \sqrt{ L_x^2 + L_y^2}</math>

while the gradient orientation can be estimated as

:<math>\theta = \operatorname{atan2}(L_y, L_x).</math>

Other first-order difference operators for estimating image gradient have been proposed in the [[Prewitt operator]], [[Roberts cross]], Kayyali<ref>{{Cite journal|last1=Dim|first1=Jules R.|last2=Takamura|first2=Tamio|date=2013-12-11|title=Alternative Approach for Satellite Cloud Classification: Edge Gradient Application|journal=Advances in Meteorology|language=en|volume=2013|pages=1–8|doi=10.1155/2013/584816|issn=1687-9309|doi-access=free}}</ref> operator and [[Frei–Chen operator]].

It is possible to extend filters dimension to avoid the issue of recognizing edge in low [[Signal-to-noise ratio|SNR]] image. The cost of this operation is loss in terms of resolution. Examples are Extended Prewitt 7×7.

=== Thresholding and linking ===

Once we have computed a measure of edge strength (typically the gradient magnitude), the next stage is to apply a threshold, to decide whether edges are present or not at an image point. The lower the threshold, the more edges will be detected, and the result will be increasingly susceptible to [[image noise|noise]] and detecting edges of irrelevant features in the image.  Conversely a high threshold may miss subtle edges, or result in fragmented edges.

If the edge is applied to just the gradient magnitude image, the resulting edges will in general be thick and some type of edge thinning post-processing is necessary. For edges detected with non-maximum suppression however, the edge curves are thin by definition and the edge pixels can be linked into edge polygon by an edge linking (edge tracking) procedure. On a discrete grid, the non-maximum suppression stage can be implemented by estimating the gradient direction using first-order derivatives, then rounding off the gradient direction to multiples of 45 degrees, and finally comparing the values of the gradient magnitude in the estimated gradient direction.

A commonly used approach to handle the problem of appropriate thresholds for thresholding is by using [[Adaptive thresholding|thresholding]] with [[hysteresis]].  This method uses multiple thresholds to find edges. We begin by using the upper threshold to find the start of an edge. Once we have a start point, we then trace the path of the edge through the image pixel by pixel, marking an edge whenever we are above the lower threshold.  We stop marking our edge only when the value falls below our lower threshold. This approach makes the assumption that edges are likely to be in continuous curves, and allows us to follow a faint section of an edge we have previously seen, without meaning that every noisy pixel in the image is marked down as an edge. Still, however, we have the problem of choosing appropriate thresholding parameters, and suitable thresholding values may vary over the image.

=== Connectivity of gradients without using (high) magnitude thresholds ===
This method finds connected set of pixels having a directional derivative magnitude larger than a fairly small threshold.<ref>{{Cite journal |last=Pak |first=Mesut |last2=Bayazit |first2=Ulug |date=2020-07-01 |title=Regional bit allocation with visual attention and distortion sensitivity |url=https://link.springer.com/article/10.1007/s11042-020-08686-z |journal=Multimedia Tools and Applications |language=en |volume=79 |issue=27 |pages=19239–19263 |doi=10.1007/s11042-020-08686-z |issn=1573-7721}}</ref> It considers only presence of gradients instead of strength of gradients. After applying a dramatically small threshold (i.e. 5), a binary image is obtained. The morphological opening operation and the morphological closing operation are applied to the binary image to close gaps. Then, the distance transform operation is applied to the binary image to clear the pixels far from the background, so blob-like shapes or other false labeled regions are deleted from the edge map. 

=== Edge thinning ===

Edge thinning is a technique used to remove the unwanted spurious points on the edges in an image. This technique is employed after the image has been filtered for noise (using median, Gaussian filter etc.), the edge operator has been applied (like the ones described above, Canny or Sobel) to detect the edges and after the edges have been smoothed using an appropriate threshold value.
This removes all the unwanted points, and if applied carefully, results in one pixel thick edge elements.

Advantages:
# Sharp and thin edges lead to greater efficiency in [[object recognition]].
# If [[Hough transform]]s are used to detect lines and ellipses, then thinning could give much better results.
# If the edge happens to be the boundary of a region, then thinning could easily give the image parameters like perimeter without much algebra.

There are many popular algorithms used to do this, one such is described below:

# Choose a type of [[Pixel connectivity#2-dimensional|connectivity]], like 8, 6 or 4.
# [[Moore neighborhood|8 connectivity]] is preferred, where all the immediate pixels surrounding a particular pixel are considered.
# Remove points from North, south, east and west.
# Do this in multiple passes, i.e. after the north pass, use the same semi processed image in the other passes and so on.
# Remove a point if:<br />The point has no neighbors in the North (if you are in the north pass, and respective directions for other passes).<br />The point is not the end of a line.<br />The point is isolated.<br />Removing the points will not cause to disconnect its neighbors in any way.
# Otherwise, keep the point.
The number of passes across direction should be chosen according to the level of accuracy desired.

=== Second-order approaches ===

Some edge-detection operators are instead based upon second-order derivatives of the intensity.  This essentially captures the [[Derivative|rate of change]] in the intensity gradient. Thus, in the ideal continuous case, detection of zero-crossings in the second derivative captures local maxima in the gradient.

The early [[Marr–Hildreth algorithm|Marr–Hildreth]] operator is based on the detection of zero-crossings of the Laplacian operator applied to a Gaussian-smoothed image. It can be shown, however, that this operator will also return false edges corresponding to local minima of the gradient magnitude. Moreover, this operator will give poor localization at curved edges. Hence, this operator is today mainly of historical interest.

==== Differential ====
A more refined second-order edge detection approach which automatically detects edges with sub-pixel accuracy, uses the following ''differential approach'' of detecting zero-crossings of the second-order directional derivative in the gradient direction:

Following the differential geometric way of expressing the requirement of non-maximum suppression proposed by Lindeberg,<ref name=lin98/><ref name=lin93>[http://kth.diva-portal.org/smash/record.jsf?pid=diva2%3A473368&dswid=5061 T. Lindeberg (1993) "Discrete derivative approximations with scale-space properties: A basis for low-level feature extraction", J. of Mathematical Imaging and Vision, 3(4), pages 349–376.]</ref> let us introduce at every image point a local coordinate system <math>(u, v)</math>, with the <math>v</math>-direction parallel to the gradient direction. Assuming that the image has been pre-smoothed by Gaussian smoothing and a [[scale space representation]] <math>L(x, y; t)</math> at scale <math>t</math> has been computed, we can require that the gradient magnitude of the [[scale space representation]], which is equal to the first-order directional derivative in the <math>v</math>-direction <math>L_v</math>, should have its first order directional derivative in the <math>v</math>-direction equal to zero
:<math>\partial_v(L_v) = 0</math>
while the second-order directional derivative in the <math>v</math>-direction of <math>L_v</math> should be negative, i.e.,
:<math>\partial_{vv}(L_v) \leq 0.</math>
Written out as an explicit expression in terms of local partial derivatives <math>L_x,  L_y, \ldots , L_{yyy}</math>, this edge definition can be expressed as the zero-crossing curves of the differential invariant

:<math>L_v^2 L_{vv} = L_x^2 \, L_{xx} + 2 \, L_x \,  L_y \, L_{xy} + L_y^2 \, L_{yy} = 0,</math>

that satisfies a sign-condition on the following differential invariant

:<math>L_v^3 L_{vvv} = L_x^3 \, L_{xxx} + 3 \, L_x^2 \, L_y \, L_{xxy} + 3 \, L_x \, L_y^2 \, L_{xyy} + L_y^3 \, L_{yyy} \leq 0</math>

where <math>L_x, L_y, \ldots , L_{yyy}</math> denote partial derivatives computed from a [[scale space representation]] <math>L</math> obtained by smoothing the original image with a [[Gaussian kernel]]. In this way, the edges will be automatically obtained as continuous curves with sub-pixel accuracy. Hysteresis thresholding can also be applied to these differential and subpixel edge segments.

In practice, first-order derivative approximations can be computed by central differences as described above, while second-order derivatives can be computed from the [[scale space representation]] <math>L</math> according to:

:<math>
\begin{align}
L_{xx}(x, y) & = L(x-1, y) - 2 L(x, y) + L(x+1, y), \\[6pt]
L_{xy}(x, y) & = \frac 1 4 (L(x-1, y-1) - L(x-1, y+1) - L(x+1, y-1) + L(x+1, y+1)), \\[6pt]
L_{yy}(x, y) & = L(x, y-1) - 2 L(x, y) + L(x, y+1).
\end{align}
</math>

corresponding to the following filter masks:

:<math>
L_{xx} = \begin{bmatrix}
1 & -2 & 1
\end{bmatrix} L
\quad \text{and} \quad
L_{xy} = \begin{bmatrix}
-1/4 & 0 & 1/4 \\
0 & 0 & 0\\
1/4 & 0 & -1/4
\end{bmatrix} L
\quad \text{and} \quad
L_{yy} = \begin{bmatrix}
1 \\
-2 \\
1
\end{bmatrix} L.
</math>

Higher-order derivatives for the third-order sign condition can be obtained in an analogous fashion.

=== Phase congruency-based ===
A recent development in edge detection techniques takes a frequency domain approach to finding edge locations.  [[Phase congruency]] (also known as phase coherence) methods attempt to find locations in an image where all sinusoids in the frequency domain are in phase.  These locations will generally correspond to the location of a perceived edge, regardless of whether the edge is represented by a large change in intensity in the spatial domain.  A key benefit of this technique is that it responds strongly to [[Mach bands]], and avoids false positives typically found around [[roof edge]]s. A roof edge, is a discontinuity in the first order derivative of a grey-level profile.<ref>T. Pajdla and V. Hlavac (1993) "[https://link.springer.com/chapter/10.1007/3-540-57233-3_54 Surface discontinuities in range images]," in Proc IEEE 4th Int. Conf. Comput. Vision, pp. 524–528.</ref>

=== Phase Stretch Transform (PST) ===
[[File:PST edge detector saint Paul.tif|thumb|500px| Feature enhancement in an image ([[St Paul's Cathedral]], London) using Phase Stretch Transform (PST). Left panel shows the original image and the right panel shows the detected features using PST.]]

The [[phase stretch transform]] or PST is a physics-inspired computational approach to signal and image processing. One of its utilities is for feature detection and classification.<ref name="original">M. H. Asghari, and B. Jalali, [https://downloads.hindawi.com/journals/ijbi/2015/687819.pdf "Edge detection in digital images using dispersive phase stretch,"] International Journal of Biomedical Imaging, Vol. 2015, Article ID 687819, pp. 1–6 (2015).</ref><ref>M. H. Asghari, and B. Jalali, "[https://ieeexplore.ieee.org/abstract/document/7032125/ Physics-inspired image edge detection]," IEEE Global Signal and Information Processing Symposium (GlobalSIP 2014), paper: WdBD-L.1, Atlanta, December 2014.</ref> PST is a spin-off from research on the [[time stretch dispersive Fourier transform]]. PST transforms the image by emulating propagation through a diffractive medium with engineered 3D dispersive property (refractive index). The operation relies on symmetry of the dispersion profile and can be understood in terms of dispersive eigenfunctions or stretch modes.<ref>B. Jalali and A. Mahjoubfar, "[https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7118650 Tailoring Wideband Signals With a Photonic Hardware Accelerator]," Proceedings of the IEEE, Vol. 103, No. 7, pp. 1071–1086 (2015).
</ref> PST performs similar functionality as phase contrast microscopy but on digital images. PST is also applicable to digital images as well as temporal, time series, data.

=== Subpixel ===
To increase the precision of edge detection, several subpixel techniques had been proposed, including curve-fitting, moment-based,<ref>{{Cite journal|last1=Ghosal|first1=S.|last2=Mehrota|first2=R|date=1993-01-01|title=Orthogonal Moment Operators for Subpixel Edge Detection|journal=Pattern Recognition|volume=26|issue=2|pages=295–306|doi=10.1016/0031-3203(93)90038-X|bibcode=1993PatRe..26..295G }}</ref><ref name="Christian">{{Cite journal|last=Christian|first=John|date=2017-01-01|title=Accurate Planetary Limb Localization for Image-Based Spacecraft Navigation|journal=Journal of Spacecraft and Rockets|volume=54|issue=3|pages=708–730|doi=10.2514/1.A33692|bibcode=2017JSpRo..54..708C}}</ref> reconstructive, and partial area effect methods.<ref>{{Cite journal|last1=Trujillo-Pino|first1=Agustín|last2=Krissian|first2=Karl|last3=Alemán-Flores|first3=Miguel|last4=Santana-Cedrés|first4=Daniel|date=2013-01-01|title=Accurate subpixel edge location based on partial area effect|journal=Image and Vision Computing|volume=31|issue=1|pages=72–90|doi=10.1016/j.imavis.2012.10.005|hdl=10553/43474|hdl-access=free}}</ref> These methods have different characteristics. Curve fitting methods are computationally simple but are easily affected by noise. Moment-based methods use an integral-based approach to reduce the effect of noise, but may require more computations in some cases. Reconstructive methods use horizontal gradients or vertical gradients to build a curve and find the peak of the curve as the sub-pixel edge. Partial area effect methods are based on the hypothesis that each pixel value depends on the area at both sides of the edge inside that pixel, producing accurate individual estimation for every edge pixel. Certain variants of the moment-based technique have been shown to be the most accurate for isolated edges.<ref name="Christian"/>[[File:Subpixel edge detection.png|thumb|754x754px|Edge detection on an [[Angiography|angiographic image]]. On the left, edge detection is made at a pixel level. On the right, subpixel edge detection locates the edge inside the pixel precisely.|none]]

=== The Marr-Hildreth Edge Detector ===
[[Marr–Hildreth algorithm|The Marr-Hildreth edge detector]]<ref>{{Cite book |last=Gonzalez |first=Rafael |title=Digital Image Processing |publisher=Pearson Education |year=2018 |isbn=978-0-13-335672-4 |edition=4th}}</ref> is distinguished by its use of the Laplacian of Gaussian (LoG) operator for edge detection in digital images. Unlike other edge detection methods, the LoG approach combines Gaussian smoothing with second derivative operations, allowing for simultaneous noise reduction and edge enhancement. The key advantage of this method lies in its ability to detect edges at various scales by adjusting the standard deviation of the Gaussian kernel, enabling detection of fine details as well as broader transitions. Moreover, the technique leverages zero-crossing detection on the LoG response to precisely locate edges, offering robustness against noise and maintaining edge continuity. This approach is particularly effective for detecting edges with clear boundaries in images while minimizing false positives due to noise, making it a valuable tool in computer vision applications where accurate edge localization is crucial.

== Code for Edge Detection using Prewitt, Scharr and Sobel Operator ==

Source:<ref>{{Cite web |date=2021-10-11 |title=Edge detection using Prewitt, Scharr and Sobel Operator |url=https://www.geeksforgeeks.org/edge-detection-using-prewitt-scharr-and-sobel-operator/ |access-date=2024-05-08 |website=GeeksforGeeks |language=en-US}}</ref>

=== Edge detection using Prewitt operator ===
<syntaxhighlight lang="matlab" line="1">
% MATLAB code for prewitt
% operator edge detection
k = imread("logo.png");
k = rgb2gray(k);
k1 = double(k);
p_msk = [-1 0 1; -1 0 1; -1 0 1];
kx = conv2(k1, p_msk, 'same');
ky = conv2(k1, p_msk', 'same');
ked = sqrt(kx.^2 + ky.^2);

% display the images.
imtool(k,[]);

% display the edge detection along x-axis.
imtool(abs(kx), []);

% display the edge detection along y-axis.
imtool(abs(ky),[]);

% display the full edge detection.
imtool(abs(ked),[]);
</syntaxhighlight>

=== Edge detection using Scharr operator ===
<syntaxhighlight lang="matlab" line="1">
% Scharr operator -> edge detection
k = imread("logo.png");
k = rgb2gray(k);
k1 = double(k);
s_msk = [-3 0 3; -10 0 10; -3 0 3];
kx = conv2(k1, s_msk, 'same');
ky = conv2(k1, s_msk', 'same');
ked = sqrt(kx.^2 + ky.^2);
% display the images.
imtool(k,[]);
% display the edge detection along x-axis.
imtool(abs(kx), []);
% display the edge detection along y-axis.
imtool(abs(ky), []);
% display the full edge detection.
imtool(abs(ked), []);

</syntaxhighlight>

=== Edge Detection using Sobel operator ===
<syntaxhighlight lang="matlab" line="1">
% MATLAB code for Sobel operator
% edge detection
k = imread("logo.png");
k = rgb2gray(k);
k1 = double(k);
s_msk = [-1 0 1; -2 0 2; -1 0 1];
kx = conv2(k1, s_msk, 'same');
ky = conv2(k1, s_msk', 'same');
ked = sqrt(kx.^2 + ky.^2);

% display the images.
imtool(k,[]);

% display the edge detection along x-axis.
imtool(abs(kx), []);

% display the edge detection along y-axis.
imtool(abs(ky), []);

% display the full edge detection.
imtool(abs(ked), []);
</syntaxhighlight>

==See also==
*{{section link|Convolution|Applications}}
*[[Edge-preserving filtering]]
*[[Feature detection (computer vision)]] for other low-level feature detectors
*[[Image derivative]]
*[[Gabor filter]]
*[[Image noise reduction]]
*[[Kirsch operator]] for edge detection in the compass directions
*[[Ridge detection]] for relations between edge detectors and ridge detectors
*[[Log Gabor filter]]
*[[Phase stretch transform]]

==References==
M. Gupta, S.N. Tazi, A. Jain and Deepika, "Edge Detection Using Modified Firefly Algorithm", Computational Intelligence and Communication Networks (CICN) 2014 International onference on, pp. 167-173, 14-16 Nov. 2014.
[https://ieeexplore.ieee.org/document/7065467 View Article]
[https://scholar.google.com/scholar?as_q=Edge+Detection+Using+Modified+Firefly+Algorithm&as_occt=title&hl=en&as_sdt=0%2C31 Google Scholar]
<references />

==Further reading==
*{{SpringerEOM| title=Edge detection | id=Edge_detection | oldid=17883 | first=Tony | last=Lindeberg }}
*[https://onlinelibrary.wiley.com/doi/10.1002/9780470050118.ecse603 Entry on edge detection in Encyclopedia of Computer Science and Engineering]
*[http://edge.kitiyo.com/ Edge Detection using FPGA]
*[[:doi:10.5201/ipol.2012.gjmr-lsd|A-contrario line segment detection with code and on-line demonstration]]
* [https://www.mathworks.com/discovery/edge-detection.html Edge detection using MATLAB]
* [http://www.mathworks.com/matlabcentral/fileexchange/48908-accurate-subpixel-edge-location Subpixel edge detection using Matlab]
* [https://photokit.com/tools/effects/edgedetect/ Image Tools Effects - Edgedetect]
* [https://sdk.docutain.com/blogartikel/edge-detection-for-image-processing Edge Detection for Image Processing]

{{DEFAULTSORT:Edge Detection}}
[[Category:Edge detection| ]]
[[Category:Image processing]]