我的《计算机视觉》系列参考UC Berkeley的CS180课程，PPT可以在课程主页看到。

在上一篇文章3D视觉中我们介绍了在两个照相机像平面共面的情况下如何计算深度：深度与景物在图片中的位移成反比。这篇文章我们讨论更一般的情形，像平面不必共面，甚至不必平行。假设两个相机的内参（intrinsics）都是标定（calibrate）过的。

一、极线约束（Epipolar Constraint）

设两个相机的投影中心分别为$O$和$O^{\prime }$（回想一下投影中心其实可以理解为所有光线都汇聚到的点），两个像平面分别为$\Pi$和${\Pi }^{\prime }$。设景物在$P$点，$OP$与$\Pi$交于点$p$，这个$p$就是景物在像平面$\Pi$上的对应点。知道了$p$在第一张照片上的坐标，就知道了景物所在的直线——图中的$OP$。现在我们需要在第二张照片上找到景物对应的点。在哪儿找呢？上一篇文章我们讨论的情况中景物一定会出现在一条水平线上。在我们现在讨论的一般情况下，它还是出现在一条直线上吗？答案是肯定的。因为，任取$OP$上的点$P_1,P_2,\cdots$，令$O^{\prime }{P}_i$与${\Pi }^{\prime }$交于$p_i^{\prime }$，$p_i^{\prime }$就是假设景物在$P_i$点时 其对应于第二张照片上的点。还是那个套路，我们知道$O{P}_i$一定在 由$OP$和$O{O}^{\prime }$确定的平面$O{O}^{\prime }P$上，那么$P_i$在第二张图片上的对应点$p_i^{\prime }$也一定在 平面$O{O}^{\prime }P$上；而$p^{\prime }$又在平面${\Pi }^{\prime }$上，所以$p^{\prime }$一定在平面${\Pi }^{\prime }$和平面$OO{P}^{\prime }$的交线上（图中的$l^{\prime }$）。所以，我们寻找$P$在第二张图片上的对应点时只需要在直线$l^{\prime }$上寻找即可。直线$l$和$l^{\prime }$称为极线（epipolar lines）。

但我们怎么知道极线$l^{\prime }$在哪里呢？两点确定一条直线，找到$l^{\prime }$上的两个点目前还有些困难，不过找到一个点是可以的。注意到，$O$点也在极线$OP$上，而相机的内参是知道的，也就是说我们知道$O$点的坐标（相对于$O^{\prime }$而言），$O{O}^{\prime }$与${\Pi }^{\prime }$的交点$e^{\prime }$一定在极线$l^{\prime }$上。$e^{\prime }$连同$O{O}^{\prime }$与$\Pi$的交点$e$被称为对极点（epipoles）；其实就是一个相机看到另一个相机在图片中的位置，它不一定在图片上。当两个相机的像平面共面时，对极点$e$和$e^{\prime }$就在无穷远处。$O{O}^{\prime }$称为摄影基线（baseline）。包含$O{O}^{\prime }$的所有平面称为极平面（epipolar plane），它绕着$O{O}^{\prime }$旋转；极平面和像平面的交点就是极线，它也绕着$O{O}^{\prime }$旋转。

二、相机标定过的情况

想要找到$l^{\prime }$上的另一个点其实是不可能的——没有另一个点可以找。但是，注意我们的相机是标定过的，我们知道两个相机之间的坐标变换。令点$p$在第一个相机坐标系下的坐标为$\mathbf{x}$，即$\overrightarrow{OP}=\mathbf{x}$，再令点$p^{\prime }$在第二个相机坐标系下的坐标为${\mathbf{x}}^{\prime }$。现在我们在第二个相机坐标系（即$O^{\prime }$坐标系）下讨论问题。向量$\mathbf{x}$就不能直接使用了，需要转换到$O^{\prime }$坐标系：${\mathbf{x}}_O=R\mathbf{x}+\mathbf{t}$，其中$R$是旋转矩阵，$\mathbf{t}=\overrightarrow{O{O}^{\prime }}$是平移向量。我们还知道，$\mathbf{x},{\mathbf{x}}^{\prime },\mathbf{t}$是共面的，即$${\mathbf{x}}^{\prime }\cdot (\mathbf{t}\times {\mathbf{x}}_O)=0$$其中$\mathbf{t}\times \mathbf{x}$是极平面的法向量，${\mathbf{x}}^{\prime }$与其点积为$0$说明与其垂直，进而说明${\mathbf{x}}^{\prime }$在极平面上。化简：$$\mathbf{t}\times {\mathbf{x}}_O=\mathbf{t}\times (R\mathbf{x}+\mathbf{t})=\mathbf{t}\times R\mathbf{x}+\mathbf{x}\times \mathbf{t}=\mathbf{t}\times R\mathbf{x}+0=\mathbf{t}\times R\mathbf{x}$$因此有$${\mathbf{x}}^{\prime }\cdot (\mathbf{t}\times R\mathbf{x})=0$$叉乘可以转化成与一个反对称矩阵$[{\mathbf{t}}_{\times }]$的乘法：

故等式化为${\mathbf{x}}^{\prime T}[{\mathbf{t}}_{\times }]R\mathbf{x}=0$。令$E=[{\mathbf{t}}_{\times }]R$，则有$${\mathbf{x}}^{\prime T}E\mathbf{x}=0$$这就是Longuet-Higgins方程。$E$被称为本质矩阵（Essential Matrix）。

其实，$E\mathbf{x}$就表示极线$l^{\prime }$。设$l^{\prime }$在像平面上的方程为$a{x}^{\prime }+b{y}^{\prime }+c=0$，即$[a,b,c][x^{\prime },y^{\prime },1{]}^T=0$。注意像平面${\Pi }^{\prime }$的法向量和$O^{\prime }$坐标系下的$z$轴平行（即${\Pi }^{\prime }$与$x^{\prime }O{y}^{\prime }$面平行），所以$x^{\prime },y^{\prime }$既是$O^{\prime }$坐标系下的横纵坐标，也是像平面坐标系下的横纵坐标。那么$a,b,c$就可以用$E\mathbf{x}$来确定了。

最后，$E$是奇异矩阵，秩为$2$，有五个自由度：3个平移，2个旋转（平面绕法线旋转等于没旋转，所以少一个旋转自由度）。

三、相机没有标定过的情况

设图像上的坐标为$(u,v)$，令$\hat{\mathbf{x}}=[u,v,1{]}^T$。令$K$和$K^{\prime }$分别是连哥哥相机的$3\times 3$版本的内参矩阵（intrinsic matrix），则$\mathbf{x}=K^{-1}\hat{\mathbf{x}}$，${\mathbf{x}}^{\prime }=K^{\prime -1}{\hat{\mathbf{x}}}^{\prime }$，代入${\mathbf{x}}^{\prime T}E\mathbf{x}=0$得$${\hat{\mathbf{x}}}^{\prime T}\underset{F}{\underbrace{{(K^{\prime -1})}^{T}E{K}^{-1}}}\hat{\mathbf{x}}=0$$其中$F={(K^{\prime -1})}^{T}E{K}^{-1}$称为基础矩阵（Fundamental Matrix）。它也是秩为2的矩阵，有7个自由度：秩为2相当于多一个方程，损失一个自由度；把$F$放大若干倍等式不变，再损失一个自由度。

四、八点算法（eight-point algorithm）

如何求得基础矩阵$F$呢？还是老套路，线性回归。给定两张图片上的8个点对，代入方程${\hat{\mathbf{x}}}^{\prime T}F\hat{\mathbf{x}}=0$用最小二乘法求得最优的$F$即可。

用$8$个点是利用到了秩为$2$的约束，少了一个自由度；另外一个缺失的自由度没必要利用，因为没必要手动确定$F$的缩放大小。实践中应该用多于$8$个点。

最后，如果我们标定了相机，那么就可以从$F$求得$E$；而$E$又可以进行奇异值分解最终还原$R$和$\mathbf{t}$。过程比较复杂，可以参考https://inst.eecs.berkeley.edu/~ee290t/fa19/lectures/lecture10-3-decomposing-F-matrix-into-Rotation-and-Translation.pdf。