A Computational Approach to Edge Detection

“A Computational Approach to Edge Detection” is a twenty-page paper by John Canny of the MIT Artificial Intelligence Laboratory, published in IEEE Transactions on Pattern Analysis and Machine Intelligence in November 1986. It grew out of his 1983 MIT master’s thesis, “Finding Edges and Lines in Images”. Instead of proposing another operator and arguing for it by example, the paper first wrote down what an edge detector should achieve, expressed those goals as functionals of the filter’s impulse response, and derived the filter that optimizes them. The detector it described, simplified to Gaussian smoothing, gradient computation, non-maximum suppression, and hysteresis thresholding, became the Canny edge detector.

Problem

By the mid-1980s, edge detection was the front end of many vision systems, from line finders and model-based recognition to stereo and shape from motion. The paper argues that these share two requirements: a low error rate and edge points close to the true edge.

The thesis abstract notes that edge operators were typically designed to estimate a first or second derivative optimally over a small support, with output signal-to-noise ratio or bandwidth argued for in some cases. The paper discusses the difference of boxes of Rosenfeld and Thurston and of Herskovits and Binford, Macleod’s difference of two displaced Gaussians, and Marr and Hildreth’s zero crossings of the Laplacian of a Gaussian. Marr–Hildreth zero crossings were not thresholded and form closed contours that need not match image contours. Canny’s thesis set out instead to formulate criteria that capture the desirable properties of an edge operator directly, and to find the best operator over all linear shift-invariant filters.

Contribution

• Explicit criteria. Good detection, measured by the output signal-to-noise ratio; good localization, measured by the reciprocal of the root-mean-square distance of the marked point from the true edge; and a single response to each edge, expressed through the mean spacing of noise maxima. The paper shows that without the third criterion, the first two are maximized by the difference of boxes, which responds to a noisy step with many nearby maxima.
• Optimal operators by optimization. The criteria apply to any one-dimensional profile: numerical optimization gave operators for ridges and roofs; for step edges, a variational derivation gave a parametric closed form whose last parameters were found numerically.
• An uncertainty principle. For steps, stretching an operator raises its signal-to-noise ratio and lowers its localization by the same factor. One operator shape is therefore optimal at every scale, and width only moves the balance between detection and localization.
• The Gaussian-derivative approximation. The optimal step operator is closely approximated by the first derivative of a Gaussian, which is much cheaper in two dimensions.
• A complete detector. Edges marked at maxima of the smoothed gradient magnitude along the gradient direction, thresholds set from a noise estimate, hysteresis between two thresholds, several operator widths combined by “feature synthesis”, and elongated directional operators where edges fit a straight-edge model.

Method

The paper develops the criteria for a one-dimensional edge in white Gaussian noise, with edges marked at maxima of the filter output. The design problem maximizes the product of the detection and localization measures under the multiple-response constraint, which fixes the expected number of noise maxima within the operator’s width. A table of optimal step operators for different settings of this constraint shows that the best multiple-response measure the constrained optimization reached was about 0.576, against the target value of 1. The first derivative of a Gaussian is about 20 percent worse on the combined measure and about 10 percent worse on the multiple-response measure, a difference the paper judges hard to see on real images. The criteria, their formulas, and the resulting pipeline are derived in the Canny edge detector article.

In two dimensions, the edge normal is estimated from the direction of the Gaussian-smoothed gradient, and edge points are maxima of the gradient magnitude in that direction, equivalently zero crossings of the second derivative along the normal. The paper notes that Torre and Poggio and Haralick had used the same nonlinear operator, and argues that it beats the Laplacian, whose component along the edge only adds noise.

Noise estimation is posed as a Wiener filtering problem: the operator output is convolved with a kernel that, for strong edges, reduces to a second derivative, and the result is squared. Because edge responses are rare and large, a low percentile of a global histogram of these values (the paper suggests below about 80 percent) reflects mainly the noise. Thresholds follow from this estimate, and hysteresis keeps a contour segment above the low threshold if any part of it exceeds the high one, which the paper uses to prevent “streaking”, the breakup of contours whose response hovers around a single threshold. The implementation used a high-to-low ratio of two or three to one.

For scale, the paper prefers the smallest operator whose signal-to-noise ratio is sufficient, since it localizes best. Feature synthesis marks edges from the smallest operator, predicts the output a larger operator would give if only those edges were present, and marks new edges only where the actual output is significantly larger. Finally, the paper proves that elongating the operator along the edge improves detection and builds directional masks from five samples of the circular operator along a line, at six orientations, suppressing them where a variance test shows that the edge is curved or not aligned with the mask.

Results

Beyond the operators’ performance figures, the evaluation is qualitative, on 576 by 454 images. On an image of machine parts, single thresholds at one level and at twice that level are compared with hysteresis between the two. Feature synthesis is shown on the parts image with operators of $\sigma = 1$ and $2$, where the coarser operator adds mostly shadow edges and synthesis removes its displaced duplicate responses, and on a second image with $\sigma = 1$ and $5$, where the two sets of edges are largely independent and most coarse edges survive. A final example compares circular and directional operators. The paper reports that most edges in typical images are marked by the smallest, non-elongated operators. No ground-truth comparison or timing is reported, and the paper states that a thorough empirical comparison of the alternative optimal operators remained to be done.

Impact

The simplified detector became a standard classical method. OpenCV’s cv::Canny and scikit-image’s skimage.feature.canny both implement it and cite the 1986 paper; both compute gradients with Sobel operators (scikit-image after Gaussian smoothing), thin by non-maximum suppression, and link by hysteresis, and neither implements the paper’s noise estimation, multiple widths, feature synthesis, or directional operators, so threshold and scale are left to the user. Xie and Tu (2015) describe the detector as widely adopted. When boundary detection became a benchmarked learning problem, Canny was the classical baseline: Martin, Fowlkes, and Malik (2004) compared against MATLAB’s implementation, and Xie and Tu report it on the BSDS500 benchmark. The criteria were also reused to derive other filters, as in Deriche (1987).

Limitations

Canny named several limits himself. The analysis assumes edges with a constant cross-section, which holds for smooth contours but not at corners; the paper suggests the criteria could be extended to corner detectors but leaves that open. It does not consider more than one edge within an operator’s support, and its attempt to combine edge and ridge detector outputs by feature synthesis was inconclusive. Edges between textures are straightforward in its framework only when the texture can be modeled as filtered Gaussian noise; for other textures the paper points to Markov image models.

Later work found others. The step model fits poorly where texture is everywhere: Martin et al. reported that the detector fires inside textured regions with no boundary and misses boundaries between textures of similar brightness, and that hysteresis gave only a marginal improvement on natural images.

What Came After

Deriche (1987) solved Canny’s optimization for a filter of infinite extent and implemented the result as two recursive filters running in opposite directions, at a cost per pixel independent of the filter width. Scale-space theory offered a more principled alternative to feature synthesis: Lindeberg (1998) defined edges by a maximum over scale of a normalized edge strength as well as a maximum along the gradient, so that the scale can vary along an edge.

The larger change came from learning. Martin, Fowlkes, and Malik (2004) trained on human-annotated boundaries, learning to combine brightness, color, and texture gradients into a boundary probability (Pb). Structured forests followed, and Xie and Tu (2015) introduced holistically-nested edge detection (HED), a fully convolutional network trained end to end.