The Canny Edge Detector

Imagine handing a robot a photograph and asking it to trace every meaningful boundary in the scene. A naive gradient filter lights up around every edge with a thick, noisy smear. It doubles and triples lines that should be single pixels wide. It also reacts violently to sensor noise. The challenge is not detecting some edges — that is easy. The challenge is detecting the right edges, each exactly once, as a thin curve. It must do this without drowning in false positives from texture and noise. The Canny edge detector, introduced by John Canny in 1986, was the first edge detector derived from an explicit optimality criterion rather than from intuition or trial and error. Canny asked: what is the mathematically best possible edge operator? He specified precise goals for detection, localization, and single-response behavior. The algorithm that emerged from this analysis — Gaussian smoothing, gradient computation, non-maximum suppression, and hysteresis thresholding — has remained the reference standard for classical edge detection for nearly four decades. It still ships inside OpenCV, MATLAB, and countless vision pipelines today. This matters because edges are a compact, information-rich summary of an image. They mark object boundaries, occlusions, texture changes, and surface discontinuities. They feed downstream tasks like segmentation, stereo matching, feature tracking, and shape recognition. A detector that produces thin, connected, well-localized edges saves enormous computation and error downstream. This is compared to a noisy thick response that later stages must clean up. Even in the deep learning era, Canny edges remain useful. They serve as a fast, interpretable preprocessing step, a training signal for edge-aware losses, and a diagnostic baseline against which learned detectors are measured. This article builds the algorithm from its criteria. It gives runnable pseudocode for every stage. It works a numerical trace by hand. It explains precisely why each stage is necessary — not just what it does.

Key takeaways

Canny edge detection optimizes three criteria simultaneously: good detection, good localization, and single response per edge.
The pipeline is: Gaussian smoothing → gradient magnitude/direction → non-maximum suppression → double thresholding → hysteresis linking.
Non-maximum suppression thins thick gradient ridges down to one-pixel-wide edge curves.
Hysteresis thresholding uses two thresholds so weak-but-connected edges survive while isolated weak noise is discarded.
The full algorithm runs in O(n) time and space for an n-pixel image, dominated by convolution and a linear-time flood fill.
It remains a standard building block in classical vision pipelines, medical imaging, and as a preprocessing/evaluation baseline for learned edge detectors.

The core insight

Canny edge detection is optimal-criteria-driven: smooth to suppress noise, find gradient ridges, thin them to one pixel with non-maximum suppression, and stitch them into continuous curves with two-threshold hysteresis instead of one brittle cutoff.

The idea

An edge is a location where image intensity changes sharply, typically corresponding to an object boundary, shadow, or surface discontinuity — see Edge Detection for the general problem setting. Any real edge detector must contend with sensor noise, which produces spurious gradient responses everywhere, and with the fact that a genuine step edge, after any smoothing, becomes a ridge of gradient magnitude several pixels wide rather than a single line. Canny formalized "the best edge detector" as the solution to a constrained optimization problem with three simultaneous criteria. Good detection means a low probability of missing real edges and a low probability of falsely marking non-edges — formalized as maximizing the signal-to-noise ratio of the filter's response. Good localization means the detected edge points should sit as close as possible to the true center of the underlying edge. Single response means one real edge should produce one detected edge, not multiple parallel responses from the same physical discontinuity. Canny showed that for a step edge in additive white noise, the operator that best trades off the first two competing criteria (detection vs. localization, which pull in opposite directions) is closely approximated by the first derivative of a Gaussian. The third criterion, uniqueness of response, is what motivates the non-maximum suppression and thresholding stages built on top of that derivative filter. The resulting algorithm is not a single filter but a pipeline: it smooths with a Gaussian (building on Gaussian and Median Filtering) to control noise and set the operating scale, computes intensity gradients to locate candidate edges, thins the resulting gradient ridges to single-pixel width via non-maximum suppression, and finally uses two thresholds linked by connectivity — hysteresis — to keep only edges that are part of a strong, connected structure while discarding isolated noise responses. Each stage exists to correct a specific failure mode of the stage before it.

How it works

Stage 1 — Gaussian smoothing. Convolve the input image with a 2D Gaussian kernel of standard deviation $\sigma$ to suppress noise before differentiating (differentiation amplifies high-frequency noise, so smoothing first is essential). Larger $\sigma$ removes more noise but blurs and can merge nearby edges or shift their location; smaller $\sigma$ preserves fine detail but tolerates less noise. This is the same Gaussian filtering machinery from Gaussian and Median Filtering, applied here as a preprocessing step rather than an end in itself.

Stage 2 — Gradient computation. Estimate the horizontal and vertical intensity derivatives $I_x, I_y$ (commonly with Sobel-like kernels) on the smoothed image, then compute gradient magnitude and orientation:

M(x,y) = \sqrt{I_x(x,y)^2 + I_y(x,y)^2}, \qquad \theta(x,y) = \operatorname{atan2}\big(I_y(x,y),\, I_x(x,y)\big).

Because convolution is associative, smoothing then differentiating is equivalent to convolving with a derivative-of-Gaussian kernel directly — this is the operator Canny's analysis singles out as (near-)optimal.

Stage 3 — Non-maximum suppression (NMS). The gradient magnitude image is a "ridge": genuine edges appear as several-pixel-wide bands of high magnitude, not single lines. NMS thins each ridge to one pixel by keeping a pixel only if its magnitude is a local maximum along the gradient direction (i.e., perpendicular to the edge). The gradient direction at each pixel is quantized to one of four discrete orientations (0°, 45°, 90°, 135°), and the pixel is compared against its two neighbors along that direction.

Stage 4 — Double thresholding. Classify surviving pixels using a high threshold $T_h$ and a low threshold $T_l$ (typically $T_h \approx 2$ – $3 \times T_l$ ). Pixels above $T_h$ are strong edges; pixels between $T_l$ and $T_h$ are weak edges; pixels below $T_l$ are suppressed immediately.

Stage 5 — Hysteresis linking. A weak edge pixel is kept only if it is 8-connected (directly or through a chain of other weak pixels) to at least one strong pixel; otherwise it is discarded. This is implemented as a graph traversal (BFS/DFS or flood fill) seeded at every strong pixel. ``` function CannyEdgeDetector(image I, sigma, T_low, T_high): // Stage 1: noise suppression G = GaussianBlur(I, sigma) // Stage 2: gradients Ix = ConvolveSobelX(G) Iy = ConvolveSobelY(G) for each pixel p: M[p] = sqrt(Ix[p]^2 + Iy[p]^2) theta[p] = atan2(Iy[p], Ix[p]) dir[p] = QuantizeAngleTo4Bins(theta[p]) // 0, 45, 90, 135 degrees // Stage 3: non-maximum suppression N = zeros_like(M) for each pixel p not on border: (n1, n2) = NeighborsAlongDirection(p, dir[p]) if M[p] >= M[n1] and M[p] >= M[n2]: N[p] = M[p] else: N[p] = 0 // Stage 4: double threshold classification STRONG, WEAK, NONE = 2, 1, 0 label = zeros_like(N) for each pixel p: if N[p] >= T_high: label[p] = STRONG else if N[p] >= T_low: label[p] = WEAK else: label[p] = NONE // Stage 5: hysteresis via flood fill from strong seeds visited = zeros_like(N) // boolean final = zeros_like(N) // boolean, the output edge map queue = empty queue for each pixel p: if label[p] == STRONG and not visited[p]: push p onto queue visited[p] = true final[p] = true while queue not empty: q = pop from queue for each 8-neighbor r of q: if not visited[r] and label[r] != NONE: visited[r] = true final[r] = true push r onto queue return final // binary edge map ``` The `QuantizeAngleTo4Bins` step maps the continuous gradient orientation to whichever of the four principal directions it is closest to, so that `NeighborsAlongDirection` can always look up two integer-coordinate neighbor pixels (interpolated NMS variants instead interpolate magnitude between the two nearest pixels along the exact gradient direction, at extra cost, for slightly better sub-pixel accuracy).

Figure

The five-stage Canny pipeline, with an intermediate gradient-ridge and its thinned result

Complexity & correctness

Time complexity. Let the image have $n = W \times H$ pixels and let the Gaussian kernel have radius $k = O(\sigma)$ (a separable Gaussian is applied as two 1D passes). Each stage is:

Gaussian blur (separable): $O(n \cdot k)$ — two 1D convolutions per pixel.
Sobel gradients: $O(n)$ — fixed-size $3\times 3$ kernels, constant work per pixel.
Non-maximum suppression: $O(n)$ — constant work (angle quantization + two comparisons) per pixel.
Double thresholding: $O(n)$ — one comparison per pixel.
Hysteresis (flood fill / BFS over the pixel grid graph): $O(n)$ — each pixel is enqueued and visited at most once, and each has a constant number (8) of neighbors, so total work is $O(n)$ by the standard graph-traversal argument (edges examined $\le 8n$ ).

Summing, the total is

O(n\cdot k) + O(n) + O(n) + O(n) + O(n) = O(n\cdot k),

which is $O(n)$ whenever $\sigma$ (and hence $k$ ) is treated as a constant independent of image size — the typical regime in practice, since $\sigma$ is chosen for noise scale, not image resolution. This is asymptotically as fast as any single-pass linear filter; the pipeline's extra stages (NMS, hysteresis) do not change the asymptotic order, only the constant factor.

Space complexity. $O(n)$ : the algorithm keeps a handful of full-resolution buffers (blurred image, $I_x$ , $I_y$ , magnitude, direction labels, visited flags, output map), each of size $n$ , plus an $O(n)$ -capacity queue in the worst case for hysteresis (a queue that in the worst case holds every strong-labeled pixel simultaneously, still $O(n)$ ).

Correctness argument, stage by stage. Smoothing suppresses noise without destroying the edge signal. A step edge convolved with a Gaussian is smeared over a width proportional to $\sigma$ , but its peak-gradient location is unchanged in expectation for a straight edge (the Gaussian is symmetric), while independent pixel noise has its variance reduced by convolution — a standard fact for linear filtering (variance of a sum of $\propto k^2$ i.i.d. terms scaled by kernel weights shrinks by the sum of squared weights). This is the formal detection/noise tradeoff Canny's optimization targets. Non-maximum suppression correctly extracts a thin ridge. Near a true edge, gradient magnitude, viewed as a 1D function along the direction perpendicular to the edge, is unimodal (it rises to a peak at the edge center and falls off symmetrically, assuming the underlying step convolved with a smooth low-pass kernel). Keeping only pixels that are local maxima along that direction therefore keeps exactly the peak of each such unimodal profile and discards its shoulders — this is precisely what produces a one-pixel-wide response for a single physical edge, which is the "single response" criterion. The quantization to four directions introduces a bounded angular error (at most 22.5°), trading a small, provably bounded localization error for O(1) neighbor lookups instead of interpolation. Hysteresis is sound because it never introduces new spurious components. Formally, consider the graph $G$ whose vertices are pixels with label WEAK or STRONG and whose edges connect 8-adjacent such pixels. Hysteresis keeps exactly the pixels in a connected component of $G$ that contains at least one STRONG vertex. This guarantees: (1) every kept pixel has some justification — either it is itself a high-confidence edge point, or it is part of an unbroken chain reaching one — and (2) isolated weak responses (their own connected component contains no STRONG vertex) are discarded, precisely the noise pixels that crossed $T_l$ by chance but never reached $T_h$ . This is why two thresholds strictly dominate one: a single fixed threshold $T$ either lets through isolated noise (if $T$ is set to $T_l$ ) or breaks up genuine but locally weak edge segments into disconnected fragments (if $T$ is set to $T_h$ ); hysteresis avoids both failure modes by using connectivity as the deciding factor for the ambiguous middle band.

Honest tradeoffs. The choice of $\sigma$ and the two thresholds is empirical, not derived from the image itself, so Canny's output is sensitive to hand-tuned parameters and to the actual noise statistics of the sensor, which are rarely known exactly. The four-direction quantization in NMS introduces a small, bounded geometric bias at diagonal edges. Corners and junctions, where the gradient direction changes rapidly over a small region, are the classic weak point: NMS and hysteresis are both built on an implicit assumption of locally straight, well-separated edges, and this assumption breaks down exactly where multiple edges meet.

Worked example

Consider a small 1D cross-section (a single row) through a noisy step edge, intensities:

x	0	1	2	3	4	5	6	7
I(x)	10	11	9	12	100	98	101	99

There is a true edge between $x=3$ and $x=4$ (jump from ~10 to ~100), plus small noise fluctuations on both sides.

Step 1 — smoothing. Apply a small Gaussian-like average (weights $\tfrac14,\tfrac12,\tfrac14$ ) along $x$ :

x	1	2	3	4	5	6
G(x)	10.25	10.25	10.75	53.25	91.5	99.25

Notice noise is already damped: the raw jump at $x=2\to3$ (9→12, a jump of 3) has shrunk relative to the still-large true-edge jump.

Step 2 — gradient (simple centered difference $G(x+1)-G(x-1)$ ).

x	2	3	4	5
M(x)	0.5	43.0	81.25	46.0

The magnitude ridge spans $x = 3,4,5$ — three pixels wide, all elevated, because the true edge's influence spreads across the smoothing window.

Step 3 — non-maximum suppression (1D case: compare each point to its two 1D neighbors).

$x=3$ : $M(3)=43.0$ ; neighbors $M(2)=0.5, M(4)=81.25$ . Not a local max (loses to $x=4$ ) → suppressed to 0.
$x=4$ : $M(4)=81.25$ ; neighbors $M(3)=43.0, M(5)=46.0$ . Local max on both sides → kept.
$x=5$ : $M(5)=46.0$ ; neighbors $M(4)=81.25, M(6)$ (off the small table, treat as lower) → suppressed.

Result: the three-pixel-wide ridge collapses to a single surviving pixel at $x=4$ , exactly at the true discontinuity. This is the thinning effect NMS is designed to produce.

Step 4 — double thresholding. Suppose $T_l = 20$ , $T_h = 60$ . Then $x=4$ with $M=81.25$ is STRONG. If a neighboring noisy region elsewhere in the image produced an isolated pixel with $M = 25$ (between $T_l$ and $T_h$ , hence WEAK) but with no STRONG neighbor within 8-connectivity, hysteresis discards it in Step 5; if instead that WEAK pixel sits immediately next to the STRONG pixel at $x=4$ (e.g., is a continuation of the same physical boundary curving through the image), it survives.

Step 5 — hysteresis. Flood fill from the STRONG seed at $x=4$ absorbs any connected WEAK pixels, confirming the final one-pixel edge (extended in 2D, this becomes a connected curve tracing the object boundary rather than a scatter of dots).

Stage	Output at the edge region
Raw intensity	Noisy jump ~10 → ~100 spread over several samples
Blurred	Smooth transition ~10 → ~99, noise reduced
Gradient magnitude	Ridge of width 3 (x=3,4,5), peak at x=4
After NMS	Single point at x=4
After threshold+hysteresis	Confirmed STRONG edge at x=4; isolated weak noise discarded

Common pitfalls & traps

Pitfall	Why it happens	Consequence
Single fixed threshold instead of hysteresis	Treating thresholding as a one-parameter decision	Either noisy specks pass through, or real edges fragment into dashed segments
$\sigma$ too large	Over-smoothing to "be safe" against noise	Nearby edges merge, fine detail and corners are lost, localization error grows
$\sigma$ too small	Under-smoothing on genuinely noisy images	Gradient step amplifies noise; NMS keeps thousands of spurious 1-pixel maxima
Angle quantization at exactly 45°/135° boundaries	Ties in `QuantizeAngleTo4Bins` mishandled	Inconsistent neighbor choice can create small gaps in diagonal edges
Forgetting border pixels in NMS/gradient	Neighbor lookup goes out of bounds	Crash, or silently wrong values if not handled with padding/clamping
Applying NMS/threshold before smoothing	Pipeline stages reordered	Raw noise gradients dominate; hysteresis cannot rescue a corrupted magnitude map
Treating $T_h, T_l$ as scale-invariant constants	Reusing thresholds across images with different contrast/exposure	Detector over- or under-fires depending on image brightness/contrast

Pioneers & history

Origins · 1 minJohn F. Canny and how this was discovered

John F. Canny

born 1958 · Computer scientist, MIT AI Lab, 1980s

Canny developed the edge detector bearing his name as part of his 1986 master's thesis at MIT, framing edge detection for the first time as a formal optimization problem with explicit, quantifiable criteria — detection, localization, and single response — rather than as an ad hoc filter design exercise. His approach connected signal processing theory (matched filtering, signal-to-noise analysis) directly to a practical, widely deployable computer vision algorithm, and the derivative-of-Gaussian operator he derived, together with non-maximum suppression and hysteresis thresholding, has remained essentially unchanged in most modern implementations.

History

1980

— Marr and Hildreth propose the Laplacian-of-Gaussian zero-crossing edge detector, an early principled predecessor.

1986

— John Canny publishes "A Computational Approach to Edge Detection," introducing the optimality criteria and the full pipeline.

1986–1990

s — Canny's method is adopted widely in robotics and industrial vision as the reference edge detector.

1996

— Publicly available reference implementations (and later OpenCV's `cv2.Canny`) make the algorithm a standard library function.

2010

s–present — Learned edge/boundary detectors (e.g., holistically-nested edge detection) surpass Canny on benchmark accuracy, but Canny remains a fast, parameter-light baseline and preprocessing tool.

Where this matters

Canny edge detection is a foundational step in classical computer vision pipelines and remains embedded in production software today. OpenCV's `Canny()` function is one of the most-called routines in industrial and research vision code, used for lane detection in early driver-assistance prototypes, document boundary detection in scanning apps, and PCB or part-inspection systems in manufacturing quality control. Medical imaging pipelines use Canny-style edge maps to delineate organ or tumor boundaries as a preprocessing step before segmentation refinement. Optical character recognition and document analysis systems use edge maps to locate text regions and table borders before layout analysis. In robotics and SLAM-adjacent perception, edge maps assist feature extraction and line-based mapping when full learned pipelines are too heavy for embedded hardware. Even as convolutional and transformer-based boundary detectors have overtaken Canny in raw accuracy on curated benchmarks, Canny persists as an interpretable, hyperparameter-light, real-time-capable tool, and as the textbook example that teaches the general design pattern — smooth, differentiate, thin, threshold with hysteresis — reused across many other detection problems in vision.

Ask the tutor: Why does non-maximum suppression need the gradient direction, not just the gradient magnitude, to correctly thin an edge?

Why smooth with a Gaussian before computing gradients, instead of differentiating the raw image?

Differentiation is a high-pass operation: it amplifies high-frequency content, and sensor noise is largely high-frequency, so differentiating a raw noisy image produces a gradient map dominated by noise spikes rather than genuine structure. Gaussian smoothing is a low-pass filter that attenuates that high-frequency noise while preserving the lower-frequency structure that constitutes real edges, at the cost of some blurring and localization error controlled by the parameter $\sigma$ . Because convolution is associative and the derivative of a convolution equals the convolution with the derivative, smoothing-then-differentiating is mathematically equivalent to convolving directly with a derivative-of-Gaussian kernel — which is exactly the operator Canny's optimality analysis identifies as the best available compromise between detection sensitivity and noise robustness.

How should sigma, T_low, and T_high be chosen in practice?

There is no universal formula; all three are typically set empirically based on image noise level, resolution, and the scale of structures of interest. A common heuristic sets $T_h$ to roughly 2–3 times $T_l$ , and both are often derived from the image's own gradient-magnitude statistics (for example, percentiles of the magnitude histogram) rather than fixed absolute numbers, so the thresholds adapt somewhat to contrast and exposure. $\sigma$ is chosen relative to the expected noise scale and the smallest edge features one wants to preserve — larger $\sigma$ for noisy, low-resolution images, smaller $\sigma$ when fine detail must survive. Some practical pipelines use automatic threshold selection (e.g., based on Otsu's method applied to the gradient magnitude) to reduce manual tuning across varying image conditions.

Why is a single-pixel-wide edge response considered "correct," rather than just an implementation convenience?

A physical edge — a real object boundary or intensity discontinuity — is, in the idealized world, an infinitesimally thin locus in the scene; a thick, multi-pixel response is an artifact of blurring and differentiation, not a property of the underlying scene. Canny's "single response" criterion formalizes this: for one physical edge, the detector should output one detected edge, because downstream tasks (contour tracing, junction detection, stereo matching along epipolar lines, shape descriptors) assume a thin, unambiguous curve and would otherwise have to disambiguate spurious duplicate or parallel detections themselves. Non-maximum suppression achieves this by keeping only the local maximum of the gradient-magnitude ridge along the direction perpendicular to the edge, which — under the reasonable assumption that this magnitude profile is locally unimodal — provably picks exactly one point per ridge cross-section.

How does Canny edge detection compare to simpler operators like Sobel or Prewitt used alone?

Sobel and Prewitt are just the gradient-computation stage of Canny in isolation: they return a gradient magnitude and direction map but perform no thinning and no principled thresholding strategy, so their raw output is a thick, noisy band around every intensity change. Using Sobel alone, a user must apply an ad hoc single threshold, which reintroduces exactly the failure mode (noise vs. fragmentation) that Canny's hysteresis avoids, and there is no thinning step, so edges remain several pixels wide unless the user adds their own non-maximum suppression. In effect, Canny embeds Sobel-style gradients as one internal stage within a larger, theoretically motivated pipeline; the extra stages (blurring, NMS, hysteresis) are precisely what elevate a raw gradient filter into a detector that satisfies detection, localization, and uniqueness criteria simultaneously.

Does the Canny edge detector handle corners and junctions well?

Not particularly well, and this is one of its well-known limitations. Non-maximum suppression assumes the gradient direction is roughly constant across a small neighborhood so that comparing a pixel to two neighbors along that single direction is meaningful; near corners and junctions, the true edge direction changes rapidly, or two or more edges overlap, and the four-direction quantization plus 1D-ridge assumption can suppress or merge responses incorrectly. In practice, corner and junction detection is treated as a separate problem (e.g., Harris corner detector, or learned keypoint detectors) rather than something Canny is expected to solve, and pipelines needing both edges and corners typically run complementary detectors side by side rather than relying on Canny for junction accuracy.

Is Canny edge detection still relevant given modern learned edge detectors?

Yes, though for different reasons than raw accuracy. Learned boundary detectors trained on large annotated datasets now outperform Canny on standard benchmarks measuring agreement with human-perceived object boundaries, because they can exploit semantic and contextual cues that a purely local gradient-based method cannot see. Canny remains valuable where speed, determinism, interpretability, and the absence of a training dataset matter: it runs in real time on embedded hardware, requires no labeled data, has few, interpretable parameters, and its behavior can be reasoned about mathematically rather than treated as a black box. It is also still used as a fast preprocessing step feeding into other classical algorithms (Hough transforms for line/circle detection, contour-based shape analysis) and as a lightweight baseline against which the accuracy gains of learned methods are measured.