GeoComputation 2000 HomeConference ProgrammeAlphabetical List of AuthorsPaper

Efficient Generalisation and Abstraction of Network Data Using Perceptual Grouping

1 Prologic Systems Ltd.
2 National Atlas of Canada, Canada

Key words: Network Analysis, Abstraction, Generalisation, Perceptual Organisation, Cartography

Spatial data generalisation or abstraction is a vital computational procedure in data presentation (notably in cartography) and in data integration. This paper considers the particular difficulties of the generalisation of road and river networks, outlining the approach developed at Canada Centre for Remote Sensing (CCRS) which exploits the principles of perceptual organisation (or grouping). Perceptual grouping principles present a powerful set of analysis tools for spatial data, with applications in various fields. They are key to the human understanding of images and hence can direct us to the crucial aspects of spatial analysis.

By means of the perceptual grouping principle of 'good continuation,' the network can be analysed (i.e., broken down) into linear elements, which are non-branching chains of arcs. We term these linear elements "strokes;" this term is prompted by the idea of a curvilinear segment that can be drawn in one smooth movement and without a dramatic change in style. Unlike arcs, strokes may in theory contain any positive number of nodes, and may intersect each other or themselves. Unlike the "axial lines" proposed by Mackaness (1995) for use in urban road generalisation, they are computationally simple to derive, and can be applied in both road and river network analysis.

In the case of hydrologic networks, the established method of generalisation on the basis of stream orders can be viewed as a special instance of this more general approach. Furthermore, the stroke-building algorithm is both robust enough to operate on incomplete or erroneous data, and can be easily constrained using additional information.

Further analysis allows the derived strokes to be ordered, to reflect their relative importance in the network. The deletion of the elements according to this sequence then provides a simple and effective method of generalising (attenuating) the network. We also note that when two sub-strokes are combined into a new stroke the attributes of the resulting stroke can be easily obtained from those of the component sub-strokes. This allows the analysis of a network to be derived from the analysis of component pieces - with concomitant advantages in efficiency and storage.

This perception-based approach to network generalisation has been implemented and evaluated at CCRS. The implementation is outlined, results presented, and the effectiveness of the techniques demonstrated on both road and river networks. The technique has been used to do the hydrology selection for a map covering Canada's three northern territories.