Lesson 7: Distance Measures¶
"Distance" on a pixel grid is not as simple as it sounds. We look at three different flavors:
- Point-to-point distance metrics (Manhattan, chessboard, and Euclidean) — which measure how far apart two pixels are.
- Curve-length estimators (Freeman and a refined weighted estimator) — which measure the length of a digitized curve (e.g. the boundary of a blob) from its chain code.
- Chamfer distance transform — a fast, image-wide approximation to the Euclidean distance transform, computed with two raster-scan passes.
import numpy as np
import cv2
import matplotlib.pyplot as plt
Part 1: Point-to-point distance metrics¶
Given two pixels $p=(x_1,y_1)$ and $q=(x_2,y_2)$, let $d_x = x_2-x_1$ and $d_y=y_2-y_1$. Three common metrics:
Manhattan / city-block ($L_1$): distance if you can move only along the grid axes (like walking city blocks).
$D_4(p,q) = |d_x| + |d_y|$
Chessboard ($L_\infty$): number of king moves on a chessboard (diagonal steps are "free").
$D_8(p,q) = \max(|d_x|,\,|d_y|)$
Euclidean ($L_2$): ordinary straight-line distance.
$D_E(p,q) = \sqrt{d_x^2+d_y^2}$
The names $D_4$ and $D_8$ come from the fact that each is the shortest path length when only 4-connected (axis) or 8-connected (axis + diagonal) moves are allowed, one unit per move.
def manhattan(dx, dy):
return np.abs(dx) + np.abs(dy)
def chessboard(dx, dy):
return np.maximum(np.abs(dx), np.abs(dy))
def euclidean(dx, dy):
return np.sqrt(dx**2 + dy**2)
Visualizing the three metrics as distance fields¶
For every pixel in a grid, we compute its distance to the center pixel under each metric and display it as an image. The metrics agree only along the axes — everywhere else they diverge.
size = 101
half = size // 2
yy, xx = np.mgrid[-half:half + 1, -half:half + 1]
fields = {
'Manhattan ($D_4$)': manhattan(xx, yy),
'Chessboard ($D_8$)': chessboard(xx, yy),
'Euclidean': euclidean(xx, yy),
}
# Compute a single vmin/vmax to prevent each imshow() from auto-scaling
# (Manhattan's max is 100, Euclidean's is ~71, chessboard's is 50).
vmax = max(field.max() for field in fields.values())
fig, axes = plt.subplots(1, 3, figsize=(12, 4))
for ax, (name, field) in zip(axes, fields.items()):
im = ax.imshow(field, cmap='viridis', vmin=0, vmax=vmax)
ax.contour(field, levels=8, colors='white', linewidths=0.5)
ax.set_title(name)
ax.axis('off')
plt.tight_layout()
plt.show()
The contour lines reveal each metric's characteristic shape: Manhattan distance forms diamonds, chessboard distance forms squares, and Euclidean distance forms circles — the one shape most people intuitively think of as "equal distance away".
Part 2: Estimating curve length from a chain code¶
Now suppose we want to estimate the length of a curve, not just the distance between two points. Let's create a test image of a circle with known radius ($60$) and known circumference ($120 \pi = 377$). Note that the number of boundary pixels ($336$) is a poor estimate of the circumference, since $336 \neq 377$.
radius = 60
img = np.zeros((150, 150), dtype=np.uint8)
cv2.circle(img, (75, 75), radius, 255, 1)
contours, _ = cv2.findContours(img, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)
pts = contours[0][:, 0, :]
plt.imshow(img, cmap='gray')
plt.title(f'Digitized circle, radius={radius}, {len(pts)} boundary pixels')
plt.axis('off')
plt.show()
A Freeman chain code describes a digital curve as a sequence of unit steps in 8 possible directions (0–7, 45° apart). Four of the eight directions are even (horizontal/vertical, true length 1) and four are odd (diagonal, true length $\sqrt{2}$).
If a curve's chain code has $N_e$ even steps and $N_o$ odd steps, Freeman's estimate of its length is simply
$$L_{\text{Freeman}} = N_e + \sqrt{2}\,N_o$$
This sounds right, but it systematically overestimates smooth curves: a real circle's boundary, when digitized, alternates through many short zig-zag "staircase" steps that add up to more than the true arc length.
To fix this problem, the exact weights $(1, \sqrt{2})$ can be replaced with weights $(a, b)$ tuned to minimize the average error over many digitized curves — an idea sometimes associated with Kimura's chain-code length correction. Commonly cited values (they vary slightly by source) are approximately $a \approx 0.948$ and $b \approx 1.343$:
$$L_{\text{corrected}} = a\,N_e + b\,N_o$$
steps = np.diff(np.vstack([pts, pts[:1]]), axis=0) # step from each boundary pixel to the next
is_diagonal = (steps[:, 0] != 0) & (steps[:, 1] != 0)
N_o = int(np.sum(is_diagonal)) # odd (diagonal) steps
N_e = int(np.sum(~is_diagonal)) # even (axis-aligned) steps
true_length = 2 * np.pi * radius
L_freeman = N_e + np.sqrt(2) * N_o
a, b = 0.948, 1.343
L_corrected = a * N_e + b * N_o
print(f'N_e (even/axis steps) = {N_e}')
print(f'N_o (odd/diagonal steps) = {N_o}')
print(f'number of boundary pixels = {len(pts):.1f}')
print(f'true circumference = {true_length:.1f}')
print(f'Freeman estimate = {L_freeman:.1f} (error {100*(L_freeman-true_length)/true_length:+.1f}%)')
print(f'Corrected estimate = {L_corrected:.1f} (error {100*(L_corrected-true_length)/true_length:+.1f}%)')
The corrected weights bring the estimate much closer to the true circumference, without needing anything more than a count of even and odd steps — useful when you want a cheap length estimate directly from a chain code.
Part 3: Chamfer distance transform¶
A distance transform labels every pixel of a binary image with its distance to the nearest foreground (or background) pixel — useful for skeletonization, shape matching, and path planning. Computing it exactly with Euclidean distance requires comparing every pixel against every foreground pixel (slow), or a more careful algorithm.
The chamfer distance transform is a fast approximation: instead of a single global search, it propagates local distances across the image in just two raster-scan passes (top-left to bottom-right, then bottom-right to top-left), adding a small fixed cost for each step to a neighbor. Using integer weights $a=3$ for axis-aligned neighbors and $b=4$ for diagonal neighbors (then dividing by 3 at the end) gives the classic 3-4 chamfer distance, a good, cheap approximation to Euclidean distance — the same idea as the Freeman/corrected chain-code weights from Part 2, but applied to every pixel instead of just a boundary.
OpenCV's cv2.distanceTransform with DIST_L2 computes the chamfer distance. The maskSize governs the quality of the approximation: a larger mask is more accurate but requires more compute.
img = np.zeros((100, 100), dtype=np.uint8)
cv2.circle(img, (50, 50), 10, 255, -1)
img = 255 - img # we will compute distance from each background pixel to the nearest foreground (nonzero) pixel
im_dist3 = cv2.distanceTransform(img, cv2.DIST_L2, maskSize = 3) # (3,4) chamfer algorithm
im_dist5 = cv2.distanceTransform(img, cv2.DIST_L2, maskSize = 5) # more accurate algorithm
error = im_dist3 - im_dist5
print(f'max error = {np.abs(error).max():.3f} pixels')
print(f'mean error = {np.abs(error).mean():.3f} pixels')
fig, axes = plt.subplots(1, 3, figsize=(12, 4))
for ax, field, title in zip(
axes,
[im_dist3, im_dist5, error],
['Chamfer (3-4) approx.', 'More accurate estimate', 'Difference'],
):
im = ax.imshow(field, cmap='viridis' if title != 'Difference' else 'coolwarm')
ax.set_title(title, fontsize=10)
ax.axis('off')
plt.colorbar(im, ax=ax, fraction=0.046)
plt.tight_layout()
plt.show()
The chamfer transform approximates the exact Euclidean distance transform, computed in two fast linear passes instead of an expensive nearest-neighbor search.
Exercise¶
- Repeat the circle experiment for a few different radii (e.g. 10, 20, 40, 80). Does the Freeman estimate's percent error stay roughly constant, or does it shrink as the circle gets bigger? Why might that be?
- The chessboard distance $D_8$ is the exact shortest path length when diagonal moves are allowed and cost 1. Can you construct a modified chessboard-like metric, using a diagonal cost of $\sqrt{2}$ instead of 1, that behaves like a coarse local version of the chain-code length estimators above? Compare it to true Euclidean distance for a few points.