### How to compute a homography

We are given 2D to 2D point correspondences (these are points in and hence are homogeneous vectors of size ), and we have to find the homography ( matrix) such that .

Note that and are not numerically equal and they can differ by a scale factor. However, they have the same direction, and, hence .

Writing the row of as , we have Writing , the cross product becomes: Since , the system of equations can be written in terms of the unknowns (the entries of ) as: These equations have the form where is a matrix and is a vector (the entries of ). Note that has rank of 2 (third row is obtained, up to a scale, by a sum of times the first row and 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 (a point at infinity), then the first two collapse to a single equation.

Stacking up the equations for (four points) we have where is a matrix whose rank is 8 (of-course, you will not choose four points such that any three are collinear). Consequently has a 1-dimensional null space which provides a solution for . Such a solution can only be determined up to a non-zero scale factor, which suits you fine because is anyway defined only up to a scale! A scale may be arbitrarily chosen for by insisting that .

One can, of-course, stack up more equations by taking more point correspondences. The resulting over-determined system may not have a solution at all (inconsistent measurements?). We can still find a least-squares solution: minimize subject to .

In either case is given by the last column of where is the singular value decomposition (SVD) of .

Subhashis Banerjee 2008-01-20