Canny edge detector

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

Preprocessing

Since the algorithm can only work on grayscale images, a previous conversion of color images to gray images is required. In these gray scale images edges are characterized by large fluctuations in brightness between two adjacent pixels. They can thus be seen as a discontinuity of the gray value function of the output image. Since such discontinuities even without the presence of edges can easily occur due to image noise, the algorithm uses the normal distribution to smooth the image.

In this case, the original image is convolved with the aid of a mask approximating the normal distribution. The new gray value of a pixel is obtained from the weighted values ​​of the surrounding pixels. An example of such a mask is

Respect, the greater the mask is chosen, the more robust the algorithm is against noise, but can be lost due to excessive smoothing fine edges.

Edge detection

Partial derivatives

The Canny algorithm, the partial derivatives of each pixel are required in the direction and in the direction. The partial derivatives of or determined by the pre-processed image with the help of Sobeloperators respectively - is folded or direction. Thus, horizontal or vertical edges are emphasized. Even when Sobel operator gives the new value of a pixel from the weighted values ​​of the surrounding pixels:

After application of the two respective Sobeloperatoren on the preprocessed image, there are two new images, the partial derivatives.

Edge direction

Using the two partial derivatives determined the direction of a potential edge can be achieved by means of a pixel

Each other, including atan2 here the so-called " two-argument arctangent " is.

However, since a pixel 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 from the Euclidean sum of the two partial derivatives is formed.

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

Calculated increase ( rounded)

Calculated increase ( rounded ) showing edge thickness

Non -maximum suppression

To ensure that an edge is no longer than one pixel wide, will remain along an edge in the following step only the maxima. For this, it is assumed from the image with the absolute edge strengths and compared for each pixel the values ​​with those of its eight neighbors. Any of the adjacent pixels may have a higher value, unless the neighboring pixels in question is calculated along the edge direction. If this is not given, the gray value is set to zero. This technique is suppression (NMS ) called non- maximum.

Hysteresis

Finally, it is found, from which edge strength of a pixel to belong to an edge. To avoid the breaking up of an edge due to fluctuations in the calculated edge strength, a process called hysteresis is applied. In this method, using two threshold values. It scans through the image until a pixel is found, its strength is greater. This edge is then followed by both sides. All pixels along this edge increase with thickness marked as edge element.

After this last step, the algorithm is terminated and returns a set of points that show present in the output image edges with a suitable choice of threshold values.

Use

The amount of edge points obtained by the algorithm may be used in many different ways to extract more information from the image (e.g., the Hough transform for the detection of simple geometric objects or Waltz algorithm for detection of three-dimensional objects in the image ).