Edge detection: Difference between revisions

Revision as of 07:14, 3 February 2022

Latest revision as of 12:09, 6 August 2025

(47 intermediate revisions by 38 users not shown)

Line 1:

{{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 ==

Line 42:

<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 ==

== Why it is a non-trivial task ==

ToOutside illustrateof whyimages with simple objects or featuring well-controlled lighting, edge detection is not a trivial task, considersince theit problemcan ofbe detectingdifficult edgesto determine what threshold should be used to define an edge between two pixels.<ref name=lin98/> For example, in the following one-dimensional signal. Here, wemost maywould intuitively say that there should beis an edge between the 4th and 5th pixels.:

{| style="border:0; margin:0.5em auto"

Line 71:

|}

IfHowever, if the intensity difference were smaller between the 4th and the 5th pixels and if the intensity differences between the adjacent neighboring pixels were highersmaller, it would not be as easy to say that there should be an edge in the corresponding region. MoreoverSimilarly, if the intensity differences between the adjacent neighboring pixels were higher, one could argue that thismore case isthan one inedge whichshould therebe considered to exist, or even arenone severalat edgesall.

{| style="border:0; margin:0.5em auto"

Line 78:

| 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;" | 4161

| style="border:1px solid #000; padding:5px" | 113

| style="border:1px solid #000; padding:5px" | 148

Line 89:

| style="background:#060606" |

| style="background:#2929293d3d3d" |

| style="background:#717171" |

Line 97:

| style="background:#959595" |

|}

Hence, to firmly state a specific threshold on how large the intensity change between two neighbouring pixels must be for us to say that there should be an edge between these pixels is not always simple.<ref name=lin98/> Indeed, this is one of the reasons why edge detection may be a non-trivial problem unless the objects in the scene are particularly simple and the illumination conditions can be well controlled (see for example, the edges extracted from the image with the girl above).

== Approaches ==

Line 111 ⟶ 109:

=== 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>

Line 173 ⟶ 177:

:<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|lastlast1=Dim|firstfirst1=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|issue=1 |pages=1–8|doi=10.1155/2013/584816|issn=1687-9309|doi-access=free|bibcode=2013AdMet201384816D }}</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.

Line 184 ⟶ 188:

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 |last1=Pak |first1=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|url-access=subscription }}</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:

Line 197 ⟶ 204:

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.

# ElseOtherwise, keep the point.

The number of passes across direction should be chosen according to the level of accuracy desired.

Line 222 ⟶ 229:

:<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 satisfysatisfies 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>

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:

Line 266 ⟶ 273:

[[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/iel7stamp/5/4357935/07118650stamp.pdfjsp?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|lastlast1=Ghosal|firstfirst1=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|lastlast1=Trujillo-Pino|firstfirst1=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

Line 289 ⟶ 374:

==Further reading==

*{{SpringerEOM| title=Edge detection | id=Edge_detection | oldid=17883 | first=Tony | last=Lindeberg }}

*[httphttps://mrw.interscienceonlinelibrary.wiley.com/emrwdoi/10.1002/9780470050118/ecse/article/.ecse603/current/abstract 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]]

* [httphttps://www.mathworks.com/helpdiscovery/images/detect-edges-inedge-imagesdetection.html Edge detection using MATLAB]

* [http://www.mathworks.com/matlabcentral/fileexchange/48908-accurate-subpixel-edge-___location Subpixel edge detection using Matlab] {{Webarchive|url=https://web.archive.org/web/20211216123504/http://www.mathworks.com/matlabcentral/fileexchange/48908-accurate-subpixel-edge-___location |date=2021-12-16 }}

* [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:FeatureEdge detection| (computer vision)]]

[[Category:Image processing]]