homography

Reference

多视图几何

2D homography

问题描述：给定一组点$x_i$和对应的一组点$x_i^{‘}$,$x_i,x_i^{‘}$都是平面上的点，求投影变换H，使得$x_i^{‘}=Hx_i$.(在实际情况下，这两组点分别是两幅图像上的点或者是同一幅图像上的点，其中每幅图像都被看成是一个投影平面。)

解法一：DLT（Direct Linear Transformation）

点$x_i,x_i^{‘}$使用齐次坐标表示。要求解H，使得$x_i^{‘}=Hx_i$.

先做叉积可得：$x_i^{‘}\times Hx_i=0$,可知H乘以一个尺度因子k也满足该等式，即H有8个自由度,令$h^{jT}$表示H的第j行，则：

$Hx_i=\left[\begin{matrix} h^{1T}x_i\\ h^{2T}x_i\\ h^{3T}x_i \end{matrix}\right]$

令点$x_i^{‘}$为$(x_i^{‘},y_i^{‘},w_i^{‘})^T$,所以上面的叉积可以表示为：

$x_i^{'}\times Hx_i=\left[\begin{matrix} y_i^{'}h^{3T}x_i-w_i^{'}h^{2T}x_i\\ w_i^{'}h^{1T}x_i-x_i^{'}h^{3T}x_i\\ x_i^{'}h^{2T}x_i-y_i^{'}h^{1T}x_i \end{matrix}\right]=0$

由于$h^{jT}x_i=x_i^{T}h^j$,所以上式可写成

$\left[\begin{matrix} 0^{T} & -w_i^{'}x_i^{T} & y_i^{'}x_i^{T}\\ w_i^{'}x_i^{T} & 0^{T} & -x_i^{'}x_i^{T}\\ -y_i^{'}x_i^{T} & x_i^{'}x_i^{T} & 0^{T} \end{matrix}\right] \left[\begin{matrix} h^{1}\\ h^{2}\\ h^{3} \end{matrix}\right]=0$

由于第三行可由前两行通过线性变换得到（第一行乘以$x_i^{‘}$加上第二行乘以$y_i^{‘}$得到的和再缩放一个尺度因子即可得到），所以一对点提供了两个方程,如式一：

$\left[\begin{matrix} 0^{T} & -w_i^{'}x_i^{T} & y_i^{'}x_i^{T}\\ w_i^{'}x_i^{T} & 0^{T} & -x_i^{'}x_i^{T} \end{matrix}\right] \left[\begin{matrix} h^{1}\\ h^{2}\\ h^{3} \end{matrix}\right]=0$

将上式记为$A_ih=0$,则8个自由度需要4对点。求解h的步骤为：

有$4\le n$对点，用每对点计算一个$A_i$
将n个$A_i$堆砌写成一个A
将A进行SVD分解，最小奇异值对应的单位奇异向量即为解h

退化

若给定的4对点中，其中三点共线则会出现退化，即在这条线$l$上的点$x_i$都会使得$H^x_i=0$,从而$x_i$对应的映射点$x_i^{‘}$就不确定了（其中$H^=x_4^{‘}l^T$,可验证：$x_i^{‘}\times H^x_i=0$,也可验证对于所有的$i$都满足式一，所以$H^$是$x_i^{‘}=Hx_i$的解）。若给定点大于4对，则在多余的对应点中只要存在3点共线，则退化问题没有解决。若$H^$为$x_i^{‘}=Hx_i$的唯一解（这种情况在$x_1,x_2,x_3$共线但$x_1^{‘},x_2^{‘},x_3^{‘}$不共线时发生），则不存在$x_i$到$x_i^{‘}$的变换；若除了$H^$外，还有另一个解$H$存在，则$\alpha H^*+\beta H$都是该变换的解。

归一化

归一化变换将消除由任意选取图像坐标系的原点和尺度所产生的影响。数据归一化提高了结果的精度。假设一幅图像的坐标$x$被$\overline x=Tx$替代，另一幅图的坐标$x^{‘}$被$\overline x^{‘}=T^{‘}x^{‘}$替代。则：

$x=Hx^{'} \rightarrow T^{-1}\overline x=HT^{'-1}\overline x^{'} \rightarrow \overline x =THT^{'-1}\overline x^{'}$

令：

$\overline x= H^{'}\overline x^{'}$

则：

$H^{'}=THT^{'-1} \rightarrow H=T^{-1}H^{'}T^{'}$

归一化是重要的，在进行DLT求解H时，先将每幅图像的坐标进行归一化，求解$H^{‘}$后,再进一步求解H。推荐的归一化方法：平移+缩放

平移。将点进行平移使其形心位于原点
缩放。对点进行缩放使他们到原点的平均距离为$\sqrt 2$

判断一对点在给定的H下是否是内点

计算对称转移误差。设这对点为$x,x^{‘}$,计算$d(x,H^{-1}x^{‘})$,若$d<t^2$则反向变换为内点，否则反向变换为外点，$t^2=5.99\sigma^2$(在显著性水平为5%的情况下，查表)，同理计算$d(x^{‘},Hx)$并判断前向变换，若前向和反向变换均为内点，则这对点为内点。