In the image processing world a procedure similar to ACS has been developed in connection with work on pattern recognition. The procedure is known as the Distance Transform (DT) process, and is typically implemented on binary images in a scanning manner, starting from the top left of the image, proceeding to the bottom right, and then scanning back to the top left. Extremely efficient algorithms have been developed to generate exact Euclidean DTs and excellent approximations to exact Euclidean DTs on large images, including implementation within hardware for real-time applications. GIS vendors do not currently utilise DT methods, but they are included in many image processing toolsets and packages, including the MATLab Image Processing Toolkit — see the bwdist() function, which provides a variety of metrics for black and white images, including City Block and exact Euclidean. Another example with more direct links with GIS is the Leica product suite, ERDAS Imagine.

The basic DT procedure has been extended and developed by Ratti et al. (Architecture and the built environment; 2001, 2004), de Smith (Transport routes; 2004, 2006) and Ikonen and Toivanen (Image processing; 2005) to provide a new and fast family of ACS-like procedures for solving many grid-related distance problems. The procedure can be readily extended to full 3D problems if required (see Borgefors, 1996, for more details). Details of the procedures and sample code or pseudo-code are provided in the references cited, so we limit discussion here to a small sample of applications. The first deals with radially symmetric models of traffic in cities ― see Angel and Hyman, Urban Fields (1976) for a full discussion of the models involved.

Figure 4‑57A shows the result of applying a least cost distance transform (LCDT) to a city with traffic speeds varying from almost 0kph in the centre (where the crossed lines meet) to much higher levels (e.g. 50kph) at the city edge. The widening concentric circles in the diagram represent the cost field, in this case being traffic speeds (a velocity field) and the curved lines (blue and light grey) show contours of equal travel time (isochrones) to/from a point due South of the city centre. Shortest paths (minimum travel time paths) across this transformed surface may be plotted by following routes to or from the source point in any given direction, remaining at right angles (orthogonal) to the equal time contours, or by using tracking of the computed shortest paths (shown by the vector map, Figure 4‑57B). Angel and Hyman applied models of this type to the analysis of traffic flows in Manchester, UK. Distance transform methods enable such models to be calibrated against known analytical results and then applied to more realistic complex velocity and cost fields, for example to examine the possible effects of introducing central zone congestion charging.

Figure 4‑57 Urban traffic modelling

A second example of this procedure is shown in Figure 4‑58. This shows a section of the Notting Hill area of central London, with the annual Carnival route shown in white and areas in dark grey being masked out (buildings etc.). Colours indicate increasing distances (in metres) from the Carnival route along nearby streets. Although this example has been created by a DT scanning procedure the result is sometimes described as a “burning fire” analogy, with the fire spreading from the source locations (in this case a route) outwards along adjacent streets and squares — for true fire spread models see www.fire.org and Stratton (2004). The same techniques can be applied in public open spaces and even within building complexes such as shopping malls, galleries and airports. This illustrates the ability of DT methods to operate in what might be described as complex friction environments.

Figure 4‑58 Notting Hill Carnival routes

Distance transforms are very flexible in their ability to incorporate problem-specific constraints. For example, in a typical ACS procedure variable slopes are modelled by regarding steeper slopes as higher cost, rather than relating the spreading process to slope directly (other than some uphill/downhill constrained implementations). The route for a road, railway or pipeline is affected by slope, but primarily in the direction of the path rather than the maximum slope of the physical surface.

Figure 4‑59 illustrates the application of a gradient-constrained DT (GCDT) to the selection of road routes through a hilly landscape. The most northerly pair of these routes was constrained to a 1:12 and 1:11 gradient (before engineering grading) whilst the most southerly pair represent routes found using less restrictive 1:9 and 1:8 gradient constraints.

Figure 4‑59 Alternative routes selected by gradient constrained DT

With minor modifications the same procedure has been utilised with a very fine resolution (10metre) DEM to locate pipeline routes for the Hellisheiði 80MW geothermal power station in Iceland by Kristinsson, Jonsson and Jonsdottir (2005). In this case additional constraints were applied giving the maximum and minimum heights permitted for the route and differential directional constraints that permitted limited flow uphill, which is possible for these kinds of two-phase pipelines (Figure 4‑60A,B).

Ratti and Richens (2004) and Ratti, Baker and Steemes (2004) have applied similar ideas to urban landscapes, deriving measures of accessibility, noise diffusion, wind flow and solar factors (shadows, energy, light etc.) from DEMs utilising DTs to determine distances within the built environment as part of LT (lighting and thermal) modelling.