An efficient and comprehensive method for drainage network extraction from DEM with billions of pixels using a size-balanced binary search tree

• We present a drainage network extraction method with O(NlogN) complexity.
• We use a size-balanced binary search tree to speed up the depression-filling.
• The vectors and parameters of channels and hillslopes are obtained after six steps.
• This method can process both global and LiDAR DEMs at billion-pixel scales.
• Extracting the whole Amazon River basin from 30-m ASTER GDEM requires only 14 h.

With the increasing resolution of digital elevation models (DEMs), computational efficiency problems have been encountered when extracting the drainage network of a large river basin at billion-pixel scales. The efficiency of the most time-consuming depression-filling pretreatment has been improved by using the O(NlogN) complexity least-cost path search method, but the complete extraction steps following this method have not been proposed and tested. In this paper, an improved O(NlogN) algorithm was proposed by introducing a size-balanced binary search tree (BST) to improve the efficiency of the depression-filling pretreatment further. The following extraction steps, including the flow direction determination and the upslope area accumulation, were also redesigned to benefit from this improvement. Therefore, an efficient and comprehensive method was developed. The method was tested to extract drainage networks of 31 river basins with areas greater than 500,000 km2 from the 30-m-resolution ASTER GDEM and two sub-basins with areas of approximately 1000 km2 from the 1-m-resolution airborne LiDAR DEM. Complete drainage networks with both vector features and topographic parameters were obtained with time consumptions in O(NlogN) complexity. The results indicate that the developed method can be used to extract entire drainage networks from DEMs with billions of pixels with high efficiency.