Automatic extraction of flow paths from digital elevation models

Once a raindrop falls on the ground, it flows downward. During this journey, the raindrop joins other raindrops and the mass/volume of the water increases, flowing along creeks, streams, and rivers. This is called the surface flow. The surface flow ranges from trickling surface runoff over hillslopes near watershed boundaries to massive flows of big rivers near estuaries.

Because we know surface water is drawn downward by gravity and so flows toward lower elevations, we can estimate expected flow paths of surface flow from a topographic map. Ideally, the surface water flow paths are perpendicular to elevation contour lines (Figure 1). Using this characteristic, we can estimate where water will be accumulated and hence will form streams. We can also estimate where water will dissipate becoming the watershed divide (Figure 1). In this way, we can draw an expected trajectory of streams only using a topographic map without visiting the site.

This traditional way of estimating flow paths from topographic maps, however, can be time-consuming especially for large areas. Also the task is subjective so flow paths obtained by different people can be different. Since around 1990s, these issues have been resolved by the use of computers. This computer-based procedure to calculate flow paths is called the automatic extraction of flow paths. This has become possible with the introduction of digital elevation models (DEMs).

DEMs are digital versions of conventional topographic maps. While there are different types of DEMs, the most widely used ones are the raster DEMs. Raster DEMs are composed of rectangular cells or raster grids. Each raster grid contains a value of its elevation (Figure 2). One advantage of raster DEMs is their matrix format, i.e., the elevation values are stored in a table-like format (also similar with spreadsheet). This format is actually preferred for most computer softwares. Therefore, raster DEMs can be conveniently used by computers.

Computers can calculate the expected flow paths from given DEMs using the rule that the flow should be in the downward direction. For example, Figure 3 shows how flow direction can be determined based on this rule. Note that there is more than one direction in which the water can flow. In this case, a computer calculates the slope (elevation difference divided by the distance) in each of the directions and determines the flow direction as the steepest one. This simple algorithm is called the D8 method.

In fact, there are other methods proposed for the automatic extraction of flow paths. A problem with the D8 approach is that the representation of flow directions is limited to only eight directions. To resolve this issue, some algorithms divide water flow into multiple directions. One well-known algorithm is called the D∞ implying that it can express an infinite number of flow directions. For example, the flow direction in Figure 3 is determined as North (N) by D8 but the slope toward Northwest (NW) direction is also steep. In this case, D∞ does not determine flow direction specifically as N or NW. Rather, D∞ allocates large portion of flow in the N direction and the rest of flow in the NW direction.

There is another class of methods that can overcome the limitation of the D8 approach. These methods do not divide water flow into multiple directions. They specifically determine flow direction as one of eight directions like D8, but they use more sophisticated rules so that the overall flow paths can be determined in a more reasonable manner. For example, one of those methods, called GD8, determines flow directions using elevation of not only nearby eight cells but also other cells. Figure 4 shows the flow paths calculated by D8 and GD8. This figure shows significant differences in resulting flow paths by two different methods for the same topography. This example provides some idea about the magnitude of errors induced from wrong flow path extraction. As calculated flow paths are very different, further estimation of flow rate, sediment flux, etc. along the wrong flow paths will inevitably carry large errors.

There are other interesting problems in automatic flow path extraction. For instance, if there is a cell whose elevation is lower than any surrounding cells, flow direction cannot be determined for this cell. These cells are called depression cells. While there are real depression cells such as lakes and ponds, when these occur on DEMs they are mostly regarded as errors in DEM production. Because automatic flow path extraction methods cannot calculate directions over depression cells, depression cells should be filled. This task requires an additional algorithm.

Another interesting problem is the case of flat surfaces, i.e., where elevation values of adjacent cells in a DEM are identical and so slopes between nearby cells are calculated as zero. In this case, again, flow direction cannot be calculated with methods explained above. There are some algorithms which have been developed to handle this problem, for example a method called the imposed gradient method.

Automatic extraction of flow paths from DEMs is a very important process in many studies in geomorphology, hydrology, ecology, etc. (literally any study which deals with rivers). As we have seen, there are a number of methods proposed but none of them is perfect. This is an area which attracts continuous interest among scientists and engineers.

• Callow, J. N., K. P. Van Niel, and G. S. Boggs (2007) How does modifying a DEM to reflect known hydrology affect subsequent terrain analysis? J. Hydrol., Vol. 332, pp. 30-39.
• Costa-Cabral, M. C. and S. J. Burges (1994) Digital elevation model networks (DEMON): A model of flow over hillslopes for computation of contributing and dispersal areas, Water Resour. Res., Vol. 30(6), pp. 1681-1692, doi: 10.1029/93WR03512.
• Fairfield, J. and P. Leymarie (1991) Drainage networks from grid digital elevation models, Water Resour. Res., Vol. 27(5), pp. 709-717. (Correction, Water Resour. Res., Vol. 27(10), p. 2809)
• Freeman, T. G. (1991) Calculating catchment area with divergent flow based on a regular grid, Comput. Geosci., Vol. 17(3), pp. 413-422.
• Garbrecht, J. and L. W. Martz (1997) The assignment of drainage direction over flat surfaces in raster digital elevation models, J. Hydrol., Vol. 193, pp. 204-213.
• O'Callaghan, J. F. and D. M. Mark (1984) The extraction of drainage networks from digital elevation data, Computer Vision, Graphics, and Image Processing, Vol. 28, pp. 323-344.
• Paik K. (2008) Global search algorithm for nondispersive flow path extraction. Journal of Geophysical Research, Vol. 113, F04001, doi:10.1029/2007JF000964.
• Paik, K. (2009) Reply to comment by Stefano Orlandini and Giovanni Moretti on "Global search algorithm for nondispersive flow path extraction". Journal of Geophysical Research, Vol. 114, F04005, doi:10.1029/2009JF001351.
• Quinn, P., K. Beven, P. Chevallier, and O. Planchon (1991) The prediction of hillslope flow paths for distributed hydrological modeling using digital terrain models, Hydrol. Process., Vol. 5, pp. 59-80.
• Seibert, J. and B. L. McGlynn (2007) A new triangular multiple flow direction algorithm for computing upslope areas from gridded digital elevation models, Water Resour. Res., Vol. 43, W04501, doi:10.1029/2006WR005128.
• Tarboton, D. G. (1997) A new method for the determination of flow directions and upslope areas in grid digital elevation models, Water Resour. Res., Vol. 33(2), pp. 309-319.