介绍

亮点:

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

图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^*$是被确定为循环的地方的索引