关键词: 点云数据, 多核计算, 分治法, 随机分配, 三角网渐进加密滤波

Abstract: Filtering is one of the key steps in the processing of airborne LiDAR data. General serial algorithms are inefficient in the processing of large scale point cloud and couldn’t meet the demand of rapid mapping. A parallel filter of progressive TIN densification based on the technology of multi-core computing is developed which parallelizes the most time-consuming job, i.e. triangulation and point filtering. The parallelization of triangulation is based on the divide-conquer method, and the point filtering employs a strategy of random allocation by decomposing the triangle sets into many sub-sets featuring discrete distribution to realize load balance. In an 8 cores environment, the algorithm gains a speed-up of 3.1 approximately in progressive densification. Comparative experiments have evaluated the algorithm’s capability of fully exploiting the advantages from multi-core technology and better adaptability to different spatial point patterns.

Key words: point clouds, multi-core computing, divide-conquer method, random allocation, filter of progressive TIN densification