Canny

From Wikipedia, the free encyclopedia

Canny may also mean shrewd, cagey or clever, see Intelligence (trait).

The Canny edge detection operator was developed by John F. Canny in 1986 and uses a multiple stage algorithm to detect a wide range of edges. Most importantly, Canny also produced a computational theory of edge detection explaining why the technique works.

The Canny edge detector applied to a black and white photograph.
The Canny edge detector applied to a black and white photograph.

Contents

[edit] Development of the Canny algorithm

Canny's aim was to discover the optimal edge detection algorithm. In this situation an 'optimal' edge detector means:

  • good detection - the algorithm should mark as many real edges in the image as possible.
  • good localisation - edges marked should be as close as possible to the edge in the real image.
  • minimal response - a given edge in the image should only be marked once, and where possible, image noise should not create false edges.

To satisfy these requirements Canny used the calculus of variations - a technique which finds the function which best satisfies a given functional. The optimal detector was described by the sum of four exponential terms, but closely approximated the first derivative of a gaussian.

[edit] Stages of the Canny algorithm

[edit] Noise reduction

No edge detection algorithm can be expected to work well on raw unprocessed image data, so to begin with the raw image is convolved with a gaussian mask. The output appears as a slightly blurred version of the original. Therefore a single noisy pixel has little effect on the gaussian smoothed image.

[edit] Finding the intensity gradient of the image

An edge in an image may point in a variety of directions, so the Canny algorithm uses 4 masks to detect horizontal, vertical and diagonal edges. The results of convolving the original image with each of these masks is stored. For each pixel, we then mark the largest result at that pixel, and the direction of mask which produced that edge. From the original image, we have now created a map of intensity gradients at each point in the image, and direction of the intensity gradient points.

[edit] Tracing edges through the image

The higher intensity gradients are more likely to be edges. There is not an exact value at which a given intensity gradient switches from not being an edge into being an edge. Therefore Canny uses thresholding with hysteresis.

Thresholding with hysteresis requires two thresholds - high and low. Making the assumption that important edges should be in continuous lines through the image allows us to follow a faint section of a given line, but avoid identifying a few noisy pixels that do not constitute a line. Therefore we begin by applying a high threshold. This marks out the edges we can be fairly sure are genuine. Starting from these, using the directional information derived earlier, edges can be traced through the image. While tracing a line, we apply the lower threshold, allowing us to trace faint sections of lines as long as we find a starting point.

Once this process is complete we have a binary image where each pixel is marked as either an edge pixel or a non-edge pixel.

A more refined approach to obtain edges with sub-pixel accuracy is by using the following differential approach of detecting zero-crossings of the second-order directional derivative in the gradient direction (Lindeberg 1998)

L_x^2 \, L_{xx} + 2 \, L_x \, L_y \, L_{xy} + L_y^2 \, L_{yy} = 0,

that satisfy a sign-condition on the third-order directional derivative in the same direction (for more details, please see the relations between edge detection and ridge detection in the article on ridge detection)

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} < 0

where Lx, Ly ... Lyyy denote partial derivatives computed from a scale-space representation L obtained by smoothing the original image with a Gaussian kernel. In this way, the edges will be automatically obtained as continuous curves with subpixel accuracy. Hysteresis thresholding can also be applied to these differential and subpixel edge segments.

[edit] Parameters

The Canny algorithm contains a number of adjustable parameters, which can affect the computation time and effectiveness of the algorithm.

  • The size of the gaussian filter: the smoothing filter used in the first stage directly affects the results of the Canny algorithm. Smaller filters cause less blurring, and allow detection of small, sharp lines. A larger filter causes more blurring, smearing out the value of a given pixel over a larger area of the image. As a result, this is more useful for detecting larger, smoother edges - for instance the edge of a rainbow.
  • Thresholds: the use of two thresholds allows more flexibility than in a single-threshold approach, but general problems of thresholding still apply. A threshold set too high can miss important information. A threshold set too low will falsely identify irrelevant information as important. It is difficult to give a generic threshold that works well on all images. No tried and tested approach to this problem yet exists.

To experiment with the parameters of the Canny algorithm, the on-line Canny application on http://matlabserver.cs.rug.nl can be useful.

[edit] Conclusion

The Canny algorithm is adaptable to various environments. Its parameters allow it to be tailored to recognition of edges of differing characteristics depending on the particular requirements of a given implementation. In Canny's original paper, the derivation of the optimal filter led to a Finite Impulse Response filter, which can be slow to compute in the spatial domain if the amount of smoothing required is important (the filter will have a large spatial support in that case). For this reason, it is often suggested to use Rachid Deriche's Infinite Impulse Response form of Canny's filter, which is recursive, and which can be computed in a short, fixed amount of time for any desired amount of smoothing. The second form is suitable for real time implementations in FPGAs or DSPs, or very fast embedded PCs. In this context, however, the regular recursive implementation of the Canny operator does not give a good approximation of rotational symmetry and therefore gives a bias towards horizontal and vertical edges.

[edit] References

[edit] See also

[edit] External links

Retrieved from "http://en.wikipedia.org../../../c/a/n/Canny.html"
In other languages