Table 4‑10 3x3 Chamfer metrics

 

A selection of 3x3 masks is shown in Table 4‑10. These are known as chamfer metrics because the locus of the metric generates a figure similar to a cross-section of a piece of wood with chamfered or beveled edges. The generic form of such masks is defined by the two unique mask values (a,b), e.g. (2,1) or (3,4). The maximum error percentages shown in Table 4‑10 provide the global maximum errors for the metric as compared with global Euclidean measure. The use of 3x3 local metrics is fast and simple, but results in directional bias in the resulting DT. These show the familiar 4- or 8-direction patterns seen in many GIS processes that rely on 3x3 neighborhoods (see, for example, Figure 4‑34).

This problem can be considerably reduced by extending the neighborhood to a 5x5 mask (M=5), in which case 3 values define the mask: (a,b,c) as shown in Figure 4‑64. Amongst the best integer values for this mask size are the triple (5,7,11), dividing all cell values by 5 at the end to give (1,1.4,2.2). The best fractional values are (0.9866, 1.4141, 2.2062). Use of the integer values above ensures that every grid cell distance computed (i.e. global values) is within 2% of the exact Euclidean distance and within 1.36% for the fractional masks. This compares with global errors of up to 7.6% with a pure local Euclidean metric.

Figure 4‑64 5x5 DT mask

Figure 4‑65A provides the simplest test case for the DT procedure. This shows a uniform region with a single target point in the center (originally coded as 0, with all other grid cells coded 999). This figure shows the best non-exact DT possible using a fractional-valued 5x5 scanning template. The exact Euclidean distance transform (EDT) of this uniform space yields a perfectly circular set of filled contours around the central point. The vector equivalent would be a multi-ring buffer operation. When applied to multiple points (e.g. as part of a point-pattern analysis exercise) the set of computed distances, F(), is known as the empty space function.

If a simple barrier is introduced, e.g. representing a river with a bridge point, shortest paths appear diffracted through the gap (Figure 4‑65B). In this example the target point has been set as (2,50). With a complex barrier, as in Figure 4‑65C, a single extra iteration has been used to ensure full convergence. In all cases shortest paths to target points can be drawn as orthogonal to the distance bands, but are best constructed using tracking of the selected steps, as described further in the examples below. Although the DT approach may seem somewhat divorced from practical GIS analysis, DT procedures have been extended and developed by: Ratti et al. (architecture and the built environment; 2001, 2004); de Smith (transport routes; 2004, 2006), Ikonen and Toivanen (image processing; 2005); and Kristinsson et al. (geothermal pipelines, 2005) to provide a new and fast family of ACS-like procedures for solving many grid-related distance problems.

Figure 4‑65 Distance transform, single point

A. 5x5 DT, no constraints, target (50,50)

B. 5x5 DT, barrier – target (2,50)

C. 5x5 DT, complex obstacle – target (50,90)

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, pp 15-16 and 159) for a full discussion of the models involved. The second example examines pedestrian movement within urban areas, whilst the third set of examples address questions of optimal road and pipeline location under a range of constraints.

Figure 4‑66 shows the result of applying a least ‘cost’ distance transform (LCDT) to a city with traffic speeds symmetrically varying from almost 0kph in the center (where the crossed lines meet) to much higher levels (e.g. 50kph+) at the city edge. The cost field in this case is traffic speed (i.e. a velocity field) and the curved lines show contours of equal travel time (isochrones) to or from a point due South of the city center.

Figure 4‑66 Urban traffic modeling

The central function in the DT procedure in this instance is of the form:

d0 = min{d+D(i)*COST(r,c), d0}

where d0 is the current value at the central point (0) of the mask, D(i) is the local distance to the i^th element of the mask, d is the current value at (r,c) and COST(r,c) is the (averaged) cost function at row r, column c. As can be seen, the velocity field distorts the distance bands. Shortest (quickest) 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 tracking of the computed quickest paths. Hence the quickest route from the start point due South of the center to locations North of the city center would curve around (East or West) the center to avoid congestion (low traffic speeds. In this particular example these curve form log spirals (Wardrop, 1969).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.

A second example of this procedure is shown in Figure 4‑67. This shows a section of the Notting Hill area of central London, with the annual Carnival route shown in white and areas in dark gray being masked out (buildings etc.). Colors indicate increasing distances (in meters) from the Carnival route along nearby streets.

Figure 4‑67 Notting Hill Carnival routes

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.

Distance transforms are very flexible in their ability to incorporate problem-specific constraints. For example, in a typical ACS procedure variable slopes are modeled by regarding steeper slopes as higher cost, rather than relating the spreading process to slope directly (other than some uphill/downhill constrained implementations). The selection of a 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 (although this does have a bearing on construction cost).

Figure 4‑68 Alternative routes selected by gradient constrained DT

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

With minor modifications the GCDT procedure described above has been utilized with a high resolution (10meter) DEM to locate alternative pipeline routes for the Hellisheiði 80MW geothermal power station in Iceland (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‑69A,B).

Figure 4‑69 Hellisheiði power plant pipeline route selection