M2DP：一种新的三维点云描述子及其在回环检测中的应用

文章：M2DP: A Novel 3D Point Cloud Descriptor and Its Application in Loop Closure Detection

作者：Li He , Xiaolong Wang and Hong Zhang

编辑：点云PCL

来源：iros2016

代码：https://github.com/LiHeUA/M2DP.git

欢迎各位加入免费知识星球，获取PDF论文，欢迎转发朋友圈。文章仅做学术分享，如有侵权联系删文。未经博主同意请勿擅自转载。

公众号致力于分享点云处理，SLAM，三维视觉，高精地图相关的文章与技术，欢迎各位加入我们，一起交流一起进步,有兴趣的可联系微信：920177957。本文来自点云PCL博主的分享，未经作者允许请勿转载，欢迎各位同学积极分享和交流。

摘要

本文提出了一种新的三维点云全局描述子M2DP，并将其应用于闭环检测的问题中。在M2DP中，我们将3D点云投影到多个2D平面，并为每个平面的点云生成密度签名，然后使用这些签名的左奇异向量值和右奇异向量值作为三维点云的描述子。实验结果表明，该算法在精度和效率上均优于最新的全局3D描述子。

主要贡献

描述点云局部或全局形状的点云描述子可分为两类，签名方法和直方图方法，签名通过定义不变的局部参考轴或坐标系，将点云的区域拆分为索引的bin。在每个bin内，签名方法计算一个或多个几何测量值，例如点数、法线，并对bin中的信息进行编码。直方图生成每个点或点子集上特征值的计数，并将这些计数与描述子连接起来。签名方法中最早的算法之一是结构索引（SI），SI根据3D点云支持从3D曲线或构造的表示。前者从点生成曲线，并对曲线边的连续线段之间的角度进行编码，而后者考虑了沿圆的曲面方向的局部分布。3D SURF通过体素化3D网格并通过Haar小波响应定义每个体素的显著性，将流行的2D SURF描述符扩展到3D数据。最近引入的描述子大多属于直方图类，Spin image在关键点周围使用圆柱体计算，然后将圆柱体径向和垂直分割为体积，并计算每个体积内的点数。VFH描述子由两个步骤组成。首先，VFH找到视点方向以确保旋转不变性。然后，VFH计算垂直于此方向的点之间的角度，并将角度归入直方图。为了提高VFH对遮挡的鲁棒性，CVFH首先将整个点云划分为平滑区域，然后，CVFH使用区域的平均法线和质心来计算VFH描述符，SmallSized Signatures是一种简单的方法，专门针对激光雷达数据的环路闭合检测问题。它首先计算所有点的法线，然后沿法线的z轴将组件作为描述符放入直方图中。VFH、CVFH和小型签名都需要预处理步骤来计算所有点的法线。ESF方法通过在定义描述子时仅使用形状属性（距离、角度和面积）来避免常规计算。ESF使用体素栅格来近似真实曲面，迭代采样三个点并计算形状属性。SHOT可以看作是签名和直方图方法的混合，SHOT将一个以关键点为中心的球体拆分为几个箱子，并收集每个箱子中法线角度的直方图以构建描述符。最后，3D Normal Distributions Transform（NDT）将3D空间划分为规则的网格单元。根据该单元的协方差矩阵，将每个单元分为线性、平面或球形三类之一。通过计算属于一个类的单元数，NDT将类的直方图作为一个点云的描述子。

大多数现有方法在构建三维描述子时都使用点的法线，对于具有噪波数据的点云，通常很难获得一个点的精确法线，对于普通的开源的方法，如Spine Image或ESF，由于这些描述符中缺乏空间信息，因此无法在不同的云中捕获复杂的细节，在本文中，我们的目标是为3D点云构建一个高效、准确的描述子，该描述子易于计算，并能够捕获点云的局部几何细节，这两个属性在闭环检测中非常重要。

主要内容

A 算法总览

本文M2DP点云描述子是签名类型的；考虑到一个点云P和两个投影平面X、Y，将P投影到X、Y平面上，得到Px、Py，假设X、Y不平行，且投影无遮挡，那么可以利用X、Y之间的角度从Px和Py中重建P；获得Px的签名vx以及Py的签名vy，组成签名矩阵A=[vxT vyT]T来代表P；然后通过比较签名矩阵来匹配两个点云；可以通过增加投影平面的数量，来获得一个扩增的签名矩阵A；为了压缩签名，可以使用SVD来降维。本文中，使用分解后的左右奇异值矩阵的第一个向量作为点云描述子；方法框架如图1

图1:M2DP方法框架

B 点云预处理

回环检测中，描述子需要对三维空间保持移动不变性和旋转不变性，为了保持移动不变性，使用输入点云的中心作为描述子参考坐标系的原点，使用主成分分析（PCA）对齐输入点云来实现旋转不变性。对点云进行主成分分析，利用第一和第二个主成分来定义描述子参考坐标系的x轴和y轴。该步骤假设每一个点云有两个dominant direction，这使得我们可以沿着这些dominant direction来粗略的将匹配的两个点云对齐。

C 单视图的二维签名

通过法向量m来定义二维投影平面X，且X需要过原点，另外，法向量可以通过方位角θ和俯仰角Φ来确定，因此，平面X可由参数对[θ, Φ]唯一确定。把点云、中心、x轴投影到X上；将二维平面划分为多个容器（bin）。以投影后的中心点为中心，生成l个同心圆，半径为[r, 22r, …, l2r]，另外，最大半径与最远点到中心点距离相等；上面的一系列圆环，每个圆环都分成t个bin，并按照x轴把这些bin编号；这样就把一个平面分成了l×t个bin；对于每一个bin，简单计算其中的点的数量，然后就获得一个lt×1的签名向量vx，以此描述三维点云在X上的投影；使用这样的二维描述子的好处：计算高效，描述准确。该描述子避免了表面法向量的计算，而计算法向量通常计算代价大，且容易受到噪声的影响，一般对于大量的点数据，需要进行下采样，这样就会有丢失准确性的风险。

图2：二维平面中的Bin编号示意图

D 多视角二维投影描述子

通过使用p个不同的方位角θ和q个不同的俯仰角Φ，生成pq个不同的二维平面；方位角的步幅为π/p，俯仰角的步幅为π/2q；对于每一个二维平面，都生成一个lt×1的二维签名，因此可以得到一个pq×lt的矩阵A来表示点云，每一行代表一个二维签名；在A上使用SVD，将分解后的左右奇异值矩阵的第一个向量结合起来，作为最终的描述子；整体算法框架及伪代码如下：

实验

本文将提出的M2DP算法和现存五种算法进行实验比较：全局描述子VFH、ESF、Z-projection；局部描述子SHOT、Spin Image；另外还对比了基于视觉的基准描述子GIST，通常有两种方式使用局部描述子来代表整个点云：

• 第一种是词袋法，使用向量化的局部描述子的直方图作为全局描述子；
• 第二种是将整个点云作为一个参照点的支撑，关于该点计算局部描述子，本文采用第二种方式；

本文使用的数据集为KITTI的00，05，06，07序列和Freiburg Campus、Ford Campus，点云数目分别为4541、2761、1101、1101、77、3817；对于每一个点云，计算它的描述子并找到它的最近邻居作为匹配候选，设置一个距离阈值，如果两者之间距离小于阈值，则认为是闭环；为避免相邻帧匹配，把当前帧的前后50帧排除在外；利用召回率-精确度曲线来评估各算法性能；

本文设计三个实验进行比较：实验一使用原始点云作为输入；实验二采用不同下采样网格大小处理后的点云作为输入，以此测试算法鲁棒性；实验三对每一个点的位置添加一个服从均匀分布的噪声来测试算法对于噪声的鲁棒性。不同方法的召回精度曲线如图3所示，此外，表I显示了所有方法100%精度的召回值。表II分别显示了在KITTI00序列上生成描述子和最近邻搜索所有方法的时间成本。

图3: KITTI, Freiburg Campus and Ford Campus数据集的召回精度曲线

实验结果分析：VFH算法和Z-projection算法性能比较差。VFH仅考虑角度而缺乏点的位置信息，因此获得的描述子区分性差；Z-projection同样用于匹配的信息不充分；

ESF算法和Spin Image算法实验结果相对较好。而在准确率为100%下的召回率上，这两种算法与SHOT和本文算法相比较差；SHOT算法在召回率和准确率上达到了一个很好的平衡，然而在准确率为100%下的召回率强烈依赖点云的大小，当下采样网格增大时，精确率下降显著。因此，使用SHOT时，需要仔细选择下采样大小来获得效率和准确率的平衡；本文的M2DP算法显示了很大的优势，尤其在小的下采样网格时。该算法对噪声也有很好的鲁棒性，计算时间也是最短的。

总结

本文提出了一种新的三维点云全局描述子M2DP，并将其应用于基于激光雷达的环路闭合检测中，M2DP描述子是根据3D点云到多个2D平面的投影和这些平面上云的特征计算构建的，然后应用SVD来减小最终描述符的尺寸，在基准数据集KITTI、Freiburg Campus和Ford Campus上的实验证明，该方法在精度和计算效率方面均优于现有的三维点云描述子，当涉及稀疏点云时，这种优势尤为明显，当使用低空间分辨率的廉价激光雷达或计算时间是主要问题时，处理稀疏点云的能力是一个重要优势，未来，将研究M2DP对其他类型深度数据的适用性，如RGB-D和立体视觉深度图。