经典文献阅读之–STD(激光SLAM回环检测算法)

0. 简介

各位也知道，我们在之前的博客中，介绍了很多回环的方法，比如Scan Context，Lris, BoW3D等方法。之前作者也在《重定位解析与思考》一文中，给到了一些回环检测算法的介绍。最近林博新开源了一个回环检测算法《STD: A Stable Triangle Descriptor for 3D place recognition》。我们从小乌坞博主中的实验中发现，确实效果不错，同时相关的代码也已经在Github上开源了。

在这里插入图片描述

图1。(a)显示从查询点云中提取的稳定三角形描述符(STD)。(b)显示从历史点云中提取的STD。（c）显示了这两帧点云之间STD匹配的示例。正确匹配的STD描述符由白色框标示，并且通过STD提供的姿态进行点云配准。这两帧点云是由一个小视场角激光雷达(Livox Avia)在相反方向移动收集的，导致点云重叠度低且视角变化剧烈(请查看我们的YouTube附带视频: youtu.be/O-9iXn1ME3g)。

1. 主要贡献

本文开发了一种新的描述符：STD，它用三角形对场景中的任意三个关键点进行编码。与其他描述符中使用的多边形相比，三角形更稳定，因为三角形的形状是根据边长(或夹角)唯一定义的。与关键点周围的局部描述符相比，三角形的形状完全是旋转和平移不变的。为了提取三角形描述符的关键点，作者在平面上进行点云投影，并在边界上提取关键点，然后将关键点组成三角形。匹配是基于三角形的相似度进行的。

典型的STD位置识别案例如图所示，在同一位置成功识别了两个从相反视角采集的点云。具体而言如下:

设计了一个三角形描述符，这是一个六维向量，由三个三角形边的长度和法向量之间的夹角组成。描述子保持旋转和平移完全不变，同时保持高度的可区分性。
提出了一种基于关键帧的快速关键点提取方法。为了表示场景的结构信息，将点云投影在平面边界处，并提取其中的关键点，这些关键点与相邻关键点形成三角形描述符。
在多种类型的场景(城市、室内和非结构化环境)和不同的激光雷达数据(传统旋转激光雷达和固态激光雷达)下评估算法。充分的实验结果验证了该方法的有效性。

2. 主要方法

在后面几节中，我们描述如何从点云中提取稳定三角形描述符。接下来，我们介绍如何构建描述符字典以及如何选择环路候选项。最后，我们提出了基于RANSAC的环路检测和几何验证，用于完整的环路检测流程。我们的方法的整体流程如图2所示。

在这里插入图片描述

图2. 我们算法的工作流程。我们的方法从关键帧中计算三角形描述符。然后使用哈希表作为描述符的数据库，以进行快速存储和匹配。具有前10个描述符匹配分数的帧将被选为候选项。一旦通过几何验证，环路候选项将被视为有效的环路。在触发环路时，还将获得环路帧和候选帧之间的相对变换。

3. 稳定三角形描述符

受[26]的启发，为了提高分割的稳定性，我们在关键帧上执行环路检测，这些关键帧具有从几个连续的扫描中积累的点，因此具有增加的点云密度，而不管具体的LiDAR扫描模式。具体而言，我们使用LiDAR里程计[28]将每个新进入的点云注册到当前关键帧中。当子帧数累积到一定数量时，将创建一个新的关键帧。给定点云的关键帧时，我们首先通过区域生长进行平面检测。具体而言，我们将整个点云分成给定大小的体素(例如1m)。每个体素包含一组点

(

，

…

，

)

p_i(i = 1，…，N)

pi(i=1，…，N)；然后我们计算点协方差矩阵

Σ：

在这里插入图片描述

设

λ_k

λk为矩阵

Σ的第

k大特征值。平面判定原则为：

在这里插入图片描述

其中

σ_1

σ1和

σ_2

σ2是预设的超参数。根据这个判定标准，我们可以检查体素中的点是否形成一个平面，如果是，则称该体素为平面体素。然后，我们从任何一个平面体素开始初始化一个平面，并通过搜索其相邻的体素来扩展平面。如果相邻的体素是相同的平面(具有相同的平面法线方向，距离低于阈值)，则它们将被添加到正在生长的平面中。否则，如果相邻的体素不在同一个平面上，则将其添加到平面的边界体素列表中。上述生长过程重复，直到所有添加的相邻体素被扩展，或者到达边界体素(参见图4)。

在这里插入图片描述

图4. 平面扩展过程

对于边界体素，我们将其包含的点投影到相应的平面上(参见图5(a)和图5(b))。对于每个平面，我们创建一个图像，其中图像平面与平面重合，每个像素表示包含在平面的边界体素中的点的最大距离。然后，我们选择一个点，在其5 * 5邻域中具有最大像素值，作为关键点(参见图5（c）)。每个提取的关键点对应于输入点云中的一个3D点，并且可以附加其从中提取的平面的法线。

使用关键帧中提取的关键点，我们构建一个k-D树，并为每个点搜索20个近邻点以形成三角形描述符。具有相同边长的冗余描述符将被消除。每个三角形描述符包含三个顶点

p_1

p1、

p_2

p2和

p_3

p3，具有投影法线向量

n_1

n1、

n_2

n2和

n_3

n3。此外，三角形的顶点按照边长规则按升序排列(参见图3)。我们总结一个三角形描述符

∆

∆的内容如下：

p

1

、

p

2

、

p

3

p_1、p_2、p_3

p1、p2、p3：三个顶点，
n

1

、

n

2

、

n

3

n_1、n_2、n_3

n1、n2、n3：三个投影法线向量，
l

12

、

l

23

、

l

13

l_{12}、l_{23}、l_{13}

l12、l23、l13：三个边，

l

12

≤

l

23

≤

l

13

l_{12}≤l_{23}≤l_{13}

l12≤l23≤l13，
q

q

q：三角形的重心，
k

k

k：对应于描述符的帧号。

除了描述符，我们还将保存从该关键帧提取的所有

n

n

n个平面

Π

=

(

π

1

，

π

2

，

…

，

π

n

)

Π = (π_1，π_2，…，π_n)

Π=(π1，π2，…，πn)，用于以下的几何验证步骤。

图5. (a) 边界体素中的点以黄色着色。(b) 将这些点投影到相邻的平面上(蓝色点)。©平面图像，其中每个像素表示边界体素中的点到平面的最大距离(以厘米为单位)。如果一个点在其5 * 5邻域中具有最大像素值，它将被视为关键点(红色点)。

4. 搜索环候选项 (比较重要的知识)

由于一个关键帧中可以提取出数百个描述子，为了快速查询和匹配描述子，我们使用哈希表来存储所有描述子。我们在描述子中使用具有旋转和平移不变性的六个属性来计算哈希键，这些属性是边长

l

12

、

l

23

、

l

13

l_{12}、l_{23}、l_{13}

l12、l23、l13以及法向量投影向量

n

1

⋅

n

2

，

n

2

⋅

n

3

，

n

1

⋅

n

3

n_1·n_2，n_2·n_3，n_1·n_3

n1⋅n2，n2⋅n3，n1⋅n3的点积。具有所有六个类似属性的描述子将具有相同的哈希键，因此存储在同一个容器中。对于一个查询关键帧，我们提取其所有描述子，如3节所述。对于每个描述子

∆

i

∆_i

∆i，我们计算其哈希键，将其定位到哈希表中相应的容器，并为在此容器中具有描述子的关键帧投票一次。当查询关键帧中的所有描述子

∆

i

∆_i

∆i都被处理时，匹配过程结束。获得前10个票数的关键帧将被选为具有匹配描述子的候选项，并保存供环检测步骤使用。