Spatial Reasoning about Flow Directions: de:
riv
Towards an Ontology for River Networks* in
pre
(Extended Abstract) dir
ne
Joäo Argemiro de Carvalho Paivat , Max J. Egenhofer, and Andrew U. Frank à
National Center for Geographic Information and Analysis dir
University of Maine Th
Orono, ME 04469
paiva@thrush.umesve.maine.edu m
(max,frank )Q mecanl.maine.edu IT
Abstract dra
pat
Humans are very good in deriving the flow directions of a river network from such representations are aerial photographs or remotely sensed m
images. Apparently, the 2-dimensional geometry of the network is in most cases sufficient to derive its sources and destinations by reasoning e
about the flow directions of river network, and they need no additional information about slopes or heights. Formalizing the problem such that it
can be automatically performed, however, has proven to be an extremely difficult problem. Within the realm of reasoning about flow directions 25
in river networks, a particularly important problem is the analysis of relevant hydrological features. This paper describes initial results of the
development of an ontology for river networks and formalizes the features in terms of a graph. It is shown how certain reasoning processes, Th:
simplifying the complexity of a river network, can be expressed as graph operations. ma
1 Introduction This paper is part of a larger effort investigating different d
human reasoning mechanisms in geographic space (NCGIA, on
River or drainage networks are fundamental concepts used for 1992). Reasoning in geographic space is typically based on
various analyses in geo-sciences. Geologists, for instance, inference, rather than direct observations (Chase and Chi, Aa
derive original slope and original structure from drainage 1981). Different types of geographic spaces may be B
patterns, or transportation engineers examine river networks to conceptualized such as complete partitions in 2-D as used to 2
determine how to access undeveloped land via waterways. A model such political subdivisions as countries; and networks
common problem in analyzing river networks is that these to represent highway systems (Egenhofer and Herring, 1991; e
studies frequently have to be based on "incomplete" spatial Frank and Mark, 1991). The geographic (large-scale) space efi
information, i.e., information that lacks some clues that are that is made up by a river network is, in a first approximation, RT
crucial for certain decisions. Remotely sensed images or aerial best modeled as a directed graph, in which the flow of the of a
photographs, for example, are data sources that contain only water determines the direction of the edges in the graph. (This Run
the necessary information about the location and extent of model may be too simplistic for some situations such as tidal as
rivers, but unlike in situ observations, they lack explicit changes or human-regulated dams, which may periodically fey
information about the flow direction. While humans have a reverse the flow ofsome channels in ativer network.) eg
distinct ability to derive the flow directions of such a
planimetric representation of a river network, it is a difficult The first quantitative studies of river networks and drainage A d
problem to infer them automatically, basins (Horton, 1945) introduced the idea of ordering channel ne
networks. Further work (Strahler, 1952) simplified the Horton -
Usually, additional information from a digital elevation model ordering scheme, making it purely topological (Melton, 1959). Re
is used to complete the inference of the flow directions Geologists recognized early that the angles at which stream ina
(O'Callaghen and Mark, 1084; Band, 1086; Frank er al, segments join contain crucial information for the inference of
1986). While such an approach may be appropriate for steep the flow directions in drainage networks (see Serres and Roy
terrain with significant elevation differences, it is infeasible in (1990) for a review). Previous work in this area uses remotely
flat terrain. The Amazon region, located in northern Brazil, is sensed images. These images frequently provide only a partial
a prototypical area of the latter type. It extends over 5,000,000 view of a river network. Flow directions have been inferred by
km? with approximately 100 m elevation differences along skelettonizing the water channels and applying a set of
large parts of the Amazon and Solimoes rivers. Current efforts constraint rules about the junctions (angles and channel
in building a geographic information system of this area to lengths) of river channels (Wand et al., 1983; Haralick et al.,
monitor deforestation (Souza, 1992) face the difficulties of 1985). A simplified set of rules uses only on the angle
covering a very large area with no existing maps and many geometry at each junction of three channels and is based on
temporal changes, e.g. due to high-water and erosion the assumption that the two consecutive channels that bound
(Larovere and Goodman, 1992). In order to apply remotely the most acute angle are the upstream channels (Serres and :
sensed images as a means to monitor environmental changes Roy, 1990). Given
in this area, it is necessary to explore alternative approaches to ; orient
derive the flow direction In à river network. Most work on river network topology takes into consideration vertex
the existence of channels and their junctions, while Senex
* Joäo Paiva's work has been supported by the Brazilian National Research disregarding other hydrological features such as lakes, islands, ep
Council (CNPq) under grant number 260226/91.2. Additional support Or river deltas. An exception 1s Marks and Goodchild's (1982) poni
from Intergraph Corporation and NSF for the NCGIA under grant No. SES — extension of Shreve's ( 1966; 1967) "probabilistic-topological is
88-10917 is gratefully acknowledged. model" for channel networks by lakes. This paper develops a ds d
On a leave of absence from the National Institute for Space Research more comprehensive model of features in a river network and CE
(INPE), Image Processing Division, Sáo José dos Campos, SP, Brazil. p
318
