基于GPU的并行ICP点云配准算法研究

王嘉琛, 叶周润, 欧 鑫, 袁 斌, 吴言安, 张树峰

(1.合肥工业大学 土木与水利工程学院,安徽 合肥 230009; 2.广西中马园区数字城市科技有限公司,广西 钦州 535008; 3.安徽开源路桥有限责任公司,安徽 合肥 230093)

0 引 言

三维激光扫描技术具有数据采样率高、分辨率高等优点,近年来在测绘、实景三维中国等领域得到越来越广泛的使用。三维激光扫描技术的发展使得扫描仪器的精度越来越高,这也导致点云数据量不断增加,给后续的点云数据处理工作带来挑战。点云配准是点云处理技术中的一种,在三维重建、三维定位、姿态估计中具有至关重要的作用,点云配准的速度是点云数据处理中急需解决的问题。目前,点云配准的研究热点是通过采用并行技术提高其速度[1-3]。

点云配准分为粗配准与精配准。点云粗配准算法主要有以下3种:① 基于全局搜索思想的配准方法,如随机抽样一致(random sample consensus,RANSAC)配准算法[4-5];② 基于几何特征描述的配准方法,如采样一致性初始配准(sample consensus initial alignment,SAC-IA)算法[6-7];③ 基于正态分布变换的配准方法,主要算法为正态分布变换(normal distributions transform,NDT)配准算法[8-9]。

粗配准与精配准是相互关联的,粗配准为精配准提供初始位置,精配准能进一步优化粗配准结果,得到更精确的配准效果。点云精配准中最经典的算法是迭代最近点(iterative closest point,ICP)算法[10]。但是传统ICP算法在没有良好的初始位置时,存在无法实现全局最优解的情况;并且ICP算法需要遍历点云中的所有点,此过程在ICP算法中耗时最长,使海量点云配准效率很低。针对上述不足,国内外研究者提出一些改进算法。文献[11]通过构建KD树(k-dimensional tree,KD-Tree)加速点云遍历的过程,减少寻找最邻近点的耗时;文献[12]提出广义迭代最近点(generalized iterative closest point,GICP)算法,与传统ICP算法相比,GICP算法的鲁棒性与精确性更强;文献[13]提出体素化广义迭代最近点(voxelized generalized iterative closest point,VGICP)算法,通过体素化扩展GICP算法,避免了高代价的最近邻搜索;文献[14]提出一种快速点云配准算法,通过提取点云特征进行粗配准,然后进行ICP精配准,减少配准耗时;文献[15]利用开放运算语言(open computing language,OpenCL)实现KD-Tree的并行搜索,从而实现并行的ICP配准;文献[16]利用信息传递接口(message passing interface,MPI)实现多幅点云配准并行化。

随着计算机的中央处理器(central processing unit,CPU)与图形处理器(graphics processing unit,GPU)的发展,GPU的算力越来越高,利用GPU的多线程运算能力能有效提高一些传统算法的效率[17]。针对传统的ICP算法在大数据量点云配准中速度慢的问题,本文利用GPU的多线程能力加速ICP算法中点云遍历过程,基于GPU实现并行化的统一计算设备架构迭代最近点(compute unified device architecture iterative closest point,CUDAICP)算法,从而减少ICP配准的耗时。

本文配准流程如图1所示。

1 点云预处理与点云粗配准

1.1 点云预处理

在点云配准前要进行点云预处理,包括点云下采样与去噪。用体素法进行点云下采样,进而在保证点云特征的情况下,降低点云数据量,提高去噪和粗配准的速度;用统计滤波去噪剔除部分噪声点、离群点,减少配准过程中出现的误匹配问题。

1.2 点云粗配准算法

为了避免ICP算法陷入局部最优解,本文采用3种点云粗配准方法,即改进的RANSAC配准算法、SAC-IA算法、NDT配准算法,为点云精配准获得较好的初始位置。

1) 改进的RANSAC配准算法。通过快速点特征直方图(fast point feature histograms, FPFH)的最近邻匹配,找到源点云中3个及以上随机采样点及其在目标点云中的对应点;用采样对应来估计假设变换。

2) SAC-IA算法。首先计算源点云和目标点云的方向信息、各自的FPFH,基于FPFH对2幅点云中的点进行配准,然后随机选择3对以上匹配点,通过奇异值分解(singular value decomposition,SVD)求解变换矩阵。

3) NDT配准算法。针对点云中每个点计算其法向量与偏移量,通过协方差矩阵计算特征值与特征向量,并计算出高维特征空间中高斯网格图,将每个点转换为高维特征空间中的点并进行匹配和配准。

2 点云精配准

源点云经过粗配准得到较好的初始位置后,源点云与目标点云没有完全对齐,还需要精配准进一步优化粗配准结果,得到更精确的配准效果。本文选用ICP算法并对其进行优化。

2.1 ICP算法

ICP算法的实质是寻找2幅点云中的对应点,最小化其欧式距离d,计算公式为:

(1)

其中:Np为2幅点云对应的数量;pi为源点云中的点;qi为目标点云中pi的对应点;R、T为需要求解的旋转矩阵与平移矩阵。

ICP算法具体流程为:

1) 给定源点云P、目标点云Q。

2) 遍历P、Q,寻找P、Q最近点,计算对应点对的欧氏距离d。

3) 利用SVD计算相应的变换矩阵。

4) 对P进行旋转平移得到新的点云P′。

5) 设置阈值d′或者最大迭代次数,若d

经过多次迭代,点云P就会越来越接近Q,2幅点云最终趋于完全对齐。

2.2 CUDA架构

近年来,随着GPU的发展,GPU计算能力得到极大提升,不仅能处理传统的图形计算,而且在数据的并行计算上也得到广泛应用。NVIDIA公司的统一计算设备架构(compute unified device architecture,CUDA)可以有效解决一些复杂的计算。

在 CUDA 的架构下,一个程序可以分成2个部分,分别是对CUDA程序进行控制和管理的主机(Host)端与负责执行CUDA核函数的设备(Device)端。CUDA架构示意图如图2所示。图2中,RAM表示随机存取存储器(random access memory)。

并行程序流程为:Host端程序会将数据准备好,先在GPU中开辟所需的内存空间,复制到GPU的内存中,再由GPU执行Device端程序,执行完成后将运行结果传回Host端,最后释放GPU所开辟的内存。

2.3 CUDAICP算法

传统的ICP算法需要遍历2幅点云内所有点,此过程是传统ICP算法中耗时最长的,仅使用CPU对大数据量点云进行点的遍历耗时较长,需要利用GPU的多线程计算能力,调用多个计算单元同时搜索。理论上用GPU可以加速ICP配准的过程。

CUDAICP算法具体流程为:

1) 给定源点云P、目标点云Q。

2) 在GPU上为2幅点云开辟内存空间。

3) 将P、Q从主机内存传输至GPU内存。

4) 并行寻找最近点、计算对应点对的欧式距离d。

5) 利用SVD求解对应的刚体变换。

6) 对P做变换得到新的点云P′。

7) 设置阈值d′或者最大迭代次数,若d

8) 释放GPU上开辟的内存。

CUDAICP算法流程如图3所示。

图3 本文CUDAICP算法流程

3 实例分析

本文以Windows10系统Microsoft Visual Studio 2017为实验平台,利用点云库(Point Cloud Library,PCL)实现点云预处理与点云粗配准,使用Eigen库以及CUDA库实现点云精配准。实验平台配置为:Dell工作站,CPU为Intel酷睿i5-10500,GPU为NVIDIA GeForce GTX 1660 SUPER,内存为16 GiB。采用房间点云数据、带有楼梯的房间点云数据验证算法的可行性,具体点数分别为112 605、1 128 055。

2种场景原始点云数据如图4所示。

图4 2种场景原始点云数据

图4中:红色点云为源点云;蓝色点云为目标点云。

2种场景点云数据粗配准结果见表1所列,配准误差为均方误差。

表1 2种场景点云数据粗配准结果

从表1可以看出:对于房间点云,SAC-IA算法相对于RANSAC配准算法和NDT配准算法,具有较低的配准误差(0.544 m2)和相对较短的耗时(42.94 s);对于带有楼梯的房间点云,SAC-IA算法表现出较低的配准误差(0.059 m2),但相对于RANSAC配准算法与NDT配准算法,其耗时略长(69.14 s);NDT配准算法在房间点云数据的粗配准中精度低且耗时长,RANSAC配准算法在带有楼梯的房间点云数据粗配准中精度低。因此选择使用SAC-IA算法得到的初始位置进行点云精配准。带有楼梯的房间点云数据量较大,本文在房间点云、带有楼梯的房间点云精配准时迭代次数分别设置为20、5次。2种场景点云数据精配准情形如图5所示。图5中:红色点云为变换后点云;蓝色点云为目标点云。

图5 2种场景点云数据精配准情形

精配准结果见表2所列。

表2 2种场景点云数据精配准结果

从图5、表2可以看出:在房间点云和带有楼梯的房间点云精配准中,房间点云配准误差从0.544 m2降到0.085 m2,带有楼梯的房间点云配准误差从0.059 m2降到0.017 m2,配准误差变得更小;相比于传统的ICP算法,CUDAICP算法在房间点云和带有楼梯的房间点云配准中耗时分别减少257.16、116 208.86 s,CUDAICP算法表现出明显的加速效果,对2种场景点云数据的配准速度分别提升8.2倍、4.7倍。

4 结 论

本文针对海量点云精配准时效率低的问题,基于GPU对传统ICP算法并行化,提出CUDAICP算法。通过对2种场景点云数据的粗配准实验得出,SAC-IA算法在2种场景点云的粗配准中配准误差较小、耗时较短,因此本文使用SAC-IA算法为精配准提供初始位置,再使用CUDAICP算法进行精配准,得到最终结果。实验结果表明,CUDAICP算法在保证精度与ICP算法基本相同的前提下,可大幅提高点云配准效率,速度提升最高可达8.2倍,具有实际工程应用意义。本文仅关注点云刚性配准,未来研究可拓展到非刚性配准、粗配准方法的适用性及CUDAICP算法的进一步加速。