基于OpenCL的点云分割方法
|
摘要
点云分割是逆向工程中模型重建的关键技术之一,然而在求取点云特征时非常耗时,通过OpenCL异构计算对其进行性能加速有着重要的现实意义。以散乱无序的点云为研究对象,通过OpenCL对点云分割算法加以改进。算法主要分为并行计算点云数据的特征值,并行计算点云数据的法向量和曲率3个步骤。在计算中,根据GPU的并行结构和硬件特点,优化了数据存储结构,提高了数据访问效率,降低了算法复杂度。实验结果表明,算法充分利用了OpenCL的并行处理能力,运行效率是基于CPU实现的16倍。
The segmentation of point cloud is one of the key technologies of reverse engineering reconstruction, however,the computation time of point cloud feature is heavy. So it is of significance to accelerate the algorithm by heterogeneous computing with OpenCL. This paper aims to segment unordered point cloud efficiently with OpenCL. The algorithm is mainly divided into three steps: compute parallel eigenvalues of point cloud data, compute parallel normal, and curvature computation of point cloud. In the process of calculation, the data storage structure, the efficiency of data access, and the complexity of the algorithm have been optimized and improved according to the GPU parallel architecture and hardware features. Experimental results show that the algorithm takes full advantage of the parallel processing capabilities of OpenCL,the running time is 16 times faster than implementation of the CPU.
The segmentation of point cloud is one of the key technologies of reverse engineering reconstruction, however,the computation time of point cloud feature is heavy. So it is of significance to accelerate the algorithm by heterogeneous computing with OpenCL. This paper aims to segment unordered point cloud efficiently with OpenCL. The algorithm is mainly divided into three steps: compute parallel eigenvalues of point cloud data, compute parallel normal, and curvature computation of point cloud. In the process of calculation, the data storage structure, the efficiency of data access, and the complexity of the algorithm have been optimized and improved according to the GPU parallel architecture and hardware features. Experimental results show that the algorithm takes full advantage of the parallel processing capabilities of OpenCL,the running time is 16 times faster than implementation of the CPU.
引文
[1]王功明.分形理论及骨架模型在土壤和根系可视化中的应用[D].北京:首都师范大学,2007.
[2]刘增艺,江开勇,林俊义.散乱点云特征边缘交互提取[J].计算机工程与应用,2016,52(6):186-190.
[3]Richtsfeld A,M?rwald T,Prankl J,et al.Segmentation of unknown objects in indoor environments[C]//Proceedings of 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems,2012:4791-4796.
[4]刘雪梅,庄晋林,张树生,等.利用自适应模糊椭球聚类实现点云分区[J].计算机工程与应用,2007,43(15):33-34.
[5]Rabbani T,van den Heuvel F,Vosselmann G.Segmentation ofpoint clouds using smoothness constraint[J].International Archives of Photogrammetry,Remote Sensing and Spatial Information Sciences,2006,36(5):248-253.
[6]刘进,武仲科,周明全.点云模型分割及应用技术综述[J].计算机科学,2011,38(4):21-24.
[7]Lari Z,Habib A.A novel hybrid approach for the extraction of linear/cylindrical features from laser scanning data[J].ISPRS Ann Photogramm,Remote Sens Spatial Inf Sci,2013,2:151-156.
[8]Jang B,Schaa D,Mistry P,et al.Exploiting memory access patterns to improve memory performance in data-parallel architectures[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(1):105-118.
[9]Jang B,Do S,Pien H,et al.Architecture-aware optimization targeting multithreaded stream computing[C]//Proceedings of 2nd Workshop on General Purpose Processing on Graphics Processing Units,2009:62-70.
[10]Chen Y,Lin J X,Lu T.Implementation of LU decomposition and Laplace algorithms on GPU[J].Journal of Computer Applications,2011,31(3):851-855.
[11]Ryoo S,Rodrigues C I,Stone S S,et al.Program optimization space pruning for a multithreaded GPU[C]//Proceedings of the 6th Annual IEEE/ACM International Symposium on Code Generation and Optimization,2008:195-204.
[12]Rodriguez A,Laio A.Clustering by fast search and find of density peaks[J].Science,2014,344:1492-1496.
[13]孙金虎,周来水,安鲁陵.应用最小生成树实现点云分割[J].中国图象图形学报,2012,17(7):858-865.
[14]Belton D,Lichti D D.Classification and segmentation of terrestrial laser scanner point clouds using local variance information[J].The International Archives of the Photogrammetry,Remote Sensing and Spatial Information Sciences,2006,36:44-49.
[15]El-Halawany S,Moussa A,Lichti D D,et al.Detection of road curb from mobile terrestrial laser scanner point cloud[C]//Proceedings of the ISPRS Workshop on Laserscanning,Calgary,Canada,2011.
[16]Yücer K,Sorkine-Hornung A,Wang O,et al.Efficient3D object segmentation from densely sampled light fields with applications to 3D reconstruction[J].ACMTransactions on Graphics(TOG),2016,35(3):22.
[17]Huang H,Wu S,Cohen-Or D,et al.L1-medial skeleton of point cloud[J].ACM Trans on Graph,2013,32(4):65.
[2]刘增艺,江开勇,林俊义.散乱点云特征边缘交互提取[J].计算机工程与应用,2016,52(6):186-190.
[3]Richtsfeld A,M?rwald T,Prankl J,et al.Segmentation of unknown objects in indoor environments[C]//Proceedings of 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems,2012:4791-4796.
[4]刘雪梅,庄晋林,张树生,等.利用自适应模糊椭球聚类实现点云分区[J].计算机工程与应用,2007,43(15):33-34.
[5]Rabbani T,van den Heuvel F,Vosselmann G.Segmentation ofpoint clouds using smoothness constraint[J].International Archives of Photogrammetry,Remote Sensing and Spatial Information Sciences,2006,36(5):248-253.
[6]刘进,武仲科,周明全.点云模型分割及应用技术综述[J].计算机科学,2011,38(4):21-24.
[7]Lari Z,Habib A.A novel hybrid approach for the extraction of linear/cylindrical features from laser scanning data[J].ISPRS Ann Photogramm,Remote Sens Spatial Inf Sci,2013,2:151-156.
[8]Jang B,Schaa D,Mistry P,et al.Exploiting memory access patterns to improve memory performance in data-parallel architectures[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(1):105-118.
[9]Jang B,Do S,Pien H,et al.Architecture-aware optimization targeting multithreaded stream computing[C]//Proceedings of 2nd Workshop on General Purpose Processing on Graphics Processing Units,2009:62-70.
[10]Chen Y,Lin J X,Lu T.Implementation of LU decomposition and Laplace algorithms on GPU[J].Journal of Computer Applications,2011,31(3):851-855.
[11]Ryoo S,Rodrigues C I,Stone S S,et al.Program optimization space pruning for a multithreaded GPU[C]//Proceedings of the 6th Annual IEEE/ACM International Symposium on Code Generation and Optimization,2008:195-204.
[12]Rodriguez A,Laio A.Clustering by fast search and find of density peaks[J].Science,2014,344:1492-1496.
[13]孙金虎,周来水,安鲁陵.应用最小生成树实现点云分割[J].中国图象图形学报,2012,17(7):858-865.
[14]Belton D,Lichti D D.Classification and segmentation of terrestrial laser scanner point clouds using local variance information[J].The International Archives of the Photogrammetry,Remote Sensing and Spatial Information Sciences,2006,36:44-49.
[15]El-Halawany S,Moussa A,Lichti D D,et al.Detection of road curb from mobile terrestrial laser scanner point cloud[C]//Proceedings of the ISPRS Workshop on Laserscanning,Calgary,Canada,2011.
[16]Yücer K,Sorkine-Hornung A,Wang O,et al.Efficient3D object segmentation from densely sampled light fields with applications to 3D reconstruction[J].ACMTransactions on Graphics(TOG),2016,35(3):22.
[17]Huang H,Wu S,Cohen-Or D,et al.L1-medial skeleton of point cloud[J].ACM Trans on Graph,2013,32(4):65.