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

slam

slam

a collection / overriew / master / book / … of SLAM
/ slam methods / resources / projects / …!

#


slam

slam overriew

input

use one or more

  • laser scan / lidar
  • imu
  • odometry
  • visual rgbd / stereo / monocular
  • visual odometry
  • pointcloud
  • 3d pointcloud
  • ir
  • ultrasound

slam category

  • laser slam
  • visual slam
  • 3d slam
  • laser and visual slam
  • laser and odometry slam
  • laser and imu slam

output

  • occupancy grid map
  • pointcloud / 3d pointcloud / pointcloud map
  • odometry

further more

  • plan plan
  • path optimization
  • move
  • obstacle avoidance
  • loop closure

mapping

  • hector
  • gmapping
  • rtabmap

localization

  • amcl
  • gps (gps localization)
  • indoor localization

path plan

  • move base
  • path optimization
  • dynamic path

move

  • move base
  • obstacle avoidance
  • by controller

slam list


see also

related

mirror

quaternion

quaternion

什么是四元数

In mathematics, the quaternions are a number system that extends
the complex numbers.
They were first described by Irish mathematician William Rowan Hamilton in
184312 and applied to mechanics in three-dimensional space.
A feature of quaternions is that multiplication of two quaternions is
noncommutative.
Hamilton defined a quaternion as the quotient of two directed lines
in a three-dimensional space3
or equivalently as the quotient of two vectors.4

Quaternions are generally represented in the form:

where a, b, c, and d are real numbers,
and i, j, and k are the fundamental quaternion units.

相比欧拉角(euler angles) 四元数 (quaternion) 则是一种紧凑、易于迭代、
又不会出现奇异值的表示方法.
它在程序中广为使用, 例如 ros 和几个著名的 slam 公开数据集、
g2o 等程序都使用四元数记录机器人的姿态.
因此, 理解四元数的含义与用法, 对学习 slam 来说是必须的.

四元数仅是 3d 姿态的一种表达方式,
我们用一个单位四元数表达原本用旋转矩阵表示的三维旋转.
这样做一个直接的好处是省空间.
一个旋转阵有 9 个分量, 但只有三个自由度.
那么, 能不能用三个数来描述呢? 可以是可以的,
但不可避免会出现奇异的情况, 欧拉角就是一个例子.
而四元数, 比三维向量多了一个分量, 从而可以无奇异地表示各种姿态.

四元数是 hamilton 找到的一种扩展的复数.
一个四元数拥有一个实部和三个虚部
(故事上说他原先找了很久带两个虚部的, 结果怎么也找不到,
最后豁然开朗找到了三虚部的四元数):


其中 i, j, k 为四元数的三个虚部. 这三个虚部满足关系式:


where i, j, and k are basis elements of H,
determine all the possible products of i, j, and k.


All the other possible products can be determined by similar methods,
resulting in


由于它的这种特殊表示形式, 有时人们也用一个标量和一个向量来表达四元数:

这里, 标量 r 称为四元数的实部, 而向量 v 称为它的虚部.
如果一个四元数虚部为 0, 称之为实四元数.
反之, 若它的实部为0, 称之为虚四元数. 该定义和复数是相似的.

四元数可以表示三维空间中任意一个旋转. 与旋转矩阵中类似,
我们仍假设某个旋转是绕单位向量:


进行了角度为 θ 的旋转, 那么这个旋转的四元数形式为:

\(
\begin{equation} \label{eq:ntheta2quaternion}
\mathbf{q} = \left[
\cos \frac{\theta}{2},
n_x \sin \frac{\theta}{2},
n_y \sin \frac{\theta}{2},
n_z \sin \frac{\theta}{2}\right]^T
\end{equation}
\)

事实上 这还是一个模长为 1 的四元数 称为单位四元数.
反之 我们亦可通过任意一个长度为 1 的四元数 计算对应旋转轴与夹角:

\(
\begin{equation} \begin{cases}
\theta = 2\arccos {q_0}\\
{\left[{{n_x},{n_y},{n_z}} \right]^T} =
{{{\left[ {{q_1},{q_2},{q_3}} \right]}^T}}
/ {\sin \frac{\theta }{2}} \end{cases} \end{equation}
\)

对式 θ 加上 2π 我们得到一个相同的旋转 但此时对应的四元数变成了 -1.
因此 在四元数中 任意的旋转都可以由两个互为相反数的四元数表示.
同理 取 θ 为 0 则得到一个没有任何旋转的四元数:

\(
\begin{equation} \mathbf{q}_0 = \left[ { \pm 1,0,0,0} \right]^T \end{equation}
\)

see also and reference