基于B-SHOT特征和3D-NDT的点云自动配准

王 鹏，李少达，赵 雪

（1.成都理工大学，成都 610059；2.西南交通大学地球科学与环境工程学院，成都 611756）

地面激光点云技术作为目前空间地理信息获取的重要手段，广泛用于三维重建[1]、文物保护[2]等领域。地面激光扫描仪由于其视角限制，需要多角度扫描才能获取完整的目标物体点云，并且不同角度扫描数据位于扫描仪局部坐标系下，需要通过点云配准算法将多站不同坐标系下的扫描数据进行坐标系统一。2009年，Magnusson[3-4]提出了3D-NDT算法，在精度和效率上都优于经典的ICP算法[5]，但和ICP一样需要初始值。因此，国内学者提出了基于2D特征点[6]、3D特征点[7]、2D特征点和3D特征点结合[8]的粗配准算法对3D-NDT算法进行改进。2014年，Salti等[9]提出了SHOT（signatures of histograms of orientations）3 D特征描述子，速度和精度都优于FPFH[10]、3D-SURF[11]等3D特征描述子。2015年，Prakhya等[12]对SHOT 3D特征描述子进行改进，提出了二进制SHOT(binary signatures of histograms of orientations,b-SHOT)的3D特征描述子，提高了SHOT特征描述子的速度和精度。本文主要研究利用B-SHOT特征描述子进行点云粗配准并结合3D-NDT实现点云数据的自动配准。

1 B-SHOT特征描述子

B-SHOT特征描述子与SHOT特征描述子的区别在于，B-SHOT通过迭代的方式将SHOT的特征描述子由十进制编码为二进制。利用双向汉明距离搜索两视点云之间的同名点，提高了配准的效率和精度。

B-SHOT特征描述子通过结合符号（signatures）和直方图（histograms）进行特征描述，主要包括建立唯一局部参考框架、子空间直方图统计、二进制编码等3个步骤。

为了使特征描述子对旋转、平移和尺度保持不变，采用修改后的邻域协方差矩阵C的特征向量创建局部参考框架，如式（1）：

式中，r表示支持区域半么，di=||qi-q||表示支持区域r中的采样点qi与参考点q的距离。

将局部x和z轴的方向朝向它们所代表的向量的多数方向，通过z和x的叉积，即y=z×x获得局部y轴，这样便可以得到唯一的局部参考框架。

图1 球形栅格示意图[12]

确定了局部参考框架以后，将参考点的所有邻域点变换到局部参考框架下，以保证后面计算的直方图对刚体变换的鲁棒性。然后利用球体栅格方法将局部参考空间按照距离、俯仰和方位分成32个子空间（如图1）。通过建立每个子空间的局部直方图得到每个子空间的子特征，然后将每个子特征连起来就得到了SHOT特征描述子。最后通过迭代方式对SHOT特征描述子进行二进制编码得到B-SHOT特征描述子。

2 3D-NDT算法原理

3D正态分布变换算法的目标是找到目标点集在参考点集表面匹配的似然函数最大化时的姿态。3D-NDT算法首先将三维点集均匀地划分为规则立方体，每个立方体内包含一定数量的点。对于立方体中每一个点xi的概率密度函数可以表示为：

式中，x和V分别表示单个立方体内点云的均值和方差。

3D-NDT算法通过目标点集经过初始坐标转换参数映射到参考点集中的概率密度之和s(p)作为坐标变换参数的分数值进行评价，通过对s(p)进行最优化估计，便可以得到2个点集对于坐标系的转换参数：

式中，x'i表示当前扫描点映射到参考点集的坐标；T(p,xi)表示当前点集的坐标转换矩阵。为了得到两个点集之间的转换矩阵，可以把最优化问题看成最小化问题，即s(p)最小化。通过牛顿迭代法结合Hessian矩阵进行目标函数求取最小值。令s(p)为0，为了使目标函数最小，需求解以下方程：

其中g为f的梯度，用一阶导数表示；H为Hessian矩阵，用f的二阶导数表示。

3 实验与分析

实验在ubuntu16.04系统（内存4G）下进行，算法通过C++语言并结合点云数据库PCL编码实现。实验数据采用斯坦福的bunny数据，如图2a所示。为验证本文算法的可行性，首先对两视点云分别计算B-SHOT特征描述子，然后利用双向汉明距离（Hamming distance）计算两视点云的同名点集，最后通过随机采用一致性算法（random sample consensus,RANSAC）进行初始参数估计，再利用3D-NDT进行精确配准，实验结果如图2（c）。同时，与基于FPFH特征描述子的3D-NDT算法对比，结果如表1。为了提高配准的效率，原始数据进行体素栅格采样（栅格大小为0.001）。

图2点云配准过程示意图

图2b和2c分别为基于B-SHOT特征描述子的粗配准结果和3D-NDT的精配准结果。实验证明了B-SHOT结合3D-NDT进行点云自动配准的可行性。两种粗配准实验对比结果如表1所示。在粗配准中，基于B-SHOT特征描述子的粗配准时间少于基于FPFH特征描述子的粗配准，使用3D-NDT进行精配准的时间基本不变。最后基于B-SHOT特征描述子的粗配准使得3D-NDT的精度高于基于FPFH特征描述子的粗配准，也间接证明了3D-NDT算法需要好的初始值才能表现出好的配准精度。

表1 点云自动配准实验结果

4 结 语

本文针对3D-NDT点云配准算法需要初始值的问题，提出了结合B-SHOT特征描述子与3D-NDT的点云自动配准算法，不需要提供初始值便能完成相邻两个点云之间的高精度配准。通过实验对比，本文算法有效可行，且在精度和效率上均优于目前最优秀的FPFH特征配准算法。但是3D-NDT算法还有许多需要改进的地方，在三维网格大小等参数确定过程中很难快速确定最佳参数，降低了整个实验过程的效率，常研究如何快速自适应地确定网格大小等参数。这也将是下一步的研究方向。