DISTANCE
TRANSFORMS Home
Distance transforms compute the distance of every pixel in
a binary image, or every cell in a lattice dataset, to the nearest point in an
object set – the object set may be a single point, in which case the distance
contours should be circular if the transform is strictly Euclidean. However,
distance transforms often use approximations to Euclidean distance for speed of
processing (so-called chamfer metrics). These result in an approximation to the
circular form, usually as an 8-sided or 16-sided closest fit polygon. The
initial examples below (see links provided) illustrate extensions to the
standard DT models in order to handle anisotropic spaces. In the first example
(Wardrop’s model), a Least Cost Distance Transform (LCDT) is shown, where cost
is a function of traffic velocity. In the second example the physical street
pattern of Notting Hill constrains feasible paths, and the distance transform
takes this into account. Discussion papers on Distance Transforms can be found
on the Thesis page, here
Distance
transform of Wardrop’s velocity field model
Code samples and generated diagrams
In the first sample, below, MATLAB and Python code is provided for a
simple 5x5 chamfer metric distance transform. The second example provides
similar code using the Image Toolbox provided as an option with MATLAB. It is
possible to convert the chamfer metric diagram into an exact Euclidean distance
transform by (i) retaining details of the local nearest points (vectors) to each
cell (this can be implemented within the standard DT routine provided with
minimal overhead); (ii) tracing the paths determined by these vectors to
identify the closest object point (in the examples below, the object point is
the centre of the diagram); and then (iii) computing the Euclidean distance from
the number of x- and y-steps from cell to target point.
Sample DT code (MATLAB routine, Borgefors fractional chamfer
metric)
Sample DT
code (Python routine, Borgefors
fractional chamfer metric)
MATLAB Imagelib DT Exact Euclidean Distance Transform (EDT) - must have Image
toolbox installed
Sample WDT code
1: MATLAB routine, EDT, Steiner
solution – unweighted solution (all weights=
1) result illustrated below
Sample MWDT code
2: MATLAB routine, EDT, modified Steiner solution –
weighted solution result illustrated below. In this final example use has again
been made of the Image Toolbox to compute 2 separate exact distance transforms
which have then been weighted and added together to provide a decision-diagram.
The upper two black squares are “train stations” either of which are acceptable
to a prospective homebuyer (transform 1), whilst the third black square is the
location of a school, which has been weighted 50% more important than the
stations (transform 2) – the two transforms have been added together to produce
the decision diagram – regions of common colour have equal cost in terms of
(weighted) distance to travel.
