Multi-View Geometry

1. Epipolar Basics

1.1 Setup

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

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

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

  • 人话：$e_l$$e_l$ 是右侧相机在左侧 Image Plane 上的投影，$e_r$$e_r$ 同理

  • They are unique for a given stereo pair

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

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

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

 

 

 

1.2 Epipolar Constraint

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

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

Epipolar Constraint 即

 

 

1.3 Essential Matrix

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

• 预处理 1

  Assume $x_l$$x_l$ is in the form

  $$\begin{array}{c}{x}_l=\left[\begin{array}{c}{l}_x\\ l_y\\ l_z\end{array}\right]\end{array}$$

  Express the Epipolar Constraint in matrix form

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

  $$\begin{array}{}\text{(1)}& \begin{array}{c}{x}_l\cdot (t\times x_l)=\left[\begin{array}{ccc}{l}_x& l_y& l_z\end{array}\right]\left[\begin{array}{ccc}0& -t_z& t_y\\ t_z& 0& t_x\\ t_y& t_x& 0\end{array}\right]\left[\begin{array}{c}{l}_x\\ l_y\\ l_z\end{array}\right]=0\end{array}\end{array}$$

• 预处理 2

  Assume $x_r$$x_r$ is in the form

  $$\begin{array}{c}{x}_r=\left[\begin{array}{c}{r}_x\\ r_y\\ r_z\end{array}\right]\end{array}$$

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

  $$\begin{array}{}\text{(2)}& \begin{array}{c}{x}_l=R{x}_r+t⟶\left[\begin{array}{c}{l}_x\\ l_y\\ l_z\end{array}\right]=\left[\begin{array}{ccc}{R}_{11}& R_{12}& R_{13}\\ R_{21}& R_{22}& R_{23}\\ R_{31}& R_{32}& R_{33}\end{array}\right]\left[\begin{array}{c}{r}_x\\ r_y\\ r_z\end{array}\right]+\left[\begin{array}{c}{t}_x\\ t_y\\ t_z\end{array}\right]\end{array}\end{array}$$

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

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

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

In summary

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

 

 

 

1.4 Fundamental Matrix

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

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

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

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

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

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

合并后得到

In Summary

 

 

1.6 Model Summary

• Essential Matrix 展开

  For Calibrated Cameras

  $$\begin{array}{c}{x}_l^T\cdot E\cdot x_r=0\\ \\ \left[\begin{array}{ccc}{l}_x& l_y& l_z\end{array}\right]\underset{\text{Essential Matrix }E}{\underbrace{\left[\begin{array}{ccc}{E}_{11}& E_{12}& E_{13}\\ E_{21}& E_{22}& E_{23}\\ E_{31}& E_{32}& E_{33}\end{array}\right]}}\left[\begin{array}{c}{r}_x\\ r_y\\ r_z\end{array}\right]=0\end{array}$$

• Fundamental Matrix 展开

  For Uncalibrated Camera

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

  $$\begin{array}{c}{p}_l^T\cdot F\cdot p_r=0\\ \\ \left[\begin{array}{ccc}{u}_l& v_l& 1\end{array}\right]\underset{\text{Fundamental Matrix }F}{\underbrace{\left[\begin{array}{ccc}{F}_{11}& F_{12}& F_{13}\\ F_{21}& F_{22}& F_{23}\\ F_{31}& F_{32}& F_{33}\end{array}\right]}}\left[\begin{array}{c}{u}_r\\ v_r\\ 1\end{array}\right]=0\end{array}$$

• 一半展开

  $$\begin{array}{c}{p}_l^T\cdot K_l^{-T}\cdot E\cdot K_r^{-1}\cdot p_r=0\\ \\ \left[\begin{array}{ccc}{u}_l& v_l& 1\end{array}\right]\underset{\text{Fundamental Matrix }F}{\underbrace{K_l^{-T}\stackrel{\text{Essential Matrix }E}{\overbrace{\left[\begin{array}{ccc}{E}_{11}& E_{12}& E_{13}\\ E_{21}& E_{22}& E_{23}\\ E_{31}& E_{32}& E_{33}\end{array}\right]}}{K}_r^{-1}}}\left[\begin{array}{c}{u}_r\\ v_r\\ 1\end{array}\right]=0\end{array}$$

• 完全展开

  $$\begin{array}{c}{p}_l^T\cdot K_l^{-T}\cdot (t\times R)\cdot K_r^{-1}\cdot p_r=0\\ \\ \left[\begin{array}{ccc}{u}_l& v_l& 1\end{array}\right]\underset{\text{Fundamental Matrix }F}{\underbrace{K_l^{-T}\stackrel{\text{Essential Matrix }E}{\overbrace{\left[\begin{array}{ccc}0& -t_z& t_y\\ t_z& 0& t_x\\ t_y& t_x& 0\end{array}\right]\left[\begin{array}{ccc}{R}_{11}& R_{12}& R_{13}\\ R_{21}& R_{22}& R_{23}\\ R_{31}& R_{32}& R_{33}\end{array}\right]}}{K}_r^{-1}}}\left[\begin{array}{c}{u}_r\\ v_r\\ 1\end{array}\right]=0\end{array}$$

 

 

 

 

 

2. Epipolar 相关应用

2.1 相机 - 求相对位姿

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

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

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

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

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

   $$p_l^{T}F{p}_r=0$$

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

   $$E=K_l^{T}F{K}_r$$

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

   $$E=t\times R$$

 

 

 

2.2 八点法 8-Point Algorithm

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

 

2.2.1 基本部分

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

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

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

然后求 Least-Square Solution

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

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

 

 

2.2.2 Rank Constraint

• Rank Constraint of Fundamental Matrix

  $$\mathrm{rank}(F)=2$$

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

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

see 4.

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

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

 

2.2.3 八点法的缺陷

• 精度较低

• $W$$W$ 中各元素差异较大

• SVD 分解有数值计算问题

 

 

 

2.3 Find Correspondence

在左侧相机的 Image Plane 里指定一 Scene Point $P$$P$ 的投影点，那 $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$$P$ 都有对应的 Unique Epipolar Plane，它与两相机的 Image Plane 有唯二交线为 Epipolar Line，在图中标红

简而言之：每个 $P$$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$$F$

  2. Left Image 上一点 $(u_l,v_l)$$(u_l, v_l)$

• 方法 1：

  依据 1.6 提供的公式

  $$\left[\begin{array}{ccc}{u}_l& v_l& 1\end{array}\right]\underset{\text{Fundamental Matrix }F}{\underbrace{\left[\begin{array}{ccc}{F}_{11}& F_{12}& F_{13}\\ F_{21}& F_{22}& F_{23}\\ F_{31}& F_{32}& F_{33}\end{array}\right]}}\left[\begin{array}{c}{u}_r\\ v_r\\ 1\end{array}\right]=0$$

  展开后得

  $$\begin{array}{rl}0& =\underset{a_l}{\underbrace{(F_{11}{u}_l+F_{21}{v}_l+F_{31})}}\cdot u_r\\ \\ & +\underset{b_l}{\underbrace{(F_{12}{u}_l+F_{22}{v}_l+F_{32})}}\cdot v_r\\ \\ & +\underset{c_l}{\underbrace{(F_{11}{u}_l+F_{21}{v}_l+F_{31})}}\cdot 1\end{array}$$

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

  $$E{L}_r:a_l{u}_r+b_l{v}_r+c_l=0$$

  然后做个 1D Search 就完事了

• 方法 2：

  参考 1.6 提供的公式

  $$p_l^T\cdot F\cdot p_r=0$$

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

  $$x^T\cdot l=0$$

  对比一下可以很快得出左右 Epipolar Line 的公式 $E{L}_l,E{L}_r$$EL_l, EL_r$

  $$\begin{array}{rl}E{L}_l& =F{p}_l\\ E{L}_r& =F^T{p}_r\end{array}$$

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

 

 

2.3.3 Example

 

 

 

2.4 Find Depth

• Given:

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

     $$\begin{array}{c}{z}_l\cdot p_l=z_l\left[\begin{array}{c}{u}_l\\ v_l\\ 1\end{array}\right]z_r\cdot p_r=z_r\left[\begin{array}{c}{u}_r\\ v_r\\ 1\end{array}\right]\end{array}$$

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

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

• Find:

  Depth of $P$$P$ from the Right Camera !

• 预处理 1

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

  $$\begin{array}{c}{x}_l=\left[\begin{array}{c}{l}_x\\ l_y\\ l_z\end{array}\right]x_r=\left[\begin{array}{c}{r}_x\\ r_y\\ r_z\end{array}\right]\end{array}$$

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

  $$\begin{array}{c}{z}_l\left[\begin{array}{c}{u}_l\\ v_l\\ 1\end{array}\right]=K_l\left[\begin{array}{cc}I& 0\end{array}\right]\left[\begin{array}{c}{l}_x\\ l_y\\ l_z\\ 1\end{array}\right]z_r\left[\begin{array}{c}{u}_r\\ v_r\\ 1\end{array}\right]=K_r\left[\begin{array}{cc}I& 0\end{array}\right]\left[\begin{array}{c}{r}_x\\ r_y\\ r_z\\ 1\end{array}\right]\end{array}$$

• 预处理 2

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

  $$\left[\begin{array}{c}{l}_x\\ l_y\\ l_z\\ 1\end{array}\right]=\left[\begin{array}{cc}R& t\\ 0& 1\end{array}\right]\left[\begin{array}{c}{r}_x\\ r_y\\ r_z\\ 1\end{array}\right]$$

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

  $$\begin{array}{c}{z}_l\left[\begin{array}{c}{u}_l\\ v_l\\ 1\end{array}\right]=K_l\left[\begin{array}{cc}I& 0\end{array}\right]\left[\begin{array}{cc}R& t\\ 0& 1\end{array}\right]\left[\begin{array}{c}{r}_x\\ r_y\\ r_z\\ 1\end{array}\right]\end{array}$$

• Computation

  联立预处理后的两个公式

  $$\begin{array}{rl}{z}_l\cdot p_l=M_l\left[\begin{array}{c}{x}_l\\ 1\end{array}\right]& ⟶z_l\left[\begin{array}{c}{u}_l\\ v_l\\ 1\end{array}\right]=\underset{M_l}{\underbrace{K_l\left[\begin{array}{cc}I& 0\end{array}\right]\left[\begin{array}{cc}R& t\\ 0& 1\end{array}\right]}}\left[\begin{array}{c}{r}_x\\ r_y\\ r_z\\ 1\end{array}\right]\\ \\ z_r\cdot p_r=M_r\left[\begin{array}{c}{x}_r\\ 1\end{array}\right]& ⟶z_r\left[\begin{array}{c}{u}_r\\ v_r\\ 1\end{array}\right]=\underset{M_r}{\underbrace{K_r\left[\begin{array}{cc}I& 0\end{array}\right]}}\left[\begin{array}{c}{r}_x\\ r_y\\ r_z\\ 1\end{array}\right]\end{array}$$

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

  $$\begin{array}{rl}{p}_l& \sim M_l\left[\begin{array}{c}{x}_l\\ 1\end{array}\right]\\ p_r& \sim M_r\left[\begin{array}{c}{x}_r\\ 1\end{array}\right]\end{array}$$

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

  $$\begin{array}{rl}{p}_l\times M_l\left[\begin{array}{c}{x}_l\\ 1\end{array}\right]& =0\\ p_r\times M_r\left[\begin{array}{c}{x}_r\\ 1\end{array}\right]& =0\end{array}$$

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

  $$\begin{array}{c}A{x}_r=b⟶A\cdot \left[\begin{array}{c}{r}_x\\ r_y\\ r_z\end{array}\right]=b\text{with }A\in {\mathbb{R}}^{4\times 3},b\in {\mathbb{R}}^{4\times 1}\end{array}$$

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

  $$\begin{array}{rl}A\cdot x_r& =b\\ A^{T}A\cdot x_r& =A^T\cdot b\\ \\ x_r& =(A^{T}A{)}^{-1}{A}^T\cdot b\end{array}$$

 

 

 

 

 

3. Stereo

3.1 Binocular Vision Setup

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

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

这个系统有如下特性：

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

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

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

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

 

 

 

3.2 Triangulation

设定两台相机的 Camera Matrix 为

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

展开后分别得到

• 右侧投影点

  $$\begin{array}{rl}{u}_l& =f_x\frac{x}{z}+o_x\\ v_l& =f_y\frac{y}{z}+o_y\end{array}$$

• 左侧投影点

  $$\begin{array}{rl}{u}_r& =f_x\frac{x-b}{z}+o_x\\ v_r& =f_y\frac{y}{z}+o_y\end{array}$$

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

 

 

 

3.3 Disparity

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

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

• Disparity 与 Depth $z$$z$ 成 反比

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

• Disparity 于 Baseline $b$$b$ 成 正比

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

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

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

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

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

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

 

 

 

3.4 Stereo Matching

• Given

  1. 用 Binocular Vision 拍摄的左右两张图片

  2. Binocular Vision 的相机配置 $b,K$$b, K$

• Find

  Depth Map!

 

3.4.1 Template Matching

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

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

能找到对应点，就能找到 $u_r$$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$$A$ is a set of vectors $x$$x$ satisfying $Ax=0$$Ax = 0$

  $$Null(A)=\{x|Ax=0\}$$

• Nullity

  Nulity of $A$$A$ is the dimension of Nullspace

  $$Nullity(A)=\dim (Null(A))$$

• Rank-Nullity Theorem

  $$\mathrm{rank}(A)+nullity(A)=\text{number of columns in A}$$