Canny algorithm

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

This article or section needs to be revised. Details should be given on the talk page. Please help to improve it , and then remove this flag.

The Canny algorithm (also: Canny edge detector ), named after John Francis Canny, is a robust algorithm for edge detection that is widely used in digital image processing . It is divided into various convolution operations and provides an image which ideally only contains the edges of the original image.

Preprocessing (image smoothing)

Initial image for the algorithm

The Canny algorithm works on two-dimensional intensity values. It can therefore detect edges on gray-scale images or individual color channels, but does not contain any rules on how several monochrome channels would be merged. As a rule, color images are converted into a common gray value image before edge detection.

In gray-scale images, edges are characterized by large fluctuations in brightness between two neighboring pixels. For an output image they can thus be understood as a discontinuity in the gray value function (not derivable) or - in the usual discretized variant - as a step function (derivable). When designing the edge detector, Canny assumed a useful signal (image) overlaid with white noise . This assumption is entirely appropriate, since thermal noise in electronic components that are used for image acquisition has a comparable distribution. As a result, it is not possible to determine whether an edge originates from the actual signal or is caused by the overlying noise. The Canny algorithm counteracts the Gaussian distributed white noise with a smoothing function based on the bell curve , for example in the form of a convolution with a binomial filter . In the preprocessing, the image is thus deep-fitted so that the white noise, which mainly occurs in the high frequency range, is attenuated or eliminated before edges are found. A new gray value of a pixel results as a convolution response from the weighted values ​​of its own and the pixels around it . An example of such a convolution matrix is ${\displaystyle g(x,y)}$ ${\displaystyle g_{n}(x,y)}$

${\displaystyle g_{n}(x,y)={\frac {1}{4}}{\begin{bmatrix}1\\2\\1\end{bmatrix}}\cdot {\frac {1}{4}}{\begin{bmatrix}1&2&1\end{bmatrix}}={\frac {1}{16}}{\begin{pmatrix}1&2&1\\2&4&2\\1&2&1\end{pmatrix}}}$.

That is, the convolution matrix can be separated . The vectors that are linked dyadically to form the matrix correspond to the nth row of a Pascal triangle .

A larger convolution matrix strengthens the low-pass effect and thus the robustness against noise. At the same time, however, fine edges disappear.

Edge detection

Partial derivatives

Result of the Sobel operator in -direction ${\displaystyle X}$

Result of the Sobel operator in -direction ${\displaystyle Y}$

The partial derivatives of the individual pixels in -direction and in -direction are required for the Canny algorithm . The partial derivatives or are determined by folding the preprocessed image in or in the direction with the help of the Sobel operator . This emphasizes vertical or horizontal edges. With the Sobel operator too, the new value of a pixel results from the weighted values ​​of the surrounding pixels: ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle g_{x}}$ ${\displaystyle g_{y}}$ ${\displaystyle X}$ ${\displaystyle Y}$

${\displaystyle {\begin{pmatrix}-1&0&1\\-2&0&2\\-1&0&1\end{pmatrix}}}$Sob operator in -direction, ${\displaystyle X}$

${\displaystyle {\begin{pmatrix}1&2&1\\0&0&0\\-1&-2&-1\end{pmatrix}}}$Sob operator in -direction. ${\displaystyle Y}$

After each application of the two Sobel operators to the preprocessed image, two new images result, the partial derivatives.

Instead of the Sobel operator and preprocessing, it is also possible to filter directly with the 1st derivatives (in x and y directions) of the Gaussian kernel. This follows from the associativity of linear filters and from the fact that the derivative can be represented as a filter. So it is quasi smoothed and derived in one pass. Canny has shown that this approach optimizes the signal to noise ratio.

Edge direction

Calculated rise or angle of potential edges at the respective point

With the help of the two determined partial derivatives, the direction of the gradient of a potential edge through a pixel can be determined using ${\displaystyle \theta }$

${\displaystyle \theta (x,y)=\operatorname {arctan2} {\bigl (}g_{x}(x,y),g_{y}(x,y){\bigr )}}$

calculate, where arctan2 is the so-called "arctangent with two arguments".

However, since a pixel only has 8 neighbors, the edge directions are rounded to 0 °, 45 °, 90 ° and 135 °.

Absolute edge strength

In the third step, an image of the absolute edge strengths is calculated. The value of a single pixel is formed from the Euclidean amount of the two partial derivatives.

${\displaystyle G(x,y)={\sqrt {g_{x}(x,y)^{2}+g_{y}(x,y)^{2}}}}$

In practice, an approximation is often used to increase efficiency:

${\displaystyle G(x,y)=\left|g_{x}(x,y)\right|+\left|g_{y}(x,y)\right|}$

• 

  Calculated increase in potential edges at the respective point with representation of the edge strength

• 

  Calculated increase (rounded)

• 

  Calculated increase (rounded) showing the edge thickness

Non-maximum suppression

Remaining pixels (local maxima)

To ensure that an edge is not more than one pixel wide, only the maxima along an edge should be retained in the following step. This is based on the image with the absolute edge strengths and the values ​​for each pixel are compared with the two pixels to the right and left of the edge (or along the gradient). If one of the values ​​is larger, the gray value is set to zero. You can imagine that the algorithm walks along the “ridge” of a “ridge” and sets all pixels to zero that do not belong to the ridge. This technique is called non-maximum suppression (NMS). ${\displaystyle G(x,y)}$

Hysteresis

Edge extraction result

Finally, it is also determined from which edge thickness a pixel is to be counted as an edge. A method known as hysteresis is used to prevent an edge from breaking due to fluctuations in the calculated edge strength . This method uses two threshold values . The image is scanned until a pixel with a greater strength is found. You then follow this edge on both sides. All pixels along this edge with a thickness greater than that are marked as edge elements. ${\displaystyle T_{1}<T_{2}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$

After this last step, the algorithm is finished and provides a set of points which, with a suitable choice of the threshold values, show the edges present in the initial image.

use

The set of edge points obtained by the algorithm can be used in many different ways to extract further information from the image (e.g. Hough transformation for the recognition of simple geometric objects or Waltz algorithm for the recognition of three-dimensional objects in the image).

software

The algorithm is implemented in the free image processing libraries Scikit-image and OpenCV .

literature

• An improved CANNY edge detection algorithm by Bing Wang, Department of Electric and Information Engineering Changsha University of Science and Technology Changsha, Hunan, China, 2009
• DGW-Canny: An Improvised Version Of Canny Edge Detector, by Ravi Kumar Dalal, Rahul Gupta, Pulkit Wadhwa and Anand Gupta, Neta Subhas Institute of Technology, New Delhi, India, 2011

Web links

Commons : Edge detection  - collection of images, videos and audio files

Individual evidence

1. ↑ ^{a b} [1] (PDF; 7.3 MB) John Canny: A Computational Approach to Edge Detection, 1986 PAMI
2. ↑ Canny edge detector - skimage docs. Retrieved September 13, 2018 . 
3. ^ OpenCV: Canny Edge Detector. Retrieved September 16, 2018 .