The TerraWatershed Project

The most important process that can be performed based on flow direction and flow accumulation is the delineation of the terrain into watersheds. In TerraFlow we defined a watershed to be a sink in the terrain together with the part of the terrain that routes flow to that sink. Computing all the sinks in the terrain and their watersheds gives a unique partitioning of the terrain into watersheds.

In general a watershed is a region or area bounded peripherally by a divide and draining ultimately to a particular watercourse or body of water. More formally, a watershed is defined relative to an outlet point. Given any point x in the terrain, the watershed of x is the part of the terrain that flows (has a flow path) to x. The point x is called the outlet of the watershed. With this definition of watershed, the problem is how to select the outlet points in the terrain such that the union of their watersheds defines a (realistic) partition. Watersheds are viewed as basic units of the landscape having homogeneous features, and many processes can be modeled by simulating the interaction of watersheds.

In practice watersheds are delineated using the stream network of the terrain. The stream network (or river network) is a set of directed river trees. The root of a river tree is called the outlet node (the farthest point downstream). The node set is composed of stream sources (the leaves of the river tree, i.e. the farthest points upstream) and stream junctions (the interior nodes of the river tree, i.e. points where two upstream channels join to form one downstream channel). The edge set consists of interior and exterior links: exterior links are segments of channels between a source and the first junction downstream, while interior links are segments of channels between two successive junctions. Given the river network, a watershed partitioning can be obtained by computing the watershed of each link.

The most commonly-used method to compute the stream network is based on flow accumulation: the stream network can be defined as the set of all the cells in the terrain with flow accumulation value larger than a user-defined threshold k. Every threshold value k determines a particular stream network S_k and a corresponding watershed delineation W_k of the terrain: the larger this threshold, the smaller the stream network (fewer streams), the larger the streams segments, and the larger and fewer the watersheds. The threshold k is thus a knob that the user can turn to decide the scale (resolution) of the stream network and watersheds. In practice the determination of the threshold is an interactive process, where the user tries several values until obtaining the desired resolution.

Using the same techniques as in TerraFlow, we can compute, for a given k, the corresponding stream network S_k and the watershed partitioning W_k in scanning bound. Note that the values of flow accumulation are strictly increasing on any leaf-to-root path in a river tree S_k (the sources have the lowest value, the outlet has the highest value). It can be shown that increasing the value of the threshold k to a value l > k has the effect of removing leaf subtrees in S_k, which in turn correspond to merging the watersheds corresponding to these leaves. Some watersheds in W_l may be the same as in W_k, while others will be the union of watersheds in W_k. Thus for different values of k, the watershed partitioning defines a hierarchy.

An interesting problem is the computation of the complete watershed hierarchy of a terrain (for all relevant values of k). If the hierarchy is known, one could potentially use this information in an appropriate data structure in order to compute more efficiently S_k and W_k for given k. Another application is maintaining the current S_k and W_k dynamically in order to be able to switch to higher or lower values of k without re-computing from scratch. Pre-computing the watershed hierarchy (and all relevant information) and storing it efficiently may enable efficient solutions to other type of queries; for instance queries of the type ``given s, find k, S_k and W_k such that no watershed is larger than x cells''; or, ``find a river network S_k such that there are no more than x exterior links''.

Another problem is considering an alternative definition of the watershed hierarchy using multiple flow directions. Watershed partitioning has been studied only in the context of SFD flow directions. If more than one flow directions are allowed, the river network defined by these flow directions is no longer a set of trees, but a set of directed acyclic graphs. In TerraFlow we showed how to generalize the algorithms for computing flow directions and flow accumulation to handle MFD. The resulting algorithms are more complicated, but the practical results of MFD versus SFD are significantly better.

Implementation coming soon. Stay tuned.


<laura@cs.duke.edu>
Last modified: Fri Jun 27 11:38:08 2003 by laura.