Research On Parallel Algorithm Of Generating DEM From LiDAR Point Clouds In High Performance Cluster

DEM is one of the most important data in Geographic Information Science.It is widely used in digital terrain analysis,digital basins analysis and three-dimension terrain display etc.With the development of data acquisition technology and DEM applications,the demand for DEM of large area and high resolution become urgent.LiDAR technology can obtain three-dimensional information in high precision of geospatial objects.So,generating DEM from LiDAR point clouds has become a common method.However,LiDAR point clouds always have a large amount of data,with millions of points.Such a huge amount of data is great challenges to LiDAR processing in traditional computer.Fortunately,parallel computing is an effective method of generating DEM from LiDAR point clouds.The parallel processing of LiDAR data is computation intensive and I/O intensive.However,on one hand,most of existing parallel algorithms of generating DEM from LiDAR data are based on multi-core computer or PC cluster.The parallel environment is relatively backward.And the scalability of existing parallel algorithms is not strong.At the same time,there is no effective strategy to reduce the I/O cost.On the other hand,the load balancing(data decomposition,schedule strategy)of existing parallel algorithms may cause long decomposition time and imbalance when dealing with large area data.This research aims at designing effective and scalable parallel algorithm of generating DEM from LiDAR point clouds in new hardware architecture represented by high performance cluster,analyses the key issues in parallel LiDAR processing,applies hybrid parallel strategy that combines process with thread into parallel processing of generating DEM from LiDAR point clouds.This dissertation focuses on some key issues such as data decomposition,schedule strategy and parallel I/O,implements a hybrid parallel algorithm,and tests the parallel algorithm.The main contents are listed as follows:(1)Process and thread hybrid parallel strategy research.This dissertation analyses the key issues in parallel processing of generating DEM from LiDAR point clouds,puts forward a hybrid parallel algorithm combined by processes and threads.This dissertation focuses on the specific collaborative strategy between processes and threads,takes advantages of processes and threads to improve the efficiency of I/O,reduce the boundary issue,and ensure the scalability of the parallel algorithm.The hybrid parallel algorithm can satisfy the requirement of computational intensive and I/O intensive requirements in parallel LiDAR data processing.(2)Two levels LiDAR data decomposition.Based on the characteristics of process and thread,this dissertation designs different data decomposition methods for them.The parallel algorithm partitions LiDAR data in coarse-grained stripes for processes,and partitions the stripe taking the load balance into account for threads.At the same,the parallel algorithm put forward two level spatial indexes for LiDAR points.For processes,this dissertation designs coarse-grained index including data buffer,explores the parallel building method for coarse-grained index.And for threads,the index is based on grid index to speed up neighborhood points searching.The study also does some work to reduce the memory usage of grid index.(3)Two levels parallel scheduling strategies.In process level,this dissertation takes advantage of processes that schedule across nodes,explores a dynamic scheduling strategy based on computational complexity in data parallel mode.In thread level,this dissertation takes advantage of threads that share memory,designs asynchronous parallel strategy to hide the I/O time of LiDAR point clouds.(4)Hybrid parallel algorithm of generating DEM from LiDAR point clouds implementing and testing.This dissertation implements the hybrid parallel algorithm combined by processes and threads in parallel computing environment,and tests the algorithm in high performance cluster by different data size.The effectiveness of hybrid parallel strategy,data decomposition methods,and parallel scheduling strategies is evaluated.This dissertation also does some contrast experiments with existing strategies.In summary,this dissertation put forward a hybrid parallel algorithm combined by process and thread in generating DEM from LiDAR point clouds for high performance cluster,makes some key breakthroughs about load balance strategy(data decomposition,schedule strategies)and parallel I/O,and tests the parallel algorithm in high performance cluster.The result illustrates that the hybrid parallel algorithm can generate high resolution DEM from large area LiDAR point clouds more effectively than the one which is implemented by processes parallel.The hybrid strategy can provide effective parallel I/O for LiDAR data and the asynchronous strategy between threads can hide the reading time of LiDAR point effectively.Data decomposition methods,spatial indexes and schedule strategies in this dissertation can achieve better load balancing.