Skip to the lesson
FixTheRobot Explore Robotics / Navigation / M2 Maps and Costmaps / M2-T3

Navigation · Theory · M2

M2-T3 — Distance Transforms and Euclidean Distance Fields

How far is every cell from the nearest obstacle? A field answers it for the whole map at once, and two sweeps are enough.

  • Lesson 3 of 6
  • Module 2: Maps and Costmaps
  • Theory
  • About 7 minutes to read

Inflation, safe routes and many local planners all need one number per cell: the distance to the nearest obstacle. Asking every obstacle about every cell is slow. A distance transform answers for all cells with two passes over the grid, and the field it produces has a useful slope.

Learning objectives

After this lesson, you should be able to:

  • Compute a chamfer distance transform with a forward and a backward pass.
  • State the error of the chamfer distance against the Euclidean distance and when exact methods are needed.
  • Use a distance field to measure clearance and to find a direction away from obstacles.
  • Describe an Euclidean signed distance field (ESDF) and where it is used.

The intuition

Drop a pebble in a pond and the ripples spread outward at a steady speed. The time a ripple takes to reach a point is the distance to the pebble. A distance transform computes that for a whole map, with every obstacle a pebble: each cell learns how far the nearest ripple has travelled.

The cheap way to get it uses one observation: the distance of a cell is at most one step more than the distance of one of its neighbours. If you sweep across the grid once, each cell can inherit from the neighbours already visited above and to the left. That finds obstacles that lie up and to the left. A second sweep in the opposite direction handles the ones that lie down and to the right. Two sweeps, and every cell has its answer.

Two sweeps of a distance transformA small grid with a row of obstacles at the bottom. A forward sweep from the top-left cannot see them and leaves large values. A backward sweep from the bottom-right fixes every cell.Forward sweep: top-left to bottom-right ∞∞∞∞∞∞∞∞∞∞00000 Backward sweep: bottom-right to top-left 222221111100000 obstacle row at the bottom: the backward sweep carries 1, then 2, upwards
The forward sweep alone does not see obstacles below or to the right. The backward sweep finishes the job.

The mathematics

The chamfer transform

Start with 0 at obstacle cells and a large value elsewhere. Then:

forward (rows top→bottom, columns left→right)
d[r][c]=min⁡(d[r][c], d[r−1][c]+1, d[r][c−1]+1, d[r−1][c−1]+2, d[r−1][c+1]+2)d[r][c]=\min (d[r][c],\,d[r-1][c]+1,\,d[r][c-1]+1,\,d[r-1][c-1]+\sqrt{2},\,d[r-1][c+1]+\sqrt{2})
backward (rows bottom→top, columns right→left)
d[r][c]=min⁡(d[r][c], d[r+1][c]+1, d[r][c+1]+1, d[r+1][c+1]+2, d[r+1][c−1]+2)d[r][c]=\min (d[r][c],\,d[r+1][c]+1,\,d[r][c+1]+1,\,d[r+1][c+1]+\sqrt{2},\,d[r+1][c-1]+\sqrt{2})

The work is proportional to the number of cells: about ten operations per cell, whatever the number of obstacles. The brute-force alternative takes cells × obstacles.

How accurate is it?

The result is the length of the shortest chain of straight (cost 1) and diagonal (cost √2) steps. That is exact along rows, columns and diagonals and too long in other directions, by up to about 8%, because the chain has to go around the corner. The worst case is a direction about 27° from an axis:

Chamfer error
obstacle at(0, 0), cell at(3, 1): Euclidean=32+12=3.162\text{obstacle at}(0,\,0),\,\text{cell at}(3,\,1):\,\mathrm{Euclidean}=\sqrt{3^{2}+1^{2}}=3.162
chamfer=1⋅2+2⋅1=3.414\text{chamfer}=1\cdot \sqrt{2}+2\cdot 1=3.414
ratio 1.080\text{ratio}\,1.080

Weights 0.95509 and 1.36930 (Borgefors) reduce the worst error to about 4.5%, and exact Euclidean transforms (for example the lower-envelope method of Felzenszwalb and Huttenlocher) remove it, at a modest extra cost.

Signed distance and the gradient

A signed distance field is positive in free space and negative inside obstacles, so the zero set is the surface. A Euclidean signed distance field (ESDF) is common in 3D mapping. Its gradient points away from the nearest obstacle with unit length wherever it is defined:

Gradient by central differences
∇d≈(d[r][c+1]−d[r][c−1]2, d[r+1][c]−d[r−1][c]2)\nabla d\approx (\frac{d[r][c+1]-d[r][c-1]}{2},\,\frac{d[r+1][c]-d[r-1][c]}{2})
∣∇d∣≈1 for an exact field\lvert \nabla d\rvert \approx 1\,\text{for an exact field}

On a ridge, equally far from two obstacles, the two sides cancel and the gradient is zero: the field has no preferred direction there.

A worked example

A corridor, by hand. A corridor is five cells wide, so the chamfer distance of the three cells between two walls (rows of obstacles above and below) is 1, 2, 1. The centre line has d = 2, and an obstacle-clearing path should follow it.

One door, two answers. In the lab (M2-L2) a wall has a 3-cell door and a 9-cell door. The centre of the 3-cell door has clearance 2 cells, the centre of the 9-cell door has 5. With 0.10 m cells that is 0.2 m against 0.5 m: Scout’s inscribed radius is 0.2 m, so the narrow door gives it no margin at all and the wide one gives 0.3 m.

Cost of the brute-force alternative. A 1000 × 600 grid with 40 000 obstacle cells needs 600 000 × 40 000 = 2.4 × 10¹⁰ distance evaluations by brute force. The two sweeps need about 600 000 × 10 = 6 × 10⁶ operations, four thousand times fewer. The inflation code in the previous lesson’s lab avoids the cost another way: each obstacle only looks inside the window of the inflation radius.

Engineering implications and limitations

The field is a service

Once a distance field exists, many consumers share it: the inflation layer reads costs from it, a local planner reads clearance and its gradient, and a safety monitor checks the distance to the robot’s own footprint. Compute it once per map update and share it.

Update cost

Recomputing a whole field after every sensor message is wasteful. Incremental methods update only the cells affected by changed obstacles, which is how 3D systems keep an ESDF current at sensor rate.

Resolution again

Distances are only as fine as the grid. A cell 0.12 m from a wall on a 0.10 m grid is reported at 0.1 or 0.2 m. The gradient is noisy near obstacles for that reason, so smooth or clamp it before using it to push a robot.

Three dimensions

The same two-sweep idea works in 3D with more neighbours. Systems such as voxblox and nvblox compute ESDFs from depth cameras for drones and ground robots.

Common misconceptions

“A distance transform needs to loop over all obstacles for each cell.”

Two passes over the grid are enough. That is the point of the method.

“The chamfer distance is the Euclidean distance.”

It is within about 8% (or 4.5% with tuned weights). For clearance margins in centimetres, use an exact method or a margin.

“Following the gradient leads to a goal.”

It leads away from obstacles, up to a ridge or a local maximum. It is a safety nudge, not a route.

“A signed field and an unsigned one carry the same information.”

The signed one also knows how deep inside an obstacle a point is, which matters for collision penetration and for 3D surfaces.

Engineering takeaways

  1. A distance transform gives the distance to the nearest obstacle for every cell in two passes over the grid.
  2. The chamfer distance overestimates by up to about 8%; exact methods remove the error.
  3. The field’s gradient points away from obstacles and vanishes on ridges.
  4. Compute the field once and let inflation, planners and safety monitors share it.
  5. An ESDF is the 3D, signed version used by mapping systems for drones and ground robots.

References and further reading

The classic algorithms for distance transforms.

  • A. Rosenfeld and J. Pfaltz, “Sequential Operations in Digital Picture Processing”, Journal of the ACM, 13(4), 1966.
  • G. Borgefors, “Distance Transformations in Digital Images”, Computer Vision, Graphics, and Image Processing, 34(3), 1986.
  • P. Felzenszwalb and D. Huttenlocher, “Distance Transforms of Sampled Functions”, Theory of Computing, 8, 2012.
  • H. Oleynikova et al., “Voxblox: Incremental 3D Euclidean Signed Distance Fields for On-Board MAV Planning”, IEEE/RSJ IROS, 2017.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

Question 1

An obstacle sits at (0,0). What is the chamfer distance of the cell (3,1), and the Euclidean distance?

Explanation

Chamfer: one diagonal step (√2) plus two straight steps = 3.414. Euclidean: √10 = 3.162. The chamfer value is 8% too long.

Question 2

Why is a single forward pass not enough?

Explanation

It propagates distance only from cells above and to the left. Obstacles below or to the right never reach a cell in the first pass, so those cells keep an over-large value until the backward pass.

Question 3

A path follows the cells with the largest distance in a corridor. Why can its gradient be zero in the middle?

Explanation

The middle is a ridge: it is equally far from the two walls, so the slopes toward them cancel. There is no direction that increases clearance.

What’s next

Next: how several maps and sensors combine into one layered costmap, and why ghosts appear.

Practice this lesson

Compute a Distance Field

Compute the distance to the nearest obstacle for every cell, and use it to find the safest corridor.

Next lesson

M2-T4 — Layered Costmaps

Describe static, obstacle, inflation and social layers, and explain marking, clearing and why ghost obstacles appear.

Nothing below is required to finish this lesson.