多层语义地图

简介

《面向室内环境的智能机器人分层语义地图设计与实现》

1.引入

如同我们在科幻片中所看到的，在遥远的未来，机器人很可能将进入家家户户。 通过相机及其他传感器，机器人可以确认哪些空间是可通行的，哪些是被占据的或墙。 不过仅仅这样是不够的。

“萝卜！储存下你的当前坐标！移动，目标是x坐标10.32，y坐标13.25！转向135°方向！ 伸出你的第二机械臂，向x加0.5，y加0.45，z为0.7的目标！握住！收回机械臂！回到储存的上个坐标！”

这样就会很奇怪。

“萝卜！把桌子上的水杯给我拿来！”

这才是人们理想中的交互方式。

虽然人们很容易幻想到这一层，但实际实现起来还是很麻烦的，人工智能之父马文·明斯基有这么一句话吧。

In the fifties, it was predicted that in 5 years robots would be everywhere.

In the sixties, it was predicted that in 10 years robots would be everywhere.

In the seventies, it was predicted that in 20 years robots would be everywhere.

In the eighties, it was predicted that in 40 years robots would be everywhere.

-- Marvin Minsky

显然，最后这个四十年也结束了，机器人虽然开始在工业界和部分服务场景下使用， 但仍然不是日常生活中的常见物体（或许部分是被智能家居代替了），但和人们想象中的还差得远。

为了解决让机器人和人类正常交互的问题，人们在这些年间做了各种各样的努力，总的说是人工智能但也派生出了很多个不同的分支学科。 考虑如何获取、储存、易于使用的地图格式，就形成了语义建图这个方向。

2.历史研究

八九十年代，早期的地图表示就形成了。

1987年，学者A. Elfes就在IJRA上发表了一篇名为《Sonar-Based Real-World Mapping and Navigation》的文章， 其中给出了一个完整的，通过声呐获取周围环境信息，更新二维栅格地图，并在栅格地图中导航的完整方案。 该方法提出后就得到了广泛的应用，不过对复杂的需要处理三维占据情况的场景，该方法有着根本无法接受的空间开销。 后来的人们对空间栅格使用了八叉树来压缩。 另一个系列的方案是使用surfel（和pixel同样的构词法，surface element，指微小的表面片，无规范中文译名），因为和本文无关，暂且不提。 现在通常将这样表示底层测量信息的地图统称为尺度地图（metric map，这里metric是“度量的”的意思，部分文献翻译成米制地图其实不准确）。

栅格地图随着空间的增长成比例增大，进行导航时比较难进行有的放矢的加载，所以对于较大的环境是不适合的。 因此，导航任务天然地催生出了一种表示空间连接关系的稀疏地图，一般称为拓扑地图（topological map）。 表示空间的连接方式时，朴素的做法是按照拍照路径等距离选取结点构成一张图，但这样面临着地图直接被构建的具体过程细节影响的问题。 1995年，学者H. Choset在ICRA上提出了一个关于把视觉领域的Voronoi图的扩展到机器人地图中（广义Voronoi图，GVG）， 以表示空间的连接关系的方法。

然而这些方法都没有上面说的，存储房间和物体信息，一般称为语义信息的能力。

3.分层语义地图

人们不久后就想到了把拓扑地图的结点对应到房间、走廊、门这样的结构的策略，但是和上面的拓扑地图有一点冲突在于， 这个方法会过于稀疏化，导致难以足够精确地获取到尺度层的范围。 终于，2013年，学者I. Kostavelis发表了《Learning Spatially Semantic Representations for Cognitive Robot Navigation》一文， 接着2016年又发表了《Robot Navigation via Spatial and Temporal Coherent Semantic Maps》作为补充， 其中提出了一个具有四层的语义地图的结构及构建方式。 该地图中建立一个关于点的稠密地图，然后按照机器人行走路径等距离选取关键帧来构造拓扑地图， 然后再通过特征点支持向量机预测标签，结合临近相同标签结点得到一个场所地图（文中称为语义标注的拓扑地图(labeled topological map)）， 最后结合房间关联性构成一个房间地图（文中称为增广导航地图(augmented navigation map)）。

注意：

考虑工作量问题，本项目的输入是拼接好的点云及确认好的物体、房间，未实现逐帧的拼接； 对于如何通过仅输入相机位置和图像，拼接地图、检测物体并建立物体地图，见后续工作； 对于如何拼接点云、识别房间、利用其导航，是其他同学的工作。

4.论文中的方案

类似于上述方案，加上可能要考虑如何处理物体的问题，我们制作了一个三层地图。

1. 最底层是八叉树压缩的空间栅格地图。与上述论文中所述方法的区别是，因为使用的是拼接好的点云， 对每个点，不是更新从相机位置到反射为止的全部栅格的占据信息，而是只对反射点的栅格进行更新。
2. 中间层是拓扑地图。将栅格地图指定高度区间投影到平面上，然后提取其骨架。
3. 最上层是房间及物体的地图。要通过输入的已确认的房间和物体信息进行建立。

项目属性

语言：C++

定位：毕业设计。

目前状态：已结束（2018.12-2019.5）

代码：未公开

目前状态：按当时的需求，已结束。（2018.12-2019.5）后续工作见后续工作。

主要依赖：pcl（点云处理），Qt（仅用作界面），EVG-thin（已集成）。

地位：个人完成

系统架构

• 地图部分
  • 尺度地图（八叉树压缩的栅格地图）
  • 拓扑地图（GVG）
  • 语义地图（房间连通、物体所在房间）
• 界面部分
  • 可视化：用于展示三层地图。
  • 查询：关于当前使用的地图的列表查询方法。
• 输入输出部分
  • 点云加载
  • 文件化（持久化）：用于将现有地图写入文件或从文件中重新加载。

在以前的组会材料中找到的一张结构稿（图中不知道为什么没有语义层部分，应该只是做了一半的已完成部分）：

实际的结果有很多细化内容，大概是这个样子。

一些实现细节及运行截图

输入数据：

栅格地图

八叉森林结构：将空间划分为长宽高相等的网格，每个网格用一棵八叉树代表。 可以使用比指定分辨率倒数大的2的幂次的整数作为系数，取整后得到整数坐标，然后通过位运算确定子结点位置。 八叉树被初始化成只有根结点的形式，然后对于需要更新结点内容的写操作，通过查找子结点位置的过程进行结点的划分。 因为更新概率数据几乎不会遇到相等可合并的情况，所以在这种使用方式中可以不去尝试合并。

更新时对概率有相互独立假设，所以采取了ln-odds方式更新。 初始化时假定所有结点都是未占据的状态， （注意，这是因为在给定占据数据下，我们只能将结点向被占据更新。 栅格地图的原论文因为存在路径上向未占据更新的更新方式，其初始化假设是各半）， 更新结点内容时，将被占据的得分以正态分布分散到周围的结点中。

从这些要求中可以看到，栅格地图需要支持范围查询及范围更新操作。 实际上，考虑加入对投影视角展示和类似更新激光路径的支持，添加一些圆锥形搜索的方法更加有利，但这个没有做支持。

栅格地图展示

展示时按计算的概率进行了阈值化，所以不是所有沾边的栅格都会被标蓝。

学院楼走廊。

Navvis数据集的一组数据。

拓扑地图

将栅格地图投影到平面上，与指定高度范围有重合的作为无法通过路径，有占据数据无重合情况的视为可通过区域， 然后把它作为一张图像交给EVG-THIN提取骨架。

当然，EVG-THIN算法本身有会因占据噪点形成小圈和被未知区域吸引产生悬挂路径的问题，所以需要预处理。 我们采取的预处理方法是将已知已占据、已知未占据、未知这个三值数据处理成已知和已占据的二值图像，然后进行二值软形态学操作。 软形态学是对像素数稍稍放宽要求的普通形态学。 实际操作中，考虑到噪声点的分布特点，选择了在5×5的图像中，对已知情况进行1和25的闭运算，而对占据情况则选择8和17的软闭运算。

提取出图像的骨架后（标记为红色），为了处理成图，我们还需要把这个骨架转换为由顶点和边构成的图。 选择的方法如下：首先去除图像中2×2的红色团簇。其具体做法就是检测到这样的团块以后，尝试在保持4×4区域红色的连通性的条件下移除像素， 若无法移除，可以推知这个是仅有区域的中心和四角为红色这个特殊情况，此时对像素进行指定移动。 因为移动需要有至少一个移动到已检测区域，需要递归检测那边是否形成新的2×2团簇。

然后检查每个像素的m-相邻像素个数。1个或超过2个，就把它标记为蓝色，当作图的顶点，然后以每个顶点为起点， 对不跨过起点的m-相邻有色（红或蓝）像素建立新的边，直到遇到下一个蓝色结点为止。 穷举可能性可以知道，此时不会出现因复杂的像素变化导致遍历一条边时把另一条的像素遍历到的情况，因此一定能把全部有色像素都遍历到。

这样就可以建立完整的图。

拓扑地图展示

原始投影：

预处理后：

提取：

标注顶点后：

对于navvis数据：

这个是提高分辨率的实验：

一个显示的示例：

语义地图

在这个项目中，语义信息直接由外部输入，所以不需要进行获取。

语义地图展示

查询界面

查询引擎维护一个栈和一个数据源（输入指定地图和地图中查询的参数，返回封装的数据的函数）列表，每收到一个命令就会对这个栈进行一个操作。 From操作：选择数据。清空当前栈，运行数据源函数，将返回内容压栈。 Show操作：展示。弹出栈顶元素，将其交给展示窗口，并展示指定数目元素。 Filter操作：过滤。弹出栈顶元素，与字符串过滤函数一同封装再压栈。 Proj指令：投影。指定最后显示的列。 Push操作：用于调试时准备数据，直接压入指定字符串作为数据。

一个结果的示意，为了避免要显示的数据量过多，这里是16栅格/米，仅显示叶结点及阈值后的占据标签。

文件化模块

对于栅格地图，有原始浮点数据和标签二值数据两种，所以除了写入文件的头部不同，后面也分别使用不同的写入方案。 头部除了这个还要有八叉森林的数目信息等。 通过访问者模式可以很容易完成不同的串行化与不同的结点类型间的双dispatch。

对于拓扑地图和语义地图，因为其结点的一致性，就简单地写一个记录结点数边数的头部，后面保存其属性即可。

因为是二进制文件，也没办法展示，本部分没有展示方案。