Where the Distance Transform Matters

Introduction

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.

Watch the Glow Expand

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.

<!-- Interactive chamfer distance transform demo -->
<p class="hint">Draw shapes by clicking or dragging on the canvas. Press <b>Run transform</b> to compute the chamfer distance field — each background pixel glows brighter the farther it sits from your shapes.</p>
<canvas id="canvas" width="200" height="200"></canvas>
<div class="status" id="status">Draw shapes, then run the transform.</div>
<div class="btns">
  <button id="run" type="button">Run transform</button>
  <button id="clear" type="button" class="ghost">Clear</button>
</div>

/* Styles for the distance transform demo */
* { 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; }

/* Chamfer distance transform — two-pass O(N) algorithm */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width;
const H = canvas.height;

/* Image grid: W x H pixels */
const fg = new Uint8Array(W * H); // 1 = foreground (shape), 0 = background
let painting = false;
let transformDone = false;

/* Draw helpers */
function drawDefaultShapes() {
  /* Three circles as the initial foreground */
  const shapes = [
    { cx: 50, cy: 50, r: 18 },
    { cx: 155, cy: 60, r: 22 },
    { cx: 100, cy: 140, r: 30 }
  ];
  for (const s of shapes) {
    for (let y = 0; y < H; y++) {
      for (let x = 0; x < W; x++) {
        const dx = x - s.cx;
        const dy = y - s.cy;
        if (dx * dx + dy * dy <= s.r * s.r) fg[y * W + x] = 1;
      }
    }
  }
}

function paintPixel(x, y) {
  /* Paint a filled circle of radius r at (x,y) */
  const r = 5;
  for (let dy = -r; dy <= r; dy++) {
    for (let dx = -r; dx <= r; dx++) {
      if (dx * dx + dy * dy <= r * r) {
        const px = x + dx;
        const py = y + dy;
        if (px >= 0 && px < W && py >= 0 && py < H) fg[py * W + px] = 1;
      }
    }
  }
}

function renderFg() {
  /* Render the foreground/background as a grayscale image */
  const img = ctx.createImageData(W, H);
  for (let i = 0; i < W * H; i++) {
    const v = fg[i] ? 255 : 30;
    img.data[i * 4] = v;
    img.data[i * 4 + 1] = v;
    img.data[i * 4 + 2] = v;
    img.data[i * 4 + 3] = 255;
  }
  ctx.putImageData(img, 0, 0);
}

/* Chamfer 3-4 distance transform (Borgefors, 1984) */
function runChamfer() {
  /* Two-pass approach: forward pass then backward pass */
  const INF = 999999;
  const dist = new Int32Array(W * H).fill(INF);

  /* Initialize distance — 0 for foreground, INF for background */
  for (let i = 0; i < W * H; i++) if (fg[i]) dist[i] = 0;

  /* Forward pass: top-left to bottom-right */
  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
      if (fg[y * W + x]) continue;
      let best = INF;
      /* Axis-aligned neighbors: cost 3 */
      if (x > 0)     best = Math.min(best, dist[y * W + x - 1] + 3);
      if (y > 0)     best = Math.min(best, dist[(y - 1) * W + x] + 3);
      /* Diagonal neighbors: cost 4 */
      if (x > 0 && y > 0) best = Math.min(best, dist[(y - 1) * W + x - 1] + 4);
      if (x < W - 1 && y > 0) best = Math.min(best, dist[(y - 1) * W + x + 1] + 4);
      dist[y * W + x] = best;
    }
  }

  /* Backward pass: bottom-right to top-left */
  for (let y = H - 1; y >= 0; y--) {
    for (let x = W - 1; x >= 0; x--) {
      if (fg[y * W + x]) continue;
      let best = dist[y * W + x];
      if (x < W - 1)     best = Math.min(best, dist[y * W + x + 1] + 3);
      if (y < H - 1)     best = Math.min(best, dist[(y + 1) * W + x] + 3);
      if (x < W - 1 && y < H - 1) best = Math.min(best, dist[(y + 1) * W + x + 1] + 4);
      if (x > 0 && y < H - 1)     best = Math.min(best, dist[(y + 1) * W + x - 1] + 4);
      dist[y * W + x] = best;
    }
  }

  /* Render the distance field as a color glow */
  let maxD = 0;
  for (let i = 0; i < W * H; i++) if (dist[i] !== INF && dist[i] > maxD) maxD = dist[i];

  const img = ctx.createImageData(W, H);
  for (let i = 0; i < W * H; i++) {
    let r, g, b;
    if (fg[i]) {
      /* Foreground pixels are white */
      r = 255; g = 255; b = 255;
    } else {
      /* Background pixels glow blue-purple by distance */
      const t = dist[i] / maxD;
      r = Math.round(30 + 180 * t);
      g = Math.round(30 + 120 * t);
      b = Math.round(60 + 195 * t);
    }
    img.data[i * 4] = r;
    img.data[i * 4 + 1] = g;
    img.data[i * 4 + 2] = b;
    img.data[i * 4 + 3] = 255;
  }
  ctx.putImageData(img, 0, 0);
  return maxD;
}

/* Mouse and touch interaction */
function canvasXY(e) {
  const rect = canvas.getBoundingClientRect();
  const sx = canvas.width / rect.width;
  const sy = canvas.height / rect.height;
  const src = e.touches ? e.touches[0] : e;
  return [Math.floor((src.clientX - rect.left) * sx), Math.floor((src.clientY - rect.top) * sy)];
}

canvas.addEventListener('mousedown', e => {
  painting = true;
  if (transformDone) { fg.fill(0); transformDone = false; }
  const [x, y] = canvasXY(e);
  paintPixel(x, y); renderFg();
});
canvas.addEventListener('mousemove', e => {
  if (!painting) return;
  const [x, y] = canvasXY(e);
  paintPixel(x, y); renderFg();
});
canvas.addEventListener('mouseup', () => { painting = false; });
canvas.addEventListener('mouseleave', () => { painting = false; });
canvas.addEventListener('touchstart', e => {
  e.preventDefault(); painting = true;
  if (transformDone) { fg.fill(0); transformDone = false; }
  const [x, y] = canvasXY(e); paintPixel(x, y); renderFg();
}, { passive: false });
canvas.addEventListener('touchmove', e => {
  e.preventDefault(); if (!painting) return;
  const [x, y] = canvasXY(e); paintPixel(x, y); renderFg();
}, { passive: false });
canvas.addEventListener('touchend', () => { painting = false; });

document.getElementById('run').addEventListener('click', () => {
  const fgCount = fg.reduce((a, v) => a + v, 0);
  if (fgCount === 0) {
    document.getElementById('status').textContent = 'Draw at least one shape first.';
    return;
  }
  const maxD = runChamfer();
  transformDone = true;
  document.getElementById('status').textContent = i18nFmt('Transform done — max distance approx. %maxD% px.', { maxD: Math.round(maxD / 3) });
});

document.getElementById('clear').addEventListener('click', () => {
  fg.fill(0); transformDone = false; renderFg();
  document.getElementById('status').textContent = 'Draw shapes, then run the transform.';
});

/* Initialize with default shapes */
drawDefaultShapes();
renderFg();

<!-- Interactive chamfer distance transform demo -->
<p class="hint">Draw shapes by clicking or dragging on the canvas. Press <b>Run transform</b> to compute the chamfer distance field — each background pixel glows brighter the farther it sits from your shapes.</p>
<canvas id="canvas" width="200" height="200"></canvas>
<div class="status" id="status">Draw shapes, then run the transform.</div>
<div class="btns">
  <button id="run" type="button">Run transform</button>
  <button id="clear" type="button" class="ghost">Clear</button>
</div>

/* Styles for the distance transform demo */
* { 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; }

/* Chamfer distance transform — two-pass O(N) algorithm */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width;
const H = canvas.height;

/* Image grid: W x H pixels */
const fg = new Uint8Array(W * H); // 1 = foreground (shape), 0 = background
let painting = false;
let transformDone = false;

/* Draw helpers */
function drawDefaultShapes() {
  /* Three circles as the initial foreground */
  const shapes = [
    { cx: 50, cy: 50, r: 18 },
    { cx: 155, cy: 60, r: 22 },
    { cx: 100, cy: 140, r: 30 }
  ];
  for (const s of shapes) {
    for (let y = 0; y < H; y++) {
      for (let x = 0; x < W; x++) {
        const dx = x - s.cx;
        const dy = y - s.cy;
        if (dx * dx + dy * dy <= s.r * s.r) fg[y * W + x] = 1;
      }
    }
  }
}

function paintPixel(x, y) {
  /* Paint a filled circle of radius r at (x,y) */
  const r = 5;
  for (let dy = -r; dy <= r; dy++) {
    for (let dx = -r; dx <= r; dx++) {
      if (dx * dx + dy * dy <= r * r) {
        const px = x + dx;
        const py = y + dy;
        if (px >= 0 && px < W && py >= 0 && py < H) fg[py * W + px] = 1;
      }
    }
  }
}

function renderFg() {
  /* Render the foreground/background as a grayscale image */
  const img = ctx.createImageData(W, H);
  for (let i = 0; i < W * H; i++) {
    const v = fg[i] ? 255 : 30;
    img.data[i * 4] = v;
    img.data[i * 4 + 1] = v;
    img.data[i * 4 + 2] = v;
    img.data[i * 4 + 3] = 255;
  }
  ctx.putImageData(img, 0, 0);
}

/* Chamfer 3-4 distance transform (Borgefors, 1984) */
function runChamfer() {
  /* Two-pass approach: forward pass then backward pass */
  const INF = 999999;
  const dist = new Int32Array(W * H).fill(INF);

  /* Initialize distance — 0 for foreground, INF for background */
  for (let i = 0; i < W * H; i++) if (fg[i]) dist[i] = 0;

  /* Forward pass: top-left to bottom-right */
  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++) {
      if (fg[y * W + x]) continue;
      let best = INF;
      /* Axis-aligned neighbors: cost 3 */
      if (x > 0)     best = Math.min(best, dist[y * W + x - 1] + 3);
      if (y > 0)     best = Math.min(best, dist[(y - 1) * W + x] + 3);
      /* Diagonal neighbors: cost 4 */
      if (x > 0 && y > 0) best = Math.min(best, dist[(y - 1) * W + x - 1] + 4);
      if (x < W - 1 && y > 0) best = Math.min(best, dist[(y - 1) * W + x + 1] + 4);
      dist[y * W + x] = best;
    }
  }

  /* Backward pass: bottom-right to top-left */
  for (let y = H - 1; y >= 0; y--) {
    for (let x = W - 1; x >= 0; x--) {
      if (fg[y * W + x]) continue;
      let best = dist[y * W + x];
      if (x < W - 1)     best = Math.min(best, dist[y * W + x + 1] + 3);
      if (y < H - 1)     best = Math.min(best, dist[(y + 1) * W + x] + 3);
      if (x < W - 1 && y < H - 1) best = Math.min(best, dist[(y + 1) * W + x + 1] + 4);
      if (x > 0 && y < H - 1)     best = Math.min(best, dist[(y + 1) * W + x - 1] + 4);
      dist[y * W + x] = best;
    }
  }

  /* Render the distance field as a color glow */
  let maxD = 0;
  for (let i = 0; i < W * H; i++) if (dist[i] !== INF && dist[i] > maxD) maxD = dist[i];

  const img = ctx.createImageData(W, H);
  for (let i = 0; i < W * H; i++) {
    let r, g, b;
    if (fg[i]) {
      /* Foreground pixels are white */
      r = 255; g = 255; b = 255;
    } else {
      /* Background pixels glow blue-purple by distance */
      const t = dist[i] / maxD;
      r = Math.round(30 + 180 * t);
      g = Math.round(30 + 120 * t);
      b = Math.round(60 + 195 * t);
    }
    img.data[i * 4] = r;
    img.data[i * 4 + 1] = g;
    img.data[i * 4 + 2] = b;
    img.data[i * 4 + 3] = 255;
  }
  ctx.putImageData(img, 0, 0);
  return maxD;
}

/* Mouse and touch interaction */
function canvasXY(e) {
  const rect = canvas.getBoundingClientRect();
  const sx = canvas.width / rect.width;
  const sy = canvas.height / rect.height;
  const src = e.touches ? e.touches[0] : e;
  return [Math.floor((src.clientX - rect.left) * sx), Math.floor((src.clientY - rect.top) * sy)];
}

canvas.addEventListener('mousedown', e => {
  painting = true;
  if (transformDone) { fg.fill(0); transformDone = false; }
  const [x, y] = canvasXY(e);
  paintPixel(x, y); renderFg();
});
canvas.addEventListener('mousemove', e => {
  if (!painting) return;
  const [x, y] = canvasXY(e);
  paintPixel(x, y); renderFg();
});
canvas.addEventListener('mouseup', () => { painting = false; });
canvas.addEventListener('mouseleave', () => { painting = false; });
canvas.addEventListener('touchstart', e => {
  e.preventDefault(); painting = true;
  if (transformDone) { fg.fill(0); transformDone = false; }
  const [x, y] = canvasXY(e); paintPixel(x, y); renderFg();
}, { passive: false });
canvas.addEventListener('touchmove', e => {
  e.preventDefault(); if (!painting) return;
  const [x, y] = canvasXY(e); paintPixel(x, y); renderFg();
}, { passive: false });
canvas.addEventListener('touchend', () => { painting = false; });

document.getElementById('run').addEventListener('click', () => {
  const fgCount = fg.reduce((a, v) => a + v, 0);
  if (fgCount === 0) {
    document.getElementById('status').textContent = 'Draw at least one shape first.';
    return;
  }
  const maxD = runChamfer();
  transformDone = true;
  document.getElementById('status').textContent = i18nFmt('Transform done — max distance approx. %maxD% px.', { maxD: Math.round(maxD / 3) });
});

document.getElementById('clear').addEventListener('click', () => {
  fg.fill(0); transformDone = false; renderFg();
  document.getElementById('status').textContent = 'Draw shapes, then run the transform.';
});

/* Initialize with default shapes */
drawDefaultShapes();
renderFg();

Result

Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/chamfer-distance-transform/Content licensed under CC BY-NC 4.0.

Cookies & privacy

The Distance Transform

How a two-pass sweep labels every pixel with its distance to the nearest edge