Two View Geometry

Homographies

Definition

Def Projective Transformation $\text{require}mhchem\left[\begin{array}{c}{x}^{\prime }\\ y^{\prime }\\ 1\end{array}\right]=\left[\begin{array}{cc}\mathbf{A}& t\\ {\mathbf{v}}^{\top }& b\end{array}\right]\left[\begin{array}{c}x\\ y\\ 1\end{array}\right]=\mathbf{H}\left[\begin{array}{c}x\\ y\\ 1\end{array}\right]$

Definition

Def Cross Ratio The cross ratio of four points $A$, $B$, $C$ and $D$ is defined as: $(A,B;C,D)=\frac{AC\cdot BD}{BC\cdot AD}$

Proposition

Prop Projective transformation preserves colinearity.

Proposition

Prop Projective transformation preserves cross ratio of $4$ collinear points: $(A,B;C,D)=(A^{\prime },B^{\prime };C^{\prime },D^{\prime })$

Proposition

Prop Transformation of 2D Points and Lines Suppose we have transformation from points into points $\mathbf{H}$, i.e. $x^{\prime }=\mathbf{H}x$, then for any line $l:\text{tr}ax=b$, it maps to $l^{\prime }:({\mathbf{H}}^{-\top }a)x=b$. Proof $b=\text{tr}ax=\text{tr}a({\mathbf{H}}^{-1}\mathbf{H})x=\text{tr}({\mathbf{H}}^{-\top }a)\mathbf{H}x$.

Definition

Def Homography (Matrix) Homography is a projective transformation between two images of the same planar surface. It is represented by a $3\times 3$ transformation matrix under a homogenous coordinates.

Homography Estimation

Algorithm

Algorithm Direct Linear Transformation Given an equation of the form $Ax=0$in the presence of noise. The DLT solution is obtained by computing the SVD of $A=U\Sigma V^{\top }$ and taking the last column of $V$ as the solution for $x$.

Algorithm

Algorithm Direct Linear Transformation for Homography Estimation Goal: Given $n\ge 4$ 2D-2D point correspondences $\{{\mathbf{x}}_i\sim {\mathbf{x}}_i^{\prime }\}$, determine the $3\times 3$ homography matrix $\mathbf{H}$ such that ${\mathbf{x}}_i^{\prime }\approx \mathbf{H}{\mathbf{x}}_i$.

1. For each correspondence $x_i\sim x_i^{\prime }$ compute matrix ${\mathbf{A}}_i$, taking only the first $2$ rows.
2. Assemble the $n$ $2\times 9$ ${\mathbf{A}}_i$ matrices into a single $2n\times 9$ matrix $\mathbf{A}$.
3. Compute the SVD of $\mathbf{A}=\mathbf{U\Sigma }{\mathbf{V}}^{\top }$.
4. Take the last column of $\mathbf{V}$ as the solution for $\mathbf{h}$.
5. Rearrange $\mathbf{h}$ to obtain $\mathbf{H}$.

where for ${\mathbf{x}}_i=[x_1,y_1,w_1]$ and

Algorithm

Algorithm Normalised DLT for Homography Estimation Goal: Given $n\ge 4$ 2D-2D point correspondences $\{{\mathbf{x}}_i\sim {\mathbf{x}}_i^{\prime }\}$, determine the $3\times 3$ homography matrix $\mathbf{H}$ such that ${\mathbf{x}}_i^{\prime }\approx \mathbf{H}{\mathbf{x}}_i$.

1. Normalise 2D points: ${\tilde{\mathbf{x}}}_i=\mathbf{T}{\mathbf{x}}_i$, ${\tilde{\mathbf{x}}}_i^{\prime }={\mathbf{T}}^{\prime }{\mathbf{x}}_i^{\prime }$.
2. Apply the DLT algorithm to $\{{\tilde{\mathbf{x}}}_i\sim {\tilde{\mathbf{x}}}_i^{\prime }\}$, get $\tilde{\mathbf{H}}$.
3. Denormalise the recovered solution $\tilde{\mathbf{H}}$ using $\mathbf{H}={\mathbf{T}}^{\prime -1}\tilde{\mathbf{H}}\mathbf{T}$.

e.g. Example normalisation matrices: $\mathbf{T}={\left[\begin{array}{ccc}w+h& 0& w/2\\ 0& w+h& h/2\\ 0& 0& 1\end{array}\right]}^{-1},{\mathbf{T}}^{\prime }={\left[\begin{array}{ccc}{w}^{\prime }+h^{\prime }& 0& w^{\prime }/2\\ 0& w^{\prime }+h^{\prime }& h^{\prime }/2\\ 0& 0& 1\end{array}\right]}^{-1}$where $w$,$h$ and $w^{\prime }$,$h^{\prime }$ are image widths and heights respectively.

Algorithm

Algorithm Gold Standard Goal: Given $n\ge 4$ 2D-2D point correspondences $\{{\mathbf{x}}_i\sim {\mathbf{x}}_i^{\prime }\}$, determine the $3\times 3$ homography matrix $\mathbf{H}$ such that ${\mathbf{x}}_i^{\prime }\approx \mathbf{H}{\mathbf{x}}_i$.

1. Initialisation: Compute an initial estimate using normalised DLT or RANSAC.
2. Geometric minimisation of reprojection error:
3. Minimise using Levenberg-Marquardt over the $9$ entries of $\mathbf{H}$.
4. Compute initial estimate for optimal $\{{\mathbf{x}}_i\}$.
5. Minimise cost
6. Denormalise the recovered solution.

Epipolar Geometry

Comment

Epipolar geometry is the intrinsic geometry of 2 different views of the same 3D scene.

Definition

Def Baseline and Epipole Baseline is the line joining the camera centers. Epipole is the point of intersection of baseline with image plane. Epipolar plane is the plane containing baseline and world point. Epipolar line is the intersection of epipolar plane with the image plane. e.g. In the following diagram, we have world point $X$, camera centers $C$ and $C^{\prime }$, then $C{C}^{\prime }$ is the baseline, $ex$ and $e^{\prime }{x}^{\prime }$ is the epipolar line, $\pi$ is the epipolar plane.

Proposition

Prop All epipolar lines intersect at the epipole.

Proposition

Prop Epipole is the projection of one optical centre in the other image.

Essential and Fundamental Matrices

Definition

Def Essential Matrix The essential matrix encapsulates the epipolar geometry constraints between two views of a 3D scene, with calibrated cameras and contains the intrinsic camera parameters. It is $E:=[t{]}_{\times }R$where $R$ is the rotation matrix in ${\mathbb{R}}^{3\times 3}$ and $[t{]}_{\times }$ is the translation crossproduct matrix in ${\mathbb{R}}^{3\times 3}$ of rank $2$: $[t{]}_{\times }=\left[\begin{array}{ccc}0& -t_z& t_y\\ t_z& 0& -t_x\\ -t_y& t_x& 0\end{array}\right]$

Prop The essential matrix $E$ has following properties:

• It has a rank of $2$.
• It is singular, has singular values ${\sigma }_1={\sigma }_2$ and ${\sigma }_3=0$.
• $\det (E)=0$
• $2E{E}^{\top }E-\text{trace}E{E}^{\top }E=0$.

Algorithm Recovering $R$ and $t$ from $E$

1. Implement SVD: $E=U\Sigma V^{\top }$.
2. Output $R=U{W}^{-1}{V}^{\top }$ and $[t{]}_{\times }=UW\Sigma U^{\top }$ where $W=\left[\begin{array}{ccc}0& -1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right]$
3. To get all 4 solutions, solve for combinations of $W$ and $W^{-1}$.
4. Select solution where all of the 3D points are in front of both cameras.

Definition

Def Fundamental Matrix The fundamental matrix encodes the relationship between two images of a 3D scene by encapsulating the epipolar geometry constraints, while the intrinsics of both cameras are not known. Mathematically, such matrix $F$ is the unique $3\times 3$ rank $2$ matrix that satisfies $x_i^{\prime \top }F{x}_i=0$ for all corresponding points $x_i^{\prime }$ and $x_i$.

Prop The fundamental matrix $F$ has following properties:

• If $F$ is fundamental matrix for $(x,x^{\prime })$,then $F^{\top }$ is the fundamental matrix for $(x^{\prime },x)$.
• $F$ maps from a point $x$ in one image to a line $l^{\prime }=Fx$ in the other image.
• Lie on all epipolar lines, thus $x^{\prime \top }Fx=0$ for all $x$ implies $Fe=0$.

Algorithm

Algorithm DLT for Fundamental Matrix Estimation It is also called the 8-point algorithm. Given $n\ge 8$ 2D-2D point correspondences $\{{\mathbf{x}}_i\sim {\mathbf{x}}_i^{\prime }\}$, determine the $3\times 3$ fundamental matrix $F$ such that ${\mathbf{x}}_i^{\prime \top }F{\mathbf{x}}_i=0$.

1. Let $x=[u,v,1{]}^{\top }$, $x^{\prime }=[u^{\prime },v^{\prime },1{]}^{\top }$ and $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]$
2. Construct the matrix $\mathbf{A}=\left[\begin{array}{ccccccccc}{u}^{\prime }u& u^{\prime }v& u^{\prime }& v^{\prime }u& v^{\prime }v& v^{\prime }& u& v& 1\end{array}\right]$. And construct the vector $\mathbf{f}=[f_{11},f_{12},f_{13},f_{21},f_{22},f_{23},f_{31},f_{32},f_{33}{]}^{\top }$.
3. Minimise $\Vert A\mathbf{f}{\Vert }^2$ subject to $\Vert \mathbf{f}\Vert =1$, get $\mathbf{f}$ as the least right singular vector of $A$.
4. Reshape $\mathbf{f}$ to get $F^{\prime }$.
5. But since $\text{rank}F=2$, replace $F^{\prime }$ with $F$ by computing the SVD of $F^{\prime }$ and setting the smallest singular value to $0$. That is to solve the following optimization problem: $F={\mathrm{argmin}}_F\Vert F-F^{\prime }{\Vert }^2\text{subject to}\det (F)=0$Concretely, decompose $F^{\prime }=U\Sigma V^{\top }$ and set $F=U{\Sigma }^{\prime }{V}^{\top }$ where $\Sigma =\left[\begin{array}{ccc}{\sigma }_1& 0& 0\\ 0& {\sigma }_2& 0\\ 0& 0& {\sigma }_3\end{array}\right],{\Sigma }^{\prime }=\left[\begin{array}{ccc}{\sigma }_1& 0& 0\\ 0& {\sigma }_2& 0\\ 0& 0& 0\end{array}\right]$
6. Return $F$.

Comment

The 8-Point Algorithm has advantage of being simple and fast, but it is sensitive to noise, and it optimises a non-physical algebraic quantity.

Algorithm Normalised DLT for Fundamental Matrix Estimation

1. Transform the points using normalisation matrices $T$ and $T^{\prime }$: ${\hat{x}}_i=T{x}_i$ and ${\hat{x}}_i^{\prime }=T^{\prime }{x}_i^{\prime }$.
2. Apply the DLT algorithm to $\{{\hat{x}}_i\sim {\hat{x}}_i^{\prime }\}$, get $\hat{F}$.
3. Then denormalise the recovered solution $\hat{F}$ using $F=T^{\prime \top }\hat{F}T$.

Triangulation

Def Triangulation Problem The triangulation problem is to compute the 3D location $\mathbf{X}$, given image points $\mathbf{x}$ and ${\mathbf{x}}^{\prime }$ in correspondence across two or more images (taken from calibrated cameras with known intrinsics and extrinsics).

Algorithm DLT Triangulation Given camera projection matrix $\mathbf{P}$, ${\mathbf{P}}^{\prime }$ and corresponding points $\mathbf{x}$, ${\mathbf{x}}^{\prime }$:

1. Precondition points and projection matrices.
2. Create matrix $A$.
3. Compute SVD of $A=U\Sigma V^{\top }$.
4. Extract $\mathbf{X}$ from the last column of $V$.
5. Then refine with respect to a geometric error. sample code can be found here.

Stereo Vision

Comment

Humans do 3D perception well from a single image and very well from stereo (binocular) images. An intermediate goal of computer vision was to mimic the functionality of the biological system.

Definition

Def Disparity Disparity is the positional difference between the two retinal projections of a given point in space. e.g. In the following setting, we have disparity $d=u_L-u_R$.

Proposition

Prop If optical axes are parallel and heights of the camera centers are identical, then for points at a fixed depth, the disparity between the corresponding points in the two images is constant.

Def Rectified Stereo Images We say the stereo images are rectified if

• Image planes of cameras are parallel;
• Principal axes are at same height;
• Identical focal lengths.

Prop The epipolar lines fall along the horizontal scan lines of the images in a rectified stereo setting.

The Correspondence Problem

Def Correspondence Problem The correspondence problem in stereo vision is the problem of measuring the disparity of each point in the two eye (camera) projections.

Law Colour Constancy Constraint Same world point has same intensity (or colour) in both images.

Def Sum of Squared (Pixel) Differences Suppose $W_L$ and $W_R$ are corresponding $m$ by $n$ windows of pixels. Define the following window function: $W_m(x,y)=\left\{u,v\mid x-\frac{m}{2}\le u\le x+\frac{m}{2},y-\frac{m}{2}\le v\le y+\frac{m}{2}\right\}$The sum of squared difference cost measures the intensity differences as a function of disparity: $C_r(x,y,d)={\sum }_{(u,v)\in W_m(x,y)}[I_L(u,v)-I_R(u-d,v){]}^2$

Interpretation Problem

Def Interpretation Problem The interpretation problem in stereo vision is about how to use disparity information to recover the orientation and distance of surfaces in the scene.