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.