Epipolar geometry

1Two images of one point

One image cannot tell how far away a point is. A pixel m₁ fixes the ray on which its point of space lies, the ray from the optical center C₁ through m₁, but not where on that ray. Now take a second image from another place. A point M of space appears in both, as m₁ in the first and m₂ in the second. Two such pixels are called corresponding points: images of the same point of space.

Given m₁ alone, where can m₂ be? M is somewhere on the ray of m₁, and every point of that ray is a candidate. The second camera sees each candidate from its own optical center C₂. A camera takes a straight line of space to a straight line of the image, so the images of all the candidates lie on one line of the second image. That line is the epipolar line of m₁, ℓ₂.

This is the epipolar constraint: if m₁ and m₂ are corresponding points, then m₂ lies on the epipolar line of m₁. The constraint is necessary, but not sufficient. Every pixel of the line passes it, and only one of them is the image of M. A third image can single it out, as the note on multiple views shows. Still, it turns a search for m₂ over the whole second image into a search along one line. In an image of N × N pixels, that is N candidates instead of N².

2The epipolar plane and the epipoles

The two optical centers and M lie on one plane, the epipolar plane π. Both rays lie on it: the ray of m₁ joins C₁ and M, and the ray of m₂ joins C₂ and M. Each image plane cuts π along a line, and those two lines are the epipolar lines. With R₁ and R₂ for the two image planes,

So the constraint works both ways. m₁ lies on ℓ₁, the epipolar line of m₂ in the first image.

The line through the two optical centers is the baseline. Another point M′ of space has an epipolar plane π′ of its own, with other epipolar lines. But every epipolar plane contains C₁ and C₂, so every one contains the baseline. So all the epipolar lines of an image pass through one point, where the baseline crosses its image plane. That point is the image's epipole:

The baseline passes through both centers, so e₁ is where the first camera sees C₂, and e₂ is where the second camera sees C₁.

The example

The example on this page is a series of X-ray images, 2688 × 2208 pixels each, of an object that turns 2° about a vertical axis between one image and the next. The X-ray source plays the part of the optical center, as in the note on 3D transformations. Seen from the object, the source moves around a horizontal circle. Images 1 and 82 are 162° apart on that circle, so their sources almost face each other. Two things follow.

• The plane of the circle contains both optical centers, so it is an epipolar plane. Both epipoles lie on the line where it crosses the images, which is almost a row of pixels, at v ≈ 1285.
• Each source lies almost straight ahead of the other, so each image sees the other source, near its edge: both epipoles fall inside their images.

3The fundamental matrix from the two cameras

Now in equations. Call the general projection matrices of the two cameras A and B, as in the note on camera calibration. A point M = [X Y Z 1]^T, in the same coordinates for both cameras, appears at

The goal is the epipolar line ℓ₂ from m₁, A and B alone.

Two points of the ray

ℓ₂ is the image of the ray of m₁, and a line is fixed by two of its points, so two points of the ray are enough. One is C₁. Every ray of the first camera starts there, so A sends it to the zero vector, AC₁ = 0, and it can be found from A alone, as in the note on camera calibration.

The other point comes from m₁. Any M with AM = m₁ projects onto m₁, so it lies on the ray. Three equations do not fix four unknowns, but the pseudo-inverse of A picks one solution:

AA^T is a 3 × 3 matrix, invertible because A has rank 3. Then AA⁺ = AA^T(AA^T)⁻¹ = I, so AM⁺ = m₁. The product the other way round, A^TA, would not do: it is 4 × 4 but still has rank 3, so it has no inverse.

M⁺ is a different point from C₁, since A sends it to m₁, not to 0. Of all the points of the ray, it is the one whose vector [X Y Z W]^T is shortest, which makes it perpendicular to C₁ as a vector of four numbers. That choice is a matter of algebra: any other point of the ray would give the same line.

Their images in the second view

B projects both points into the second image:

The first is the epipole, the image of C₁. The second is some point of ℓ₂.

The line through them

The line through two points is their cross product, as in the note on homogeneous coordinates:

A cross product with a fixed vector u is linear in the other factor, so it is a matrix product, u × v = [u]_×v, with

Multiplying it by v = [v₁ v₂ v₃]^T gives the three components of u × v; the first is u₂v₃ − u₃v₂. With u = BC₁, the line becomes a matrix times m₁:

The 3 × 3 matrix F is the fundamental matrix. It depends only on A and B, not on m₁, m₂ or M: one matrix gives the epipolar line of every pixel of the first image.

The epipolar constraint

A point lies on a line when their dot product is zero, ℓ^Tm = 0, as in the note on homogeneous coordinates. So m₂ lies on ℓ₂ = Fm₁ exactly when

That is the epipolar constraint as one equation, which every pair of corresponding points satisfies.

4Properties of F

Epipolar lines in the first image

Transposing the constraint gives m₁^TF^Tm₂ = 0, which says that m₁ lies on the line F^Tm₂. So

F takes points of the first image to lines of the second, and F^T goes the other way. Swapping the cameras, with B as the first and A as the second, gives F^T, up to scale.

Scale

For any number k ≠ 0, kF gives the same lines and the same constraint. So F is homogeneous, like A and B.

Its determinant is 0

[u]_×u = u × u = 0, so [u]_× sends a vector other than 0 to 0, and it is singular. F has it as a factor, so det F = det [BC₁]_× · det BA⁺ = 0. A homogeneous 3 × 3 matrix has eight free numbers, and det F = 0 takes one more away: F has seven degrees of freedom.

The epipoles

Every epipolar line of the second image passes through e₂, so e₂^TFm₁ = 0 for every m₁. That can only happen if e₂^TF is the zero row, and in the same way for the other epipole:

Fe₁ = 0 has a picture too. The ray of e₁ is the baseline itself, which passes through C₂, so the second camera sees the whole ray as one point, e₂, not as a line. And the zero vector stands for no line.

These equations find the epipoles from F alone. F^Te₂ = 0 says that e₂ is perpendicular to every column of F, so it is the cross product of two columns of F, divided by its third component to read it. In the same way, e₁ is the cross product of two rows of F.

Two images from one optical center

If C₂ = C₁, then BC₁ = 0 and F = 0: there is no baseline, no epipole and no epipolar line. Both images then show the same rays, and they are related by a homography instead, as in the note on 2D transformations.

5The same F from one determinant

The same F comes out of the two projection equations without drawing any line. Move all their terms to the left, AM − λ₁m₁ = 0 and BM − λ₂m₂ = 0. That is six equations in six unknowns, the four components of M, λ₁ and λ₂, and they form one system Gv = 0:

Here G is 6 × 6: A and B fill its first four columns, m₁ and m₂ its last two. If m₁ and m₂ correspond, the point M they come from gives a solution v ≠ 0. A square system with right side 0 has a solution other than 0 only when its determinant is 0, so det G = 0.

Expand det G along its last two columns, the only ones that hold the pixels. Picking component j of m₁ strikes out row j of A, and picking component i of m₂ strikes out row i of B. Each term is those two components times the 4 × 4 determinant of the rows left: two rows of A and two of B. So det G is linear in m₁ and linear in m₂, which is exactly the form m₂^TFm₁, with

For the two images of the example, this F equals [BC₁]_×BA⁺ up to scale, to eleven significant digits. It also shows why the constraint has this form and no other: det G is linear in each pixel, however the cameras are placed.

6Measured points miss the line

Real pixels are measured and A and B are estimated, so a pair of corresponding points almost never satisfies m₂^TFm₁ = 0 exactly: m₂ lies near its epipolar line, not on it. So the constraint is used with a tolerance. m₂ is accepted as a possible match when its distance to ℓ₂ = Fm₁ = [a b c]^T is below some d₀:

Why this is the distance: (a, b) is perpendicular to the line ax + by + c = 0. Moving a point by a distance t along the unit vector (a, b)/√(a² + b²) changes ax + by + c by t√(a² + b²), and the value is 0 on the line. So the value at m₂, which is m₂^TFm₁, divided by √(a² + b²), is how far m₂ is from the line. A line scaled so that a² + b² = 1 gives the distance directly, with a sign for the side.

The tolerance depends on how well the pixels and the cameras are known: a pixel or two for corners found by a program, more for points clicked by hand. With a third image the test becomes much stricter, as the note on multiple views shows.

7Estimating F from corresponding points

So far F came from A and B. When the cameras are not calibrated, F can be estimated from the images alone, from pairs of points known to correspond, such as the same corner found in both. Each pair m₁ = [x₁ y₁ 1]^T, m₂ = [x₂ y₂ 1]^T satisfies m₂^TFm₁ = 0. Multiplied out,

F_ij multiplies component i of m₂ and component j of m₁, and the pixels are known numbers, so the equation is linear in the nine entries of F. Stacking them row by row in f = [F₁₁ F₁₂ … F₃₃]^T, each pair gives one row:

Eight pairs

F is homogeneous, so one entry can be fixed, as a₃₄ was in calibration: F₃₃ = 1. The last term of each row moves to the right side, and the eight unknowns left, f′ = [F₁₁ … F₃₂]^T, satisfy

where each row of Q is [x₁x₂ y₁x₂ x₂ x₁y₂ y₁y₂ y₂ x₁ y₁] and each entry of r is −1. Eight pairs give a square system, solved as f′ = Q⁻¹r. More pairs are fitted by least squares, as in calibration: f′ = (Q^TQ)⁻¹Q^Tr.

Fixing F₃₃ = 1 fails only if the true F₃₃ is 0. F₃₃ is m₂^TFm₁ for m₁ = m₂ = [0 0 1]^T, so that happens when pixel (0, 0) of the second image lies on the epipolar line of pixel (0, 0) of the first. The choice can also be avoided, as for homographies and calibration: keep all nine unknowns and solve Qf = 0 with ‖f‖ = 1, whose answer is the right singular vector of Q with the smallest singular value.

Why eight, when F has seven degrees of freedom

The linear method treats the eight ratios of F as independent. It cannot also impose det F = 0, which is not a linear condition on the entries of F, so it needs eight equations. And an estimate from measured pixels is not exactly singular.

Which pairs

Eight pairs are not enough if their points of space all lie on one plane. The pixels of a plane in two images are related by a homography, as in the note on 2D transformations, and then Q has rank 6 at most: a whole family of matrices satisfies every equation. The points must spread in depth, off any single plane.

How sensitive it is

In pixels, the columns of Q differ enormously in size: x₁x₂ reaches 7·10⁶ in images of this size, while x₁ stays below 3000. The entries of F differ in the opposite way, and small errors in the pixels are magnified. With exactly eight pairs, the estimate passes each epipolar line exactly through its m₂, a wrong one included, and the lines of all the other points pay for it. More pairs, fitted by least squares, let the fit notice the wrong one: its line no longer follows it, and the others move less.

In the figure below, the pairs are points of the object, projected into images 1 and 82 and rounded to whole pixels. The rounding alone leaves the lines of other points of the object 1.10 pixels from their true matches on average with eight pairs, and 0.47 with sixteen. Moving the point of pair 3 in image 82 down by 30 pixels makes the difference plain. With eight pairs, its line follows it exactly, and the lines of the other points move off by 22.38 pixels on average. With sixteen, its line stays 21.12 pixels from it, and the others move off by only 2.90.

8Summary

The key ideas next to their NumPy equivalents. In code, A, B and F are mat_a, mat_b and mat_f, and pixels are homogeneous vectors such as m1 = np.array([x1, y1, 1]).