点云配准FPFH特征子异构并行优化研究

王敏

摘要：三维点云配准在逆向工程中应用广泛，能为古建筑保护实现三维建模提供精确的数据依据。针对大规模多视角古建筑点云数据进行配准，研究了FPFH特征提取的串行算法，设计了三类并行方案，分别为利用基于CPU的并行编程标准OpenMP进行并行优化加速、利用基于GPU的并行计算架构CUDA进行并行优化加速，以及利用CPU/GPU的异构并行，结合OpenMP和CUDA的特点应用于特征子求取。实验结果表明，第三种方案能合理设计并优化特征子求取，获得较为理想的加速比。

关键词关键词：点云配准；FPFH；并行计算；CUDA；OpenMP

DOIDOI：10.11907/rjdk.171848

中图分类号：TP301

文献标识码：A文章编号文章编号：16727800（2017）011002904

0引言

古建筑保护需要使用逆向工程，主要是利用测试仪器获取的多视点数据加上它们之间的原始坐标变换关系，进行点云数据间的配准。随着扫描仪测量精度不断提高，点云数据规模将变大。

針对配准算法、点云配准算法，应用最为广泛的是由Besl和Mkcya[1]提出的最近点迭代（Iterative Closest Point，ICP）算法，通过迭代搜索两片点云之间的最近点，建立对应的匹配关系。然而，搜索过程相当耗时且会陷入局部极值。尤其是针对解决多视点的配准，为了解决这类问题，学者们提出了许多基于几何特征的改进配准算法，如Rusu、Radu等[2]提出了点特征直方图PFH（Point Feature Histograms），后来又提出了快速点特征直方图FPFH（Fast Point Feature Histograms）[3]，并在PCL点云库中实现了相应算法[4]。

随着GPU/CPU异构并行技术的快速发展，GPU浮点计算能力与CPU相比提高了几个数量级。特别是英伟达的统一计算架构CUDA（Compute Unified Device Architecture）[5]提供了更直观的编程模型和优化原则[6]。为更加合理地利用GPU/CPU异构并行技术，解决点云配准过程中可并行FPFH算法的时间成本随点云规模变大而加大的问题，进行了如下工作：首先，分析点云配准算法中串行实现的具体步骤，计算出配准算法中特征描述子的时间消耗比；其次，设计了3种方案，即使用CPU并行的OpenMP[7]、GPU并行的CUDA技术以及将两种技术结合的方案；最后，利用PCL（Point Cloud Library）点云库实现程序，并通过标准点云文件进行实验，求取加速比并进行分析对比。

1配准算法概述

点云配准是根据两点云之间的交集融合两个点云的过程，最终目的是求得坐标变换参数R（旋转矩阵）和T（平移向量），使两视角下测得的三维数据经坐标变换后的距离和最小。串行算法的基本思想是对得到的点云文件进行去噪等预处理，之后计算点云关键点，以及关键点处的曲面法线；然后估计曲面的FPFH特征描述子，利用随机采样一致性算法RANSAC（Random Sample Consensus）对两片点云进行初始匹配；最后，运用ICP算法对点云的初始配准结果进行二次配准，进一步优化配准结果，从而实现点云的精确配准。配准过程最重要的部分是提取关键点与计算特征描述子，以保证多次迭代求得对应关系估计的准确性和效率，以及后续流程中刚体变换矩阵估计的无误性。

实现配准的具体步骤为：①首先加载两个点云数据集合，并利用关键点选取标准算法提取关键点；②对选择的所有关键点计算特征描述子；③结合特征描述子在两个数据集中的坐标位置，根据两者之间特征和位置的相似度，估计它们的对应关系，初步估计对应点对；④除去对配准有影响的错误对应点对；⑤利用过滤后的正确对应点关系估计刚体变换，完成最终配准。

3.2CUDA方案

CUDA程序流程[10]如下：

图5CUDA并行模型方案

CUDA核心代码分为两部分：

（1）host端要进行的操作：

//在host端设置设备

cudaError_t cudaSDStatus=cudaSetDevice（0）；

//之后分配显存

cudaError_t cudaIStatus=cudaMalloc（&input， input.size（）*sizeof（pcl：：pointXYZ））；

cudaError_t cudaOStatus=cudaMalloc（&output， output.size（）*sizeof（pcl：：Normal））；

//将host数据存入显存

cudaError_t cudaIStatusH2D=cudaMemcpy（input， input， input.size（）

*sizeof（pcl：：pointXYZ），cudaMemcpyHostToDevice）；

cudaError_t cudaOStatusH2D=cudaMemcpy（output，output，output.size（）*sizeof（pcl：：pointXYZ），cudaMemcpyHostToDevice）；

//host程序等待显存内核程序执行

pcl：：GPU：：FPFHEstimation：：PointCloud gCloud

gCloud.upload（cloud->points）；//从主机端到GPU端

//…

使用CUDA封装好的程序对GPU的操作进行了封装，并且有很好的API提供给用户。

（2）在device端内核程序的设计分为两个内核kernel函数：endprint

__global__void SpfhKernel<<>>（spfh）；

__global__void FpfhKernel<<>>（fpfh）；

3.3CUDA+OpenMP方案

图6CUDA+OpenMP并行模型方案

Input：点云数据分块

Output：FPFHEstimation

#pragma omp parallel for schedule（dynamic）//OpenMP并行部分

for （i=0； i<任务分解； i++）

{

checkCudaErrors（cudaSetDevice（dev_id））；

int tid=omp_get_thread_num（）；

execute（任务[i]， handles， streams， tid）；

}

cudaDeviceSynchronize（）；//同步

//资源回收

其中execute（任务[i]， handles， streams， tid）可以在GPU或CPU上执行FPFH特征子求取算法。

4实验结果分析

4.1实验环境

实验环境为：Intel酷睿i5 6300HQ处理器，主频2.3GHz，4GB內存。

4.2方案一

图7为Parallel Studio中OpenMP优化线程并行过程的函数热点。

图7OpenMP优化线程并行过程函数热点

在本次实验硬件环境下，串行程序总共产生了3个线程，在四核处理器中并行程序总共产生了6个线程，其中OpenMP产生了3个线程，以对特征值进行求解。在pcl：normal_estimation并行化程序中，特征值采用FPFH特征子进行求解，以及采取kdtree寻找邻接点，为最耗时的两部分。求得加速比为：

S（P）=T串行T并行=141.703115.188=1.23（5）

针对式（5）中得到的加速比，加速效果不是很明显，原因如下：①OpenMP启动与销毁线程需要时间；②相对于大规模点云，本次测试的数据规模较小，从pcd文件中的POINTS可以看出，点数约为30多万；③点云特征值描述子占整个配准过程的耗时比例不大。

4.3方案二

对于内核kernel函数spfh和fpfh的对比，结果过滤只显示关注的设备利用率时间与Nsight上函数的执行时间，可以看出内核函数对设备的利用还有很大提升空间。对于CPU/GPU耗时的统计，每次实验结果都不一样，但点云数目越大，加速比将趋于稳定，如表1所示。

表1不同规模测试点云CUDA耗时与加速比

点云规模1001 00030 000

CPU串行耗时（s）0.3076.30370.648

GPU并行耗时（s）1.0011.9815.873

加速比0.303.1812.029

由此得出单独利用CUDA平台进行并行优化加速时，使用PCL封装的GPU操作将会带来加速比的提升，只需少量显存空间进行申请释放等额外操作。

4.4方案三

在GPU内的FPFH描述子算法建立方案二的基础上，此方案更加充分利用了CPU并行模型OpenMP，在外层利用OpenMP多线程对其进行了任务调度，以对GPU进行操作。实验结果如表2所示。

表2不同规模测试点云CUDA+OpenMP耗时与加速比

点云规模1001 00030 000

CPU串行耗时（s）0.2976.46771.231

GPU/CUDA并行耗时（s）3.8174.1734.923

加速比0.081.5514.47

可以看出采用CUDA和OpenMP两者相结合的方案，不仅需要少量的显存空间进行申请释放等额外操作，而且OpenMP的线程开销也会影响程序运行时间，但两者的时间在数据规模变大后影响将变小。同时，在数据规模在万级以上时，其将比仅依靠GPU并行的程序更加高效，可获得更好的加速比。

5结语

配准多视角扫描的点云数据是获得被测量物体表面完整模型的关键步骤，而三维测量技术的发展使测量点云的数据更精确、数据量更大。处理必然带来时间开销，如今随着异构并行技术的发展，特别是显卡并行计算能力的提高，特别适合点云这类数据量大、逻辑结构不复杂，但数据计算繁重的任务，有助于在成本减少的情况下提高数据处理速度，减少时间成本。针对如何高效地利用异构并行的问题，提出了耗时FPFH特征描述子，以求取并行优化方案，并通过几种专业分析软件得出运行时间、函数热点。结果表明，CUDA+OpenMP的方案能较好地结合CPU并行和GPU并行的优势，减少运行时间，提高加速比，具有较高的实用价值。

参考文献参考文献：

[1]P J BESL，H D MCKAY. A method for registration of 3D shapes[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence，1992.

[2]R B RUSU，N BLODOW，Z C MARTON，et al. Aligning point cloud views using persistent feature histograms[C]. IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE，2013：33843391.

[3]RADU BOGDAN RUSU，NICO BLODOW，MICHAEL BEETZ. Fast point feature histograms （FPFH） for 3D registration[C]. IEEE International Conference on Robotics and Automation，2009：18481853.

[4]RADU BOGDAN RUSU，STEVE COUSINS. 3D is here： point cloud library （PCL）[C]. IEEE International Conference on Robotics and Automation，2011：14.

[5]NVIDIA. CUDA C programming guide[EB/OL]. www.nvidia.com.

[6]JOHN NICKOLLS，IAN BUCK，MICHAEL GARLAND，et al. Scalable parallel programming with CUDA[J]. Queue，2008，6（2）：4053.

[7]LEONARDO DAGUM，RAMESH MENON. OpenMP： an industrystandard API for sharedmemory programming[J]. IEEE Computational Science & Engineering，1998，5（1）：4655.

[8]陆军，彭仲涛，董东来，等.点云FPFH特征提取优化配准算法[J].新型工业化，2014（7）：7581.

[9]朱德海.点云库PCL学习教程[M].北京：北京航空航天大学出版社，2012.

[10]荆锐，赵旦谱，台宪青.基于GPU的实时三维点云数据配准研究[J].计算机工程，2012，38（23）：198202.

责任编辑（责任编辑：黄健）