Homography & rectification

A photo of a flat object, such as a sheet of paper or a facade, is a projective transformation of its front view. Mark the four corners, and the homography HH follows from a small homogeneous linear system solved with the SVD. With HH, the photo can be unwarped into the front view.

Photo drag the corners 1–4; click elsewhere to pick a point
Rectified front view

A plane seen at an angle

All points of a plane in the scene are related to their pixels in a photo by one projective transformation, a homography:

[x′y′w′]=[abcdefgh1][xy1],p′=(x′w′,y′w′)\begin{bmatrix} x' \\ y' \\ w' \end{bmatrix} = \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix}, \qquad p' = \left(\frac{x'}{w'}, \frac{y'}{w'}\right)

HH is only defined up to scale, so it has 8 degrees of freedom. Lines stay lines, but parallel lines may meet and ratios change; the 2D transformations demo shows these properties one by one. Here HH maps the photo (pp, in pixels) to the front view (p′p', in pixels of the output rectangle). The four corners of the object go to the four corners of the rectangle.

Two equations per point

Write the last entry as a ninth unknown ii and multiply out the division by w′w':

x′=ax+by+cgx+hy+i  ⇒  ax+by+c−gxx′−hyx′−ix′=0x' = \frac{a x + b y + c}{g x + h y + i} \;\Rightarrow\; a x + b y + c - g x x' - h y x' - i x' = 0

and likewise for y′y'. Both equations are linear in the entries of HH. Stacking them for all correspondences gives a homogeneous system, set up the same way as the one for camera calibration:

[x1y11000−x1′x1−x1′y1−x1′000x1y11−y1′x1−y1′y1−y1′⋮⋮xnyn1000−xn′xn−xn′yn−xn′000xnyn1−yn′xn−yn′yn−yn′][abcdefghi]=0\begin{bmatrix} x_1 & y_1 & 1 & 0 & 0 & 0 & -x'_1 x_1 & -x'_1 y_1 & -x'_1 \\ 0 & 0 & 0 & x_1 & y_1 & 1 & -y'_1 x_1 & -y'_1 y_1 & -y'_1 \\ \vdots & & & & & & & & \vdots \\ x_n & y_n & 1 & 0 & 0 & 0 & -x'_n x_n & -x'_n y_n & -x'_n \\ 0 & 0 & 0 & x_n & y_n & 1 & -y'_n x_n & -y'_n y_n & -y'_n \end{bmatrix} \begin{bmatrix} a \\ b \\ c \\ d \\ e \\ f \\ g \\ h \\ i \end{bmatrix} = 0

Solving Ah=0Ah = 0 with the SVD

h=0h = 0 always solves the system, so we look for the unit vector hh that makes ∣Ah∣|Ah| smallest: the right singular vector of the smallest singular value (see the SVD and total least squares). Four points give 8 equations for 9 unknowns, so AA is 8 × 9 and there is always a direction with Ah=0Ah = 0 exactly: the ninth column of VV. It fixes HH up to its scale, and dividing by the last entry gives the form [a b c; d e f; g h 1][a\ b\ c;\ d\ e\ f;\ g\ h\ 1]. With more than four correspondences the system is overdetermined; the same vector is then the least-squares solution, and its singular value tells how well all points agree.

Not every set of four points works. If three of the corners lie on one line, no invertible projective map can send them to three corners of a rectangle. The best hh is then a singular HH, which squashes the plane.

Rectification by inverse mapping

To fill the front view, go backwards: for every output pixel p′p', compute p=H−1p′p = H^{-1} p' (again with the division by ww), and interpolate the photo bilinearly at pp. Mapping the photo forward instead would leave holes where the front view is stretched. The four corners only fix where the object's corners go, not the object's true proportions; the width-to-height ratio of the rectangle has to come from knowing the object, e.g. √2 for an A4 sheet.

Try this