分类 Computer Vision 下的文章

RGB-D三维重建/SLAM方案整理


MonoSLAM

第一个实时的单目SLAM系统[1]。以EKF为后端,追踪前端稀疏的特征点。状态由相机运动参数和所有三维点构成,每个特征点的位置服从高斯分布,其概率偏差可以用一个椭球表示。

PTAM

PTAM[2]首次提出跟踪与建图的并行化;不同于[1]中使用的传统滤波器,PTAM首次在后端使用了非线性优化;引入了关键帧机制,不精细处理每一张输入图像,而是优化几个连续keyframe的轨迹和地图。

KinectFusion

RGB-D实时稠密重建的开山之作[3],掀起了基于消费级深度相机三维重建的研究热潮。以TSDF模型更新表面,tracking部分使用frame-to-model的策略进行ICP配准,抛弃了传统RGB重建中的核心--特征点。

VoxelHashing

用Volumetric fusion的方式重建时,空间被划分成voxel,重建范围大小收到显存大小限制。[4]提出只在场景表面划分voxel,并将其用哈希表存储,从而使大规模重建成为可能。

InfiniTAM

VoxelHashing的改进版本[5],速度更快并且可以在移动端实时运行。代码跨平台,各模块分离,易读且方便扩展,但是重建结果不带color。理论创新不是很大,更像是一个框架性的系统工程。

BundleFusion

为了解决大规模重建时相机轨迹的漂移,[6]引入了特征点,对输入的每一帧都会进行全局优化,修正过去已有帧的相机位姿,类似于Structure from Motion里的bundle adjustment,而不进行显式的loop closure检测。相应地,重建部分除了integration也有deintegration,根据优化后的历史帧相机位姿修正重建结果。其relocalization效果也十分惊艳。代码由VoxelHashing一脉相承,需要两块GPU才能实时,并且需要记录每一帧的信息,内存需求会随重建时间增长而增大。对比ICP为tracking的方法,其对于弱纹理场景无能为力。

To be continued...

参考文献

[1] Davison A J, Reid I D, Molton N D, et al. MonoSLAM: real-time single camera SLAM[J]. IEEE Trans Pattern Anal Mach Intell, 2007, 29(6):1052-1067.
[2] Klein G . Parallel tracking and mapping for small AR workspaces[C]// Proc. Sixth IEEE and ACM International Symposium on Mixed and Augmented Reality (ISMAR 2007), Nara, Japan, Nov. IEEE, 2007.
[3] Newcombe R A, Izadi S, Hilliges O, et al. KinectFusion: Real-time dense surface mapping and tracking[C]// IEEE International Symposium on Mixed & Augmented Reality. 2012.
[4] Nie?Ner M , Zollh?Fer M , Izadi S , et al. Real-time 3D reconstruction at scale using voxel hashing[J]. ACM Transactions on Graphics, 2013, 32(6):1-11.
[5] Prisacariu V A, Kähler O, Golodetz S, et al. InfiniTAM v3: A Framework for Large-Scale 3D Reconstruction with Loop Closure[J]. 2017.
[6] Dai A, Nießner M, Zollhöfer M, et al. BundleFusion: real-time globally consistent 3D reconstruction using on-the-fly surface re-integration[J]. Acm Transactions on Graphics, 2017, 36(4):76a.


A Fast Voxel Traversal Algorithm for Ray Tracing解析


简介

这篇文章[1]提出了一种用于光线追踪的三维体素遍历算法。[2]中voxel block的分配环节采用了该算法来计算和当前视角下的ray相交的block。算法本质上属于一种数值微分法(Digital Differential Analyzer, DDA),能够将离散数据模拟出连续的特性,举例来讲,一张图片由一组离散的二维点表示,要在上面画出一条斜线,则需要决定何时在X或Y方向上前进。该类插值问题可以通过DDA解决,记得本科的CNC这门课就有讲过DDA算法。

具体实现

首先考虑二维的情况,三维同理。请看下图,一个正确的遍历算法应该按照a, b, c, d, e, f, g和h的顺序访问各个体素。ray的方程为$\vec{u}+t\vec{v}, t>0 $。$u$实际上是ray的起点坐标,$v$为ray的方向,$t$则为每一步的步进长度。该遍历算法将ray以间隔为$t$的大小分割,分割后的每一段都横跨一个体素。我们从ray的起点开始按照顺序访问每个体素。
该图中ray的起始位置是block a。记此时的ray与第一条垂直线相交的$t$为$tMaxX$,和第一条水平线相交的$t$为$tMaxY$。若$tMaxX < tMaxY$,则在X方向上前进$stepX$,反之则在Y方向上前进$stepY$。$stepX$和$stepY$为+1或者-1,由$v$的方向决定,表示ray在当前block的位置在X或者Y方向上前进或者后退一个block。
继续以该图为例,ray的起点在block a,在点1处与第一条垂直线相交,在点2处与第一条水平线相交,此时$tMaxX < tMaxY$,所以在X方向上前进一个block,ray的位置则右移到达block b。以block b中ray的某点为起点,在点3处与第一条垂直线相交,在点2处与第一条水平线相交,此时$tMaxX > tMaxY$,所以在Y方向上前进一个block,ray的位置则上移到达block c。以block c中ray的某点为起点,在点3处与第一条垂直线相交,在点6处才与第一条水平线相交,此时$tMaxX < tMaxY$,所以在X方向上前进一个block,ray的位置右移到达block d。以此类推,依次遍历block e,f,g,h。
20171206094701216.png
文章中给出了二维和三维下的算法伪代码,这里就不列举了。

参考文献

[1] AMANATIDES, J., AND WOO, A. 1987. A fast voxel traversal algorithm for ray tracing. In Proc. Eurographics, vol. 87, 3–10.
[2] Nießner, Matthias & Zollhöfer, Michael & Izadi, Shahram & Stamminger, Marc. (2013). Real-time 3D Reconstruction at Scale using Voxel Hashing. ACM Transactions on Graphics (TOG). 32. 10.1145/2508363.2508374.
[3] voxel hashing解析


关于近期工作的一些看法与总结(一)


UAV+VR+Semantic 3D reconstruction,很明显三维重建是核心。目前结合语义的三维重建颇为冷门,仍处于探索阶段,有几个组已经做出了一些开创性工作,但在如何将传统重建方法更好的与DL、ML结合上还有很长的路要走。这个方向是一个趋势,是一片蓝海,而UAV和VR的介入,既是三维重建现实应用的体现,也为三维重建提供了一个工作载体。
以上是近期阅读文献的一些肤浅的感悟。在代码方面,voxel hashing的源码结构上着实有些复杂,读来略显吃力,抛却算法不谈,工程架构就很值得钻研学习,在此深感自身代码能力欠佳。从头复现有些难度,计算在移植到TX2的同时做一些简化,方便后续开发。
以上


OpenMesh简介


OpenMesh是一个通用的、高效的数据结构,用来表示和处理多边形网格(polygonal mesh)。它的设计遵循以下几个原则:

  1. 灵活:为不同的算法提供了通用基础,而不需要进行调整。
  2. 高效:在最大程度节省了时间的同时尽可能的降低内存使用。
  3. 易用:为处理复杂的内在结构提供了易用的接口。

特点

OpenMesh有以下特点:

  • 任意多边形的表示(通常情况)和三角网格表示(更加高效的、专门优化的)。
  • 明了的vertices、halfedges、edges和faces表示。
  • 快速的邻域访问,尤其是One-ring neighborhood
  • 高度可定制性:
    • 可选择坐标类型(维度和标量类型)
    • 为网格添加用户自定义的元素或函数
    • 在运行过程中用动态特性添加数据

halfedge数据结构

多边形网格包含几何(vertices)和拓扑结构(edges,faces)。多边形网格数据结构的主要区别在于存储拓扑信息的方式。基于面的结构缺少清晰的边的表示,基于边的结构因为丢失了边的方向导致效率低下,而半边结构克服了这些缺点。半边结构(使得边分成了不同朝向的两个部分)存储主要的连通信息:

这种方法表示出的点边面简单又直观。半边数据结构如上图所示,它将两点之间的边抽象成两条边,首先包含一个点,给定一个向量又能表示出这个点所在的面,同时还存储了指向的下个半边和对面的半边,下个半边可以认为是vertex的跳转,对面的半边则是face的跳转。半边结构还包含可选的前向半边。

重复(2-4)可以实现相邻节点的遍历。

实现

下图为OpenMesh各部分的交互。

该架构允许用户定义网格 ,用户可以为点边面制定任意的特性,或者为网格kernel选择预先定义的属性。kernel负责网格成员的存储,可以选择使用数组或双链表作为容器类型。因为不同属性的网格需要使用不同的C++类型,OpenMesh使用泛型编程实现网格的算法。类STL的方法有以下优点:

  • 非虚函数表和动态绑定
  • 没有内存和运行时开销
  • 输入数据是模板参数,在编译时