Edge Detection – The Canny Algorithm

The Sobel edge detection method described in the video was developed in the late 1960s and was the first practical edge detection algorithm. While it remains effective and widely used today, later work by John Canny provided both a deeper understanding of the edge detection task and a more powerful technique which has become the de facto standard for the computer vision community.

In the 15 years following publication of Sobel’s method hundreds of variations on the theme were proposed. These were typically presented as alternative operators computing a set of differential measures, but lacked any deep theoretical analysis. That changed in 1986 with the publication of Canny’s MIT MSc thesis [1].

Presented with a rapidly increasing set of quite similar methods, Canny set out to identify the optimal edge detection algorithm. This required a precise definition of “edge detection”, which Canny defined as the detection of a perfect (vertical) step edge in the presence of white noise. It also required a clear definition of “optimal”. Canny identified three requirements of an optimal edge detector:

• Good detection – it should detect all and only all the step edges in the image
• Good localisation – it should mark each edge as closely as possible to its true location
• Clear response – each edge should be marked exactly once

These criteria were captured by an equation that could be applied to assess the quality of a given edge detection output – the details are not important here – and an optimisation method known as the calculus of variations used to identify the optimal operator. The full Canny method involves four differential operators but can be very closely approximated by finding peaks in the first derivative of a Gaussian-smoothed image. Canny’s work therefore provided both an improved operator and deeper understanding of why Sobel works – it loosely approximates Canny’s.

Canny went on to propose a thresholding method to be used to decide which peaks in operator output should be considered edges. Termed thresholding with hysteresis, this employs two threshold values. The first is a high threshold, set to detect outputs that are confidently expected to represent edges. The second, low threshold specifies the minimum acceptable operator response. Thresholding with hysteresis first applies the high threshold, then searches around these initial edges for other local maxima in operator output. Potential edges are tracked through the images and added to the developing contour until their operator response values drop below the low threshold. The effect is that the high threshold identifies object boundaries, etc of interest and the low threshold is used to fill in gaps. The mix of theoretical and practical advancements in Canny’s work make it a classic in the computer vision literature.

The figure below shows the application of the Canny operator to an image (a) of a plant shoot. Panels (b) and (c) show the edges achieved by simple thresholding with low and high thresholds respectively, while panel (d) gives the result obtained using thresholding with hysteresis with the same values. In practice, setting these two thresholds is noticeably easier than choosing the single threshold used in the Sobel.

[1] Canny, J., A Computational Approach to Edge Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6):679–698, 1986.