8点法估计基础矩阵

估计基础矩阵

8点法

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

约束：det(F) = 0

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

设
$$\mathbf{x}=\left[\begin{array}{c}u\\ v\\ 1\end{array}\right],{\mathbf{x}}^{\prime }=\left[\begin{array}{c}{u}^{\prime }\\ v^{\prime }\\ 1\end{array}\right],\mathbf{F}=\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]$$
因为$0=x^{\prime T}Fx$

求解线齐次坐标下的方程组
$$\left[\begin{array}{ccc}{u}^{\prime }& v^{\prime }& 1\end{array}\right]\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\\ v\\ 1\end{array}\right]=0$$
即方程组
$$u^{\prime }u{f}_{11}+u^{\prime }v{f}_{12}+u^{\prime }{f}_{13}+v^{\prime }u{f}_{21}+v^{\prime }v{f}_{22}+v^{\prime }{f}_{23}+u{f}_{31}+v{f}_{32}+f_{33}=0$$
转化为矩阵的形式
$$\mathbf{Af}=\left[\begin{array}{ccccccccc}{u}_1{u}_1^{\prime }& u_1^{\prime }{v}_1& u_1^{\prime }& v_1^{\prime }{u}_1& v_1^{\prime }{v}_1& v_1^{\prime }& u_1& v_1& 1\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮\\ u_N^{\prime }{u}_N& u_N^{\prime }{v}_N& u_N^{\prime }& v_N^{\prime }{u}_N& v_N^{\prime }{v}_N& v_N^{\prime }& u_N& v_N& 1\end{array}\right]\left[\begin{array}{c}{f}_{11}\\ f_{12}\\ f_{13}\\ f_{21}\\ ⋮\\ f_{33}\end{array}\right]=0$$
易知若$f$是方程的一个解，则$kf$也是方程的一个解，所以添加约束条件$\Vert f\Vert =0$，解得：$f$ 的最小二乘解是对应于A的最小奇异值的奇异向量

将A进行SVD分解，得到
$$A=U\Sigma V^T$$
其中：

U 的列向量，是$A{A}^T$ 的特征向量；

V的列向量，是 $A^{T}A$ 的特征向量；

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

因为可能图像存在噪声干扰的情况，所以目标为最小化$\Vert U\Sigma V^{T}f\Vert$

又因为一个矩阵乘上一个正交矩阵范数不变，所以即最小化$\Vert \Sigma V^{T}f\Vert$，切可得$\Vert V^{T}f\Vert =\Vert f\Vert$。

令$y=V^{T}f$

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

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

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

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

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

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

又由于用SVD求解得到的$\hat{F}$通常为满秩，而实际上$F$的秩为2，因此最佳解为秩为2的$\hat{F}$近似：
$$\begin{array}{rl}\underset{F}{\min }& {\Vert \mathbf{F}-\hat{\mathbf{F}}\Vert }_2\\ s.t.& \det (\mathbf{F})=0\end{array}$$
将$\hat{F}$进行SVD分解得$\hat{F}=UD{V}^T$

其中
$$D=\left[\begin{array}{ccc}{\sigma }_1& & \\ & {\sigma }_2& \\ & & {\sigma }_3\end{array}\right]({\sigma }_1\ge {\sigma }_2\ge {\sigma }_3)$$
可得
$$F=U\left[\begin{array}{ccc}{\sigma }_1& & \\ & {\sigma }_2& \\ & & 0\end{array}\right]V^T$$
即可将下图

转化为

此时极线一致

归一化 8点法

步骤

1. 归一化坐标：对每幅图像，计算一个相似变换， 并归一化图像坐标$\hat{x}=Tx,\widehat{x^{\prime }}=T^{\prime }{x}^{\prime }$ （平移到均值 ，缩放：到原点的平均距离为$\sqrt{2}$ ）
2. 在归一化后的坐标系中，采用8点法计算$\hat{F}$
3. 反归一：$F=T^{-1}\hat{F}{T}^{\prime }$

然后求解基础矩阵F

解除归一化

因为
$$\hat{x}=Tx,\widehat{x^{\prime }}=T^{\prime }{x}^{\prime }$$
且
$$\begin{array}{rl}(\widehat{x^{\prime }}{)}^T\hat{F}\hat{x}& =0\\ (T^{\prime }{x}^{\prime }{)}^T\hat{F}(Tx)& =0\\ (x^{\prime }{)}^T(T^{\prime T}\hat{F}T)x& =0\end{array}$$
可得
$$F=T^{\prime T}\hat{F}T$$