GeoComputation 2000 Paper

Presentation given at the 5th International Conference on GeoComputation, Chatham, UK, September 23-25th, 2000.

Abstract

This paper presents a new method for the identification of surface topology from Digital Elevation Models (DEMs), based on the graph-theoretic approaches originally suggested by Pfaltz (1976) and modified by Wolf (1984). Surface topology is stored as a weighted graph consisting of vertices representing the so-called surface-specific points (peaks, passes and pits) (Fowler and Little, 1979), and edges representing connecting ridges and channels. This form of representation offers several improvements over other surface topological models, such as TINs and drainage networks. Surface networks are amenable to automated generalisation through a process known as homomorphic contraction. This allows a degree of importance to be attached to both point (peak, pit and pass) and line (ridge and channel) features on a surface. The removal of relatively unimportant parts of the network results in the automated readjustment of the remains of the network.

Although weighted surface networks were proposed as a way of storing and manipulating surface topology over two decades ago, to date there has never been a satisfactory method implemented for their automated construction. Previous papers such as those by Pfaltz and Wolf based discussion around manually derived networks from contour representations of surfaces. This paper includes a discussion of some of the computational issues that have previously prevented automated construction of surface networks, and presents a new automated method that may be applied to DEMs. It is based on the use of quadratic models of conic sections to generate the morphometric information about a surface (Wood, 1998). This information is then used iteratively to build up a logically consistent surface network. The results of the process are visualised in 2 and 3 dimensions and the effects of different generalisation criteria on the network are compared. Initial results suggest that this method could provide a new and powerful way of generalising surface models while retaining their most important topological characteristics. Further work is needed in the automated embedding of surface topology back into geometrical representations of surfaces.

A Brief History of Surface Networks

In general terms, a surface network can be defined as set of statements that identify the connections between points on a surface and the nature of the edges that connect them. For the purposes of this paper, a surface is defined as a 2-dimensional continuous function of the form z = f (x,y), where there is exactly 1 value of z for any (x,y) ordered pair.

Maxwell (1870) noted that any such surface represented by contour lines would always possess a number of measurable properties...     Number of summits = number of passes +1     Number of immits = number of bars +1     Immits are connected to bars via watercourses     Summits are connected to passes via watersheds Where summits are local surface maxima, immits are local surface minima (pits), passes represent the low point connecting two summits, and bars the high point connecting two immits.

Later work by Warntz (1966), formalised the definition of point features and the nature of connecting ridges and channels. In particular he combined Maxwell's definition of passes and bars to represent a local point of inflexion where a ridge and channel intersect. Pfaltz (1976) provided a graph theoretic framework for storing such surface topology. He suggested a directed graph structure could be used to store nodes (pits, peaks, passes) and edges (channels and ridges). Traversal and homomorphic contraction (the removal of nodes and the reconnection of 'severed' edges) can be performed on such graph structures allowing surface topology to be analysed and generalised.

Wolf (1984) embedded these 'Pfaltz networks' in a metric framework by attaching spatial coordinates to all vertices, and height differences to all edges. This allowed him to use homomorphic contraction as a basis for intelligent surface generalisation. These and others have suggested networks can be used for partitioning surfaces into 'hills' and 'dales' sub-regions (e.g. Feuchtwanger and Poiker, 1987; Wolf, 1992). The combination of topological point (pit, peak, and pass), line (channel and ridge) and areal (hills and drainage basins) provides potential for hydrological and geomorphometric analysis of terrain surface models. These characteristics can also be used to quantify and understand other statistical surfaces (e.g. population density, Warntz, 1966; Wood et al, 1999).

Implementation Problems

A number of assumptions must be made when constructing well formed surface networks. Traditionally, many of these assumptions have prevented the automated construction of networks from elevation models.

Assumption
Continuous surface z = f(x,y) (slope measurable)

Problem
Must convert discrete DEM cells into continuous functions. Cannot represent true 3-dimensional surface form.

Assumption
Partial derivatives are continuous (curvature measurable).

Problem
Must convert discrete DEM cells into twice-differentiable functions in order to identify local surface extrema (peaks and pits) and points of inflexion (passes). Therefore requires at least 6 sample points from surface in order to estimate continuous function for any local region. Increasing the sample size beyond 6 tends to reduce noise and sensitivity to error at the cost of generalising the surface properties.

Assumption
Local patches represented by vertices must be isolated from one another.

Problem

Surface models contain lakes and plateaux giving rise to ‘adjacent’ pits and peaks. This arrangement of point features cannot be represented in a conventional surface network.

Assumption
Surface is bounded (enclosed by single contour line).

Problem


Most rectangular elevation models are not bounded in this way. Only islands and possibly dissected plateaux likely to be bounded by a meaningful contour. In order to ensure this condition, the surface is assumed to be an isolated island surrounded by a 'universal pit' (sea), or an isolated pit surrounded by a 'universal peak' (plateau).

The result is likely to include a set of incomplete (truncated) drainage basins and hills containing disconnected sub-networks.

Assumption
The number of passes controls the complexity and character of the network.

Problem
Only some passes can be identified morphometricly (local points of inflexion). Others may be too large or too flat to identify. Creating the network based only on morphometric information is not sufficient to build a truly characteristic network.

Assumption
All vertices are connected.

Problem

Cannot model multiple islands as single graph unless they are joined to the same universal pit, or graph structure is changed to accommodate disconnected sub-graphs.

Assumption
All passes are connected to exactly 2 peaks and 2 pits. Edges meeting at a pass alternate between ridge and channel.

Problem
One location may have superimposed features at many scales (e.g. more than 2 channels and ridges may appear to intersect at the same location).

A New Solution: Morphometric Analysis

Most of the problems in identifying and characterising surface shape arise because conventional surface analysis is too dependent on the DEM resolution (Wood, 1998). Analysis based on the comparison of DEM cell with its immediate 8 neighbours is common, but too sensitive to error and sub-pixel variation.

The solution presented here uses the following method (described in Wood, 1996; 1998)...

Network Generation Algorithm: Stage 1 - Morphometric analysis

A New Solution: Topological Analysis

Topological Properties

All surface networks consist of at least one pass. A network of one pass connected to two peaks and two pits is known as an elementary network. The entire network is bounded by global minimum or maximum. Any pits connected to this minimum are considered a single universal pit. Any peaks intersecting bounding maximum considered a single universal peak. Universal features equivalent to projection of the surface onto a sphere. The choice of whether the network is bounded by a universal peak or pit is arbitrary, and has little effect on the internal topology of the network. It is usually more convenient to assume the network is bounded by a pit (surface as an 'island').

For any surface network, it will always be the case that

Pits + peaks - passes = 2

When building more complete networks, topological integrity can be maintained by by joining any univalent nodes to others of the same type if enclosed within the same region. Such nodes will be referred to as strongly connected and represent the same topological feature. This process allows fragmented channels and ridges to be joined (a particularly significant problem in flatter regions and elevation models subject to high frequency error). Strongly connected nodes also allow us to account for incomplete basins that have been truncated by the edge of the surface model. This allows the network to represent lakes and plateaux as well as surfaces without a single bounding contour.

The connected edges defining the network can be used to partition the surface into 'hills and dales'. These sub-regions are bounded by channel and ridge edges respectively.

Network Generation Algorithm: Stage 2a - Identifying Universal Nodes

findUniversalNodes (int uType)
{
  univalentPeaks <- getUnivalentPeaks();
  univalentPits <- getUnivalentPits();

  if (#univalentPeaks = 0) && (#univalentPeaks >0)
    uType = PEAK;
  else
    if (#univalentPeaks = 0) && (#univalentPits > 0)
	uType = PIT;

  if (uType = PIT)
    startNode <- lowest(univalentPits);
  else
    startNode <- highest(univalentPeaks);

  startNode <- UNIVERSAL;

  connectLeftNodes(startNode);
}

To find all universal nodes, choose either to identify universal pits or universal peaks. Find the lowest pit or peak connected to one edge only. Starting at this pit/peak, traverse the network taking the left-hand edge at all junctions. If any univalent nodes of the same type (pit or peak) are found, label them as universal. Continue until traversal passes back to start node.

There is one degenerate case, where the network contains no univalent nodes. In this case, one of the polyvalent nodes must be arbitrarily selected.

Network Generation Algorithm: Stage 2b - Identifying Strongly Connected Nodes

connectLeftNodes (Node startNode)
{
  newNode <- searchLeft(startNode);

  if (newNode = UNIVERSAL)
    return;

  if (isStronglyConnected(startNode,newNode)
    return;

  if (newNode.type = startNode.type)
    if (newNode.valency = 1)
    {
       newNode <- UNIVERSAL;
       stronglyConnect(startNode,newNode);
    }
  else
    stronglyConnect(startNode,newNode);

  connectLeftNodes(newNode);
}

Recursive method that from a given node, will traverse the network, taking the left-most edge at any junction (returned by the method searchLeft()). In order to apply this method, the graph network structure must store the clockwise order of edges meeting at a node.

Network Generation Algorithm: Stage 3 - Correcting Intersecting edges

1. Identify any intersections between ridges and channels that do not occur at passes.

2. Insert new (topological) pass at intersection.

3. Insert new pit at most pit-like location 'downsteam' of new pass, and new peak at most peak-like location 'upridge' of new pass.

This process is required to ensure topological integrity. It is most likely to be required when morphometric passes are found a the top and bottom of an approximately planar slope. The ridge and channel traced up and down this slope may well intersect, breaking the topological consistency of the network. A new pass must be inserted at the intersection, along with an extra pit and peak.

Some Examples

The example network shown to the left is extracted from the Ordnance Survey 50m DEM of part of the Eastern Lake District (Crown Copyright). The area shown is approximately 12km east-west by 10km north-south. The network was constructed by applying morphometric analysis using a kernel size of 650m (13x13 DEM cells). Ridge and channel bifurcations are also shown as blue and yellow discs. These nodes are required in order to traverse the network when looking for strongly connected and universal nodes.

Most of the major river and ridge networks are identified by the process. For example, the so-called "Fairfield Horseshoe" is identified in area (a), both the bounding ridge and enclosed channel. In flat channel areas such as (b) the network is (morphometricly) fragmented, but the pairs of terminating pits are topologically connected maintaining channel continuity. Area (c) shows a ridge that is not identified by the process. This is because no surrounding pass has been identified with an associated pair of ridges. The algorithm presented here could be improved by adding a fourth stage of identifying peaks and adding their connected ridges to the network.

The final example shows how a network can be generalised by applying homomorphic contractions. This allows less significant nodes and edges to be removed, while maintaining the most important features. The criteria used for contraction, which have been investigated by Rana (2000), include length of edge, average slope of edge, height difference between nodes etc. Research is still required in how best to reconstruct a surface from such a contracted network.

Conclusions and Future Developments

Surface Networks are important as they provide a new and more useful (than TINs) topological data structure for representing surfaces. Unlike TINs, edges as well as vertices have an identified meaning.

Previous attempts to construct surface networks have failed because they are either wholly topological (e.g. Wolf) or wholly morphological (e.g. Wood).

There is need for

• Efficient data structures for storing, characterising and processing graphs.


• Further research on the most appropriate rules for contraction.


• Embedding (generalised) topological networks back into surface structure.

References

Cayley, A. (1859). On contour and slope lines. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science. XVIII, pp. 264-268.

Dykes J.A. (1997) cdv: A Flexible Approach to ESDA with Free Demonstration Software, Proceedings 34th Annual Symposium of British Cartographic Society, pp.100-107.

Fowler, R.J., and Little, J.J. (1979) Automatic extraction of irregular network digital terrain models, Computer Graphics 13, pp.199-207.

Maxwell, J.C. (1870). On contour lines and measurements of heights. The London, Edinburgh and Dublin Philosophical Magazine and Journal of Science 40, pp.421-427.

Pfaltz, J. L. (1976) Surface networks. Geographical Analysis 8(1), pp.77-93.

Rana, S. (2000) Experiments on the generalisation and visualisation of surface networks, Proceedings GIRUK 2000, University of York, York, UK, pp.200-209.

Wolf, G.W. (1984). A mathematical model of cartographic generalization. Geo-Processing 2, pp.271-286.

Wolf, G.W. (1989) A practical example of Cartographic Generalisation using Weighted Surface Networks, in Dollinger, F. and Strobl H. (eds.), Angewandte Geographische Informationstechnologie, Department of Geograph y, University of Salzburg, Austria, pp.125-143.

Wolf, G.W. (1991) A FORTRAN subroutine for cartographic generalization, Computers and Geosciences 17(10), pp.1359-1381.

Wood, J.D. (1998) Modelling the continuity of surface form using Digital Elevation Models, in Poiker, T. and Chrisman, N. (eds.) Proceedings, 8th International Symposium on Spatial Data Handling, pp.725-36.

Wood, J.D., Fisher, P.F., Dykes, J.A., Unwin, D.J., and Stynes, K.S. (1999), The use of the landscape metaphor in population mapping, Environment and Planning B: Planning and Design, 26, 281-295.