介绍

亮点:

  • 高效的数据编码方式。这种编码对点云的密度和法线具有不变性。
  • 保存点云的内部结构。
  • 有效的两相匹配算法。
  • 与其他最先进的空间描述符进行了彻底的验证。

图1

图2

Scan Context

把3D点云分为在传感器坐标中的方位角和径向分档，如图1。\(N_s\)代表扇形数，\(N_r\)带表环数。激光雷达的最大测量距离为\(L_{max}\)，则每个环的间隙为\(\frac{L_{max}}{N_r}\)，每个扇形的弧度为\(\frac{2\pi}{N_s}\)。论文中\(N_s=60\)，\(N_r=20\)。

对于所有的分区后的点云可以表示为：

\[ \mathcal{P} = \bigcup_{i\in[N_r],\space j\in[N_s]}P_{ij} \]

然后把每个区块用一个值表示

\[ \phi=\mathcal{P}_{ij}\rightarrow\mathbb{R} \]

取每个块中的z最大值。若是没有点则为0

\[ \phi(\mathcal{P_{ij}})=\max_{\mathbf{p}\in\mathcal{P}_{ij}}{z}(\mathbf{p}) \]

最终一次scan context表示为：

\[ I=(a_{ij})\in \mathbb{R}^{N_r\times N_s},a_{ij}=\phi(\mathcal{P_{ij}}) \]

Scan Contexts之间的相似分数

给定一个scan context对，我们就需要对两个地方的相似性进行距离测量。\(I^q\)和\(I^c\)是分别从查询点云和候选点云获得的scan context。它们以纵列方式进行比较。

距离是同一索引的列之间的距离之和。余弦距离用于计算同一索引的两个列向量\(c^q_j\)和\(c^c_j\)之间的距离。

按照扇区数使用\(N_s\)归一化，距离函数为：

\[ d(I^q, I^c)=\frac{1}{N_s}\sum^{N_s}_{j=1}\left(1-\frac{c^q_j\cdot c^c_j}{\left \| c^q_j \right \| \left \| c^c_j \right \| }\right) \]

即使在同一位置，会出现列漂移，算法改进为：

\[ \begin{align} D(I^q,I^c)&=\min_{n\in[N_s]}d(I^q,I^c_n), \\ n^*&=\text{argmin}_{n\in[N_s]}d(I^q,I^c_n) \end{align} \]

额外的漂移信息对于ICP匹配初值来说非常重要

两相搜索算法

利用ring key描述子代表每个环

从最近的环到最远的环，ring key向量为

\[ \mathbf{k}=(\psi(r_1),\dots,\psi(r_{N_r})), \space \text{where} \space \psi: r_i\rightarrow \mathbb{R} \]

使用的环形编码函数\(\psi\)是使用\(L_0\)范数（非零元素个数）的环形的占用率:

\[ \psi(r_i)=\frac{\|r_i\|_0}{N_s} \]

尽管比起scan context，ring key的信息量较小，但它能够快速搜索，找到可能的循环候选者。向量\(\mathbf{k}\)被用作构建KD树的关键。同时，查询的ring key被用来寻找类似的键和它们相应的扫描索引。将被检索的顶级相似键的数量由用户决定

这些恒定数量的候选的scan context通过使用距离与查询的scan context进行比较。满足接受阈值的、与查询最接近的候选被选为重访地点：

\[ c^*=\text{argmin}_{c_k\in C} D(I^q, I^{c_k}), \space \text{s.t} \space D < \tau \]

其中，C是一组从KD树中提取的候选的索引，\(\tau\)是一个给定的接受阈值。 \(c^*\)是被确定为循环的地方的索引