octomap

octomap

#


overview

RGBD SLAM 的目的有两个:
估计机器人的轨迹 并建立正确的地图.
地图有很多种表达方式,
比如特征点云地图、网格地图、拓扑地图等等.
在程序中 根据优化后的位姿 拼接点云 最后构成地图.
这种做法很简单, 但有一些明显的缺陷:

  • 地图形式不紧凑.

点云地图通常规模很大 所以一个 pcd 文件也会很大.
一张 640 x 480 的图像, 会产生 30 万个空间点, 需要大量的存储空间.
即使经过一些滤波之后, pcd 文件也是很大的.
而且讨厌之处在于, 它的 大 并不是必需的.
点云地图提供了很多不必要的细节.
对于地毯上的褶皱、阴暗处的影子,
我们并不特别关心这些东西. 把它们放在地图里是浪费空间.

  • 处理重叠的方式不够好

在构建点云时 我们直接按照估计位姿拼在了一起.
在位姿存在误差时, 会导致地图出现明显的重叠.
例如一个电脑屏变成了两个, 原本方的边界变成了多边形.
对重叠地区的处理方式应该更好一些.

  • 难以用于导航

说起地图的用处 第一就是导航啦.
有了地图 就可以指挥机器人从 A 点到 B 点运动,
岂不是很方便的事?
但是 给你一张点云地图 是否有些傻眼了呢?
我至少得知道哪些地方可通过
哪些地方不可通过 才能完成导航呀! 光有点是不够的!

octomap 就是为此而设计的!
它可以优雅地压缩、更新地图 并且分辨率可调!
它以八叉树(octotree 后面会讲)的形式存储地图,
相比点云, 能够省下大把的空间.
octomap 建立的地图大概是这样子的: (从左到右是不同的分辨率)

由于八叉树的原因 它的地图像是很多个小方块组成的(很像 minecraft).
当分辨率较高时, 方块很小; 分辨率较低时, 方块很大.
每个方块表示该格被占据的概率.
因此你可以查询某个方块或点 是否可以通过
从而实现不同层次的导航.
简而言之 环境较大时采用较低分辨率
而较精细的导航可采用较高分辨率

OctoMap An Efficient Probabilistic 3D Mapping Framework Based on Octrees

The OctoMap library implements a 3D occupancy grid mapping approach,
providing data structures and mapping algorithms in C++ particularly
suited for robotics.
The map implementation is based on an octree and is designed to meet the
following requirements:

  • Full 3D model

The map is able to model arbitrary environments without prior assumptions
about it.
The representation models occupied areas as well as free space.
Unknown areas of the environment are implicitly encoded in the map.
While the distinction between free and occupied space is essential for safe
robot navigation,
information about unknown areas is important,
e.g., for autonomous exploration of an environment.

  • Updatable

It is possible to add new information or sensor readings at any time.
Modeling and updating is done in a probabilistic fashion.
This accounts for sensor noise or measurements which result from
dynamic changes in the environment,
e.g., because of dynamic objects.
Furthermore, multiple robots are able to contribute to the same map
and a previously recorded map is extendable when new areas are explored.

  • Flexible

The extent of the map does not have to be known in advance.
Instead, the map is dynamically expanded as needed.
The map is multi-resolution so that, for instance,
a high-level planner is able to use a coarse map,
while a local planner may operate using a fine resolution.
This also allows for efficient visualizations which scale
from coarse overviews to detailed close-up views.

  • Compact

The map is stored efficiently, both in memory and on disk.
It is possible to generate compressed files for later usage
or convenient exchange between robots even under bandwidth constraints.

Detailed information about the implemented approach and evaluations can
be found in the paper
“OctoMap: An Efficient Probabilistic 3D Mapping Framework Based on Octrees” (PDF)
(or get from this -> mirror)
published in the Autonomous Robots Journal.

The OctoMap library is available as a self-contained source distribution for
Linux (recommended), Mac OS and Windows.
It was developed by Kai M. Wurm and Armin Hornung,
and is currently maintained by Armin Hornung.
We would like to thank all additional authors for their contributions.


3d mapping with octomap

octomap_mapping(octomap_server) + ‘3d pointcloud'(stereo to 3d pcl)

sudo apt-get install ros-kinetic-octomap-mapping

more TODO


see and reference

octree

octree

An octree is a tree data structure in which each internal node
has exactly eight children.
Octrees are most often used to partition a three-dimensional space
by recursively subdividing it into eight octants.
Octrees are the three-dimensional analog of quadtrees.
The name is formed from oct + tree,
but note that it is normally written “octree” with only one “t”.
Octrees are often used in 3D graphics and 3D game engines.

#



Left: Recursive subdivision of a cube into octants.
Right: The corresponding octree.

八叉树 想象一下一个正方形的方块的三个面各切一刀 不就变成八块了嘛

实际的数据结构呢 就是一个树根不断地往下扩 每次分成八个枝 直到叶子为止.
叶子节点代表了分辨率最高的情况.
例如分辨率设成 0.01 m 那么每个叶子就是一个 1 cm 见方的小方块了呢

每个小方块都有一个数描述它是否被占据.
在最简单的情况下 可以用 0 1 两个数表示(太简单了所以没什么用).
通常还是用 0 ~ 1 之间的浮点数表示它被占据的概率.
0.5 表示未确定, 越大则表示被占据的可能性越高, 反之亦然.
由于它是八叉树, 那么一个节点的八个孩子都有一定的概率被占据或不被占据啦

用树结构的好处时: 当某个节点的子结点都 占据 或 不占据 或 未确定 时, 就可以把它给剪掉
换句话说 如果没必要进一步描述更精细的结构(孩子节点)时,
只要一个粗方块(父节点)的信息就够了.
这可以省去很多的存储空间. 因为我们不用存一个 全八叉树.

在八叉树中 我们用概率来表达一个叶子是否被占据.
为什么不直接用 0 1 表达呢?
因为在对环境的观测过程中 由于噪声的存在 某个方块有时可能被观测到是 占据 的
过了一会儿 在另一些方块中又是 不占据 的.
有时 占据 的时候多 有时 不占据 的时候多.
这一方面可能是由于环境本身有动态特征(例如桌子被挪走了),
另一方面(多数时候)可能是由于噪声.
根据八叉树的推导, 假设 t = 1, … ,T 时刻, 观测的数据为 z1, … , zT
那么第 n 个叶子节点记录的信息为:


(每新来一个就直接加到原来的上面)

八叉树中的父亲节点占据概率 可以根据孩子节点的数值进行计算.
比较简单的是取平均值或最大值. 如果把八叉树按照占据概率进行渲染,
不确定的方块渲染成透明的, 确定占据的渲染成不透明的, 就能看到我们平时见到的那种东西

see also and reference