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.


牢骚太盛防肠断


想了想,还是忍住没向社交网络上输出负能量,这玩意儿具有传染性。我不喜欢对别人要求太多,能够做好自己就实属不易了,见贤思齐,见不贤而内自省。有时候心态爆炸吧,冷静下来反思自己有些地方明明可以做的更好,那还有什么理由推脱和逃避呢?这个话题点到为止。

----------分割线----------

最近在看《少年维特之烦恼》和进击的巨人。前者给我的感受就是,love is blind,主人公对心上人的爱太过自我与自私,选择了最极端最不负责的方式把痛苦永远地留给了女主人公;后者,直接吹爆,相对于前两季的热血,第三季开始展现出来的恢弘庞大的世界观真的让我叹服,直接让这部作品变得严肃了起来,人物的形象也随着剧情的拨云见雾逐渐饱满。


Ceres solver简介


Ceres简介

Ceres Solver是谷歌的一个开源C++库,用于解决非线性优化问题,包括具有边界约束的非线性最小二乘问题和一般的无约束优化问题。在SLAM项目中Ceres用的非常多,港科大的VINS、谷歌的开源激光雷达SLAM项目Cartographer都有用到Ceres。Ceres的官方文档还是非常详细的,它的docs明确列举了这个库的features,这里就不一一赘述。

简单教程

非线性最小二乘问题

这里我简单搬运一下官方的tutorial。在很多领域,我们都会遇到如下形式的非线性最小二乘问题。
$$\begin{split}\min_{\mathbf{x}} &\quad \frac{1}{2}\sum_{i} \rho_i\left(\left\|f_i\left(x_{i_1}, ... ,x_{i_k}\right)\right\|^2\right) \\
\text{s.t.} &\quad l_j \le x_j \le u_j\end{split} \tag{1}$$
该类问题很常见,如统计学中的拟合曲线、基于图像的三维重建,三维重建的第一步Structure From Motion中的Bundle adjustment实际上就是个非线性最小二乘问题。
公式中的$\rho_i\left(\left\|f_i\left(x_{i_1},...,x_{i_k}\right)\right\|^2\right)$称作ResidualBlock,而$f_i(\cdot)$是关于参数向量$\left[x_{i_1},... , x_{i_k}\right]$的CostFunction 。$\rho_i$是LossFunction,它是一组标量,用于减少outliers对非线性最小二乘解的影响。

一个官方demo

考虑求函数$\frac{1}{2}(10 -x)^2$的最小值。很明显它在$x = 10$处有最小值。
Ceres第一步要求定义代价函数$f(x) = 10 - x$的functor,其代码如下:

struct CostFunctor {
   template <typename T>
   bool operator()(const T* const x, T* residual) const {
     residual[0] = T(10.0) - x[0];
     return true;
   }
};

方法operator()已经模板化了,这使得Ceres可以调用CostFunctor::operator<T>(),当需要残差的值时,T的类型为double,当需要Jacobians时,T的类型为Jet
之后使用代价函数$f(x)$,也就是上面的CostFunctor构建待求解的优化问题。

CostFunction* cost_function = 
      new AutoDiffCostFunction<CostFunctor, 1, 1>(new CostFunctor);

再配置求解器,设置如何求解、是否输出求解过程等参数,调用Solve方法即可得到结果。

int main(int argc, char** argv) {
  google::InitGoogleLogging(argv[0]);

  // The variable to solve for with its initial value.
  double initial_x = 0.5;
  double x = initial_x;

  // Build the problem.
  Problem problem;

  // Set up the only cost function (also known as residual). This uses
  // auto-differentiation to obtain the derivative (jacobian).
  CostFunction* cost_function =
      new AutoDiffCostFunction<CostFunctor, 1, 1>(new CostFunctor);
  problem.AddResidualBlock(cost_function, NULL, &x);

  // Run the solver!
  Solver::Options options;
  options.linear_solver_type = ceres::DENSE_QR;
  options.minimizer_progress_to_stdout = true;
  Solver::Summary summary;
  Solve(options, &problem, &summary);

  std::cout << summary.BriefReport() << "\n";
  std::cout << "x : " << initial_x
            << " -> " << x << "\n";
  return 0;
}

该例的输出为:

iter      cost      cost_change  |gradient|   |step|    tr_ratio  tr_radius  ls_iter  iter_time  total_time
   0  4.512500e+01    0.00e+00    9.50e+00   0.00e+00   0.00e+00  1.00e+04       0    5.33e-04    3.46e-03
   1  4.511598e-07    4.51e+01    9.50e-04   9.50e+00   1.00e+00  3.00e+04       1    5.00e-04    4.05e-03
   2  5.012552e-16    4.51e-07    3.17e-08   9.50e-04   1.00e+00  9.00e+04       1    1.60e-05    4.09e-03
Ceres Solver Report: Iterations: 2, Initial cost: 4.512500e+01, Final cost: 5.012552e-16, Termination: CONVERGENCE
x : 0.5 -> 10

这里发现官方文档有个问题,示例代码examples/helloworld.cc给出的迭代的初始值为$x=0.5$,而文档给定的初值为$x=5$,提供的结果却是$x=0.5$的,小问题还望大家注意。

PS

在编辑公式的时候发现一些坑,在此记录。我博客的公式是由MathJax在客户端上渲染出来的,然而Markdown会把LaTex的符号\当作转义符,造成公式显示错误。解决方法是公式中所有的\都写成\\,方法来自这篇文章。其实我测试的结果是并不是所有的\都要写两次,如果公式中有\begin\text这种符号前端就无法正确解析,需要将\写两次。对于Tex和Markdown之间的关系,我不甚了解,所以无法给出引起这个问题的结论。不过似乎\begin\text等是Tex独占的语法,Markdown原生并不支持,当然这只是我个人猜想而已,以后再去细究。


盘点个人最喜爱的周杰伦十大单曲-第十名


No. 10

梯田+爸我回来了 (2004无与伦比演唱会)

没错,第十名是一首现场版的作品,来自2004无与伦比演唱会。这首live根据《梯田》和《爸,我回来了》改编,从歌曲的立意上讲,前者的主题为环保问题,后者的主题为家庭暴力问题,都带有一定的批判意味。从音乐角度上讲,周杰伦在这两首快歌中结合了民族元素——在《梯田》的副歌部分,突如其来的台湾原住民风格的民声唱腔,惊为天人;在《爸,我回来了》的中,时不时穿插几句闽南语,透露出主人公的无奈与愤怒。两首歌的风格初听很令人感到怪异,而就是这种怪异的风格,在不失音乐性的情况下,完美结合了歌曲想要表达的人文关怀,这种情感表达大概不是其他风格所能驾驭的,给人一种极大的震撼,越听越有味道。值得一提的是,周杰伦亲自作词的这首《梯田》入围了当年的金曲奖最佳作词奖,一同竞争的作品包括方文山的《东风破》,没有了天马行空的华丽,自然与质朴也是闪光点。
单说这首live,第一句,日常即兴调侃方文山,随后是和CD版相同的《梯田》部分,直到2:20秒,梯田的伴奏渐隐,一段更加阴郁的打击感袭来,鸡皮疙瘩起来了……老周直接切到《爸,我回来了》的第二段主歌,此刻的rap相比CD版节奏上更加紧凑,语气更加强烈甚至暴力,好似一团怒火倾泻而来。当你还在回味那句“你叫我,怎么跟你像!”时,下一个高潮来了,开口即炸裂……

“Hoi Ya Yi Ya 那鲁湾 Na Yi Na Ya Hei————不要再这样打我妈妈!!!”

两首歌的无缝衔接,配合神一般的编曲,猝不及防却又让人大呼过瘾。然而你以为这就结束了吗?并没有!在《梯田》的和声中,一段全新的rap上线了。

我做音乐不是在举办辩论大会
辩论自己对音乐有多会
买的器材有多贵 炫耀自己有多可贵
我的音乐 你们排队
看演唱会 我说的对
我做得对 我的绝对 你会不会
会不会拿音乐来比来比去
那么爱笔 我就去便利商店买只笔给你
来比比比丘比 比丘比丘比丘比
比较来比较去 比较来比较去
比较来比较去 比卡丘

如果说《梯》和《爸》两首是周杰伦基于大众角度对社会问题的思考,这段即兴则纯粹是他个人内心情感的宣泄。是的啊,金曲奖铩羽而归,媒体日常批评“周郎才尽”,作品总是被拿去和别人比较,对于自己音乐自信到自负的周杰伦怎么会甘心示弱呢?这是对外界质疑最有力的回应。
在这首live的末尾,老周吹奏着笛子又一次炸场……《梯田》的和声并没有间断,笛声却完全占了上风,婉转悠扬,却又是另一种诉说。笛声褪去,一个充满才华和灵气的音乐作品诞生了。
请输入图片描述


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解析