Scan Context——论文学习
- 0. 前言
- 1. 摘要及引言
- 2. Scan Context构建
- 3. 双层匹配算法与Scan Context相似度打分
-
- 3.1 Ring Key
- 3.2 评分
- 4. 整体流程
0. 前言
在前一段时间深蓝学院课程中，用到了Scan Context。因为时间原因，一直没有深入了解。这里重新对论文进行学习。
论文中描述了大量的实验结果，这也是作者提到的关键贡献之一。本篇文章主要对论文的理论部分进行学习。
在这篇文章中，有一些概念类词汇在学习论文过程中造成了一些困扰，这里也提前进行记录。
perception aliasing（感知混叠）：感知混叠是一种在不同的地方中产生相似的视觉区域现象1，即不同位置的相似环境产生了定位错误。就个人理解，本文中感知混叠主要指同一位置的因为不同光照、物体不同等产生了定位错误。
基于雷达的位置识别需要解决的两个问题：需要克服
egocentric 2.5D information（自我中心的2.5D 信息）：这个还没有搞清楚，大概是将3维雷达信息通过矩阵（也就是提出的Scan Context描述子）表示出来，矩阵内容含有一定的3维信息（高度），而该描述子是以机器人自身为中心的。
L0范数： 指向量中非0的元素的个数
root shift是啥，为啥可以对平移鲁棒
1. 摘要及引言
1.1 摘要
重点提炼了Scan Context 的特点，即基于3D激光雷达的非直方图环境描述方法。该方法的匹配度计算采用双层搜索算法来提高效率，且与现有算法相比有了巨大提升。
1.2 引言
基于雷达的位置识别算法有两个需要解决的问题，旋转不变性以及噪声处理。这也是本文所涉及到的。
本文贡献主要在四个方面。
- 高效的桶编码函数（Efficient bin encoding function），具有对点云密度和法线的不变性。
- 保存点云内部结构（Preservation of internal structure of a point cloud），提高了scan context对不同视角的正确识别能力。
- 高效的双层匹配算法（Effective two-phase matching algorithm），先利用Ring key进行快速的上层搜索，得到少量候选帧。随后对候选帧与当前帧进行距离计算。
- 与现有主流算法的彻底比较，大量的实验。
2. Scan Context构建
Scan Context描述子是将单帧激光雷达点云数据转换为
数值为当前桶内激光点最大高度的二维矩阵
。
首先，对Scan Context 桶（区域划分）进行介绍。如图1所示，将单帧激光雷达按两个方向：径向与环向进行划分。其区域数量分别是Nr（径向）、Ns（环向）。因此，其区域分辨率为 L max N r \frac{L_{\max }}{N_{r}} NrLmax（径向）， 2 π N s \frac{2 \pi}{N_{s}} Ns2π（环向）。
因此，当前帧点云为划分的区域的并集。
P = ⋃ i ∈ [ N r ] , j ∈ [ N s ] P i j \mathcal{P}=\bigcup_{i \in\left[N_{r}\right], j \in\left[N_{s}\right]} \mathcal{P}_{i j} P=i∈[Nr],j∈[Ns]⋃Pij
因此，当前帧点云的Scan Context描述子可以表达为Nr * Ns的矩阵，其元素值为区域点云中高度的最大值。
即，
I = ( a i j ) ∈ R N r × N s , a i j = ϕ ( P i j ) I=\left(a_{i j}\right) \in \mathbb{R}^{N_{r} \times N_{s}}, a_{i j}=\phi\left(\mathcal{P}_{i j}\right) I=(aij)∈RNr×Ns,aij=ϕ(Pij)
其中， ϕ ( P i j ) = max p ∈ P i j z ( p ) \phi\left(\mathcal{P}_{i j}\right)=\max _{\mathbf{p} \in \mathcal{P}_{i j}} z(\mathbf{p}) ϕ(Pij)=p∈Pijmaxz(p)
图1 Scan context 区域划分
疑问：因为再次回到同一位置时车道不一样而导致的scan context 行顺序不同。为了解决这个问题，将原始点云又放入 N t r a n s N_{trans} Ntrans邻域中，并将其与Scan context一起存下来。
–
3. 双层匹配算法与Scan Context相似度打分
论文中先讲了对scan context的相似度评分，而后因其计算量过大，无法对所有矩阵进行评分，故引入了中间描述子Ring Key。首先利用Ring Key进行候选帧的挑选，而后对scan context进行评分。
3.1 Ring Key
将scan context对行进行计算，从矩阵I（scan context）得到向量k，k中每一行表示该圆环区域中的占据率（非空区域与Ns的比值）。另外，通过k构建KD树，实现快速检索。
即，
k = ( ψ ( r 1 ) , … , ψ ( r N r ) ) ψ ( r i ) = ∥ r i ∥ 0 N s \mathbf{k}=\left(\psi\left(r_{1}\right), \ldots, \psi\left(r_{N_{r}}\right)\right) \\ \psi\left(r_{i}\right)=\frac{\left\|r_{i}\right\|_{0}}{N_{s}} k=(ψ(r1),…,ψ(rNr))ψ(ri)=Ns∥ri∥0
图2 Ring key示意图
这样，就可以根据阈值条件获取候选帧。
c ∗ = argmin c k ∈ C D ( I q , I c k ) , s.t D < c^{*}=\underset{c_{k} \in \mathcal{C}}{\operatorname{argmin}} D\left(I^{q}, I^{c_{k}}\right), \text { s.t } D< c∗=ck∈CargminD(Iq,Ick), s.t D<
3.2 评分
在获取到候选帧的基础上，分别进行评分，以获取最终匹配结果。对于当前帧Iq和候选帧Ic，其距离可以表示为。
d ( I q , I c ) = 1 N s ∑ j = 1 N s ( 1 − c j q ⋅ c j c ∥ c j q ∥ ∥ c j c ∥ ) d\left(I^{q}, I^{c}\right)=\frac{1}{N_{s}} \sum_{j=1}^{N_{s}}\left(1-\frac{c_{j}^{q} \cdot c_{j}^{c}}{\left\|c_{j}^{q}\right\|\left\|c_{j}^{c}\right\|}\right) d(Iq,Ic)=Ns1j=1∑Ns(1−∥∥cjq∥∥∥∥cjc∥∥cjq⋅cjc)
其中， c j q c_{j}^{q} cjq和 c j c c_{j}^{c} cjc是列向量。
然而，这里仍然有个问题，就是视角变换（偏航角的改变）会引起scan context中列向量的顺序，而行向量却不变（只有偏航角改变，只会在环向发生变化，相对距离不变）。
因此，采用遍历的形式。 这一步也是得益于利用Ring Key找出了较少的候选帧，减少了工作量。而这里的遍历分辨率，就是每个区域划分的分辨率，即 2 π N s \frac{2 \pi}{N_{s}} Ns2π。
D ( I q , I c ) = min n ∈ [ N s ] d ( I q , I n c ) n ∗ = argmin n ∈ [ N s ] d ( I q , I n c ) . \begin{aligned} D\left(I^{q}, I^{c}\right) &=\min _{n \in\left[N_{s}\right]} d\left(I^{q}, I_{n}^{c}\right) \\ n^{*} &=\underset{n \in\left[N_{s}\right]}{\operatorname{argmin}} d\left(I^{q}, I_{n}^{c}\right) . \end{aligned} D(Iq,Ic)n∗=n∈[Ns]mind(Iq,Inc)=n∈[Ns]argmind(Iq,Inc).
值得注意的是，该方法还能得到可以用于ICP初始化的偏航角信息，使ICP的速度和效果均有所提升。
4. 整体流程
对于单帧3D激光雷达，首先对其提取Scan Context描述子。在此基础上，利用Ring Key 描述子，通过KD树这一快速检索方式，找到最相似的候选帧，而后才将少数候选帧与当前帧进行相似度评分，检测是否回环。
- 出自论文：Modeling Perceptual Aliasing in SLAM via Discrete-Continuous Graphical Models ↩︎