Elsevier

Computers & Geosciences

Volume 62, January 2014, Pages 117-127
Computers & Geosciences

Priority-flood: An optimal depression-filling and watershed-labeling algorithm for digital elevation models

https://doi.org/10.1016/j.cageo.2013.04.024Get rights and content

Highlights

  • We present an algorithm to fill landscape depressions during DEM analysis.

  • Variants of the algorithm label watersheds and determine flow directions.

  • The algorithm and its variants combine over three decades of related work.

  • A new variant with the lowest time complexity of any such algorithm is presented.

  • Speed comparisons and implementation details are discussed.

Abstract

Depressions (or pits) are areas within a digital elevation model that are surrounded by higher terrain, with no outlet to lower areas. Filling them so they are level, as fluid would fill them if the terrain was impermeable, is often necessary in preprocessing DEMs. The depression-filling algorithm presented here – called Priority-Flood – unifies and improves the work of a number of previous authors who have published similar algorithms. The algorithm operates by flooding DEMs inwards from their edges using a priority queue to determine the next cell to be flooded. The resultant DEM has no depressions or digital dams: every cell is guaranteed to drain. The algorithm is optimal for both integer and floating-point data, working in O(n) and O(nlog2n) time, respectively. It is shown that by using a plain queue to fill depressions once they have been found, an O(mlog2m) time-complexity can be achieved, where m does not exceed the number of cells n. This is the lowest time complexity of any known floating-point depression-filling algorithm. In testing, this improved variation of the algorithm performed up to 37% faster than the original. Additionally, a parallel version of an older, but widely used, depression-filling algorithm required six parallel processors to achieve a run-time on par with what the newer algorithm's improved variation took on a single processor. The Priority-Flood Algorithm is simple to understand and implement: the included pseudocode is only 20 lines and the included C++ reference implementation is under a hundred lines. The algorithm can work on irregular meshes as well as 4-, 6-, 8-, and n-connected grids. It can also be adapted to label watersheds and determine flow directions through either incremental elevation changes or depression carving. In the case of incremental elevation changes, the algorithm includes safety checks not present in prior works.

Section snippets

Background

A digital elevation model (DEM) is a representation of terrain elevations above some common base level, usually stored as a rectangular array of floating-point or integer values. DEMs may be used to estimate a region's hydrologic and geomorphic properties, including soil moisture, terrain stability, erosive potential, rainfall retention, and stream power. Many algorithms for extracting these properties require (1) that every cell within a DEM must have a defined flow direction and (2) that by

Alternative algorithms

Arge et al. (2003) describes a specialized O(nlog2n) procedure to perform watershed labeling, determine flow directions, and calculate flow accumulation on massive grids in situations where I/O must be minimized. Although parts of this procedure share sufficient similarities with Priority-Flood to be considered related, the combinations of algorithms used and the way in which they are specialized place it outside the scope of this paper. It is expected that the algorithm by Arge will run slower

History

In its most general form, the Priority-Flood Algorithm works by inserting the edge cells of a DEM into a priority-queue where they are ordered by increasing elevation. The cell with the lowest elevation is popped from the queue and manipulated. Following this, each neighbor which has not already been considered by the algorithm is manipulated and then added to the priority queue. The algorithm continues until the priority queue is empty.

The Priority-Flood Algorithm may be applied to either

Ordering

A subtlety of priority queues concerns how elements of equal priority are treated. If elements of equal priority retain their order of insertion, then the priority queue may be said to be “stable” or to have a “total order”. If elements of equal priority do not retain their order of insertion, then the priority queue has a “strict weak ordering”: elements of equal priority are incomparable and may therefore be arranged in any order.

Fortunately, for depression filling with ϵ=0, it does not

Analysis

The essence of the Priority-Flood Algorithm is that a priority queue is initialized with some number of seed cells. The DEM is then progressively flooded by repeatedly pushing the neighbors of the highest priority cell into the priority queue. The improved Priority-Flood uses, in essence, a specialized priority queue.

As Table 2 shows, there are many possible ways to manage a priority queue—and the list here is by no means exhaustive, Knuth (1998) discusses many others in addition to presenting

Empirical testing

An implementation of the improved Priority-Flood was tested against an implementation of the unimproved Priority-Flood; both implementations are included in the Supplemental Materials. The C++ STL priority queue was chosen to simplify programming and the tests were conducted on floating-point DEMs using a 64-bit Intel Xeon X5560 2.8 GHz 8192 kB cache processor and 24 GB of RAM. The results are shown in Fig. 3. LIDAR-based 3 m DEMs of 44 counties in Minnesota were tested, comprising an area of

Automatic flat resolution

Priority-Flood, as it has been described above, will produce mathematically flat surfaces as a by-product of filling depressions. Such surfaces confound attempts to determine flow directions and derivative hydrologic properties. A feature of the Planchon–Darboux Algorithm is that it does not suffer this problem because it produces surfaces for which each cell has a defined gradient from which flow directions can be determined.

As Algorithm 3 demonstrates, Priority-Flood can be adapted to provide

Coda

Special cases and variants of the Priority-Flood Algorithm have been described by many authors. This paper generalizes this body of literature (Algorithm 1) to work optimally on either integer or floating-point data (Section 5), as well as on irregular meshes or 4-, 6-, 8-, or n-connected grids.

An improvement to the Priority-Flood priority queue (Algorithm 2) has been described and tested. It runs in O(mlog2m) time, where mn, on floating-point data and in O(n) time on integer data. By

Acknowledgments

Funding for this work was provided by the Minnesota Environment and Natural Resources Trust Fund under the recommendation and oversight of the Legislative-Citizen Commission on Minnesota Resources (LCCMR). David Mulla was the P.I. on this grant. Supercomputing time and data storage were provided by the Minnesota Supercomputing Institute. Adam Clark provided feedback on the paper; Joel Nelson provided LIDAR DEMs and ArcGIS support. In-kind support was provided by Earth Dance Farm, Tess

References (40)

  • R. Brown

    Calendar queuesa fast 0(1) priority queue implementation for the simulation event set problem

    Communications of the ACM

    (1988)
  • S. Edelkamp et al.

    Heuristic SearchTheory and Applications

    (2011)
  • Ehlschlaeger, C., 1989. Using the at search algorithm to develop hydrologic models from digital elevation data. In:...
  • R. Goh et al.

    MlistAn efficient pending event set structure for discrete event simulation

    International Journal of Simulation-Systems Science and Technology

    (2003)
  • Goh, R., Thng, I., 2004. Dsplay: An efficient dynamic priority queue structure for discrete event simulation. In:...
  • Gomes, T.L., Magalhães, S.V.G., Andrade, M.V.A., Franklin, W.R., Pena, G.C., 2012. Computing the drainage network on...
  • T. Hui et al.

    FeltA far future event list structure optimized for calendar queues

    Simulation

    (2002)
  • S. Jenson et al.

    Extracting topographic structure from digital elevation data for geographic information system analysis

    Photogrammetric Engineering and Remote Sensing

    (1988)
  • Knuth, D.E., May 1998. Sorting and searching. In: Art of Computer Programming, 2nd edition, vol. 3, Addison-Wesley...
  • J. Lindsay et al.

    Removal of artifact depressions from digital elevation modelstowards a minimum impact approach

    Hydrological Processes

    (2005)
  • Cited by (174)

    View all citing articles on Scopus
    View full text