牢骚太盛防肠断


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

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

最近在看《少年维特之烦恼》和进击的巨人。前者给我的感受就是,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解析