Journal of Geo-information Science >
Parallel Algorithm of Generating DEM from LiDAR Point Clouds Based on Dynamic Load Balancing Strategy
Received date: 2014-12-10
Revised date: 2015-01-09
Online published: 2015-05-10
With the development of high performance computing, parallel processing has been widely used in analyzing LiDAR point clouds. Aiming at the loading unbalancing problem that exists in current parallel algorithms for generating DEM from LiDAR point clouds, this research implements a parallel algorithm which uses dynamic load balancing strategy to generate DEM from massive LiDAR points. The parallel algorithm is based on the master- slave scheduling strategy. The master processor adaptively partitions LiDAR data and generates several strips afterwards. The data strip may be horizontal or vertical based on the characteristic of LiDAR data. The slave processors generate raster DEM from discrete LiDAR points using spatial interpolation. Furthermore, we propose a dynamic scheduling strategy based on the quantity of tasks. The quantity of each task is measured by the number of points in data strip. Firstly, all processors count the point number for all data strips and the master processor creates a task queue. The task queue is arranged according to the point number of those data strips in a descending order from the largest to the smallest. Secondly, the master processor communicates with the slave processors to distribute these tasks dynamically, thus to help the slave processors achieve the load balancing. In this way, all of the data strips are processed from the largest to the smallest based on the computational complexity. Finally, we test the proposed parallel algorithm in a cluster. The cluster is composed of 24 cores. The volume of the LiDAR point clouds for testing is 30 GB, which contains about 1.2 billion points. The resolution of the target DEM is 1 meter, and the biggest speedup ratio of the parallel algorithm is 15.16. At the same time, we compare the dynamic scheduling strategy proposed in this paper with the static scheduling strategy. The result shows that the dynamic scheduling strategy proposed in this research achieves a better load balancing among all processors. Therefore, we can come to a conclusion that the parallel algorithm proposed in this research can significantly improve the efficiency of generating DEM from massive LiDAR point clouds.
Key words： dynamic load balancing; LiDAR; DEM; parallel computation
REN Yibin, CHEN Zhenjie, CHENG Liang, LI Manchun, PIAN Yuzhe . Parallel Algorithm of Generating DEM from LiDAR Point Clouds Based on Dynamic Load Balancing Strategy[J]. Journal of Geo-information Science, 2015 , 17(5) : 531 -537 . DOI: 10.3724/SP.J.1047.2015.00531
[1] Lloyd C D, Atkinson P M. Deriving ground surface digital elevation models from LiDAR data with geostatistics[J]. International Journal of Geographical Information Science, 2006,20(5):535-563.
[2] White S A, Wang Y. Utilizing DEMs derived from LIDAR data to analyze morphologic change in the North Carolina coastline[J]. Remote sensing of environment, 2003,85(1):39-47.
[3] Ma R. DEM generation and building detection from lidar data[J]. Photogrammetric Engineering & Remote Sensing, 2005,71(7):847-854.
[4] Hu X, Li X, Zhang Y. Fast filtering of LiDAR point cloud in urban areas based on scan line segmentation and GPU acceleration[J]. Geoscience and Remote Sensing Letters, IEEE, 2013,10(2):308-312.
[5] Hongchao M, Wang Z. Distributed data organization and parallel data retrieval methods for huge laser scanner point clouds[J]. Computers & Geosciences, 2011,37(2): 193-201.
[6] Wang Y, Chen Z, Cheng L, et al. Parallel scanline algorithm for rapid rasterization of vector geographic data[J]. Computers & Geosciences, 2013,59:31-40.
[7] Bernabé S, Plaza A, Marpu P R, et al. A new parallel tool for classification of remotely sensed imagery[J]. Computers & Geosciences, 2012,46:208-218.
[8] Liu J, Zhu A X, Liu Y, et al. A layered approach to parallel computing for spatially distributed hydrological modeling[J]. Environmental Modelling & Software, 2014,51: 221-227.
[9] Chen C, Chen Z, Li M, et al. Parallel relative radiometric normalisation for remote sensing image mosaics[J]. Computers & Geosciences, 2014,73:28-36.
[10] Khaitan S K, McCalley J D, Somani A. Proactive task scheduling and stealing in master-slave based load balancing for parallel contingency analysis[J]. Electric Power Systems Research, 2013,103:9-15.
[11] Dong B, Li X, Wu Q, et al. A dynamic and adaptive load balancing strategy for parallel file system with large-scale I/O servers[J]. Journal of Parallel and Distributed Computing, 2012,72(10):1254-1268.
[12] Guan X, Wu H. Leveraging the power of multi-core platforms for large-scale geospatial data processing: Exemplified by generating DEM from massive LiDAR point clouds[J]. Computers & Geosciences, 2010,36(10):1276-1282.
[13] Huang F, Liu D, Tan X, et al. Explorations of the implementation of a parallel IDW interpolation algorithm in a Linux cluster-based parallel GIS[J]. Computers & Geosciences, 2011,37(4):426-434.
[14] Han S H, Heo J, Sohn H G, et al. Parallel processing method for airborne laser scanning data using a PC cluster and a virtual grid[J]. Sensors, 2009,9(4):2555-2573.
[15] Bater C W, Coops N C. Evaluating error associated with lidar-derived DEM interpolation[J]. Computers & Geosciences, 2009,35(2):289-300.
[16] Yang C T, Cheng K W, Shih W C. On development of an efficient parallel loop self-scheduling for grid computing environments[J]. Parallel Computing, 2007,33(7):467-487.
[17] Parsopoulos K E. Parallel cooperative micro-particle swarm optimization: A master-slave model[J]. Applied Soft Computing, 2012,12(11):3552-3579.
[18] 钱辰,窦万峰,杨坤,等.基于时间均衡的并行插值数据划 分方法研究[J].地理与地理信息科学,2013,29(4): 86-90.
[19] 齐琳,沈婕,郭立帅,等.面向D-TIN 并行构建的动态条带 数据划分方法与实验分析[J].地球信息科学学报,2012, 14(1):55-61.
[20] 张靖,高伟.LAS 格式解析及其扩展域的应用[J].测绘科 学,2008,33(3):154-155.
[21] Yero E J H, Henriques M A A. Speedup and scalability analysis of Master-Slave applications on large heterogeneous clusters[J]. Journal of Parallel and Distributed Computing, 2007,67(11):1155-1167.
/
| 〈 |
|
〉 |