Researchers Announce Advance in Image-Recognition Software

Notes on Conjugate Gradient Method

版权声明：原创作品，欢迎转载，但转载请以超链接形式注明文章来源(planckscale.info)、作者信息和本声明，否则将追究法律责任。

这是一个关于共轭梯度法的笔记。请大家注意的是，这是个笔记，并不是一个教程，因此少不了跳跃和欠解释的地方。对CG方法了解不多的同学请移步这里。

线性方程组和极小化问题

一个关于对称矩阵 $A$ 的线性方程组 $Ax=b$ 等价于求解如下极小值问题：

$f(x) = \frac{1}{2} \transp{x} A x - \transp{b} x$

这很容易说明，我们微分目标函数得

(1) $\begin{eqnarray*} \td f &=& \frac{1}{2}(\td\transp{x}Ax+\transp{x}A\td x)-\transp{b} \td x\\ &=& \transp{(Ax - b)} \td x \end{eqnarray*}$

所以 $\td f=0$ 意味着 $Ax=b$ .

设 $x^*$ 为问题的解， $e$ 为偏离极小值点的位移，即

(2) $\begin{eqnarray*} Ax^*&=&b\\ e&=&\Delta x=x-x^* \end{eqnarray*}$

我们定义残差或负梯度 $r=b-Ax$ ，容易看出， $r$ 正比于偏离梯度零点 $x^*$ 的位移 $e$ :

$r=-Ae$

最速下降法和共轭梯度法简述

最速下降法：搜索方向为本轮迭代初始点的梯度方向，搜索到梯度与搜索方向正交的位置开始下一轮迭代。

共轭梯度法：搜索方向为本轮迭代初始点的梯度方向（残差方向）用A-内积做正交化，扣除掉之前所有搜索方向的分量给出，搜索到梯度与搜索方向正交的位置开始下一轮迭代。

共轭梯度法的理解

首先考虑一个简单情形，即A=I时。此时f退化，且x的不同分量解耦，f的极小值问题分解为各分量上的极小值问题。我们只需要在各分量方向上找到极小值，问题就得解了。具体的说，我们从任意一个初始点出发，在方向 $d_0$ 上寻找极小值，然后从这个极小值出发继续在 $d_1$ 寻找 $d_1$ 方向的极小，以此类推最后到达全局极小值。

A为正定对称矩阵的一般情形，其实只是上述情形中的x表述在一个新坐标系下的结果（下文详细解释）。为了求解这种情形，我们考察上述方法的求解轨迹在新坐标系里的对应。

首先，A=I时的各个正交搜索方向在新坐标系里对应着一组A-正交的方向，因此我们需要设法找出这样一组正交方向，然后各自求解这些方向上的极小值。

求解特定方向上极小值的方法不变，极小点就是这个方向上梯度正交于搜索方向时的点（原因很简单，这说明搜索方向上梯度分量为零）。

最后一点，如何找到这样一组A-正交方向？

一般方法是找一组现成的完备基，进行A-正交化。问题是计算量比较大。

记迭代到第i步时，所搜索过的这样一组A-正交的搜索方向单位矢量为 $\{d_0,d_1,...,d_{i-1}\}$ ,它们撑起的子空间

(3) $\begin{eqnarray*} D_i=\mathrm{span}\{d_0,d_1,...,d_{i-1}\} \end{eqnarray*}$

即第 $i$ 步前已经搜索过的子空间。

共轭梯度法的一个关键之处在于它可以从每次迭代的 $r_i$ 中快速构造出新的搜索方向 $d_i$ ，而不需要对 $r_i$ 进行完整的正交化手续（即不需依次扣除 $r_i$ 中 $d_0$ , $d_1$ … $d_{i-1}$ 方向的分量）。原因在于 $r_i$ 自然的和 $D_{i-1}$ A-正交，因此构造 $d_i$ 只需要从 $r_{i}$ 中扣除掉 $d_{i-1}$ 分量即可。

因此，共轭梯度算法有两处关键，一处为通过利用A-正交关系来把搜索问题转换到一个特殊坐标系，使得各搜索方向上的极小值问题解耦；一是利用 $r_i$ 和 $D_{i-1}$ 是A-正交的这一规律来充分简化A-正交搜索方向的构造。

接下来我们详细论证这个算法。

第一个关键点，坐标变换和子问题解耦

设

(4) $\begin{eqnarray*} A&=&\transp{T}T\\ y&=&T x\\ b^{\prime}&=&T^{-T} b\\ \end{eqnarray*}$

其中 $T^{-T}$ 表示矩阵 $T$ 求逆后做转置，很拗口，不过这个不重要。

于是我们有

(5) $\begin{eqnarray*} f(x) &=& \frac{1}{2} \transp{y} y - b^{\prime T} y\\ &=& \frac{1}{2}\sum_{n}y_n^2 - b^{\prime}_n y_n \equiv \frac{1}{2}\sum_{n} P_n(y_n) \end{eqnarray*}$

可见 $f$ 已经被分解为一系列独立的子问题 $P_n(y_n)$ ， $T$ 正是将问题解耦所用的坐标变换。

在新的 $\{y_n\}$ 坐标系中，整个极小值问题可以通过在一组正交方向上依次寻找极小点来解决。但求解 $T$ 需要对 $A$ 做分解，并非一个计算上经济的解决方法。这一个变换的真正意义在于，我们可以通过它来找到求解轨迹在 $\{x_n\}$ 坐标系中的对应。

$T$ 是线性变换，因此 $\{y_n\}$ 中的一组直线仍被变换为 $\{x_n\}$ 中的一组直线。 $\{y_n\}$ 坐标系中，我们依次沿着一组正交方向求解极小值，因此只需要找到这组方向在 $\{x_n\}$ 坐标系中的对应（一组未必正交的方向），就可以等价的直接在这组方向之上寻找极小值，而不需要经过坐标变换。

考虑这组正交方向单位矢 $\{y_n\}$

(6) $\begin{eqnarray*} &&\transp{y_i} y_j = \delta_{ij}\\ &\Leftrightarrow& \transp{(T x_i)} T x_j=\delta_{ij}\\ &\Leftrightarrow& \transp{x_i} \transp{T}T x_j = \delta_{ij}\\ &\Leftrightarrow& \transp{x_i} A x_j = \delta_{ij} \end{eqnarray*}$

可见， $\{y_n\}$ 这一组正交的方向在变换到 $\{x_n\}$ 坐标系中后，虽然不是 $\{x_n\}$ 中通常意义的正交矢量组，却可以在A-内积 $\langle \bullet,\bullet \rangle_A$ 意义下成为一组A-正交矢量。这里的A-内积，指的是以对称矩阵 $A$ 定义的内积运算

(7) $\begin{eqnarray*} \langle a,b \rangle_A \equiv \transp{a} A b \end{eqnarray*}$

需要注意的是，上述结论是可逆的，如果 $\langle x_i,x_j \rangle_A = 0$ ,同样也可以得出， $x_i,x_j$ 对应着 $\{y_n\}$ 坐标系中两个正交的方向。因此，可以直接在 $\{x_n\}$ 坐标系下，寻找一组A-正交的方向，然后在这一组方向上依次极小化目标函数，就可以找到整个问题的极小值。

第二个关键点， $D_i$ 子空间结构和正交关系

算法的更新规则为

(8) $\begin{eqnarray*} e_{i+1}&=&e_i + \alpha_i d_i\\ r_{i+1}&=&-A(e_i+\alpha_i d_i)=r_i-\alpha_i A d_i\\ d_{i}&=&r_i + \sum_{j<i} \beta_{ij} d_{j}\\ \beta_{ij}&=& - \frac{\transp{r_i}d_j}{\transp{d_j}Ad_j}\\ &=& - \frac{\langle r_i,d_j \rangle }{\langle d_j,d_j \rangle _A} \end{eqnarray*}$

其中 $\alpha_i$ 为第 $i$ 步搜索方向上的位移长度，它的大小可以通过 $r_{i+1}$ 应该和 $d_i$ 正交这一要求定出

(9) $\begin{eqnarray*} &&\transp{r_{i+1}}d_i=0\\ &\Rightarrow&\transp{(e_i+\alpha_i d_i)} A d_i =0\\ &\Rightarrow&\alpha_i = - \frac{\langle d_i,e_i \rangle_A }{\langle d_i,d_i \rangle_A}= \frac{\langle d_i,r_i \rangle}{\langle d_i,d_i \rangle_A} \end{eqnarray*}$

算法将参数空间划分成了一个层级结构，下面我们来看看这个结构的性质。

根据上述更新规则，可以发现 $D_i$ 可以由另外几个矢量组撑起。首先，由 $d_i$ 的更新规则可以发现， $d_i$ 由 $r_i$ 和 $d_{j<i}$ 线性组合而成，另一方面，我们有初始条件 $d_0=r_0$ ，归纳而知， $d_i$ 可以由 $\{r_{j\leq i}\}$ 线性组合出来。于是我们有

(10) $\begin{eqnarray*} D_i=\mathrm{span}\{r_0,r_1,...,r_{i-1}\} \end{eqnarray*}$

接着我们考虑 $r_i$ 的更新规则。可以看到， $D_{i+1}=\mathrm{span}\{D_{i},Ad_i\}$ .于是我们可以从 $D_1=\{d_0\}$ 或 $D_1=\{r_0\}$ 构造出 $D_i$

(11) $\begin{eqnarray*} D_i&=&\mathrm{span}\{d_0,Ad_0,A^2d_0,...,A^{i-1}d_0\} = \mathrm{span}\{d_0,A D_{i-1}\}\\ &=&\mathrm{span}\{r_0,Ar_0,A^2r_0,...,A^{i-1}r_0\} = \mathrm{span}\{r_0,A D_{i-1}\} \end{eqnarray*}$

接下来我们再考虑各子空间和向量之间的正交关系。首先， $e_i$ 在 $D_i$ 的补空间里。这点是明显的，因为每一个优化步都会优化掉 $e_j$ 在相应 $d_j$ 方向上的分量，因而剩余的 $e_i$ 就只位于 $D_i$ 的补空间里。于是我们有

(12) $\begin{eqnarray*} e_i = \sum_{j \geq i} \delta_j d_j \end{eqnarray*}$

这样 $e$ 和 $d$ 之间的A-正交关系就很明显了。由于 $\langle d_i,d_j \rangle_A = \delta_{ij}$ ，而 $e_i$ 只包含 $d_j>i$ 分量，因而

(13) $\begin{eqnarray*} \langle e_i,d_{j<i} \rangle_A =0 \end{eqnarray*}$

即 $e_i$ 和子空间 $D_i$ 也是A-正交的。这意味着 $r_i$ 正交于 $D_i$

(14) $\begin{eqnarray*} &&\transp{e_i} A d_{j<i}=0\\ &\Rightarrow&\transp{(A e_i)} d_{j<i}=0\\ &\Rightarrow&\langle r_i,d_{j<i}\rangle =0 \end{eqnarray*}$

到这里就可以解释为什么我们有 $\langle r_i,d_{j<i-1} \rangle_A =0$ 了：

(15) $\begin{eqnarray*} &&\langle r_i,D_i \rangle =0\\ &\Rightarrow&\langle r_i,\mathrm{span}\{d_0,A D_{i-1}\} \rangle =0\\ &\Rightarrow&\langle r_i,A D_{i-1} \rangle =0\\ &\Rightarrow&\langle r_i,D_{i-1} \rangle_A =0 \end{eqnarray*}$

至此我们完成了第二个关键点的论证，且更清楚的了解了参数空间，尤其是 $D_i$ 子空间的结构。

图像拼接算法原理 1

2 Replies

版权声明：原创作品，欢迎转载，但转载请以超链接形式注明文章来源(planckscale.info)、作者信息和本声明，否则将追究法律责任。

前置广告：多路视频实时全景拼接Demo可见我们的视频主页。

0. 引言

图1,2,3. 两张图片的拼接

图像拼接是计算机视觉中一个有趣的领域，它把来自多个不同视角相机的图像变换到同一视角下，无缝拼接成一张宽视野图像（比如360度全景图，甚至360度*180度的球面全景）。上图所示，即为两张图像的拼接，结果基本是完美的。

需要注意的是，由于相机各自的指向角度不一样，因此两图片中来自同样场景的部分并不能够通过平移图像而完全重合。比如上图中那栋带有岭南风格拱顶的房子，它的屋檐在左图中要比右图中更水平些，如果试图通过平移对齐像素来拼接两幅图，结果必然不自然（比如在屋檐处出现拐角）。两图要做到完美叠合，不是一个平移变换能做到的。当然，肯定存在这样一个变换，那它是什么呢？

事实上这里边的数学原理（射影几何）很古老，什么情况下不同位置、视角的相机可以变换到同一视角下拼接起来也是久为人知的，只不过能够利用计算机来进行大规模自动拼接，还是近些年才成熟起来的事。

那到底什么情况下图像可以拼接，如何拼接呢？不妨先摆出结论吧：在两种情况下图像可拼接，一是各相机几何中心重合；二是各相机位置任意，但场景是一个平面。一种特殊情况，场景为远景时，可以近似的等价于一个平面场景，从而也是可拼的。拼接的方法很简单，在满足上述两种情况之一时，存在一个单应性变换（Homography），能够将一个相机的图像变换到另一个相机的视角下从而可以进行拼接。

下面我们用一套直观的语言来讲解这个变换，以及更复杂些的拼接方法。

1. Homography

图 4. 单应性变换

如图，计算机视觉中，我们用一个投影中心点和一张图像平面来刻画一个理想的相机。点与平面的距离为焦距，任意场景点所成像点用这样一种简单的方式来决定：将它与投影中心连线，连线与图像平面的交点即像点位置。图中给出了两个共中心的相机，它们有不同的指向（因而也有不同的图像平面 $P$ 和 $P^{\prime}$ ），同一场景点 $S$ 在两个平面上的像点由紫线与两平面的交点 $D$ 、 $D^{\prime}$ 给出。到这里我们就直观的得到了这样一个变换： $P$ 上像点到 $P^{\prime}$ 上对应像点的一个映射。这个映射可以把两张不同视角下拍摄的照片变换到同一视角下，从而能够完美拼接两张图像。这个映射正是我们要说的单应性变换。

到这里我们可以回头来解释另一个问题，为什么要求相机共中心？不妨反过来考虑，如果两相机不共中心，会出现什么样的情况？如图所示，

图 5. 单应性的破坏

我们让两相机的投影中心 $O$ 、 $O^{\prime}$ 相离。这时可以看到， $S_1$ 、 $S_2$ 两点原本在相机 $O$ 上投影到同一像点，这时在相机 $O^{\prime}$ 上却投影到了不同像点。这意味着相机 $O^{\prime}$ 看到了在 $O$ 视角下被遮挡而看不到的内容，此时我们无法把 $O^{\prime}$ 看到的图像变换到 $O$ 的视角下。考虑一个极端情形可以进一步解释这个问题：如果两个相机分别拍摄同一物体的正面和背面，那它们所看到的内容无论如何也不能变换到同一视角之下，或者说，我们根本找不到这样一个新的相机，在它的视角之下可以看到 $O$ 、 $O^{\prime}$ 二者所看到内容的总和。这就解答了我们之前的问题：非共中心放置时，各相机看到的内容太丰富以至于不能变换到同一视角下。读者可以检查，在相机共中心时，一个相机中被投影到同一像点的场景点，总会在另一相机中也被投影为同一像点。

事实上，在相机摆位任意时，我们看到的信息是如此丰富，以至于可以尝试重建出场景点的三维坐标。现代的三维重建算法可以利用不同位置、视角下拍摄的图像重建出物体的三维模型，这是后话。

当然，读者仍然可能想起，除掉共中心情形，我们还说过，相机摆位任意，但场景为一个平面时也是存在单应变换的。我们在这里不再给出这种情况的直观解释，读者可以自己思考。

（未完待续）

Hello world!

1 Reply

Welcome to WordPress. This is your first post. Edit or delete it, then start blogging!

Mind Spectrum

Formerly Singularity Vision

Researchers Announce Advance in Image-Recognition Software

Notes on Conjugate Gradient Method

版权声明：原创作品，欢迎转载，但转载请以超链接形式注明文章来源(planckscale.info)、作者信息和本声明，否则将追究法律责任。

线性方程组和极小化问题

最速下降法和共轭梯度法简述

共轭梯度法的理解

第一个关键点，坐标变换和子问题解耦

第二个关键点， $D_i$ 子空间结构和正交关系

图像拼接算法原理 1

版权声明：原创作品，欢迎转载，但转载请以超链接形式注明文章来源(planckscale.info)、作者信息和本声明，否则将追究法律责任。

前置广告：多路视频实时全景拼接Demo可见我们的视频主页。

0. 引言

1. Homography

Hello world!

版权声明：原创作品，欢迎转载，但转载请以超链接形式注明文章来源(planckscale.info)、作者信息和本声明，否则将追究法律责任。

线性方程组和极小化问题

最速下降法和共轭梯度法简述

共轭梯度法的理解

第一个关键点，坐标变换和子问题解耦

第二个关键点，子空间结构和正交关系

版权声明：原创作品，欢迎转载，但转载请以超链接形式注明文章来源(planckscale.info)、作者信息和本声明，否则将追究法律责任。

前置广告：多路视频实时全景拼接Demo可见我们的视频主页。

0. 引言

1. Homography

第二个关键点， $D_i$ 子空间结构和正交关系