Priority-flood: An optimal depression-filling and watershed-labeling algorithm for digital elevation models
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 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 , 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 time, where , 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)
Revisiting priority queues for image analysis
Pattern Recognition
(2010)Topographic distance and watershed lines
Signal Processing
(1994)- et al.
The extraction of drainage networks from digital elevation data
Computer Vision, Graphics, and Image Processing
(1984) - et al.
A fast, simple and versatile algorithm to fill the depressions of digital elevation models
Catena
(2002) - et al.
An efficient algorithm for drainage network extraction on DEMs
Journal of Visual Communication and Image Representation
(1994) - et al.
O(n) implementation of the fast marching algorithm
Journal of Computational Physics
(2006) - et al.
Efficient flow computation on massive grid terrain datasets
GeoInformatica
(2003) - et al.
An efficient assignment of drainage direction over flat surfaces in raster digital elevation models
Computers and Geosciences
(2013) - Beucher, N., Beucher, S., April 2011. Hierarchical queues: general description and implementation in mamba image...
- et al.
The morphological approach to segmentationthe watershed transformation
Optical Engineering
(1992)
Calendar queuesa fast 0(1) priority queue implementation for the simulation event set problem
Communications of the ACM
Heuristic SearchTheory and Applications
MlistAn efficient pending event set structure for discrete event simulation
International Journal of Simulation-Systems Science and Technology
FeltA far future event list structure optimized for calendar queues
Simulation
Extracting topographic structure from digital elevation data for geographic information system analysis
Photogrammetric Engineering and Remote Sensing
Removal of artifact depressions from digital elevation modelstowards a minimum impact approach
Hydrological Processes
Cited by (174)
Multiple equidistant belt technique for width function estimation through a two-segmented-distance strategy
2024, Environmental Modelling and SoftwareAn open-source GIS preprocessing tool for the ParFlow hydrological model (PFGIS-Tool v1.0.0)
2023, Environmental Modelling and SoftwareA parallel Python-based tool for meshing watershed rivers at continental scale
2023, Environmental Modelling and Software