论文

BTC是一种新颖的全局与局部相结合的三维位置识别描述子。为了实现视点不变性，我们设计了一种全局三角形描述子，它由从累积点云中提取的三个关键点形成的三角形的三条边长构成。三角形描述子本质上具有视点不变性，因为无论视点或方向如何变化，边长始终保持不变。虽然三角形描述子捕捉了点云的全局外观，但为了进一步增强其描述和区分能力，我们开发了一种名为二进制描述子的局部描述子，它编码了构成三角形的每个关键点的局部几何信息。全局与局部描述子的结合使得即使在大规模非结构化环境中，也能实现精确和鲁棒的位置识别。

相比 STD 的改进

1. 引入了二进制描述子，它提供了点云几何更详细和判别性更强的局部表示;
2. 为二进制描述子量身定制的改进关键点提取策略，减轻点云体素化引起的离散化问题;
3. 结合三角形和二进制描述子的回环检测策略;
4. 更广泛和详细的实验评估，证明了BTC在鲁棒性、准确性和效率方面在广泛的具有挑战性的场景和应用方面的优越性能。

系统概述

输入是经过配准的 LiDAR 帧，首先将其积累成子地图。然后，从子地图中提取关键点，并将其编码为二进制描述子和三角形描述子。这两种描述子结合起来形成二进制三角形组合（BTC）描述子，随后从描述子数据库中查询以检索固定数量的候选子地图。在候选池中，通过二进制描述子匹配和几何验证选择最合适的子地图，并计算出 6 自由度的位姿。一旦结果获得，当前的 BTC 描述子将被添加到数据库中以备将来使用。

BTC 描述子

A. 子地图构建

通过在子地图上执行回环检测来减轻点云密度不均和各种扫描模式的影响，子地图是对某些最近 LiDAR 扫描的积累。这种子地图积累策略对于低分辨率的 LiDAR（例如，16线旋转激光雷达）或非重复扫描 LiDAR（例如，Livox 系列 LiDAR）尤其有帮助。

子地图可以通过 LiDAR(-inertial) odometry 构建，该里程计将每一个新进入的 LiDAR帧配准到当前子地图中。每个子地图由来自 ns 次连续扫描的点组成，从而导致更密集的点云表示。

B. 关键点提取

1）平面检测：给定一个点云子地图，首先通过区域生长进行平面检测。

具体而言，首先将整个点云划分为大小为ΔL = 1 ∼ 2m 的体素。每个体素包含一组点（在代码中使用OctoTree结构表示），然后计算每个体素中点的协方差矩阵。对协方差矩阵进行特征值分解，得到其特征值和对应的特征向量。通过特征值的相对大小判断该体素是否为平面。每个被判断为平面的体素会计算其法向量、中心点、点的数量以及平面的协方差矩阵。

此过程在整个点云子地图上进行，识别出所有可能的平面区域。

2）参考平面的生成：在获取平面列表后，继续生成参考平面。

这包括合并相邻的平面以产生更大的平面。具体来说，平面合并首先选择一个初始平面体素，并逐步检查相邻体素中的平面。如果相邻体素中的平面具有相似的法向量和接近于零的距离，则与初始平面合并。（平面合并条件以及合并后的中心点、协方差矩阵计算 如公式（2）（3），合并后的法向量通过 合并后的协方差矩阵特征分解计算）

这种合并过程以区域增长的方式继续，直到相邻体素中没有平面为止。

参考平面选择：我们将合并后的平面按照包含点数的降序进行排序。然后，选择前M个点数最多的平面作为参考平面。大多数情况下，选择一个参考平面（M = 1）已足够。在一些具有不均匀地形的场景中（例如山地、城市环境中有高楼的区域，或者海拔差异较大的区域），可能需要选择两个或更多的参考平面（M ≥ 2）以适应地形的复杂性。

3）高度编码图像生成：在获取参考平面后，将3D点云投影到每个参考平面上，生成 M 个高度编码图像，每个图像具有 r×r (m²)的像素区域。选择 r 时，需要在计算效率和能够捕捉足够细节的高度编码图像之间做权衡。

为了编码高度信息，如图4所示，选择每个像素上方的最大高度 h_max，并将其分成 m 个固定分辨率 Δh 的层。对于每个像素，我们计算一个由m个比特组成的二进制字符串b，其中每个比特被设置为1，如果该层包含任何位于此高度范围内的点，否则设置为0。所有m个比特值相加得出像素强度，并与二进制字符串一起保存到每个像素中。图5(b)展示了一个高度编码图像的示例。

• 图5：关键点提取
• (a) 用于高度编码图像生成的参考平面。
• (b) 生成的高度编码图像，每个像素编码了其上方的点分布。
• (c) (b)中一个白色方框的放大区域，展示了在5×5窗口（红色方框）中检测局部最大值（白色方框）过程，关键点在相应的像素位置生成。
• (d) 在子图中提取的关键点。关键点用黄色方框表示。每个黄色方框内的红色数字表示像素强度。右侧子图显示了一个提取的关键点上方的点分布及其对应的二进制字符串。

4) 关键点提取： 在获取了M个高度编码图像后，我们继续从每个图像中提取关键点，过程如图5(c)所示。关键点通过识别局部5×5区域内的最大强度像素来确定。这些局部最大值表示具有高点数的区域，因此保留了原始3D点云的大部分信息。

为了抑制关键点的数量，我们在局部最大值强度上设置了一个阈值，只有高于该阈值的像素才被选为关键点。一旦在高度编码图像中识别出一个关键点，我们会确定它在子图中的3D坐标。为此，我们首先通过对用于高度编码的像素上方的所有点的二维坐标进行平均来确定参考平面上的点位置。然后，使用该关键点的平面参数计算关键点的完整3D位置。通过使用投影点的平均二维坐标，而不是像素的中心，我们可以达到亚像素级的精度。图5(d)展示了提取的关键点（以黄色方块表示）和附加的二进制字符串。

C. 二进制三角形组合(BTC)描述子

1）二进制描述子：二进制描述子是高度编码图像生成中的二进制字符串，它提供了对提取关键点局部几何形状的紧凑且有效的表示。二进制描述子的正式定义在数据结构 BinaryDescriptor 中，包含以下内容：

• occupy_array_：关键点的二进制字符串，封装了关键点上方的点的垂直分布。

• location_：关键点的三维位置。虽然三维位置由于缺乏位姿不变性，并不构成描述子属性，但它包含在数据结构中，以提供后续几何验证和相对位姿估计所需的基本信息。

备注1：由于关键点和二进制描述子是从点云本身检测到的参考平面中提取的，而不是固定投影平面（例如 M2DP，Scan Context 和 BEVPlace），因此它们对位姿变换具有不变性。也就是说，将点云从一个帧转换到另一个帧时，会得到相同的关键点（其坐标相应地变换）和二进制描述子。

2）三角形描述子：为了封装关键点之间的几何关系并开发场景的全局表示，我们引入了三角形描述子。选择三角形作为描述子的理由在于三角形的固有性质。首先，三角形形状对刚性变换完全不变，这意味着在不同的姿态下，三角形的边长始终相同。其次，作为最简单的多边形，三角形是稳定的形状，一旦确定了边长，三角形的形状就会唯一确定。此外，如果三条边长不同，那么三角形的顶点对应关系也可以唯一确定。这些特性使得三角形非常适合表示由关键点组成的空间配置。

3）BTC描述子：

BTC描述子结合了二进制描述子和三角形描述子的优点。BTC描述子包括一个三角形描述子和对应于形成该三角形的三个关键点（即顶点）的三个二进制描述子。这种组合使得三角形描述子能够提供姿态不变性和顶点之间的对应关系，而二进制描述子则提供局部点云分布，从而进一步提高匹配精度。BTC描述子，如数据结构 BTC 所示，并在图6中进行了可视化展示，包含以下元素：

• 一个三角形描述子
• 对应于三角形描述子的三个顶点的三个二进制描述子
• 子地图的ID

为了构建子地图的BTC描述子，我们首先使用提取的关键点的三维位置构建一个三维k-D树。对于每个关键点，我们查询k-D树以找到它的K个最近邻（例如，K = 10），这为每个关键点提供了C(K,3)个候选三角形。随后的步骤包括基于一系列选择标准过滤这组候选三角形，具体如下：

• 首先，我们丢弃任何具有两个相同边长的三角形。这是因为这类三角形可能导致顶点对应关系的模糊；当两条边长相同的三角形时，对于后续的二进制描述子匹配或位姿估计，其顶点顺序没有唯一性。
• 其次，我们丢弃边长超出指定范围的三角形。消除任何边长小于下限  或大于上限  的三角形。这样做的原因有二：一方面，非常小的三角形仅代表局部空间关系，因此提供关于更广泛场景外观的有限信息。另一方面，当两个子地图的重叠较小时，非常大的三角形不太可能被匹配，从而降低BTC描述子在这种情况下的有效性。
• 最后，移除冗余三角形。例如，考虑三个关键点，这些关键点可能在它们的K个最近邻中找到彼此，并且每个关键点会生成一个与由相同顶点 形成的三角形对应的三角形。通过将每个新三角形与子地图中的先前三角形进行检查来消除这些冗余三角形。如果新三角形具有相同的顶点集合（不考虑顺序），则将其丢弃。

经过过滤的候选三角形集合最终用于构建子地图的BTC描述子。对于每个三角形，我们构建一个BTC描述子，其中三角形的三条边长构成三角形描述子组件，三个顶点及其对应的二进制字符串构成二进制描述子组件。

数据库构建

高效管理大量描述子对于高效的回环检测至关重要。因此，我们选择哈希表作为描述子存储和检索的数据结构。与现有回环检测系统中常用的k-D树等其他流行数据结构相比，哈希表具有显著的优势，具体如下所述。

• 第一个优势是可扩展性。在大规模环境中，来自子地图的描述子数量可能会非常庞大；添加新子地图的描述子将触发包含所有历史描述子的k-D树的重建，从而导致相当大的构建时间，而且随着时间推移，构建时间呈线性增长。而哈希表则表现出卓越的可扩展性和适应性，插入和检索n个新描述子的时间复杂度为常数时间O(n)。哈希表能够有效处理动态数据集；随着新描述子的生成，它们可以被高效地插入到哈希表中，而无需像树形结构那样重新平衡。
• 第二个优势源于我们三角形描述子的结构。它们允许构建一个简单而有效的哈希函数，从量化的三角形边长计算哈希键。

在我们的哈希表中，每个哈希键都映射到一个保存相应BTC描述符的容器（比如，BTC_LOC）。同一容器中的描述符意味着它们具有相似的边长(即相似的三角形)。这种组织使我们能够有效地对形状相似的三角形描述符进行分组。

回环检测

A. 候选子地图的选择

对于一个查询子地图，首先提取其所有BTC描述子。对于每个BTC描述子 ，通过计算其哈希键查询描述子数据库。这能够在哈希表中找到相应的容器。

接下来，对容器中的所有候选描述子  进行二进制描述子相似性检查，以排除可能的异常值。具体，对于一个候选描述子，如果它是查询描述子的真实匹配，其三角形顶点应该具有相似的二进制描述子。此外，由于边长是以唯一的升序存储的，因此查询描述子的二进制描述子与候选描述子自然相互对应。具体相似度计算公式如（6）。

哈希表查询和匹配描述子的方法 如图所示：

B.几何验证

这一步旨在过滤掉那些主要源自具有相似整体外观的局部区域的虚假检测。（和STD逻辑一致）

总结

BTC是一种用于3D点云的地点识别，新的二进制和三角形结合描述子。三角形描述子负责全局描述；二进制描述子负责局部。三角形描述子通过三个关键点的边长捕捉点云的全局外观，并提供了旋转和平移不变性，同时二进制描述子编码了每个关键点的局部几何信息，增强了描述子的描述性和辨别力。

尽管BTC的性能令人印象深刻，但在某些情况下也存在一些局限性。例如，在平滑的长走廊环境（例如隧道、长走廊）中，该方法在提取有效关键点时存在困难，导致位置识别失败（即假阴性）。此外，在一些地方之间共享高度几何相似性和点云分布的情况下，也可能会观察到假阳性（例如，两个布局相同的办公室）。这些局限性最终是由于点云提供的几何特征不足或缺乏区分性所致。解决这些问题可能需要整合其他传感方式（例如视觉信息）。

代码

代码只有一个节点，类似于STD的节点 demo_livox，但是没有明确的给出数据集。于是使用STD给的数据集 park 1/2.bag 以及对应的 pose 。

对代码进行了简单修改：

• 订阅话题获取点云数据；
• 后续只对关键帧处理，生成角点和 BTC 描述子；
• 关键帧数量大于阈值进行回环检测；
• 添加当前关键帧的 BTC 描述子到数据库中

代码区别

STD 对体素点云依次检测是否是平面；非平面体素和平面体素之间投影，生成角点；根据角点生成三角形描述子；

BTC 对体素点云依次检测是否是平面，平面体素之间根据条件进行合并；然后提取与平面相关的二进制描述子（对应代码 binary_extractor）；最后生成三角形描述子。

本质区别在于 BTC 增加了二进制描述子的逻辑。

检测结果对比

 

左图显示的是 STD 检测结果，右图则是 BTC 检测结果。在首次出现回环时，BTC 成功检测到了回环，而 STD 并未检测到。

我已经在 B 站上传了两个方法的演示 Demo。从当前这个 bag 数据来看，BTC 的回环检测效果更好。后续仍需更多的数据和实际环境测试，以进一步验证哪种方法的效果更为优越。