2D transformations

1A point in two coordinate systems

Put a second coordinate system on the plane, with axes x′ and y′. Its origin sits at t′ = (t_x, t_y) and its axes are turned by an angle θ. A point then has two sets of coordinates, m′ = [x′ y′ 1]^T in the new system and m = [x y 1]^T in the old one, and one matrix converts between them:

Read H column by column. The first column, (cos θ, sin θ), is the unit vector of the x′ axis written in the old coordinates, and the second, (−sin θ, cos θ), is the unit vector of the y′ axis. The third is the new origin t′. So Hm′ says: start at t′, walk x′ units along the x′ axis and y′ units along the y′ axis. The 1 at the end of m′ is what adds t′. Without that third component, a shift could not be written as a matrix product.

In blocks, with R′ the 2 × 2 turn by θ:

Going the other way

To get m′ from m, invert H: m′ = H⁻¹m. No general inversion is needed. The columns of R′ are perpendicular unit vectors, so R′^TR′ = I: the inverse of R′ is its transpose, R = R′^T, which turns points by −θ, the same as turning the axes by θ. Its rows are the new axes, so R gives a point's coordinates in the turned axes. Undoing the shift and then the turn, m′ = R(m − t′), gives

In the figure, the new origin is t′ = (3, 1) and the x′ axis points toward (7, 4), four units right and three up, so cos θ = 0.8 and sin θ = 0.6. The point (6, 5) is (3, 4) away from the new origin, so

and in the new system the point is at (4.8, 1.4): 4.8 units along x′ and 1.4 along y′.

Adding a scale

If the new system also uses a different unit, so that one unit along x′ or y′ is s units long in the old system, both unit vectors in H grow by s:

This is a similarity. It multiplies every length by s but keeps angles, so shapes keep their shape. With s = 1 it is the Euclidean transformation above, which keeps lengths as well.

Converting coordinates or moving points

So far the point stayed where it was and H converted its coordinates. The same product can be read with a single coordinate system: H moves the point at m′ to the point at m. The rest of this page uses that reading, with the names swapped so that H moves m to m′. Which way H points is a choice: H⁻¹ moves points back, and it is a transformation of the same kind.

2Four kinds of transformation

In general, H can be any invertible 3 × 3 matrix. It moves the point m = [x y 1]^T to the point m′ given by

The factor λ is there because Hm need not end in 1. As with any homogeneous vector, divide by the third component to read the point; λ is that third component.

The matrices of section 1 keep the bottom row [0 0 1]. Freeing more entries gives looser transformations, four kinds in all, each named by what it still keeps:

Each kind also keeps everything the looser kinds keep: a Euclidean transformation keeps parallel lines and straight lines too.

Where do the counts come from? The Euclidean matrix has three free numbers, the similarity adds s, and the affine matrix frees all six entries of its top two rows. The projective matrix has nine entries, but λH moves every point exactly where H does, because the division by the third component cancels λ. Only eight numbers matter.

Why each kind keeps what it keeps: a turn and a shift move the plane as a rigid piece, so lengths survive. A scale multiplies every length by the same s, so ratios of lengths survive, and with them angles. With the bottom row [0 0 1], nothing is divided, and the transformation is a linear map plus a shift. It sends every direction d to one new direction Ad, with A the top-left 2 × 2 block, so lines that shared a direction still share one and stay parallel; but A can stretch some directions more than others, so angles change. A projective bottom row makes the final division depend on the point, and section 3 shows what that does to parallel lines.

The cross ratio

What does a projective transformation keep, besides straight lines? Lengths along a line change, and so do their ratios, but one ratio of ratios does not. For four points A, B, C and D on a line, their cross ratio is

where AC is the distance from A to C. For the points at 0, 1/4, 1/2 and 1 of the square's top side it is (1/2 · 3/4) / (1/4 · 1) = 1.5, and it stays 1.5 however the square is transformed.

Applying one transformation after another is a matrix product: first H₁, then H₂, is H₂H₁. Two transformations of one kind make a third of the same kind, just as two turns make a turn.

3A photo of a flat surface

Projective transformations come up every time a camera photographs something flat, such as a wall, a page or a floor. Put the camera's center C at the origin, its image plane at distance f₁ in front of it, and a flat surface at distance f₂. Each point of the surface reaches the image along the straight line through C, so the photo of the surface is a map from one plane to another.

If the surface faces the camera, parallel to the image plane, every point of it is at the same distance, and similar triangles shrink the whole surface by the same factor f₁/f₂. The map from the surface to the photo is a similarity:

Tilt the surface by φ about a horizontal line through its center, with its top leaning away. Measure its points (u, v) from its center, with u to the right and v downward, as rows are counted in an image, and the photo's (x, y) the same way. The point (u, v) is then at depth f₂ − v sin φ: the top half, where v is negative, is farther away. The camera divides each point's position by its depth. That division is exactly what a bottom row in H does:

The third component, λ, is the depth. Parts of the surface farther from the camera come out smaller, and the photo is a projective transformation of the surface. In the figure, f₁ = 1, f₂ = 3, and the surface is a square of 3 × 3 tiles. Its readout divides H by f₂, so that it ends in 1; as section 2 showed, that moves no point.

Straight lines stay straight

Even the loosest kind keeps straight lines, and the dot product shows why. A point m lies on the line ℓ when ℓ^Tm = 0. Put H⁻¹H = I in the middle:

So every point of ℓ lands on one line, ℓ′ = H^−Tℓ, where H^−T is the transpose of H⁻¹. Points move with H, and lines move with H^−T. In the picture of homogeneous coordinates, where a point is a line through the origin and a line is a plane through the origin, H is a linear map of space: it sends lines through the origin to lines through the origin, and planes to planes.

Parallel lines can meet

Parallel lines meet at a point at infinity, [p q 0]^T, where (p, q) is their direction. Apply H to it:

If the bottom row of H is [0 0 1], as in the first three kinds, the third component stays 0, and the lines stay parallel. With a projective bottom row it is 0 for only one direction, and parallel lines in any other direction are sent to lines that meet at an ordinary point, their vanishing point: the point in a photo where the rails of a straight track meet. In the figure, the edges of the tiles that run away from the camera have direction (0, 1) on the surface, so they meet at the point at infinity [0 1 0]^T, and in the photo at H[0 1 0]^T. The edges across the surface, direction (1, 0), meet at [1 0 0]^T, which H sends to a point that still ends in 0, so they stay parallel.

A photo of a flat scene is not the only source of homographies. Two photos taken from one spot, with the camera turned, are related by one too, whatever the depth of the scene, because the lines of sight through the shared center are the same for both photos. Section 5 uses that to stitch photos.

4Estimating H from four pairs

Often H is unknown, but some pairs of matching points are known. To straighten a photo of a sign, click its four corners in the photo, m′₁ to m′₄, and pair them with the corners of a square, m₁ to m₄. Each pair m ↔ m′ gives two equations. Since H only matters up to scale, fix h₃₃ = 1, which leaves 8 unknowns, and divide by the third component of Hm:

The division makes these equations nonlinear in the unknowns, but multiplying both sides by the denominator makes them linear:

Stack the unknowns in h = [h₁₁ h₁₂ h₁₃ h₂₁ h₂₂ h₂₃ h₃₁ h₃₂]^T. Each pair then adds two rows to a linear system Ah = b:

Four pairs give eight equations for the eight unknowns, so four is the minimum, and then h = A⁻¹b. No three of the four points may lie on one line; if they do, A is singular and no single H is found. The H found this way sends each pixel of the straightened image to the place of the photo it shows, which is exactly what warping needs (section 5). If a click is off, H still fits the four pairs exactly, and the straightened sign comes out skewed: the figure lets you see it.

More than four pairs

Measured points are never exact, so in practice more pairs are used than needed. With n > 4 pairs, A has 2n rows and no h satisfies all of them. Least squares takes the h that makes the squared errors ‖Ah − b‖² smallest. Setting their derivative to zero gives A^TAh = A^Tb, and so the least-squares solution

The matrix A^TA is 8 × 8 however many pairs there are, so the system to solve stays small.

Fixing h₃₃ = 1 fails in one case: when the true h₃₃ is 0, which happens when H sends the origin of the coordinates to infinity. The general method keeps all nine entries as unknowns, adds −x′ and −y′ as a ninth column of A, and solves Ah = 0 with ‖h‖ = 1. The answer is the right singular vector of A with the smallest singular value, the last row of V^T in the SVD. When h₃₃ ≠ 0 and the pairs fit exactly, as four pairs do, it gives the same H up to scale. With more pairs that do not fit exactly, the two methods measure the error differently, so their answers differ slightly.

5Warping an image

To transform a whole image, every pixel of the output needs a gray value. In pixel coordinates, x counts columns to the right and y counts rows downward. Let I′ be the source image and I the output. In the figure, the output is the source enlarged 1.5 times and turned by 20°.

Going forward, sending each source pixel to where it lands in the output, seems the natural way, but it fails. A landing spot is rarely the center of a pixel, and after rounding, some output pixels receive two source pixels and others receive none. When the image is enlarged, most receive none: in the figure, the enlarged source covers 124 output pixels, but its 64 pixels fill only 56 of them (the other 8 land beyond the edge of the output), and 68 are left as holes.

So warping goes backward. Write H so that λm′ = Hm takes each output pixel m to the place m′ of the source it shows, and for each pixel of the output, compute m′ and read the source there. Each output pixel asks where it comes from and gets exactly one answer, so there are no holes. The dots on the source in the figure are these answers, one for each output pixel.

An answer m′ = (x′, y′) is rarely the center of a pixel either, so the value has to be read between the four source pixels around it. Call them I′₁ (top left), I′₂ (top right), I′₃ (bottom left) and I′₄ (bottom right). There are two common ways.

Nearest pixel. Take the value of whichever of the four is closest. It is fast, but edges come out jagged.

Bilinear interpolation. Blend all four. The point m′ splits the square between their centers into four rectangles, with areas A (top left), B (top right), C (bottom left) and D (bottom right). Each pixel is weighted by the area of the rectangle opposite it:

Why the opposite rectangle? As m′ moves toward I′₁, the rectangle D opposite it grows until it fills the whole square. So a point on top of a pixel gets exactly that pixel's value, and in between the value changes smoothly. The four areas add up to the whole square, 1, so a region of constant gray keeps its gray.

When m′ falls outside the source image, there is nothing to read, and the output pixel is left empty, usually as 0.

Stitching photos into a mosaic

A panorama is made from photos taken from one spot while the camera turns. As section 3 showed, such photos are related by a homography, so one can be warped onto the other. It takes four steps, which put sections 4 and 5 to work.

1. Find distinctive points. A keypoint detector such as SIFT finds corners and blobs in each photo, and describes the patch around each one with a vector. The vectors are built so that the same spot seen in the other photo gets a similar one.
2. Match them. For each keypoint of one photo, find the two most similar vectors in the other. Keep the match only if the best is much closer than the second best. This ratio test drops spots that look like many others, such as one window in a row of windows.
3. Estimate H robustly. Some matches are still wrong after the ratio test, and one wrong pair can pull the least-squares H far off. RANSAC avoids this: pick four matches at random, compute H from them exactly, and count how many of all the matches this H maps to within a few pixels of their partners. Repeat many times, keep the H with the most such inliers, and refine it by least squares on those inliers only. The note on camera calibration shows RANSAC at work.
4. Warp onto a larger canvas. Write H so that it takes points of the second photo to the first. Sending the corners of the second photo through H shows where it lands, and some corners may land at negative coordinates or beyond the edges of the first photo. A shift T that brings every corner into view fixes this. A shift is itself a homography, so the second photo goes onto the canvas through the product TH, and the first photo through T alone. To fill the canvas, each of its pixels reads the second photo through (TH)⁻¹, backward as above.

6Summary

The key ideas next to their NumPy and OpenCV equivalents.