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.





Back