Multi-View Geometry

 

 

1. Epipolar Basics

1.1 Setup

上图是经典的 Epipolar Geometry 极几何 的设置

• $O_l, O_r \longrightarrow$ 左右两相机的光心 / 原点

• $e_l, e_r \longrightarrow$ Epipoles，Image Point of camera origin as viewed by the other camera

  • 人话：$e_l$ 是右侧相机在左侧 Image Plane 上的投影，$e_r$ 同理
  • They are unique for a given stereo pair

• $P \longrightarrow$ Scene Point，拍摄场景上的一点，每个场景点都有唯一对应的 Epipolar Plane

• $t, R \longrightarrow$ Translation & Rotation Coordinates (Matrix) of $\{O_r\}$ in $\{O_l\}$

• $x_l, x_r \longrightarrow$ Scene Point $P$ 分别在左右相机坐标系下的空间坐标

 

 

 

1.2 Epipolar Constraint

这个 constraint 的核心是：Scene Point $P$ 要在对应的 Epipolar Plane 上

图中的 $n$ 为这个 Epipolar Plane 上的 Normal Vector 法向量，由于 $x_l$ 一定在 Epipolar Plane 上，所以一定也满足

Epipolar Constraint 即

 

 

1.3 Essential Matrix

Essential Matrix 是关联 两个相机坐标系下 Scene Point 三维坐标 的工具

• 预处理 1

  Assume $x_l$ is in the form

  Express the Epipolar Constraint in matrix form

  自己查 matrix cross product 就知道为什么这么写了

• 预处理 2

  Assume $x_r$ is in the form

  $x_l$ 和 $x_r$ 可以通过 $R,t$ 建立联系

将公式 (2) 代入公式 (1) 可得

由于向量对自己叉乘结果为0，所以有 $t\cross t = 0$，因此

中间两个矩阵合并得到 Essential Matrix $E$

In summary

Tip. 只要你知道了 $E$，就能通过 SVD 拆出 $R$ 和 $t$

 

 

 

1.4 Fundamental Matrix

Fundamental Matrix 是关联 两个相机 Image Plane 中 Scene Point 投影坐标 的工具

Scene Point $P$ 在三维空间中的两个坐标 $x_l, x_r$ 在各自相机 Image Plane 上对应的点为

请原谅，齐次坐标有些别扭

假设两台相机的 Intrinsic Matrix 为 $K_l, K_r$，均为已知，则有

把整理好的 $x_l, x_r$ 公式代入 $x_l^T E x_r = 0$ 中

由于在齐次坐标的意义确保了 $z_l, z_r \not= 0$，所以可以很安全地直接从上式中把它们干掉，最后得到

合并后得到

In Summary

 

 

1.6 Model Summary

• Essential Matrix 展开

  For Calibrated Cameras

• Fundamental Matrix 展开

  For Uncalibrated Camera

  此处由于去掉了 $z_l, z_r$，若使用 $F$ 还原 $E$ 再还原 $R,t$ 便会出现尺度丢失的问题

• 一半展开

• 完全展开

 

 

 

 

 

2. Epipolar 相关应用

2.1 相机 - 求相对位姿

求 $R,t$ 需要分解 Essential Matrix $E$

求 $E$ 需要 Scene Point $P$ 在两个相机坐标系下的三维坐标，而这几乎是不可能的

但是 1.4 提供了一条用 Fundamental Matrix $F$ 求 $E$ ，然后再求 $R,t$

1. 在两个相机的 Image Plane 上找一打对应点

2. 用下式求出 Fundamental Matrix $F$

3. 用下式求出 Essential Matrix $E$

4. 用 SVD 从下式中拆解出 $R, t$

 

 

 

2.2 八点法 8-Point Algorithm

八点法是用于求解 Fundamental Matrix $F$ 的算法

 

2.2.1 基本部分

理论上 $F$ 有 7 个自由度，选取 7 对特征点即可求出 $F$，但是实际上完全不够用

如上图，八点法选取（大于）8 对特征点 $(p_l, p_r)$，代入下式

然后展开整理，能得到这么个齐次线性方程组

然后求 Least-Square Solution

$f$ 的 scale 无所谓，所以可以加个非常 handy 的 constraint，限定 $f$ 的 magnitude 为 1

用 SVD 分解可得到一个 $\hat{F}$，但它一般不是我们要的 Fundamental Matrix！

 

 

2.2.2 Rank Constraint

• Rank Constraint of Fundamental Matrix

上一部分里通过 SVD 解得的 $\hat{F}$ 一般不是我们要的 Fundamental Matrix，因为 $\hat{F}\in \mathbb{R}^{3\times3}$，且一般 $\rank(\hat{F}) = 3$，所以

这意味着 $Wf = 0$ 只有零解，即 $f = [0]$，Nein！！！

see 4.

Enforce 这个 Rank Constraint 的方法很简单，对 $\hat{F}$ 再进行一次 SVD

然后令 $s_3 = 0$，组合回去就是我们要的 $\rank = 2$ 的合法 $F$ 了

 

2.2.3 八点法的缺陷

• 精度较低
• $W$ 中各元素差异较大
• SVD 分解有数值计算问题

 

 

 

2.3 Find Correspondence

在左侧相机的 Image Plane 里指定一 Scene Point $P$ 的投影点，那 $P$ 在右侧相机的 Image Plane 的投影点在何处？

 

2.3.1 Method: Epipolar Line

Epipolar Line is the Intersection of Epipolar Plane and Image Planes

在 1.1 中有提到，每个 Scene Point $P$ 都有对应的 Unique Epipolar Plane，它与两相机的 Image Plane 有唯二交线为 Epipolar Line，在图中标红

简而言之：每个 $P$ 在 Epipolar 系统中都有 2条 这样的线，一个 Image Plane 一条

两个 Corresponding Points 一定在同一个 Epipolar Plane 上 (如下图中的虚线)

而 Epipolar Plane 一定会与 Image Plane 有一条交线

所以只要能找到右侧相机 Image Plane 里的那条 Epipolar Line，找对应点的过程就能被简化为 1D Search！

 

 

2.3.2 Find Epipolar Line

• Given

  1. Fundamental Matrix $F$
  2. Left Image 上一点 $(u_l, v_l)$

• 方法 1：

  依据 1.6 提供的公式

  展开后得

  由于 $F$ 和 $(u_l, v_l)$ 均已知，所以可以直接合并成系数，化简所得即右侧 Image Plane 上的 Epipolar Line $EL_r$

  然后做个 1D Search 就完事了

• 方法 2：

  参考 1.6 提供的公式

  以及 “点 $x$ 在线 $l$ 上” 的点乘条件

  对比一下可以很快得出左右 Epipolar Line 的公式 $EL_l, EL_r$

  和 方法 1 的结果对比一下，一模一样！

 

 

2.3.3 Example

 

 

 

2.4 Find Depth

• Given:

  1. Scene Point $P$ 在两相机 Image Plane 里的投影点坐标 $p_l, p_r$

  2. 两台相机的 Intrinsic Matrix $K_l, K_r$

  3. 两台相机的相对位置 $R,t$

• Find:

  Depth of $P$ from the Right Camera !

• 预处理 1

  假定 $P$ 在 $\{O_l\}$ 和 $\{O_r\}$ 中的三维坐标为 $x_l, x_r$

  $x_l, x_r$ 与在各自相机 Image Plane 上的投影点 $p_l, p_r$ 通过 Camera Matrix $K_l, K_r$ 分别建立联系

• 预处理 2

  $x_l, x_r$ 通过描述相机相对位置的 $R,t$ 建立联系

  然后代入 预处理 1 中右侧相机的映射关系

• Computation

  联立预处理后的两个公式

  显然 $p_l$ 与 $M_lx_l$ 只差一个 scale $z_l$，对于 $p_r$ 同理，因此有

  那更进一步，如果公式两侧叉乘，就会

  这样就能完全忽略归一化项 $z_l, z_r$，上式展开后联立可得

  最后 find least-square solution using Pseudo-Inverse 即可找出 $x_r$

 

 

 

 

 

3. Stereo

3.1 Binocular Vision Setup

这样的 Stereo System 是 Epipolar System 的特殊版本，类似于一台相机拍一张照片，然后平移一段距离，再拍一张照片

两台相机一模一样，间距为 $b$，且 Image Plane 相互平行，Scene Point 位于 $(x,y,z)$

这个系统有如下特性：

• Epipoles 在无穷远处，左侧相机的 Epipole 在左侧无穷远，右侧的在右侧无穷远

• Scene Point 的 Epipolar Line 水平于 Image Plane 的 $u$ 轴，如上图黄线所示

  不止水平，而且重合，不过原因很简单，因为此时 Epipolar Line 是 Epipolar Plane 的组成部分之一了

• Scene Point 的投影点高度相等 $v_l = v_r$

 

 

 

3.2 Triangulation

设定两台相机的 Camera Matrix 为

所以两个 Image Plane 上 Scene Point 投影点与其三维坐标的关系为

展开后分别得到

• 右侧投影点

• 左侧投影点

这里就能看出来 $v_l = v_r$ 了

 

 

 

3.3 Disparity

Solve for $(x,y,z)$ with the equations of two projection points

where $(u_l - u_r)$ is Disparity，也就是一个 Scene Point 在两个 Image Plane 上 投影点的 $u$ 轴距离差

• Disparity 与 Depth $z$ 成 反比

  若 Scene Point 位于无限远处，那么它在相机在平移前后所摄照片里会在一模一样的位置

• Disparity 于 Baseline $b$ 成 正比

  相机平移距离越长，同一个 Scene Point 在平移前后所摄照片里的 Disparity 越大

• Disparity 仅存在于 Image Plane 的 $u$ 轴

  因为 $v$ 轴数值完全相等 $v_l = v_r$

右图是用某些器械手动测量的左图场景的 Disparity Map

Map 中亮度越高的地方有更大的 Disparity

所以很明显，离相机越近，Disparity 越大，与 Depth 成反比

 

 

 

3.4 Stereo Matching

• Given

  1. 用 Binocular Vision 拍摄的左右两张图片
  2. Binocular Vision 的相机配置 $b, K$

• Find

  Depth Map!

 

3.4.1 Template Matching

在左图选一个小窗口 Template Window $T$，由于 Binocular Vision 的特性，这个窗口的 Feature 在左右图的高度是相同的

你只需要顺着一条线做 1D Search，然后用某些 Similarity Metric 匹配特征就能找到对应点

能找到对应点，就能找到 $u_r$，就能求 Disparity，就能求 Depth！

 

3.4.2 影响结果的因素

• Window Size

  在做 Template Matching 时，选取的 Template Window 大小会对最终结果造成某些影响，各有利弊

  

• Similarity Metric

  在做特征匹配时选的 Similarity Metric 也会有不同的效果

  

 

 

3.4.3 存在的问题

1. Repetitive Texture 重复 / 同质特征

   下图这两种 Texture 可谓大寄特寄，取 Template Window 做匹配的时候到处都能匹配上

   

2. Foreshortening 透视缩短

   下图中场景投影到左右两个 Image Plane 的是同一个区域，但是右侧成像长度比左侧更短，被压缩了，不太好匹配了！

   

3. 遮挡

   典中典的问题

   

 

 

 

 

 

4. 补充材料: Matrix Null Space

• Null Space

  Null Space of Matrix $A$ is a set of vectors $x$ satisfying $Ax = 0$

• Nullity

  Nulity of $A$ is the dimension of Nullspace

• Rank-Nullity Theorem