8点法估计基础矩阵

8点法

根据两幅图像中8个对应点对之间的关系，采用SVD求解最小二乘方

约束： \det(F) = 0

假设已知N对点的对应关系： \{x_i,x^{\prime}_i\}_{i=1}^N，每对点满足约束： x_i^{\prime}Fx_i=0

设

\boldsymbol{x}=\begin{bmatrix}u\\v\\1\end{bmatrix}, \boldsymbol{x}'=\begin{bmatrix}u'\\v'\\1\end{bmatrix},\boldsymbol{F}=\begin{bmatrix}f_{11}&f_{12}&f_{13}\\f_{21}&f_{22}&f_{23}\\f_{31}&f_{32}&f_{33}\end{bmatrix}


因为 0=x^{\prime T}Fx

求解线齐次坐标下的方程组

\begin{bmatrix}u'&v'&1\end{bmatrix}\begin{bmatrix}f_{11}&f_{12}&f_{13}\\f_{21}&f_{22}&f_{23}\\f_{31}&f_{32}&f_{33}\end{bmatrix}\begin{bmatrix}u\\v\\1\end{bmatrix}=0


即方程组

u'uf_{11}+u'vf_{12}+u'f_{13}+v'uf_{21}+v'vf_{22}+v'f_{23}+uf_{31}+vf_{32}+f_{33}=0


转化为矩阵的形式

\boldsymbol{Af}=\begin{bmatrix}u_1u_1'&u_1'v_1&u_1'&v_1'u_1&v_1'v_1&v_1'&u_1&v_1&1\\\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\u_N'u_N&u_N'v_N&u_N'&v_N'u_N&v_N'v_N&v_N'&u_N&v_N&1\end{bmatrix}\begin{bmatrix}f_{11}\\f_{12}\\f_{13}\\f_{21}\\\vdots\\f_{33}\end{bmatrix}=\mathbf{0}


易知若 f 是方程的一个解，则kf也是方程的一个解，所以添加约束条件 \|f\|=0，解得： f 的最小二乘解是对应于A的最小奇异值的奇异向量

将A进行SVD分解，得到

A=U\Sigma V^T


其中：

U 的列向量，是AA^T 的特征向量；

V的列向量，是 A^TA 的特征向量；

A的奇异值（ \Sigma 的非零对角元素）则是 AA^T 或者 A^TA 的非零特征值的平方根。

因为可能图像存在噪声干扰的情况，所以目标为最小化 \|U\Sigma V^Tf\|

又因为一个矩阵乘上一个正交矩阵范数不变，所以即最小化 \|\Sigma V^Tf\|，且可得 \|V^Tf\|=\|f\|。

令 y=V^Tf

于是目标转化为求满足约束条件 \|y\|=1的情况下， \|\Sigma y\|的最小值

因为 \Sigma为特征值降序的对角阵，所以 y=[0,0,\dots,1]^T

又因为 y=V^Tf，且V^T=V^{-1}

所以 f=V^{-T}y=Vy​

于是得到结论： f 的最小二乘解是对应于A的最小奇异值的奇异向量

然后将f重组为 \hat{F}

又由于用SVD求解得到的 \hat{F}通常为满秩，而实际上F的秩为2，因此最佳解为秩为2的 \hat{F}近似：

\begin{aligned}\min_F&\left\|\boldsymbol{F}-\boldsymbol{\widehat{F}}\right\|_2\\ s.t.&\det(\boldsymbol{F}){=}0\end{aligned}


将 \hat{F}进行SVD分解得 \hat{F}=UDV^T

其中

D=\begin{bmatrix}\sigma_1\\&\sigma_2\\&&\sigma_3\end{bmatrix} \quad(\sigma_1\geq\sigma_2\geq\sigma_3)


可得

F=U\begin{bmatrix}\sigma_1\\&\sigma_2\\&&0\end{bmatrix}V^T


即可将下图

转化为

此时极线一致

归一化 8点法

步骤

  1. 归一化坐标：对每幅图像，计算一个相似变换， 并归一化图像坐标 \hat{x}=Tx,\hat{x^{\prime}}=T^{\prime}x^{\prime} （平移到均值 ，缩放：到原点的平均距离为 \sqrt{2} ）

  2. 在归一化后的坐标系中，采用8点法计算\hat{F}

  3. 反归一： F=T^{-1}\hat{F}T^{\prime}

然后求解基础矩阵F

解除归一化

因为

\hat{x}=Tx,\hat{x^{\prime}}=T^{\prime}x^{\prime}

且

\begin{aligned} (\hat{x^{\prime}})^T \hat F\hat{x}&=0\\ (T^{\prime}x^{\prime})^T\hat F(Tx)&=0\\ (x^{\prime})^T(T^{\prime T}\hat FT)x&=0 \end{aligned}

可得

F=T^{\prime T}\hat FT