Scan Context——论文学习
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)
疑问：因为再次回到同一位置时车道不一样而导致的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
这样，就可以根据阈值条件获取候选帧。
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. 整体流程
-
出自论文：Modeling Perceptual Aliasing in SLAM via Discrete-Continuous Graphical Models ↩︎