Canny Edge Detector

The Canny edge detector finds thin, connected edges in an image in four steps: Gaussian smoothing, gradient computation, non-maximum suppression along the gradient direction, and double thresholding with hysteresis. John Canny derived it by optimizing three explicit performance criteria. It remains the standard classical edge detector in image processing libraries and a common baseline for newer detectors.

Problem

A gradient-magnitude image marks edges as ridges several pixels wide, mixed with responses to noise. Thresholding it directly gives thick edges, isolated noise points, and contours that break wherever the response wavers around the threshold. The detector must decide which pixels are edges, place each edge at a single, accurate position, and keep contours connected, while being robust to noise.

Inputs and Outputs

Input: a grayscale image and three parameters: the Gaussian scale $\sigma$ and a low and a high threshold on gradient magnitude.

Output: a binary edge map of one-pixel-wide contours. Implementations can also return the gradient magnitude and direction at each edge pixel.

Intuition

Smoothing trades noise for blur, so $\sigma$ decides which structures count as edges. After smoothing, an edge is a ridge in the gradient magnitude, and its center is where the magnitude peaks across the ridge, that is, along the gradient direction. Keeping only those peaks thins every ridge to one pixel.

Thresholding then decides which ridges are real. A single threshold forces a bad choice: set high, it breaks weak but genuine contours into fragments; set low, it accepts noise. Canny called the fragmentation “streaking”. Hysteresis uses two thresholds: a pixel above the high threshold starts a contour, and the contour is followed through all connected pixels above the low threshold. A real edge needs to exceed the high threshold only somewhere, and noise rarely produces long connected chains that do.

Algorithm

1. Smooth the image with a Gaussian filter of standard deviation $\sigma$.
2. Compute the gradient $(G_x, G_y)$ of the smoothed image, usually with the Sobel operator or with derivative-of-Gaussian filters, which combine steps 1 and 2. Compute the magnitude $M = \sqrt{G_x^2 + G_y^2}$ and direction $\theta = \operatorname{atan2}(G_y, G_x)$.
3. Non-maximum suppression. At each pixel, compare $M$ with its two neighbors along $\theta$, in either quantized form (one of four directions: 0°, 45°, 90°, 135°) or with interpolated magnitudes between pixels. Set $M$ to zero unless it is a local maximum.
4. Double threshold. Classify the remaining pixels as strong ($M > T_\text{high}$), weak ($T_\text{low} < M \le T_\text{high}$), or rejected.
5. Hysteresis. Keep strong pixels and every weak pixel connected to a strong pixel through a chain of weak or strong pixels, usually with 8-connectivity; discard the rest.

Mathematical Formulation

Canny’s criteria

Canny (1986) analyzed a one-dimensional edge $G(x)$ in white Gaussian noise of amplitude $n_0$, filtered by an antisymmetric operator $f$ with support $[-W, W]$, with edges marked at maxima of the output. His three criteria are:

1. Good detection: low probability of missing a real edge or marking a false one, captured by the output signal-to-noise ratio

$$\text{SNR} = \frac{\left| \int_{-W}^{W} G(-x) f(x)\, dx \right|}{n_0 \sqrt{\int_{-W}^{W} f^2(x)\, dx}} .$$

2. Good localization: marked points close to the true edge, measured as the reciprocal of the standard deviation of the position of the response maximum,

$$\text{Localization} = \frac{\left| \int_{-W}^{W} G'(-x) f'(x)\, dx \right|}{n_0 \sqrt{\int_{-W}^{W} f'^2(x)\, dx}} .$$

3. Single response: only one maximum per edge. Using Rice’s formula for the spacing of zero crossings in filtered noise, Canny required the mean distance between maxima of the noise response,

$$x_\text{max}(f) = 2\pi \left( \frac{\int f'^2(x)\, dx}{\int f''^2(x)\, dx} \right)^{1/2},$$

to equal a fixed fraction $k$ of the operator width $W$.

He maximized the product of the first two criteria under the third. Without the third, the optimum for a step is a difference of boxes, which responds to a noisy step with many nearby maxima.

For a step edge, scaling the operator by a factor $w$ multiplies its SNR by $\sqrt{w}$ and divides its localization by $\sqrt{w}$, so their product does not depend on scale. Canny called this an uncertainty principle between detection and localization: one operator shape is optimal at every scale, and the width only moves the balance between the two. He found the optimal shape numerically and showed that the first derivative of a Gaussian approximates it, with a product of SNR and localization about 20% lower and a multiple-response measure about 10% worse. He judged the difference hard to see on real images and used the Gaussian derivative because it is much cheaper in two dimensions.

Two dimensions

For the 2D image, Canny estimated the edge normal from the smoothed gradient, $\mathbf{n} = \nabla(G_\sigma * I) / |\nabla(G_\sigma * I)|$, and defined edge points as maxima of the directional derivative along $\mathbf{n}$:

$$\frac{\partial^2}{\partial \mathbf{n}^2} (G_\sigma * I) = 0, \qquad \text{strength} = |\nabla (G_\sigma * I)| .$$

Non-maximum suppression is the discrete form of this condition. Unlike the zero crossings of the Laplacian used by Marr and Hildreth (1980), it measures the second derivative only across the edge, not along it.

Parameters

• Scale $\sigma$. Larger values suppress more noise and texture but round corners, merge nearby edges, and displace curved ones. Values of 1 to 3 pixels are common for full-resolution photographs. Canny’s own implementation ran operators of several widths and combined them with a fine-to-coarse procedure he called feature synthesis; most implementations use one $\sigma$.
• High threshold. Sets which edges are detected at all. It should scale with the noise in the gradient, which depends on $\sigma$ and the image noise. Canny set the thresholds from a noise estimate: he filtered the operator output to isolate its noise component and took a low percentile of a global histogram of the result.
• Low threshold. Sets how far contours extend once started. Canny reported a high-to-low ratio of two or three to one in his implementation, a range many implementations adopt as a default.

Libraries differ in how thresholds are specified: in absolute gradient units (which depend on the derivative kernel’s normalization), as fractions of the maximum magnitude, or as quantiles of the magnitude distribution. Values do not transfer between them.

Complexity

Every step is linear in the number of pixels $N$. Separable Gaussian smoothing costs $O(\sigma)$ operations per pixel with a sampled kernel, or a constant with recursive filters; the gradient and non-maximum suppression cost a constant per pixel; and hysteresis is a connected-component search or a flood fill from the strong pixels, also $O(N)$. Memory is a few images of the input size.

Implementation

The example implements the full pipeline with NumPy and SciPy, using derivative-of-Gaussian filters for steps 1 and 2, quantized non-maximum suppression, and hysteresis by connected-component labeling. The test image contains a rectangle, a disk, and a triangle with contrasts of 0.5, 0.2, and 0.15 on a scale of 0 to 1, rendered without aliasing and corrupted by Gaussian noise with standard deviation 0.15. The ground truth is the one-pixel contour just inside each object. Precision is the fraction of detected pixels within one pixel (including diagonals) of a true edge pixel; recall is the fraction of true edge pixels with a detection within one pixel. This is simpler than the one-to-one matching used in boundary benchmarks: it does not penalize double responses. The last two columns count missed edge pixels and how many of them lie within $3\sigma$ of a corner.

import numpy as np
from scipy import ndimage

# --- Synthetic test image with known edges -------------------------------
# Objects are drawn in order; each pixel's label is the last object covering
# its center. Intensities are rendered with 4x4 supersampling, so boundary
# pixels take fractional values instead of aliased stair steps.
N, S = 160, 4
def shapes(y, x):
    lab = np.zeros(y.shape, int)
    val = np.full(y.shape, 0.2)
    rect = (30 <= x) & (x < 130) & (25 <= y) & (y < 135)          # contrast 0.5
    disk = np.hypot(x - 70, y - 75) < 28                           # contrast 0.2
    tri = (y > 95) & (y < 125) & (x > 90) & (x - 90 < 1.2 * (y - 95))  # 0.15
    for k, (m, v) in enumerate([(rect, 0.7), (disk, 0.5), (tri, 0.85)], 1):
        lab[m], val[m] = k, v
    return lab, val

yy, xx = np.mgrid[:N, :N] + 0.5                     # pixel centers
labels, _ = shapes(yy, xx)
sub = (np.arange(S) + 0.5) / S
ys, xs = np.mgrid[:N * S, :N * S] / S + sub[0]
clean = shapes(ys, xs)[1].reshape(N, S, N, S).mean(axis=(1, 3))

# Ground truth: a one-pixel contour on the inner side of every object
# (a pixel whose 4-neighbor has a lower label, i.e. lies outside the object).
pad = np.pad(labels, 1, mode="edge")
gt = np.zeros_like(labels, bool)
for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
    gt |= pad[1 + dy:N + 1 + dy, 1 + dx:N + 1 + dx] < labels

rng = np.random.default_rng(0)
noisy = clean + 0.15 * rng.standard_normal(clean.shape)

# --- Canny edge detector ---------------------------------------------------
def canny(img, sigma, low, high):
    # 1-2. Gaussian smoothing and differentiation in one step (derivative of
    #      Gaussian); scipy's order=(row, col).
    gx = ndimage.gaussian_filter(img, sigma, order=(0, 1))
    gy = ndimage.gaussian_filter(img, sigma, order=(1, 0))
    mag = np.hypot(gx, gy)
    ang = np.rad2deg(np.arctan2(gy, gx)) % 180       # gradient direction, mod 180

    # 3. Non-maximum suppression: keep a pixel only if its magnitude is not
    #    smaller than its two neighbors along the (quantized) gradient direction.
    q = (np.round(ang / 45).astype(int)) % 4          # 0, 45, 90, 135 degrees
    offsets = [(0, 1), (1, 1), (1, 0), (1, -1)]       # (drow, dcol) per bin
    H, W = mag.shape
    m = np.pad(mag, 1)
    keep = np.zeros(mag.shape, bool)
    for b, (dr, dc) in enumerate(offsets):
        fwd = m[1 + dr:H + 1 + dr, 1 + dc:W + 1 + dc]
        bwd = m[1 - dr:H + 1 - dr, 1 - dc:W + 1 - dc]
        keep |= (q == b) & (mag >= fwd) & (mag > bwd)
    thin = np.where(keep, mag, 0.0)

    # 4. Double threshold and hysteresis: keep every 8-connected chain of
    #    pixels above `low` that contains at least one pixel above `high`.
    weak = thin > low
    comp, n = ndimage.label(weak, structure=np.ones((3, 3)))
    has_strong = ndimage.maximum(thin > high, comp, index=np.arange(1, n + 1))
    return np.concatenate([[False], has_strong.astype(bool)])[comp]

def score(edges, truth, tol=1):
    """Precision and recall with a tolerance of `tol` pixels (chessboard)."""
    box = np.ones((2 * tol + 1, 2 * tol + 1), bool)
    near_truth = ndimage.binary_dilation(truth, box)
    near_edge = ndimage.binary_dilation(edges, box)
    p = (edges & near_truth).sum() / max(edges.sum(), 1)
    r = (truth & near_edge).sum() / truth.sum()
    return p, r, 2 * p * r / (p + r)

# Corners of the rectangle and the triangle, as (x, y), to locate misses.
corners = np.array([(30, 25), (130, 25), (30, 135), (130, 135),
                    (90, 95), (90, 125), (126, 125)])

print(f"ground-truth edge pixels: {gt.sum()}, noise std 0.15")
print("sigma   low   high  edges  precision  recall      F  missed  near corner")
for sigma, low, high in [(1.0, 0.10, 0.10), (1.0, 0.05, 0.10),
                         (2.0, 0.02, 0.02), (2.0, 0.04, 0.04), (2.0, 0.02, 0.04),
                         (3.0, 0.01, 0.02)]:
    e = canny(noisy, sigma, low, high)
    p, r, f = score(e, gt)
    miss = gt & ~ndimage.binary_dilation(e, np.ones((3, 3), bool))
    rows, cols = np.nonzero(miss)
    d = np.hypot(cols[:, None] + 0.5 - corners[:, 0], rows[:, None] + 0.5 - corners[:, 1])
    near = (d.min(axis=1) <= 3 * sigma).sum() if miss.any() else 0
    print(f"{sigma:5.1f} {low:5.2f} {high:6.2f} {e.sum():6d} {p:10.3f} {r:7.3f}"
          f" {f:6.3f} {miss.sum():7d} {near:12d}")

Output:

ground-truth edge pixels: 669, noise std 0.15
sigma   low   high  edges  precision  recall      F  missed  near corner
  1.0  0.10   0.10    603      0.847   0.777  0.811     149            9
  1.0  0.05   0.10   1581      0.428   0.904  0.581      64            8
  2.0  0.02   0.02   1106      0.652   0.984  0.784      11            9
  2.0  0.04   0.04    546      0.996   0.812  0.895     126           24
  2.0  0.02   0.04    739      0.976   0.984  0.980      11            9
  3.0  0.01   0.02    724      0.993   0.970  0.981      20           18

At $\sigma = 1$ the noise in each gradient component (standard deviation about 0.030) is half the peak response of the weakest edge (0.060), and no threshold works: a single threshold of 0.10 already misses a fifth of the edges while admitting false detections, and lowering the low threshold to 0.05 floods the map with noise chains connected to real edges. At $\sigma = 2$ the noise falls to about 0.007 while the weakest edge peaks at 0.030, so a margin appears. A single threshold of 0.02 finds almost every edge but also noise (precision 0.65); a single threshold of 0.04 is clean but loses the weak triangle and part of the disk (recall 0.81). Hysteresis with 0.02 and 0.04, a 2:1 ratio, keeps the precision of the high threshold and the recall of the low one (F = 0.98). At $\sigma = 3$ the result is equally clean, but the misses roughly double, and 18 of the 20 lie near corners, where heavier smoothing rounds the contour away from the true outline.

Properties and Behavior

• Thin output. Non-maximum suppression gives contours one pixel wide, except where the quantization of directions leaves occasional double pixels.
• Connected contours. Hysteresis bridges weak stretches of an edge that contains at least one strong pixel, which reduces streaking.
• Edge strength. For a straight step edge, the magnitude at the maximum is proportional to the contrast, so thresholds act directly on contrast.

Limitations

• Corners and junctions. The analysis assumes an edge with a constant cross-section, which Canny noted is not true of corners. Near corners and T-junctions the gradient direction is ill-defined, non-maximum suppression fails, and contours are rounded or broken, as the example shows.
• Texture. The detector responds to every intensity change at the chosen scale, so textured regions produce dense edges that are not object boundaries.
• Threshold sensitivity. Good thresholds depend on contrast and noise, which vary across images and within one image. Global thresholds that suit one region fail in another.
• Single model of an edge. Designed for steps, it gives double responses on thin lines and weak responses on roofs and on edges between textures.
• Localization bias. Smoothing shifts curved edges toward their center of curvature (Laplacian zero crossings shift the opposite way), by an amount that grows with $\sigma$, and merges parallel edges closer than about the smoothing scale.

Variants

• Deriche’s recursive detector. Deriche (1987) solved Canny’s optimization for an operator of infinite extent and obtained a filter implemented by two recursive passes in opposite directions, with a cost per pixel independent of the filter width.
• Sub-pixel localization. Fitting a parabola to the magnitude across the edge at each maximum places edges to a fraction of a pixel.
• Automatic thresholds. Implementations set thresholds from the image itself, for example from quantiles of the gradient magnitude, from a robust noise estimate as Canny did, or from a global thresholding method applied to the magnitude histogram.
• Multi-scale and scale-space edges. Running the detector over several scales or on an image pyramid addresses the fixed scale. Lindeberg (1998) added to the non-maximum condition a maximum over scale of a normalized edge strength, so that the scale can vary along an edge.

History

Canny formulated the three criteria in his 1983 MIT master’s thesis, published as the AI Laboratory report “Finding Edges and Lines in Images”, which derived optimal operators for steps and for ridges or valleys. The 1986 journal paper described the full system, including noise estimation, feature synthesis across scales, and elongated directional operators. Libraries today implement its simpler core: one scale, isotropic Gaussian derivatives, non-maximum suppression, and hysteresis. Canny’s paper is covered in its own article.