Source-linked AI summary
Priority-Flood: An Optimal Depression-Filling and Watershed-Labeling Algorithm for Digital Elevation Models
Richard Barnes, Clarence Lehman, David Mulla
TL;DR
Depressions disrupt DEM drainage requirements, motivating efficient preprocessing for increasingly large elevation datasets. The paper develops Priority-Flood, which floods inward from DEM edges using a priority queue and can also support watershed labeling and flow directions. Its improved variation achieved up to 37% faster performance than the generalized algorithm, while matching a six-processor parallel Planchon–Darboux implementation on one processor.
Problem
Depressions and flats prevent DEM cells from having defined drainage paths to the edge, while increasing resolution produces datasets with billions of points that strain existing algorithms.
Method
Priority-Flood floods a DEM inward from its edges, raising lower unresolved neighbors to the lowest elevation that still drains outward.
Results
Up to 37% faster than the generalized Priority-Flood Algorithm, the improved variation outperformed it in all tested cases; one processor matched a six-processor parallel Planchon–Darboux implementation.
Takeaways & Limitations
Priority-Flood supports depression filling on integer or floating-point DEMs and works across grids, meshes, watershed labeling, and flow-direction tasks.
Takeaways & Limitations
Nonzero ǫ requires careful priority ordering, and choosing ǫ too small or too large can respectively fail to change elevations or create mesas.
Abstract
from arXiv · showhide
Depressions (or pits) are low 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 were impermeable, is often necessary in preprocessing DEMs. The depression-filling algorithm presented here---called Priority-Flood---unifies and improves on 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(n lg n) time, respectively. It is shown that by using a plain queue to fill depressions once they have been found, an O(m lg m) 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.
1. Background
DEM-based hydrologic and geomorphic analyses require cells to drain toward the DEM boundary, but depressions and expanding data sizes make this difficult. The paper presents Priority-Flood to address these preprocessing needs by resolving depressions and supporting watershed and flow-direction analysis.
- Motivation: DEM algorithms estimate hydrologic and geomorphic properties but require every cell to have a flow direction leading to the boundary.These requirements are confounded by depressions and flats.
- Problem: Depressions are inwardly draining DEM regions without outlets, arising from natural terrain or collection and processing artifacts.They can be resolved by breaching their walls or filling them.
- Motivation: Increasing DEM resolution has produced gigabyte-scale datasets with billions of points, making legacy equipment and algorithms costly or impractical.The paper therefore motivates improved algorithms for processing these data sources.
- Contribution: The paper presents Priority-Flood as an algorithm that unifies and extends prior work to resolve depressions and support watershed labeling and flow-direction determination.The paper also presents variants for these related terrain-analysis tasks.
- Problem definition: A depression-filled surface must not lower any DEM cell, must provide every cell an ǫ-descending path to the boundary, and must be the lowest surface satisfying those criteria.These criteria define the depression-filling problem for DEM Z and its counterpart W.
2. Alternative Algorithms
Earlier terrain-processing algorithms offered alternatives for filling depressions, directing flow, and labeling watersheds, but differed substantially in complexity and implementation. Priority-Flood is presented as a fast, simple, and versatile alternative to these methods.
- Previous algorithms: Arge et al. describe an O(n log2 n) procedure for watershed labeling, flow directions, and flow accumulation on massive grids when minimizing I/O is necessary.Its explicit data-management overhead places it outside this paper’s scope.
- Previous algorithms: The Planchon–Darboux algorithm floods and drains edge cells, then repeatedly scans the DEM to drain adjacent undrained cells and raise them slightly.It terminates when all cells have been drained.
- Previous algorithms: Planchon–Darboux implementations range from O(n1.5) to O(n1.2) time, with the faster version requiring complex scans, recursive searches, and nested loops.The algorithm can run in fixed memory, but large DEMs make its runtime problematic.
- Previous algorithms: Earlier reported variants include O(n) integer algorithms for filling, flow directions, or accumulation, alongside an O(n2)* integer/float flow-direction and accumulation method.Table 1 records author claims and inferred complexities, with asterisks marking inferred claims.
- Priority-Flood alternative: Priority-Flood is presented as a fast, simple, and versatile alternative to the Planchon–Darboux algorithm.The paper later compares their performance.
3. The Priority-Flood Algorithm
The Priority-Flood Algorithm generalizes earlier flooding and watershed methods into an edge-inward priority-queue procedure that resolves depressions while supporting varied data types and mesh connectivities.
- The Algorithm: Priority-Flood applies to integer or floating-point DEMs and to 4-, 6-, 8-, or n-connected grids, including nonrectangular meshes.Its operation does not depend on the underlying DEM's structure or connectedness.
- History: Earlier work established integer and floating-point Priority-Flood variants, watershed labeling, flow-direction determination, and queue-based treatments of plateaus.The cited studies include O(n) integer methods, O(n log2 n) floating-point methods, and watershed procedures using hierarchical or FIFO queues.
- History: Liu et al.'s claimed O(8n log2 n) complexity is corrected to O(n log2 k), where k is the number of unique elevation levels.The paper attributes the difference to Liu et al.'s sorted dictionary implementation that bins equal elevations.
- The Priority-Flood Algorithm: Priority-Flood floods inward from DEM edges, always processing the lowest-priority cell and then adding its unprocessed neighbors.The priority queue orders cells by increasing elevation, so the lowest queued cell is processed first.
- The Priority-Flood Algorithm: The algorithm raises depression cells to the elevation of the lowest cell guaranteed to drain to the DEM edge.This elevation adjustment is applied as depressions are encountered during queue processing.
- The Algorithm: The algorithm terminates with a depression-filled DEM satisfying the stated criteria, including no digital dams or undrainable depressions.The result follows because the criteria are maintained at each processing step and the priority queue eventually becomes empty.
4. Ordering
Priority-Flood’s ordering behavior depends on whether equal-priority cells retain insertion order. Strict weak ordering suffices for ordinary depression filling with ǫ = 0, but total ordering is preferred for other uses and guarantees.
- Stable queues retain insertion order, whereas strict weak ordering allows equal-priority elements to emerge in any order.
- For depression filling with ǫ = 0, either queue ordering produces the same results.
- For ǫ ≠ 0, watershed labeling, or direct flow-direction determination, total ordering is the best choice.
- Total ordering provides predictable, reproducible results and guarantees least-cost paths to flooding sources when ǫ ≠ 0.Equal-elevation outlets can therefore support drainage from multiple outlets; strict weak ordering cannot provide these guarantees.
- A secondary insertion counter converts strict weak ordering into total ordering by breaking ties between equal-elevation cells.The two priorities are elevation and an integer incremented whenever a cell enters the queue.
5. Analysis
Priority-Flood progressively floods a DEM using a priority queue, with specialized queue management improving floating-point complexity and runtime. Its guarantees and complexity are largely independent of depression distribution and connectedness.
- Priority-Flood initializes a priority queue with seed cells and progressively floods neighboring cells from the highest-priority cell.The improved variant uses a specialized priority queue.
- Integer DEMs achieve O(n) time because the priority queue operates in O(1) time.This is optimal for integer data.
- Floating-point DEMs generally require O(log2 n) queue operations, giving Priority-Flood O(n log2 n) time, reducible to O(n log2 k) with mapped queues.
- Priority-queue choices involve hidden overheads, with implicit heaps favoring low memory and speed while hierarchical heaps and ladder queues favor very large datasets at higher memory cost.The latter queues operated faster for datasets greater than 10^6 elements.
- O(m log2 m), where m ≤ n, is achieved for floating-point DEMs by the improved Priority-Flood regardless of the underlying priority-queue algorithm.The improvement may also reduce integer-data runtime by avoiding priority-queue maintenance overhead.
- Depression distribution and connectedness do not affect the time complexities of Priority-Flood variants.
6. Empirical Testing
Empirical tests compared improved Priority-Flood with its unimproved version and with a parallel Planchon–Darboux implementation on large Minnesota DEMs. The improved algorithm matched or exceeded the older method using fewer processors.
- The improved and unimproved Priority-Flood implementations were tested on floating-point 3 m DEMs from 44 Minnesota counties covering approximately 72,500 km2.The experiments used a 64-bit Intel Xeon X5560 processor and 24 GB of RAM.
- The Planchon–Darboux comparison used varying processor counts, while improved Priority-Flood ran on one processor.The parallel implementation was tested on two representative county-sized sites.
- Six processors let parallel Planchon–Darboux match one-processor improved Priority-Flood on Test Site A; Test Site B required 11 processors.The sites contained 35% and 61% depressions, respectively.
7. Variants
The paper extends Priority-Flood to resolve flat surfaces, determine flow directions, and label watersheds. These variants use either minimal elevation increments, direct flow-direction assignment, or outlet-based labeling.
- Automatic Flat Resolution: A total-ordered priority queue lets Priority-Flood+ε treat equal-elevation boundary cells consistently and drain depressions through multiple outlets.The ordering is required for the algorithm’s handling of equal elevations and multiple outlets.
- Automatic Flat Resolution: Priority-Flood+ε fills depressions with ε-descending paths so consecutive cells differ in elevation by at least ε.The variant uses NextAfter to minimize DEM disruption and raises a warning when the alteration cannot be minimized.
- Automatic Flat Resolution: Choosing ε is difficult: values that are too small may leave elevations unchanged, while values that are too large may turn depressions into mesas.NextAfter avoids an arbitrarily defined increment, but correctness is not guaranteed when DEM precision approaches the storage type’s precision.
- Flow Directions: Priority-Flood+FlowDirs assigns directions without altering elevations by directing each cell toward the lowest processed neighbor, effectively carving depression walls.The method climbs into depressions through their lowest outlet and follows steepest descent toward their minima.
- Flow Directions: Flow directions from the carving variant produce flow-accumulation regions closer to actual rivers than directions determined after depression-filling.This comparison is attributed to results reported by Metz et al.
- Watershed Labeling: Watershed labeling floods inward from DEM edges, prioritizes cells to outlet levels, and propagates unique outlet labels through each watershed.Boundaries are identified where adjacent cells have differing labels; either the lower-label cell, higher-label cell, or both can mark the border.
8. Coda
Priority-Flood is generalized to support multiple data types and mesh connectivities, while its improved variant accelerates depression filling. The algorithm also supports watershed labeling and flow-direction determination, with concise implementations and available software.
- The algorithm generalizes Priority-Flood to integer and floating-point data, irregular meshes, and 4-, 6-, 8-, or n-connected grids.
- The improved variant uses a plain queue to speed depression filling after depressions are found.
- 37% faster performance was achieved in testing compared with the generalized Priority-Flood Algorithm, while matching it retained the stated complexity bounds.
- The method guarantees draining filled depressions, uses 20 lines of pseudocode, and has a C++ implementation under a hundred lines.
- Priority-Flood can label watersheds and determine flow directions through terrain increments or depression carving.
- Implementations and algorithms are available through the paper’s Supplemental Materials and the RichDEM analysis package.