PA170 Digital Geometry
Lecture 4: Distance Measurement
Martin Maˇska (xmaska@fi.muni.cz)
Centre for Biomedical Image Analysis
Faculty of Informatics, Masaryk University, Brno
Autumn 2023
INTRODUCTION TO DISTANCE
TRANSFORMS
Distance Transforms
Let I be a binary image, defined on a grid G, with nonempty foreground I as well as
background I . For any grid metric d, the d distance transform of I associates with
every image element p ∈ G the (shortest) d distance from p to I
Remark: The distance from p ∈ S to T ⊆ S is defined as d(p, T) = min
q∈T
d(p, q)
Binary image d4 distance transform d8 distance transform
Binary image Distance graph Distance map Iso-distance curves 3/21
Distance Transforms: Commentary
If one is interested in distances between background image elements and the
foreground, the role of background and foreground is exchanged
Foreground and background distance transforms are sometimes represented by the
signed distance function
Distance transforms are exploited in a broad range of applications:
Separation of touching objects
Computation of morphological operators (dilation, erosion)
Computation of geometrical representations (skeletonization, Voronoi tesselation,
Delaunay triangulation, medial axes, etc.)
Robot navigation
Distance-based shape measurements (object centers, maximal width, etc.)
Pattern (shape) matching
Image registration
k-NN computation
. . .
4/21
DISTANCE TRANSFORM FOR
REGULAR METRICS
Regular Distance Transform: Preliminaries
Let p ∈ G be a grid point of a grid G. Its α-adjacency set Aα(p) can be split into two
disjoint sets (Aα(p) = A←
α (p) ∪ A→
α (p)), depending on whether an adjacent grid point
q ∈ G precedes (q ∈ A←
α (p)) or follows (q ∈ A→
α (p)) the grid point p when scanning G
row by row from top to bottom and each row is scanned from left to right
A←
4 (p) A→
4 (p) A←
8 (p) A→
8 (p)
6/21
Regular Distance Transform: Two-Pass Algorithm
1 In a single left-to-right, top-to-bottom scan of G calculate for each image element p
f1(p) =
0, if p ∈ I
min{f1(q) + w(p, q) : q ∈ A←
α (p)}, if p ∈ I
2 In a single right-to-left, bottom-to-top scan of G calculate for each image element p
f2(p) = min{f1(p), f2(q) + w(p, q) : q ∈ A→
α (p)} = d(p, I )
where w(p, q) = 1 in case of d4 and d8; and w(p, q) = a for 4-adjacent image elements
and w(p, q) = b for 8-adjacent image elements in case of da,b (0 < a ≤ b ≤ 2a)
First pass (d4) Second pass (d4) First pass (d8) Second pass (d8)
7/21
Two-Pass Algorithm: Properties
The calculated distances are exact for all regular metrics on digital grids
Easy implementation without the need for an auxiliary image buffer (i.e., only the
input binary image and the ouput image with the calculated distances are needed)
Straightforward extension into higher dimensions, especially for higher-dimensional
chamfer distances
Its time complexity is O(n) (n is the number of image elements)
8/21
EUCLIDEAN DISTANCE
TRANSFORM (EDT)
Classification of Algorithms for EDT
Remark: The Euclidean metric de is not regular on digital grids, and thus the incremental
propagation of distances is not so straightforward
Brute-force approaches
Exact but inefficient calculation of Euclidean distances
Ordered-propagation approaches
Efficient but non-exact calculation of Euclidean distances
The Fast Marching algorithm is relatively difficult to implement (see PA166)
Raster-scanning approaches
Efficient but non-exact calculation of Euclidean distances
Danielsson’s algorithm is easy to implement
10/21
Danielsson’s Algorithm: Main Idea
It is a two-pass, raster-scanning algorithm for calculating non-exact Euclidean
distance transforms
It propagates pairs of integers (not distances themselves), which encode the
absolute values of the relative coordinates of the nearest background image element
The pairs of integers are propagated from top to bottom and from bottom to top,
being compared as follows: min{(x1, y1), (x2, y2)} is equal to (xi, yi) for which x2
i + y2
i
is smaller. If they are equal the pair with the smaller x-coordinate is taken.
11/21
Danielsson’s Algorithm: Pseudocode
1 Set integer pairs in tmp to (0, 0) (or (∞, ∞)) for background (or foreground) pixels
2 For each row of tmp (from top to bottom), replace each (f(x), f(y))
1 from left to right with min{(f(x), f(y)), (f(x), f(y − 1)) + (0, 1)}
2 from left to right with min{(f(x), f(y)), (f(x − 1), f(y)) + (1, 0)}
3 from right to left with min{(f(x), f(y)), (f(x + 1), f(y)) + (1, 0)}
3 For each row of tmp (from bottom to top), replace each (f(x), f(y))
1 from right to left with min{(f(x), f(y)), (f(x), f(y + 1)) + (0, 1)}
2 from right to left with min{(f(x), f(y)), (f(x + 1), f(y)) + (1, 0)}
3 from left to right with min{(f(x), f(y)), (f(x − 1), f(y)) + (1, 0)}
4 Calculate the Euclidean distances from the integer pairs stored in tmp
Final integer pairs (tmp) Euclidean distances 12/21
Danielsson’s Algorithm: Erroneous Distances
b =
1
√
2
+ a2 −
1
2
≈ a +
1
√
2
< a + 1
13/21
Danielsson’s Algorithm: Discussion
The calculated distances are not always exact, differing from the Euclidean distances
by a fraction of the grid constant at most
Easy implementation with the need of an auxiliary image buffer
Possible extension into higher dimensions
Its time complexity is O(n) (n is the number of image elements)
Different masks and propagation strategies can be taken to improve the accuracy of
the calculated distances
14/21
GEODESIC DISTANCE
Geodesic Distance (Intrinsic Distance)
A geodesic distance between two points p ∈ S and q ∈ S is defined as the length of
the shortest path ρ = (p = p1, p2, . . . , pn = q), pi ∈ S, 0 ≤ i ≤ n, from p and q within a
set S:
dS
(p, q) = L(ρ) =
n−1
i=1
dN(pi, pi+1)
where dN(·, ·) is the distance between two adjacent points along the path ρ
The shortest 8-path (of length 5) and 4-paths (of length 16 and 8) within different sets of pixels
16/21
Geodesic Distance: Algorithm
Raster-scanning approaches are not suitable because they must run until stability
Ordered-propagation approaches are thus preferred:
Their main idea is to process image elements from closest to farthest
A positive distance between adjacent image elements (i.e., dN > 0) guarantees that
every image element is propagated only once
Dijkstra algorithm (a graph-based approach): O(m · log n) (m is the number of edges,
and n is the number of vertices)
Fast Marching algorithm (a PDE-based approach): O(n · log n) (n is the number of image
elements)
17/21
DISTANCES BETWEEN SETS
Hausdorff Metric (Hausdorff Distance)
Any metric d on a compact set S can be extended to a Hausdorff metric on the family
of all nonempty compact subsets A, B of S by defining
HD(A, B) = max max
p∈A
min
q∈B
d(p, q), max
p∈B
min
q∈A
d(p, q)
The Hausdorff distance is very sensitive to outliers
Percentile Hausdorff distance (the inner maxima replaced by a percentile – often the
95th percentile), average distance (the inner maxima replaced by averaging), and
symmetric-difference-based metrics (card(A∆B) and card(A∆B)
1+card(A∪B)) are used in practice
19/21
Hausdorff Distance: Algorithm
Let A, B ⊂ Gm,n be two finite sets of grid points
Let R be the smallest isothetic rectangle of size k ×l, which contains A ∪ B
If card(A) and card(B) are O(k · l), a brute-force algorithm takes O(k2 · l2) steps
By calculating and scanning distance transforms of A and B, the Hausdorff distance
HD(A, B) can efficiently be calculated in O(k · l) steps:
1 Calculate a distance transform DT(A) in R
2 Calculate a distance transform DT(B) in R
3 Let a be the maximum value in DT(A) across all the grid points in B
4 Let b be the maximum value in DT(B) across all the grid points in A
5 Return max{a, b}
20/21
Take-Home Messages
Distance transforms for regular metrics can be calculated exactly on digital grids
using a two-pass algorithm
Non-exact Euclidean distance transforms can efficiently be computed using the
Danielsson algorithm
Geodesic (intrinsic) distances can efficiently be computed using ordered-propagation
approaches
Modified Hausdorff distances are often used in practice when calculating distances
between sets
21/21