A HADOOP-BASED ALGORITHM OF GENERATING DEM GRID FROM POINT CLOUD DATA

Xun Jian, X. Xiao, H. Chengfang, Zhizhong Zeng, Zhaohui Wu, Z. Dengzhong2015 · DOI

Abstract

Airborne LiDAR technology has proven to be a powerful tool for obtaining high-density, high-accuracy surface information. However, processing the resulting massive point cloud data to generate high-quality Digital Elevation Models (DEMs) requires significant time and computing resources. This paper explores the use of Apache Hadoop, a distributed system infrastructure featuring the Hadoop Distributed File System (HDFS) and the MapReduce parallel programming model, to improve the efficiency of DEM generation. Using point cloud data from Dongting Lake, China (approximately 311.6 million points), the researchers implemented a Hadoop-based algorithm and compared its performance against a traditional sequential C++ implementation. The results indicate that while non-Hadoop implementations perform well when memory is sufficient, the Hadoop-based approach offers a superior performance-cost ratio and better stability when handling vast quantities of data.

Introduction

Airborne LiDAR (Light Detection and Ranging) is the gold standard for mapping terrain, capable of capturing millions of data points per second. However, this high density is a double-edged sword: the resulting "point clouds" are often so massive that traditional single-machine algorithms struggle to process them. Generating a Digital Elevation Model (DEM)—a 3D grid representing the earth's surface—requires filtering out non-terrain objects and interpolating millions of points into a regular grid. On standard workstations, this process often hits memory limits and becomes agonizingly slow. The authors sought to leverage Hadoop's distributed framework to make mass DEM production faster and more economical.

Methodology

The researchers developed a workflow that transitions from standard sequential processing to a distributed MapReduce model. The process involves three main stages: data pre-processing (converting raw files to LAS format), terrain filtering (separating ground points), and the core innovation: parallelized interpolation.

The MapReduce Approach

The interpolation step, using the Inverse Distance Weighted (IDW) method, was parallelized to handle massive point sets across a cluster:

MapReduce workflow for DEM interpolation
  • Map Phase: Each LiDAR point is treated as an input. The "Mapper" determines which grid cell the point belongs to and calculates its distance to the center of that cell.
  • Reduce Phase: The "Reducer" collects all points assigned to a specific grid cell and calculates the final elevation (Z-value) for that cell based on the weighted average of the surrounding points.

Experimental Results

The study utilized a real-world dataset from the Gong Shuangcha flood diversion area in Dongting Lake, China, consisting of 311.6 million points (5.80 GB). The algorithm's efficiency was tested on Dell PowerEdge R430 servers in various configurations.

Comparison of processing time between Hadoop and non-Hadoop implementations

As shown in the performance data, processing time increases linearly with the number of points. A key finding was the scalability trade-off: while a highly optimized C++ program can be faster than Hadoop when data fits entirely within a machine's RAM, Hadoop becomes the superior choice as data volume scales beyond the capacity of a single computer. Furthermore, the Hadoop approach demonstrated a higher performance-cost ratio by allowing organizations to combine affordable commodity hardware into a powerful resource pool.

Conclusion

The Hadoop-based algorithm effectively addresses the memory and processing bottlenecks associated with massive LiDAR datasets. While network I/O overhead can impact performance on smaller tasks, the distributed approach is more stable and economical for large-scale geospatial tasks. Future work will focus on parallelizing the initial terrain filtering phase and optimizing network bandwidth to further enhance efficiency in complex topographies.

Summary updated

Abstract

Airborne LiDAR technology has proven to be the most powerful tools to obtain high-density, high-accuracy and significantly detailed surface information of terrain and surface objects within a short time, and from which the Digital Elevation Model of high quality can be extracted. Point cloud data generated from the pre-processed data should be classified by segmentation algorithms, so as to differ the terrain points from disorganized points, then followed by a procedure of interpolating the selected points to turn points into DEM data. The whole procedure takes a long time and huge computing resource due to high-density, that is concentrated on by a number of researches. Hadoop is a distributed system infrastructure developed by the Apache Foundation, which contains a highly fault-tolerant distributed file system (HDFS) with high transmission rate and a parallel programming model (Map/Reduce). Such a framework is appropriate for DEM generation algorithms to improve efficiency. Point cloud data of Dongting Lake acquired by Riegl LMS-Q680i laser scanner was utilized as the original data to generate DEM by a Hadoop-based algorithms implemented in Linux, then followed by another traditional procedure programmed by C++ as the comparative experiment. Then the algorithm’s efficiency, coding complexity, and performance-cost ratio were discussed for the comparison. The results demonstrate that the algorithm's speed depends on size of point set and density of DEM grid, and the non-Hadoop implementation can achieve a high performance when memory is big enough, but the multiple Hadoop implementation can achieve a higher performance-cost ratio, while point set is of vast quantities on the other hand.
BibTeX
@inproceedings{jian2015hadoop,
  author = {Xun Jian and X. Xiao and H. Chengfang and Zhizhong Zeng and Zhaohui Wu and Z. Dengzhong},
  title = {{A HADOOP-BASED ALGORITHM OF GENERATING DEM GRID FROM POINT CLOUD DATA}},
  booktitle = {˜The},
  year = {2015},
  doi = {10.5194/isprsarchives-xl-7-w3-1209-2015},
}
Figure