Algorithm of Canny

The algorithm of Canny (1986) is used in treatment or Analyze of image for the detection of contours. The author conceived it to be optimal according to three clearly clarified criteria:

good detection : low level of error in the indication of contours,
good localization : minimization of the distances between detected contours and real contours,
clearness of the answer : only one response per contour and not of false-positives

Implementation

Reduction of the noise

The first stage is to reduce the Bruit original image before detecting contours of them. This makes it possible to eliminate the isolated pixels which could induce strong answers during the calculation of the gradient, thus leading to false-positives.

A Gaussian filtering 2D is used (see Lissage of the image), of which here the operator of convolution:

G (X, there) = \ frac {1} {2 \ pi \ sigma^2} e^ {- \ frac {x^2+y^2} {2 \ sigma^2}}

and an example of discrete mask 5×5 with σ=1,4:

\ frac {1} {115} \ begin {bmatrix}
2 & 4 & 5 & 4 & 2 \ \
4 & 9 & 12 & 9 & 4 \ \
5 & 12 & 15 & 12 & 5 \ \
4 & 9 & 12 & 9 & 4 \ \
2 & 4 & 5 & 4 & 2
\end{bmatrix}

Usually, a filter is of size more reduced than the filtered image. Plus the mask is large, less the detector is sensitive to the noise and more the error of localization grows.

Gradient of intensity

After filtering, the following stage is to apply a Gradient which turns over the intensity of contours. The operator of Sobel is used, it is composed of a pair of two masks of convolution 3×3, one by space direction:

G_x =
\begin{bmatrix}
-1 & 0 & 1 \ \
-2 & 0 & 2 \ \
-1 & 0 & 1
\end{bmatrix}\qquad;\ qquad
G_y =
\begin{bmatrix}
1 & 2 & 1 \ \
0 & 0 & 0 \ \
-1 & -2 & -1
\end{bmatrix}

The value of the gradient in a point is approximated by the formula:

|G| = |G_x| + |G_y|

Direction of contours

The orientations of contours are determined by the formula:

\ theta = arctan (\ frac {G_y} {G_x})

We obtain finally a chart of the gradients of intensity in each point of the image accompanied by the directions of contours.

Suppression of themaximum one

The chart of the gradients obtained previously provides an intensity in each point of the image. A strong intensity indicates a strong probability of presence of a contour. However, this intensity is not enough to decide if a point corresponds to a contour or not. Only the points corresponding to maximum buildings are considered as correspondent with contours, and are preserved for the next stage of detection.

A local maximum is present on the extrema Gradient, i.e. where its Dérivée is cancelled.

Thresholding of contours

The differentiation of contours on the generated chart is done by thresholding with hysteresis.

That requires two thresholds, a top and a bottom; who will be compared with the intensity of the gradient of each point. The decision criterion is the following. For each point, if the intensity of its gradient is:

Lower than the low threshold, the point is rejected;
Higher than the high threshold, the point is accepted like formant a contour;
Between the low threshold and the high threshold, the point is accepted if it is connected to a point already accepted.

Once this carried out, the image obtained is binary with side the pixels belonging to contours and the others.

Parameters

The two principal parameters determining the computing time and the acuity of the algorithm are the size of the Gaussian filter and the two thresholds.

Size of the filter: the filter used during the reduction of the noise has a direct influence on the behavior of the algorithm. A filter of small size produces an effect of less marked blur, which allows the detection of small well marked lines. A filter of larger size produces an effect of more important blur, which makes it possible to detect contours minus Nets, for example that of a rainbow.

Thresholds: the use of two thresholds instead of one improves flexibility but certain problems specific to the thresholding remain. Thus, a too low threshold can lead to the detection of false-positives. Conversely, a too high threshold can prevent the detection of little marked contours but representing useful information.

There currently does not exist of generic method to determine thresholds producing of the satisfactory results on all the types of images.

A demonstration on line (English) can be used to study the influence of the parameters: http://matlabserver.cs.rug.nl

References

Canny, J., have Computational Approach To Edge Detection , IEEE Trans. Pattern Analysis and Machine Intelligence, 8:679 - 714 (1986).

External bonds

a demonstration in images: http://robotics.eecs.berkeley.edu/~sastry/ee20/cademo.html
an application on line allowing to try out the algorithm: http://matlabserver.cs.rug.nl

Random links: