[论文阅读]Scan Context: Egocentric Spatial Descriptor for Place Recognition within 3D Point Cloud Map

简介

位置识别 (Place Recoginition) 对于 SLAM 中的回环检测起到比较重要的作用。目前，基于 Lidar 的位置识别方案有以下几种：

比较早期的方案有：从计算机视觉中的 3D 模型移植来的基于传统的局部关键点描述子进行位置识别。而目前主要的工作集中在怎么点云中的结构化信息中构建局部和全局的描述子。作者认为这种方案有两个问题需要克服：

描述子需要有旋转不变性
由于点云中的分布，在距离和法向量都不均匀，因此空间描述子需要进行噪声处理

目前为了解决上面的问题，有很多基于直方图的方法。但是作者认为直方图类方法只提供了对场景的随机指标，对场景中的结构细节描述并不直观。基于此，作者提出了 Scan Context，主要包括空间描述子的定义方法和与之对应的匹配算法。论文的贡献主要有以下几点：

高效的 bin 编码函数：和目前的点云描述子不同，Scan Context 中提出的方法不需要计算每个 bin 中的点，而是有一个更高效的编码函数，而且这种编码对点云的密度和法向的变化不敏感
保存点云的内部结构
有效的两阶段匹配算法
相比于其他空间描述子而言性能更好

Scan Context 具体内容

基于 Scan Context 的位置识别方案整体流程如下图所示：

大概流程为：

对一帧点云先进行 SC（Scan Context）的计算
从该帧点云的 SC 中提取出一个 N 维的向量（和环数一致）用于在 KD 树中搜索相近的关键帧
将搜索得到的参考帧的 SC 和待匹配的当前帧进行比较，如果比较得分高于一定阈值则认为找到回环

Scan Context 定义

计算 SC 的主要过程为：

点云划分

将一帧 3D 点云按照传感器坐标系中的方位角和半径均匀划分不同的 bin，如上图所示，从方位角上看点云被划分成 $N_s$ 个扇面（Sector），从半径反向看，点云被划分成 $N_r$ 个环（Rings），每个扇面和环相交的部分为一个 bin。每个扇面和环的宽度（分辨率）可以从点云的最大检测距离和扇面/环数量计算得到。

从这种划分方式不难发现，距离较远的 Bin 相比于距离较近的 Bin 会稍微宽一点。这样划分的好处是可以自动对不同距离的点云密度进行动态调节。对于距离较近的地方通常点云密度会高一点，因此我们的 Bin 取窄一点，而相反，对于较远的地方，点云会比较稀疏。因此 Bin 取宽一点可以容纳更多点。

将每个环展开可以得到一个 $N_r\times N_s$ 的二维图像，每个像素点 $P_{ij}$ 是第 $i$ 个环第 $j$ 个扇面对应的 Bin，如上图 b 中所示。这就是 SC 的表现形式，因此下一步要做的就是每个 Bin 分配一个值 $\phi(P_{ij})$ 。

给每个 Bin 分配一个数作为标识，SC 中用每个 Bin 的点中最大的高度作为该 Bin 的标识，对于没有任何点的 Bin 则用 0 作为标识。即： $\phi(P_{ij}) = \max_{\boldsymbol{p}\in P_{ij}}z(\boldsymbol{p})$

从上图中不难看到，虽然 SC 在空间上来看是一个圆，应该有旋转不变性。但我们按照 $0 - 2\pi$ 展开成 2D 图像后，SC 对 Lidar 的朝向就变得敏感了。朝向稍微偏几度可能整体图像就有比较大的平移从而不相似了，为了解决这个问题，作者对图像进行 $N_{trans} = 8$ 次平移，通过这种方法来包含 Lidar 在不同朝向下的 SC。

不同的 Scan Context 的相似性比较

给定两个 SC，需要有一个方式来判断这两个地方的相似性。设 $I^q, I^c$ 为待比较的两帧点云的 SC。论文中用的方法主要是按列进行比较，对两个 SC 中的每一对对应的列向量（Column Vector）计算出一个距离，对一个列的距离方式维计算两个列向量之间的 cos 距离，整个 SC 的距离用各列的距离之和来表示。具体计算如下所示：

$$
d(I^q, I^c) = \frac{1}{N_s}\sum_{j = 1}^{N_s}\left(1 - \frac{c^q_jc^c_j}{||c^q_j||||c^c_j||}\right)
$$

这种距离计算方式对动态物体比较有效，因为考虑整个 Sector，而不是集中在单个 Bin 的影响。但同样的，这种距离方式对雷达的视角一致要求很高，哪怕在同一个位置雷达视角有一点点不同，可能计算出来的距离都会差别很大。为了解决这个问题，论文中使用的方式进行暴力匹配各个列组合的可能性（对其中一帧进行 $\frac{2\pi}{N_s}$ 次小旋转进行匹配），找出距离最小的组合。

两阶段搜索算法

目前主流方法中，在搜索相似帧中主要有三个主要流程：计算相似性、最近邻搜索、稀疏性优化。SC 方案中将计算相似得分和最近邻搜索结合成一步，有效降低了搜索时间。

由于，SC 中的距离计算相较于其他全局描述子较重，因此作者通过引入 Ring Key 提供了一个两阶段的层次搜索算法。Ring Key 是从 SC 中提取出来的一个旋转不变性的描述子。对 SC 中的每一行 $r$ 使用一个环编码函数 (Ring encoding function) $\psi$ 来分配一个值作为标识。然后每个环的值组合成一个 $N_r$ 维的向量作为 Ring Key。 $\psi$ 为：

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

简单来说，Ring Key 的计算方式，计算每个环（行）的密度（有值的像素除以总像素数），然后把不同环的密度组合在一起。显然这种方式提供了旋转不变性。因为无论 Lidar 怎么转只会造成图像平移，对每一行的密度不会有影响。

用 Ring Key 作为基准来进行比较比用 SC 本身更轻量，因此也更快。因此用每个帧的 Ring Key 构建 KD 树用来作为第一阶段搜索。然后对搜索出来的相似参考帧，再进行 SC 的比较，作为第二阶段搜索。最后 SC 距离最小的关键帧，如果距离小于一定阈值则认为找到相似帧

实验

TODO

结论

TODO

参考资料

Scan Context: Egocentric Spatial Descriptor for Place Recognition Within 3D Point Cloud Map