How to compute a homography

We are given 2D to 2D point correspondences ${\bf x_i} \leftrightarrow {\bf x_i'}$ (these are points in ${\cal P}^2$ and hence are homogeneous vectors of size $3 \times 1$ ), and we have to find the homography ${\bf H}$ ( $3 \times 3$ matrix) such that ${\bf x_i'} = {\bf H}{\bf x_i}$ .

Note that ${\bf x_i'}$ and ${\bf H}{\bf x_i}$ are not numerically equal and they can differ by a scale factor. However, they have the same direction, and, hence ${\bf x_i'} \times {\bf H}{\bf x_i} = {\bf0}$ .

Writing the $j^{th}$ row of ${\bf H}$ as ${{\bf h}^j}^T$ , we have

$${\bf H}{\bf x_i} = \left[ \begin{array}{c} {{\bf h}^1}^T {\bf x_i} \\ {{\bf h}^2}^T {\bf x_i} \\ {{\bf h}^3}^T {\bf x_i} \\ \end{array}\right]$$

Writing ${\bf x_i'}^T = (x_i',y_i',w_i')^T$ , the cross product becomes:

$${\bf x_i'} \times {\bf H}{\bf x_i} = \left[ \begin{array}{c} y_i'... ...'{{\bf h}^2}^T {\bf x_i} - y_i' {{\bf h}^1}^T {\bf x_i} \\ \end{array}\right]$$

Since ${{\bf h}^j}^T {\bf x_i} = {\bf x_i}^T {\bf h}^j$ , the system of equations ${\bf x_i'} \times {\bf H}{\bf x_i} = {\bf0}$ can be written in terms of the unknowns (the entries of ${\bf H}$ ) as:

$$\left[ \begin{array}{ccc} {\bf0}^T & -w_i' {\bf x_i}^T & y_i' {\b... ...rray}{c} {\bf h}^1 \\ {\bf h}^2 \\ {\bf h}^3 \\ \end{array}\right] = {\bf0}$$

These equations have the form ${\bf A_i}{\bf h} = {\bf0}$ where ${\bf A_i}$ is a $3 \times 9$ matrix and ${\bf h}$ is a $9 \times 1$ vector (the entries of ${\bf H}$ ). Note that ${\bf A_i}$ has rank of 2 (third row is obtained, up to a scale, by a sum of $x_i'$ times the first row and $y_i'$ times the second), and, consequently, for each point correspondence we have really only two equations. We may choose to work with only the first two, but it doesn't harm to keep all three. It may be useful to keep all three equations because if $w_i' = 0$ (a point at infinity), then the first two collapse to a single equation.

Stacking up the equations for $i = 1,2,3,4$ (four points) we have ${\bf A}{\bf h} = {\bf0}$ where ${\bf A}$ is a $12 \times 9$ matrix whose rank is 8 (of-course, you will not choose four points such that any three are collinear). Consequently ${\bf A}$ has a 1-dimensional null space which provides a solution for ${\bf h}$ . Such a solution can only be determined up to a non-zero scale factor, which suits you fine because ${\bf H}$ is anyway defined only up to a scale! A scale may be arbitrarily chosen for ${\bf h}$ by insisting that $\Vert {\bf h} \Vert = 1$ .

One can, of-course, stack up more equations by taking more point correspondences. The resulting over-determined system ${\bf Ah} = {\bf0}$ may not have a solution at all (inconsistent measurements?). We can still find a least-squares solution: minimize $\Vert{\bf Ah} \Vert$ subject to $\Vert {\bf h} \Vert = 1$ .

In either case ${\bf h}$ is given by the last column of ${\bf V}$ where ${\bf A} = {\bf U\Sigma V}^T$ is the singular value decomposition (SVD) of ${\bf A}$ .