Distance Transform models
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
Distance
transform of Notting Hill pedestrian accessibility
Code samples and generated diagrams
In the first code sample,
below, MATLAB 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)
MATLAB
Imagelib DT Exact Euclidean Distance Transform (EDT) - must have Image
toolbox installed
Sample
MWDT code 1: (MATLAB routine, EDT,
Steiner solution) – unweighted 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.
Sample MWDT code 2: (MATLAB routine, EDT, modified Steiner
solution) – weighted solution result illustrated below
