Epipolar Geometry — A Point Becomes a Line

One camera throws depth away: every point on a ray lands on the same pixel (The Pinhole Camera — A Pixel Is a Ray). A second camera brings depth back, but only if we know which pixel in picture 2 belongs to which pixel in picture 1. Searching all 640 × 480 pixels for every pixel is hopeless. The good news: we never have to.

Shine a laser pointer across a dusty room. To you, standing right behind it, the beam is a single dot. Your friend, a metre to your side, sees the whole beam as a line across the room. Your dot is a pixel in picture 1; your friend's line is everywhere its match can be in picture 2. (A metre on purpose: our two cameras sit B = 1 m apart.)

Brush up ;)

• Where Is the Camera? — R, C and t: bring camera 2's pose, R₂ (a 10° turn toward camera 1) and t₂ = −R₂C̃₂ = (−0.98481, 0, 0.17365), with C̃₂ = (1, 0, 0). In this read, as in its figures, that t₂ is written plain t.
• The Pinhole Camera — A Pixel Is a Ray: bring x̂ = K⁻¹x, the pixel turned back into a ray direction, with K = [[500, 0, 320], [0, 500, 240], [0, 0, 1]].
• Points at Infinity — Horizons, Vanishing Points and the Floor: bring lines as 3-vectors, "two points make a line by a cross product", and the vanishing point v_x of camera 2.

Same rig as always: X = (0.3, −0.2, 4) m lands at x₁ = (357.5, 215) in camera 1 and at x₂ = (320.644, 215.374) in camera 2.

1. The Plane Through Both Cameras

Three points always make a triangle, and a triangle always lies in a plane. Our three points are the two camera centres C₁, C₂ and the world point X.

X (sideways, height)

(0.3, -0.2)

depth of X along camera 1's ray

4.0

▶zoom out camera 2's picture

1

Camera: focal length and principal point

focal length f (px)

500

principal point cₓ (px)

320

principal point c_y (px)

240

Camera 1: move it and turn it

camera 1 sideways x (m)

0.0

camera 1 height (m, up is −)

0.0

camera 1 forward z (m)

0.0

camera 1 turn left/right (°)

0.0

camera 1 tilt up/down (°)

0.0

Camera 2: move it and turn it

camera 2 sideways x (m)

1.0

camera 2 height (m, up is −)

0.0

camera 2 forward z (m)

0.0

camera 2 turn left/right (°)

10

camera 2 tilt up/down (°)

0.0

the worked rigparallel camerasturn camera 2 in furtherx₁ near the top edgemove camera 2 forwardone centrefind e′Reset

• The blue plane is the epipolar plane: the one plane through C₁, C₂ and X. The ink line between the centres is the baseline, B = 1 m.
• Camera 1's whole ray, from C₁ through x₁ and on past X, lies inside that plane. The hollow rings are other points on that ray, at depths 2, 6 and 9 m. All of them land on x₁ = (357.5, 215).
• Camera 2 sees that ray as the plane's slice through its picture: a line, l′, the epipolar line of x₁. The same rings land on it in camera 2's picture, spread out along the line.
• Press play on the depth. x₁ never moves, x₂ slides along l′, and never leaves it. That is the whole read in one slider.

So the search for the match is not over 640 × 480 pixels. It is along one line. At the worked depth of 4 m the match sits at x₂ = (320.644, 215.374), right on l′.

Now press "move camera 2 forward" once. Camera 2 jumps half a metre ahead, and the lines in both pictures (x₁'s and those of four more points, in grey) stop being parallel and fan out from one point each. Then press Reset and come back. Why do they fan, and where to? That is the next section.

Try this: drag x₁ in camera 1's picture to the top edge. l′ moves with it, and still x₂ is on it.

2. Epipoles and Epipolar Lines

Here is the same figure again, opened with camera 2 half a metre forward.

X (sideways, height)

(0.3, -0.2)

depth of X along camera 1's ray

4.0

▶zoom out camera 2's picture

1

Camera: focal length and principal point

focal length f (px)

500

principal point cₓ (px)

320

principal point c_y (px)

240

Camera 1: move it and turn it

camera 1 sideways x (m)

0

camera 1 height (m, up is −)

0

camera 1 forward z (m)

0

camera 1 turn left/right (°)

0

camera 1 tilt up/down (°)

0

Camera 2: move it and turn it

camera 2 sideways x (m)

1

camera 2 height (m, up is −)

0

camera 2 forward z (m)

0.5

camera 2 turn left/right (°)

10

camera 2 tilt up/down (°)

0

the worked rigparallel camerasturn camera 2 in furtherx₁ near the top edgemove camera 2 forwardone centrefind e′Reset

• The lines in each picture are no longer parallel. They fan out from one point, off the right edge of both pictures; the arrows on the edges point to it.
• Every epipolar line in picture 2, whichever pixel of picture 1 it came from, passes through one point. That point is the epipole e′.
• Why one point? Every epipolar plane contains the baseline, so every slice through picture 2 contains the baseline's own slice. The baseline hits picture 2's plane at one point: C₁, as camera 2 sees it.
• The same holds the other way round: camera 1's epipole e is C₂ as camera 1 sees it.
• Now press "find e′". It puts camera 2 back where it was and zooms its picture out eight times: the lines of our rig meet too, at e′, far off the left edge.

Let's write that down. An epipole is the image of the other camera's centre (Hartley & Zisserman, Ch. 9 Epipolar Geometry and the Fundamental Matrix, §9.1, pp. 240–241); for our two cameras that is eq. 9.3 (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, p. 244):

• P₁ = K[I | 0] and P₂ = K[R₂ | t] are the two cameras; C̃₁ = 0 and C̃₂ = (1, 0, 0) m are their centres.
• For camera 2, Kt = (−436.8365, 41.6756, 0.1736). Divide by the last number: e′ = (−2515.64, 240), about 2,500 px off the left edge of a 640-px picture. That is why the lines look parallel in the default view.
• e′ is exactly the vanishing point v_x of Points at Infinity — Horizons, Vanishing Points and the Floor: the baseline runs along the world x axis, and the epipole is where that direction vanishes.
• Press "turn camera 2 in further" (25°, zoomed out three times) and e′ moves in to (−752.3, 240). Turn it to 0° (the "parallel cameras" preset) and Kt = (−500, 0, 0): the last number is 0, e′ is at infinity, and all the lines in picture 2 are rows.
• Camera 1's epipole is e = K C̃₂ = (500, 0, 0), at infinity whatever camera 2's turn. C₂ sits on camera 1's principal plane (beside it, not in front), so camera 1 never sees it at a finite pixel. Every line in picture 1 is a row; x₁'s is the row v = 215.

Why it exists. Every epipolar line in a picture runs through its epipole. Once we have e′, any l′ needs just one more point, and e′ is the first number of the two-camera rig we can check by hand.

What it assumes. - Two different centres, C̃₂ ≠ C̃₁. An epipole is the picture of the other camera's centre; with one shared centre there is no baseline and nothing to picture (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, §9.2.2, p. 244). - Pinhole cameras P = K[R | t] with finite centres: the book lists these formulas under "cameras not at infinity" (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, table 9.1, p. 246).

Where it breaks. - No baseline. Turn camera 2 without moving it and Kt = (0, 0, 0): no epipole, no epipolar lines, and F is the zero matrix (H&Z Ch. 11 Computation of the Fundamental Matrix F, §11.9.3, p. 297). The two pictures are then tied by a homography, the turning camera K R K⁻¹ of Points at Infinity — Horizons, Vanishing Points and the Floor. Try this: press "one centre" in the figure above; the line readout says there is none to search. - A last number of 0. Dividing fails when e′ is at infinity, as in the "parallel cameras" preset. Keep e′ as a 3-vector: the cross products below work on it unchanged.

Once we have e′, the line l′ needs no plane at all. Two points make a line, and the cross product makes it (Points at Infinity — Horizons, Vanishing Points and the Floor):

• x₂ = (320.644, 215.374, 1) is the match, and l′ = (a, b, c) is the line a·u + b·v + c = 0 through both.
• For our rig it comes out as v = −0.008682 u + 218.158: tilted by only −0.4975°, almost a row.

Where it breaks. - x₂ sitting on e′ itself: e′ × e′ = (0, 0, 0), no line. That pixel is where the whole baseline lands, so every epipolar plane goes through it and none is picked out; the book makes the same exception for F, "for any point x (other than e)" (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, p. 245). Our e′ is 2,500 px off the picture, so none of our pixels is there.

NOTE: in our rig C₂ is exactly beside C₁, so camera 1's epipole hides at infinity and picture 1's lines are all rows. That is a lucky rig, not the general case. Move C₂ in front of camera 1's principal plane, as the copy above opened, and e is a finite pixel too and picture 1's lines fan as well.

But this l′ needs x₂, which is the thing we are looking for. We want l′ from x₁ alone. That takes one more idea.

3. The Essential Matrix From Three Arrows

Back to the triangle C₁, C₂, X. Stand at camera 1 and draw three arrows, all in camera 1's axes.

Camera: focal length and principal point

focal length f (px)

500

principal point cₓ (px)

320

principal point c_y (px)

240

Camera 1: move it and turn it

camera 1 sideways x (m)

0.0

camera 1 height (m, up is −)

0.0

camera 1 forward z (m)

0.0

camera 1 turn left/right (°)

0.0

camera 1 tilt up/down (°)

0.0

Camera 2: move it and turn it

camera 2 sideways x (m)

1.0

camera 2 height (m, up is −)

0.0

camera 2 forward z (m)

0.0

camera 2 turn left/right (°)

10

camera 2 tilt up/down (°)

0.0

the true match1 px downthe worked rigReset

• The blue arrow is camera 1's ray, x̂₁ = K⁻¹x₁ = (0.075, −0.05, 1).
• The ink arrow is the baseline, C̃₂ = (1, 0, 0) m.
• The rust arrow is camera 2's ray, turned into camera 1's axes: x̂₂ = K⁻¹x₂ = (0.001287, −0.049252, 1), and R₂ᵀx̂₂ = (−0.17238, −0.04925, 0.98503).
• All three lie in the grey epipolar plane. Three arrows in one plane span a box of zero volume, and the volume of a box is the triple product.

Let's devise the equations step-by-step. The triple product first, written with the plane's normal n = C̃₂ × x̂₁:

• C̃₂ × x̂₁ is the normal n of the epipolar plane (the short grey arrow). Camera 2's ray is in the plane exactly when it is at right angles to n.
• With our numbers the product is −4.2e−17. That is zero: all that is left is rounding in the last digit.

The cross product is a matrix in disguise. For any a = (a₁, a₂, a₃), the cross-product matrix [a]ₓ does to b exactly what a × does (H&Z Appendix 4 Matrix Properties and Decompositions, eqs. A4.5–A4.6, p. 581):

• [a]ₓ is skew: flip it about the diagonal and every entry changes sign.
• For our t = (−0.98481, 0, 0.17365): [t]ₓ = [[0, −0.17365, 0], [0.17365, 0, 0.98481], [0, −0.98481, 0]], the last tile of the three-arrows figure.

Now push R₂ through the triple product. A rotation turns both arrows of a cross product together, R₂(a × b) = R₂a × R₂b, and R₂C̃₂ = −t:

• E is the essential matrix (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, §9.6, eq. 9.11, p. 257); Longuet-Higgins wrote this rule down for two calibrated pictures in 1981 [LONG81].
• The sign flipped on the third row. A zero does not mind: −0 is 0.
• E has 5 degrees of freedom: 3 for the rotation, 3 for the translation, minus 1 because the rule still holds when E is scaled (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, p. 257).

It is just the triple product, written as a matrix. With our numbers, E = [[0, −0.17365, 0], [0, 0, 1], [0, −0.98481, 0]] (the third tile of the three-arrows figure):

• Its singular values are (1, 1, 0): two equal, one zero. That is the fingerprint of every essential matrix (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, res. 9.17, p. 257).
• x̂₂ᵀEx̂₁ = 4.3e−17, zero again: the true match obeys the rule.
• Press "1 px down" in the three-arrows figure. x₂ is now 1 px off l′, camera 2's ray turns red, and x̂₂ᵀEx̂₁ = 2.00e−3. Not zero any more: the three arrows no longer fit in one plane.

Why it exists. Section 2's l′ needed x₂, the pixel we are hunting for. E gives the rule from x₁ alone: E x̂₁ is x₁'s epipolar line in camera 2's ray coordinates, and the match must lie on it.

What it assumes. - K is known for both cameras, so x̂ = K⁻¹x is the real ray (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, §9.6, p. 257). - Rays are straight: the pixels obey the pinhole camera, with no lens bending (Section 5).

Where it breaks. - No baseline, t = 0. Then E = [0]ₓR₂ = 0 and x̂₂ᵀEx̂₁ = 0 for every pair of pixels: the rule says nothing (H&Z Ch. 11 Computation of the Fundamental Matrix F, §11.9.3, p. 297). That is the "one centre" preset of Section 2's figure. - Zero is not proof. The rule only says the two rays lie in one plane: necessary for a match, not sufficient (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, res. 9.3, p. 245). Every pixel along l′ passes, so a wrong match that slides along the line goes through; Triangulation — Two Rays That Almost Meet shows how far such a slide moves the point. - Scale and side are lost. E and −2E give the same zero, so the matches give the direction of t, never its length, and one E fits four camera poses (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, §9.6.2, pp. 258–259). From Matches to Motion — Four Cameras, One Right Answer keeps the one with the point in front of both cameras.

Try this: drag x₂ off the line. Camera 2's ray tips out of the plane, and x̂₂ᵀEx̂₁ stops being zero.

4. F Is E in Pixels

The two-camera figure once more, opened at "find e′": our rig, with camera 2's picture zoomed out. Watch its third tile, F, and how every line in picture 2 runs into e′.

X (sideways, height)

(0.3, -0.2)

depth of X along camera 1's ray

4.0

▶zoom out camera 2's picture

8

Camera: focal length and principal point

focal length f (px)

500

principal point cₓ (px)

320

principal point c_y (px)

240

Camera 1: move it and turn it

camera 1 sideways x (m)

0

camera 1 height (m, up is −)

0

camera 1 forward z (m)

0

camera 1 turn left/right (°)

0

camera 1 tilt up/down (°)

0

Camera 2: move it and turn it

camera 2 sideways x (m)

1

camera 2 height (m, up is −)

0

camera 2 forward z (m)

0

camera 2 turn left/right (°)

10

camera 2 tilt up/down (°)

0

the worked rigparallel camerasturn camera 2 in furtherx₁ near the top edgemove camera 2 forwardone centrefind e′Reset

E works on rays (x̂ = K⁻¹x), so to use it you must know K. Put K back on both sides and the same rule works on raw pixels (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, eq. 9.12, p. 257):

• K⁻¹ = [[0.002, 0, −0.64], [0, 0.002, −0.48], [0, 0, 1]] turns a pixel into a ray; K⁻ᵀ does the same for the other picture's side.
• Our F, scaled so that F₃₃ = −1, is [[0, −1.15e−5, 0.0027492], [0, 0, 0.0329832], [0, −0.0288165, −1]]. Its first column is zero because e = (500, 0, 0) is at infinity along x.

Substitute x̂ = K⁻¹x into x̂₂ᵀEx̂₁ = 0, and the fundamental matrix F gives the rule in pixels (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, res. 9.3, eq. 9.5, p. 245):

• x₁ and x₂ are pixels with a 1 added; l′ is x₁'s epipolar line in picture 2, l is x₂'s in picture 1 (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, p. 245).
• F x₁ = (0.000286, 0.032983, −7.195547), which is v = −0.008682 u + 218.158: the same line as e′ × x₂ in Section 2, now found from x₁ alone. That is the second tile of the two-camera figure.
• x₂ᵀFx₁ = −8.7e−16: zero.
• Fᵀx₂ is the row v = 215 in picture 1, through x₁.

Why it exists. It is E with K folded in, so the rule runs on raw pixels, and it can be estimated from matches alone when nobody hands us K (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, §9.2.3, p. 245).

What it assumes. - Two different camera centres: the book defines F only for "cameras with non-coincident centres" (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, def. 9.4, p. 245). - Straight pixels, undistorted first (Section 5). - To go back from F to E, the right K. Use f = 550 px instead of 500 and KᵀFK's two non-zero singular values differ by 0.3%: not equal, so not an essential matrix any more (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, res. 9.17, p. 257).

Where it breaks. - x₂ᵀFx₁ is not in pixels. Move x₂ 1 px down: with F scaled to F₃₃ = −1 it reads 0.0330, with F × 1000 it reads 33.0, and x₂ is 1.000 px from l′ both times. Judge a match by its distance to its line, as the book's error does (H&Z Ch. 11 Computation of the Fundamental Matrix F, §11.5, p. 288); computeCorrespondEpilines scales lines so that a·u + b·v + c is that distance. - A flat scene, or camera 2 only turned. If every point is on one plane (a wall, a floor), or the camera only rotated, a whole family of F's fits the matches (H&Z Ch. 11 Computation of the Fundamental Matrix F, table 11.1, p. 296; §11.9.2–11.9.3, pp. 296–297). Scenes close to those give a badly conditioned F (H&Z Ch. 11 Computation of the Fundamental Matrix F, §11.9, p. 296). - A noisy F. The true match will not sit exactly on Fx₁; search a band on either side of the line, not the line alone (H&Z Ch. 11 Computation of the Fundamental Matrix F, §11.11, p. 298).

The epipoles are hiding inside F too (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, pp. 245–246). Every line l′ passes through e′, and every line l passes through e, so:

• Fe = (0, 0, 0) and e′ᵀF = (0, 0, 0) to the printed digits: e is F's right null vector, e′ its left one.
• A matrix that sends a whole vector to zero cannot be inverted, so F has rank 2.
• F has 7 degrees of freedom: 9 entries, minus 1 for scale, minus 1 for det F = 0 (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, p. 246).

Where it breaks. - An F estimated from noisy matches comes out full rank: Fe = 0 has no answer, and the lines Fx no longer meet in one point (H&Z Ch. 11 Computation of the Fundamental Matrix F, §11.1.1, fig. 11.1, p. 280). Force rank 2 first by setting its smallest singular value to zero (H&Z Ch. 11 Computation of the Fundamental Matrix F, pp. 280–281).

F knows nothing about K. That is its whole point: it is what you can estimate from matches when nobody gave you K, and E is what you get once you know K. One more way to write it, eq. 9.4 (H&Z Ch. 9 Epipolar Geometry and the Fundamental Matrix, p. 244), is F = [e′]ₓ K R₂ K⁻¹: the turning camera K R K⁻¹ of Points at Infinity — Horizons, Vanishing Points and the Floor, followed by "join to e′".

NOTE: never compare F's singular values between two programs. They change with how F was scaled, and every program scales it its own way. Only "rank 2" (one of them is zero) is a fact about F.

5. Straight Lines Need Straight Pixels

Take our rig and the series' four extra points. In two parallel cameras side by side (the "parallel cameras" preset), every match would sit on the same row as its pixel. How far off are we?

Table. 1 Row mismatch between camera 1's pixel and camera 2's pixel for four more points, in our rig (camera 2 turned in 10°). They are the grey lines of the two-camera figure in Section 1.

• Our rig is almost rectified. Picture 1's lines are exact rows; picture 2's are almost rows, all aimed at e′ = (−2515.64, 240), and x₁'s has a slope of only −0.008682. The matches are within a few rows of their pixels, but not on them: −8.91 px is a long way off when you search one row.
• Turning camera 2 back by its 10° would make picture 2's lines rows too. Stereo Depth — Rectification and Z = fB/d finishes that job, and then the search for the match is along a row.

There is a catch under all of this. Every line in this read is straight only if the pixels obey the pinhole camera. A real lens bends them (Lens Distortion — Bending Straight Lines Back): with k₁ = −0.2 the corner pixel (0, 0) moves 51.2 px inward, and our worked pixel moves 0.073 px.

• In a raw, distorted picture, the image of camera 1's ray is a curve, not a line.
• F only knows straight lines. Fed raw pixels, x₂ᵀFx₁ is not zero even for a perfect match, and the error grows toward the corners.
• So undistort the points first (undistortPoints), then estimate F or E, then draw lines.

6. In OpenCV

Table. 2 This read in OpenCV 4.x [OPEN24].

• OpenCV's p₁ and p₂ are our x₁ and x₂: points1 come from the first picture, and F maps them to lines in the second, the same order as this read.
• Both findFundamentalMat and findEssentialMat vote out bad matches by default (RANSAC); From Matches to Motion — Four Cameras, One Right Answer explains the vote and its defaults.
• computeCorrespondEpilines with whichImage = 1 computes F p₁, lines in picture 2; with whichImage = 2 it computes Fᵀ p₂, lines in picture 1.

NOTE: undistortPoints without its last argument P returns normalised points, x̂ = K⁻¹x with the distortion removed, not pixels. Pass P = K to get undistorted pixels back for F; leave P out if you want the normalised points (rays) for E. Either way, cameraMatrix is the real K.

7. What Came Next

We know the line the match must be on. Search along it, find the match, and the two rays, one from each camera, should cross at X. They almost never do: half a pixel of noise across l′, and our two rays miss each other by about 4 mm. Why, and what do we do about it? That is Triangulation — Two Rays That Almost Meet. Stay tuned.

8. References

1. [HART04] R. Hartley, A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed., Cambridge University Press, 2004. Chapters used in this read: Ch. 9 Epipolar Geometry and the Fundamental Matrix; Ch. 11 Computation of the Fundamental Matrix F; Appendix 4 Matrix Properties and Decompositions.
2. [LONG81] H. C. Longuet-Higgins, "A Computer Algorithm for Reconstructing a Scene from Two Projections", Nature 293, 1981.
3. [OPEN24] OpenCV, Camera Calibration and 3D Reconstruction (calib3d), OpenCV 4.x documentation.