基于切片原理的海量点云并行简化算法.docx

基于切片原理的海量点云并行简化算法摘要：针对传统点云简化算法效率低且处理点数少的缺陷结合快速成型领域的切片原理顾及特征计算复杂度低的特点设计并实现了适合千万级海量激光雷达（LiDAR）点云的并行切片简化算法。该算法根据切片原理对点云模型分层并按照角度排序利用NVIDA的统一计算设备架构（CUDA）和可编程图形处理器（GPU）高度并行的性能优势使用GPU多线程高效并行地执行单层切片点云简化提高了算法效率。最后应用3组不同数量级点云模型分别进行简化对比实验。实验结果表明：在保持模型特征与压缩比不变的情况下所提算法效率高出传统基于CPU的串行切片算法1～2个量级。关键词：海量点云；简化；切片法；计算设备架构；图形处理器；并行计算中图分类号：TP391.413文献标志码：A0引言随着大规模精细三维模型获取技术的不断发展三维激光扫描技术凭借其数据获取速度快、精度高、覆盖广的特点成为高精度三维模型数据获取的主流方式之一获取的点云数据量也呈几何级数增长因此如何对海量散乱点云数据进行简化已成为计算机图形学、快速成型、三维测绘、地理信息系统、数字城市、军事仿真、游戏娱乐等点云模型应用领域的重要研究课题之一。传统的点云简化方法主要分为两个大类：第一类是顾及特征的简化[1-3]此类算法需要依据单点的K邻近点集拟合曲面并构建曲面的法向量和曲率等相关特征度量因子判定单点是否为特征点从而实现点云简化。这些算法能够保持模型特征但是涉及K邻近点集等复杂计算操作耗时多仅适用于小数据量的点云简化。第二类是规则采样简化算法[4-6]此类算法依据一定规则对原始点云进行采样然后以采样点作为特征点保留剔除其他点实现点云简化。这类算法简化效率高但是不能有效地保持模型特征由于采样标准单一在特征变化明显的尖锐弯曲处会导致局部细节过度光顺丢失细节。由此可见传统算法的主要问题是点云简化过程中计算复杂与模型特征保持不能兼顾。近年来通用计算图形处理器（GeneralPurposeGraphicsProcessingUnitGPGPU）的快速兴起尤其是NVIDIA公司2006年推出的图形处理器（GraphicsProcessingUnitGPU）并行计算框架――统一计算设备架构（ComputeUnifiedDeviceArchitectureCUDA）[7]凭借其高性价比、低通信开销、卓越的并行计算能力让海量化或者计算复杂度高的三维点云模型数据快速处理成为可能。文献[8]使用GPGPU实现基于边缘点的激光雷达（LightDetectionAndRangingLiDAR）点云滤波算法文献[9]提出一种基于CUDA的双边滤波的点云滤波算法。两者都将K邻近点、曲面拟合、法向量以及曲率等计算复杂度高的步骤利用CUDA编写不同的kernel并行化从而加速点云简化但是由于在单个线程中完成类似求解单点K邻近点的计算需要消耗太多的全局内存等GPU资源这严重制约此类算法处理点云的规模仅适用于数十万级的小规模点云处理。本文借助众核GPU通用计算高性能并行的特点结合快速成型领域切片点云简化算法[10-12]顾及特征的优势实现了基于CUDA的顾及模型特征且适合千万级点云的并行简化算法并从该算法的时间效率方面的优势阐述了CUDA用于海量数据处理的优势和潜力。1切片点云算法原理基于CUDA的切片算法实现原理如下：首先在CPU端根据点云的几何分布特征对点云进行分层并降维投影至相应的投影平面上；然后依次对不同投影面上单层点云中的每一点和相应投影平面坐标原点所连直线与投影面某一坐标轴固定方向的夹角大小进行升序排序；最后使用本文提出的利用CUDA在GPU端对每层排序后的切片点云依据弦高差法并行计算各点的弦高差值和各层切片的弦高差均值作为阈值通过比较各点弦高差与阈值的关系确定该点是否为特征点从而完成该层切片简化。1.1特征点的提取原理利用弦高差法来确定切片中各点是否为特征点原理详见文献[13]其中弦高距离由式（1）求得：di=|Axi+Byi+C|/A2i+B2i+C2i（1）如图1所示pi为目标待判定点直线pi-1pi+1所构成直线方程为l：Ax+By+C=0由计算几何的原理可求得pi到直线l的垂直距离为di。其中：mj表示第j层点云的总数；di表示第j层点云中的第i个点的弦高差值。1.2基于CUDA的切片算法实现由上述原理可以看出：依次计算单点的弦高差、单层切片的阈值σ以及单点弦高与阈值的比较等操作均是计算密集的操作不涉及对原始切片数据的写操作不会因为数据的复写而引发数据的二义性具备