估计2D投影矩阵

本章主要估计这么几种2D投影矩阵

2D齐次矩阵, 就是从一个图像中的点到另外一个图像中的点的转换, 由于点的表示都是齐次的, 所以叫其次矩阵.
3D到2D的摄像机矩阵
基本矩阵
三视图之间的转换矩阵(这个可以略过)

形式化的表示, 我们已知 $x_i \leftrightarrow x'_i$ , 我们需要计算一个 $3 \times 3$ 的 $H$ , 满足 $x'_i=H x_i$

需要多少对点 $H$ 是 $3 \times 3$ 那么就是8个自由度, 所以最少4对点

估计算法的种类 我们考虑到图像中的对应点都是由噪声的, 那么只有4个点其实估计的结果就不准确了, 如果我们找出多于4对点, 那么我们就需要一个损失函数, 并且把它最小. 下文介绍的主要分成2类, 一类是代数误差, 一类是几何误差.

黄金标准算法 黄金标准算法不是一个具体的算法. 他是一个评判标准. 通俗来讲:假设我们有n个损失函数, 哪一个是最好的? 让 $H$ 能达到最小的损失函数就是最好的. 那么哪个损失函数让 $H$ 最小? 在"估计2D投影矩阵"这个问题里, 最好的损失函数就是书中4.8式. 优化最优损失函数的算法就叫黄金标准算法(p114 4.3), 其他损失函数给出的结果都是和4.8式的结果来比较的.

4.1 求解线性方程组算法(DLT)

原理很简单,既然 $x'_i=Hx_i$ , 那么就可以建立方程 $x'_i \times Hx_i=0$ , 把这个式子改写成 $Ah=0$ , 找4对点解方程就行(SVD)

4.1.1 超定的情况

假设说我们找出了多余4对点, 那么怎么利用上多出来的信息? 我们考虑到点都是有噪声的, 那我们可以考虑最优化一个目标函数, 最直观的想法就是优化 $Ah$ ,同时满足 $||A||=1$ ,

4.1.2 非齐次坐标表示下的解法

这个解法不稳定, 因为是非齐次坐标, 丢失了尺度这个因子. 所以我们就略过

4.1.3 退化的情况

我们说,如果 $x_1,x_2,x_3$ 共线且 $x'_1,x'_2,x'_3$ 也共线, 那么 $H$ 的解不是唯一的. 如果 $x_1,x_2,x_3$ 共线但是 $x'_1,x'_2,x'_3$ 不共线, 这种情况下 $H$ 不存在, 但是我们用上述方程确实可以解出来一个 $H$ , 那么这个 $H$ 是啥?代表啥? 书中给出的答案是, $H$ 是一个奇异矩阵, 根本不代表任何映射.

4.1.4 由线段和其他几何实体找对应

除了点对应, 我们也可以找线对应. 比如我们可以用线对应来构造一个方程 $l_i = H^T l'_i$ . 那么如果用线对应, 需要找多少对对应线? 我们需要的约束应该多于 $H^T$ 的自由度. 所以4对对应线足够了 (每一对是2个约束). 如果我们考虑三维空间, 一对对应点提供3对约束, 那么求解三维 $H$ 用5对对应点就够.

但是如果我们把点和线混合起来就要小心. 比如说两对对应点和两对对应线是不能确定 $H$ 的, 得3对对应线和1对对应点. 因为2对对应线就是4条,它相当于五条线加四个共线的点,间p93 图4.1,三对对应线构成一个三角形, 他不会出现共线的情况.

4.2 其他的损失函数

4.2.1 代数距离

既然 $x'=Hx$ , 那么我们可以优化 $x'$ 和 $Hx$ 的距离

4.2.2 几何距离

几何距离考虑的是理论点与实际点的误差

我们先考虑第二个图像,假设第一个图像上的点都是准确的, 我们用 $\bar{x}$ 来表示, 那我们就可以来优化

\Sigma d(x'_i,H\bar{x})^2

我们把这个式子推广到第一幅图像, 就可以得到

\Sigma d(x_i,H^{-1}x'_i)^2 + d(x'_i,Hx_i)^2

也就是第1幅图像的点变换到第二幅图像, 他们需要尽可能靠近. 反过来第2幅图像的点变换到第1幅图像, 他们也需要尽可能靠近.

4.2.3 重投影误差

讲这个概念以前, 我们需要一个概念, 就是理论上完美的点, 书中用 $\hat{x}$ 表示. 首先我们要知道理论完美点不是 $\bar{x}$ , $\bar{x}$ 就是机器学习里的ground truth. 是不存在误差的. $x$ 是我们知道的点, 是有噪声的. 那么我们用 $x,x'$ 估计出一个 $H$ , $Hx$ 肯定不等于 $x'$ . 但是我们可以找出一对 $\hat{x},\hat{x}'$ ,他们可以完美的满足 $\hat{x}=H\hat{x}'$ , 注意, $H$ 是从有噪声的数据里估计出来的, 而不是从 $\bar{x}$ 种估计出来的.

根据这个思想, 我们可以去寻找一个 $\hat{H}$ 和一对 $\hat{x},\hat{x}'$ , 他们之间满足 $\hat{x}=H\hat{x}'$ , 然后让 $x,x'$ 靠近 $\hat{x},\hat{x}'$ . 这其实是先从 $x,x'$ 估计出一个三维空间点, 然后再往图像上投影, 所以叫重投影.

4.2.4 代数误差与几何误差之间的关系

一句话总结, 他们之间差一个常数因子, 该常数因子由 $x'$ 的第三维坐标和 $\hat{x}'$ 相乘得到.

4.2.5 重投影误差的几何含义

一句话概括重投影误差相当于在4维空间中拟合一个平面. 通俗解释我们可以把 $x,x'$ 的坐标拼在一起, 得到 $X=(x_i,y_i,x'_i,y'_i)$ 然后把 $\hat{x},\hat{x}'$ 的坐标拼在一起, 得到 $\hat{X}=(\hat{x_i},\hat{y_i},\hat{x_i}',\hat{y_i}')$

那么 $||X-\hat{X}||^2$ 就是重投影误差

以上思想还可以被用来拟合圆锥, 假设说我们要拟合圆锥 $C$ , 找5个点直接解圆锥方程很很麻烦, 因为不是线性的. 那么我就求点到 $C$ 的距离, 让他们加起来最短,就可以了

4.2.6 sampson误差

其主要思想是用泰勒公式把要拟合的几何体展开到1阶, 让它余项等于0

4.2.7 对求解 $H$ 的另外一种几何解释

上文说了求解 $H$ 相当于在4维空间中拟合一个平面. 那么本节给出在n维度量空间中的几何解释. 求解H相当于在n维度量空间中找出一个和 $X$ 最接近的向量. 可以想象4维空间的平面在n维就成了点.

4.3 最大后验概率求解

我们知道图像中都会包含噪声, 如果我们认为噪声服从高斯分布, 那么我们就可以用高斯分布然后求解最大后验概率

比方说, 我们可以构造以下式子

P(x)=(\frac{1}{2 \pi \sigma^2}) exp(d(x,\bar{x})^2)/2 \sigma^2

其中 $d$ 可以换成任何你喜欢的距离, 然后求解最大后验概率就可以

4.4 DLT算法中的不变量与正则化

4.4.1 坐标原点

图像原点有时候在左下角,有时候在右上角, 那么不同的原点对DLT算法有啥影响吗? 答案是有的, 对几何损失函数是没有影响.

那么我们有这样的结论, 假设有一个相似变换 $T$ , 变换前的点 $x$ 计算出的 $H$ , 和变换后计算出的 $H'$ 之间,相差一个倍数. 也就是矩阵的向量之间相差一个倍数.

4.4.3 几何损失函数的不变量

前文说了, 几何损失函数在相似变换下保持不变.

4.4.4 对点坐标的归一化

首先我们明确为啥要对点坐标归一化, 因为有的点坐标很大, 有的很小, 那么用SVD求解出来的答案会有很大的误差.

那么怎么归一化? 先把所有点的质心旋转到原点, 然后让缩放所有点, 使所有点到原点的平均距离等于 $\sqrt{2}$ , 也就是让所有点的平均值等于 $(1,1,1)$

需要明确的是, 归一化的必须的不是可选的

4.5 迭代最优化

本节讲述如何用迭代的方法优化几何损失函数. 书中114页给出了一个案例, 我们来一起看一下: 已知多于4对点 $x \leftrightarrow x'$ , 求解重投影误差

\Sigma d(x_i,\hat{x_i})^2 + d(x'_i,\hat{x_i}')^2 \\ \hat{x_i}'=\hat{H} \hat{x_i}

先初始化 $\hat{H}$ 用DLT解出一个初始值. 或者用RANSAC找出一个初始值.
使用这个初始值来计算重投影误差的sampson余项

或者用初始值以及 $x$ 找出 $\hat{x},\hat{x}'$ , 根据 $\hat{H},\hat{x}$ 最优化重投影误差.

4.6 实验结果

一句话概括, DLT的效果事最接近黄金标准算法的

4.7 RANSAC

我们计算 $H$ 需要匹配点, 但其实很多点都是误匹配的, 所以我们先要找出合适的匹配点, 就用RANSAC找.

4.8配合RANSAC的自动算法.

先选4对点,找出 $H$
用 $H$ 估计出那些点是内点, 也就是与 $Hx$ 差距小于阈值的点.
内点数量如果够多就转下步, 否则再重复1到3
用所有的内点重新估计一次 $H$ , 怎么估计呢?用最大后验概率, 因为现在的点比4个多, 直接解DLT肯定不合适
知道了 $H$ 那么对应点就确定下来了.

剩下的就是一些小问题,比如对应点怎么找?ORB SIFT FAST等等, 点与点之间距离怎么衡量?ORB等等找出来的都是描述子, 是一个向量, 直接算向量之间距离就可以. 怎么采样? 应该对整个图像均匀采样.