The Distance Transform

Picture a black-and-white image — shapes painted in white on a black canvas. Now ask a simple question for every black pixel: how far is it from the nearest white pixel?

That question, answered simultaneously for the whole image, is the distance transform. The result is not just another black-and-white picture: it is a field of numbers, a topographic map where height encodes proximity to the shapes. Pixels deep inside empty space carry large values; pixels hugging an edge carry small ones. Painted as a glow, the image literally radiates outward from every boundary.

The naïve approach — for each pixel, scan every foreground pixel and take the minimum — costs $O(N^2)$ for an image of $N$ pixels. The chamfer distance transform, introduced by Borgefors in 1984, reduces that to $O(N)$ with just two passes: one from top-left to bottom-right, one from bottom-right to top-left. Each pass propagates small distance increments through the grid, and when both sweeps meet in the middle the field is complete.

The elegance is in the simplicity: no priority queues, no graph traversal — just two nested loops and a handful of additions.

Draw shapes on the canvas below — click or drag to paint white foreground pixels. Then press Run transform to see the chamfer distance field: every background pixel glows brighter the farther it sits from your shapes. Press Clear to start fresh.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<canvas id="canvas" width="200" height="200"></canvas>
<div class="status" id="status">{{status_draw}}</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="clear" type="button" class="ghost">{{btn_clear}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px;
         cursor: crosshair; max-width: 100%; image-rendering: pixelated; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice how the glow radiates uniformly outward from every edge, like ripples from a stone dropped in still water. The two passes of the algorithm propagate the distance field in opposite directions across the grid, meeting in the middle. Pixels deep inside empty regions glow brightest because they are farthest from any shape boundary.

How fast can a distance transform be computed, and how good is the chamfer approach?

• Naïve: for each of the $N$ background pixels, scan all $F$ foreground pixels and keep the minimum distance. Cost: $O(N \cdot F)$ — often $O(N^2)$ in practice.
• Chamfer two-pass (Borgefors, 1984): a forward pass (top-left to bottom-right) and a backward pass (bottom-right to top-left) each touch every pixel exactly once. Total cost: $O(N)$ time, $O(N)$ space. For a $W \times H$ image, $N = W \cdot H$.
• Exactness: the basic chamfer uses integer weights (typically 3 for axis-aligned neighbors, 4 for diagonals, giving the "3-4 chamfer"). This approximates Euclidean distance with a maximum error of about 8 %. Exact Euclidean distance transforms exist (e.g., the algorithm by Meijster et al., 2000) and also run in $O(N)$, but require more bookkeeping.
• Optimality: any algorithm must read every pixel at least once, so $\Omega(N)$ is a lower bound. The chamfer algorithm is therefore asymptotically optimal.

The chamfer approach trades a small approximation error for remarkable simplicity. In many applications — path planning, font rendering, collision detection — that trade-off is entirely acceptable. When exact distances are needed, exact $O(N)$ algorithms are available, but they are considerably more complex to implement. See also pattern matching and closest pair of points for related distance-minimization ideas.

The distance field produced by the transform is a universal building block anywhere a program needs to reason about how far something is from a boundary:

• Robot path planning: a robot can plan a path that stays as far as possible from obstacles by following the ridges of the distance field — the medial axis is exactly the set of points equidistant from two or more boundaries.
• Font rendering and signed distance fields (SDF): modern GPU font renderers (introduced by Valve in 2007) store a low-resolution distance field for each glyph. At render time the field is threshold-sampled, producing smooth, scalable letters at any resolution with almost no storage cost.
• Collision detection: game engines and physics simulators use distance fields to cheaply answer "how close is this object to a wall?" without scanning every wall polygon.
• Medical image segmentation: in CT and MRI processing, the distance transform helps separate touching structures — two organs that just touch in a scan can be split at the valley of the joint distance field.
• Morphological operations: erosion and dilation of binary images reduce to thresholding the distance field, connecting the transform to the whole family of pattern matching and shape-analysis algorithms.

Wherever geometry and proximity meet — vision, graphics, robotics, simulation — the distance transform is usually nearby, quietly doing its two passes.

The chamfer distance transform is a masterclass in algorithmic thinking: a problem that looks like it demands comparing every pair of pixels is solved in two linear sweeps by exploiting the fact that distances propagate locally. Each pixel only needs to look at a handful of neighbors already processed, and the global distance field assembles itself for free.

The result powers everything from the smooth fonts on your screen to the robots that navigate warehouses. Next time you see a smooth gradient glowing outward from a shape, you are looking at the distance field in action — and somewhere behind it, two quiet passes through a grid. Learn more about how algorithms exploit local structure in dynamic shortest paths.