Epipolar a personal journal

小软件:GifCam

GifCam | BahraniApps Blog

快速录屏制作GIF的小工具~类似的还有 http://www.screentogif.com/

Kalman Filter(三)

我们接着条件化 $z_k$ 。从之前得到的经过边缘化的最小二乘问题,我们加入 $z_k = \bar{z}_k$ 的条件,得到:

它的标准方程是

可以证明求解上述标准方程等价于 Kalman 滤波的更新迭代,我们这里不详细推导了。不过建议自己计算一下,在计算的过程中寻找到 Kalman 滤波对应的卡尔曼增益等相关系数。

结合前面几篇文章,我们实际上用另外一个思路进行了 Kalman 滤波。不难看出我们这个思路下许多计算与 Kalman 滤波原始的计算存在着比较大的差异。但是两种方法殊途同归。利用这里介绍的方法,可以设计另一种滤波的迭代策略,它通过跟踪标准方程的系数和常数部分来进行滤波,也被称为信息滤波(Information Filtering)。信息滤波中,如果进一步利用 LDL 分解的结构,可以设计出数值上更加稳定的平方根信息滤波(Square-Root Information Filtering, SRIF),这里就不再详细介绍了。

OpenGL 扩展:ARB 还是 EXT

OpenGL 有各种扩展,一些扩展 API 以 EXT 结尾,顾名思义就是 extension 的意思。另外有一些则是以 ARB 结尾,那么 ARB 是什么呢?

ARB 是 Architecture Review Board 的意思。在环顾了当前图形硬件的发展水平之后,如果某些扩展非常实用并且已经被广泛支持了,OpenGL 标准便会考虑在未来将这个扩展移入核心标准。中间作为一个过度,这个扩展便会带上 ARB 的记号(也就是钦点)。

基本上可以理解为 EXT -> ARB -> Core 的关系。

Gauge Ambiguity

在求解优化问题时,存在一种现象叫做 Gauge Ambiguity 。我们来看一个简单的例子:

假设在一条直线上有 $n$ 个质点,在直线上建立一维坐标系,用 $x_1, x_2, \dots, x_n$ 表示它们在这一坐标系下的坐标。现在用一把尺子测量任意两点间的距离,记 $x_i$ 点和 $x_j$ 点间的距离为 $d_{ij}$ ,每次测量带有相同的误差,且误差是零偏的。试求解每个点的坐标。

如果我们不假思索地开始写最小二乘,可以得到下面的目标优化:

但是且慢!稍微留心就可以发现:如果我们将所有的点沿着直线滑动相同的路程,这个目标优化的值不会受到任何的影响!

这种现象便叫做 Gauge Ambiguity ,是当优化变量关于外部坐标系定义,但优化能量本身与外部坐标系的选取无关时发生的现象。在这种情况下,对于任意一个最优解,我们总可以更换一下坐标系,于是就可以得到一个新的最优解。换句话说就是最优解并不唯一(有无限多)。

解决 GA 的最简单方法是采用一个与优化变量绑定的坐标系。例如上面的问题中,我们可以把 $x_1$ 定义为原点,这时就有 $x_1 = 0$ ,也就是我们固定了 $x_1$ 的值。此时剩余的变量上就不存在这个问题了(但是解还是有两个,互相镜像,这可以通过适当选取初始值来区分)。

那么在优化中,GA 会产生什么问题呢?以上面的问题为例,如果我们计算一下 $n=2,3,4$ 个质点的情形下对应的 Jacobian 就会发现发现:任何一个 Jacobian ,它的最后一列都等于左侧三列相加,这意味着每个 Jacobian 都是秩亏的。这便是 GA 带来的问题。一般来说,当我们总的变量数是 $n$ ,而外部坐标系的维度是 $k$ 时,问题的 Jacobian 的秩不大于 $n-k$ 。

前面我们介绍过,在 Jacobian 秩亏时,采用 LM 算法的最小二乘优化仍能鲁棒地收敛。然而此时算法采用的是最速下降步,这意味着算法的收敛速度会大打折扣。因此,如果在问题中存在 GA,应该首先尝试修改问题回避它,才能使优化更加高效。

Kalman Filter(二)

继续上文,我们来边缘化 $x_{k-1}$ 。我们将上文中优化的标准方程写出来:

边缘化 $x_{k-1}$ 对应于用 $Q_k^{-1}F_k(F_k^TQ_k^{-1}F_k+P_{k-1}^{-1})^{-1}$ 乘上第三行后加到第二行上。这么做之后,经过一系列(耐心的)整理后,可以得到下面的边缘化标准方程:

这里 是已知 $x_{k-1}$ 的概率分布时 $x_k$ 的后验概率分布的期望;而 是它的协方差。

如果将上面的式子左侧进行块状 LDL 分解并依此进行整理,我们可以发现这个边缘化标准方程对应了一个新的(边缘化)最小二乘问题:

这里的 是什么不妨自己根据前面的推导来观察一下。

此时,只要再条件化 $z_k$ ,我们就可以求解此时最优的 $x_k$ 了。不过在此之前我们先整理一下思路:

  • 我们知道了 $x_{k-1}$ 的分布;
  • 我们把 $x_{k-1}​$ 的分布利用边缘化“浓缩”进了 $x_k​$ 。

如果此后 $x_{k-1}$ 不再发生任何的改变,那么我们这种“浓缩”便是准确的。但是我们会看到,在很多问题里,我们会得到关于 $x_{k-1}$ 的新信息,这时这么做就会丢失掉这些有用的信息。这也是 Kalman Filter 的缺点,但是要想完全避免这个问题是很难的,也是研究的一个重点。