路面点云的并行简化研究
|
摘要
为有效解决大规模路面激光点云简化过程中的时间延迟问题,在加速简化过程的同时准确保留特征点,研究了基于斜率差的扫描线点云简化算法及2种并行加速方式。首先从路面扫描线点云的分布特点出发,以相邻点间连线的斜率差作为识别特征点的基准,实现了串行简化算法。同时,在研究算法的流程并提取出可并行步骤的基础上,分别设计实现了利用多核CPU的并行简化算法和利用GPU的并行简化算法。前者依靠OpenMP技术,实现的是一种多线程并行;后者在CUDA框架下实现,属于CPU和GPU结合的异构并行计算。在实验阶段的实际路面点云上验证算法执行效果的同时,设计了3种算法在不同规模点云数据上的性能测试。通过绘制性能曲线,分析比较了2种并行算法的并行效果优劣。最终实现的利用GPU的并行简化算法与串行算法比较取得了100左右的加速比。
To effectively solve the problem of time delay in the simplification of large-scale road surface laser point cloud,accurately reserving the feature points while accelerating the simplification process,a simplification algorithm based on slope difference of the scanning line point cloud and two parallel acceleration methods are studied. Firstly,based on the distribution characteristics of point cloud of road surface scan line,the slope difference of the line between adjacent points is taken as the benchmark to identify feature points,and a serial simplification algorithm is implemented. At the same time,based on the study of the algorithm flowand the extraction of parallel steps,the parallel simplification algorithm using multi-core CPU and the parallel simplification algorithm using GPU are designed and implemented. The former relies on OpenMP technology to achieve a multi-threaded parallelism; the latter is implemented under the CUDA framework,which belongs to the heterogeneous parallel computing combining CPU and GPU. In the experimental stage,the effectiveness of the algorithm is verified on the actual road surface point cloud. Meanwhile,The performance tests of three algorithms on point cloud data of different scales are designed. By plotting the performance curve,the advantages and disadvantages of the two parallel algorithms are analyzed and compared. The final realization of the parallel simplification algorithm based on GPU has achieved a speedup about 100 compared to the serial algorithm.
To effectively solve the problem of time delay in the simplification of large-scale road surface laser point cloud,accurately reserving the feature points while accelerating the simplification process,a simplification algorithm based on slope difference of the scanning line point cloud and two parallel acceleration methods are studied. Firstly,based on the distribution characteristics of point cloud of road surface scan line,the slope difference of the line between adjacent points is taken as the benchmark to identify feature points,and a serial simplification algorithm is implemented. At the same time,based on the study of the algorithm flowand the extraction of parallel steps,the parallel simplification algorithm using multi-core CPU and the parallel simplification algorithm using GPU are designed and implemented. The former relies on OpenMP technology to achieve a multi-threaded parallelism; the latter is implemented under the CUDA framework,which belongs to the heterogeneous parallel computing combining CPU and GPU. In the experimental stage,the effectiveness of the algorithm is verified on the actual road surface point cloud. Meanwhile,The performance tests of three algorithms on point cloud data of different scales are designed. By plotting the performance curve,the advantages and disadvantages of the two parallel algorithms are analyzed and compared. The final realization of the parallel simplification algorithm based on GPU has achieved a speedup about 100 compared to the serial algorithm.
引文
[1]SHI Baoquan,LIANG Jin,LIU Qing. Adaptive simplification of point cloud using k-means clustering[J]. Computer-Aided Design,2011,43(8):910-922.
[2] XIAO Zhaoxia,HUANG Wenming. Kd-tree based nonuniform simplification of 3D point cloud[C]//2009 Third International Conference on Genetic and Evolutionary Computing. Guilin,China:IEEE,2009:339-342.
[3]袁小翠,吴禄慎,陈华伟.特征保持点云数据精简[J].光学精密工程,2015,23(9):2666-2676.
[4]MOENNING C,DODGSON N A. A new point cloud simplification algorithm[C]//3rdIASTED International Conference on Visualization,Imaging, and Image Processing. Spain:ACTA press,2003:1027-1033.
[5]朱煜,康宝生,李洪安,等.一种改进的点云数据精简方法[J].计算机应用,2012,32(2):521-523,544.
[6] SONG Hao,FENG H Y. A progressive point cloud simplification algorithm w ith preserved sharp edge data[J]. The International Journal of Advanced M anufacturing Technology,2009,45(5-6):583-592.
[7]曹毓,冯莹,杨云涛,等. RANSAC直线估计方法在路面三维点云优化中的应用[J].红外与激光工程,2012,41(11):3108-3112.
[8]刘如飞,王鹏.保留路面特征的车载激光点云非均匀压缩方法[J].遥感信息,2017,32(1):100-103.
[9] WANG Gefang,LV Yanmei,HAN Ning,et al. Simplification method and application of 3D laser scan point cloud data[C]//Proceedings of the 1stInternational Conference on M echanical Engineering and M aterial Science. Shanghai,China:Atlantis press,2012:266-268.
[10]GUO J,LIU J Y,ZHANG Y L,et al. Filtering of ground point cloud based on scanning line and self-adaptive angle-limitation algorithm[J]. Journal of Computer Applications,2011,31(8):2243-2245.
[2] XIAO Zhaoxia,HUANG Wenming. Kd-tree based nonuniform simplification of 3D point cloud[C]//2009 Third International Conference on Genetic and Evolutionary Computing. Guilin,China:IEEE,2009:339-342.
[3]袁小翠,吴禄慎,陈华伟.特征保持点云数据精简[J].光学精密工程,2015,23(9):2666-2676.
[4]MOENNING C,DODGSON N A. A new point cloud simplification algorithm[C]//3rdIASTED International Conference on Visualization,Imaging, and Image Processing. Spain:ACTA press,2003:1027-1033.
[5]朱煜,康宝生,李洪安,等.一种改进的点云数据精简方法[J].计算机应用,2012,32(2):521-523,544.
[6] SONG Hao,FENG H Y. A progressive point cloud simplification algorithm w ith preserved sharp edge data[J]. The International Journal of Advanced M anufacturing Technology,2009,45(5-6):583-592.
[7]曹毓,冯莹,杨云涛,等. RANSAC直线估计方法在路面三维点云优化中的应用[J].红外与激光工程,2012,41(11):3108-3112.
[8]刘如飞,王鹏.保留路面特征的车载激光点云非均匀压缩方法[J].遥感信息,2017,32(1):100-103.
[9] WANG Gefang,LV Yanmei,HAN Ning,et al. Simplification method and application of 3D laser scan point cloud data[C]//Proceedings of the 1stInternational Conference on M echanical Engineering and M aterial Science. Shanghai,China:Atlantis press,2012:266-268.
[10]GUO J,LIU J Y,ZHANG Y L,et al. Filtering of ground point cloud based on scanning line and self-adaptive angle-limitation algorithm[J]. Journal of Computer Applications,2011,31(8):2243-2245.