Triangulation — Two Rays That Almost Meet

Read 7 told us where to look for the match. Say we found it: x₁ ↔ x₂, and we know both cameras. Two rays, one point. Cross them, done?

Almost. The whole read hangs on three steps:

• back-project each pixel into a ray (one per camera);
• cross the two rays, which never meet exactly, so we need a rule for "where they nearly meet";
• check how much to trust the answer, which depends on the angle between the rays.

Two friends stand at opposite ends of a field and both point at the same bird on a wire. Each finger is a ray. If their arms were perfect, the two lines would cross right at the bird. They are not: one finger is a little high, the other a little left, and the two lines pass each other in the air a few centimetres apart. Where is the bird? Somewhere between the fingers, and how sure you can be depends on how far apart the two friends stand.

Brush up ;)

• Epipolar Geometry — A Point Becomes a Line: the epipolar line l′ = Fx₁ in camera 2's picture, and F itself. l′ comes back in Section 2, F in Section 4.
• Finding the Camera From Known Points — P by Least Squares: the smallest singular vector solves Ap = 0. Here the roles swap.
• The Pinhole Camera — A Pixel Is a Ray: a pixel is a ray, x̂ = K⁻¹x.

Both cameras are known here: a calibrated rig, the kind stereoCalibrate hands you, and the series' usual one. K has f = 500 px and principal point (320, 240) for both cameras, camera 1 sits at the origin, and camera 2 sits at C₂ = (1, 0, 0), turned 10° toward camera 1 (baseline B = 1 m). The point is X = (0.3, −0.2, 4) m, seen at x₁ = (357.5, 215) and x₂ = (320.644, 215.374).

1. Four Rows and One Null Vector

noise added to x₂ (px)

(0, 0.5)

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

0.5 px on v₂along l′across l′no noisethe worked rigReset

Press no noise first. The blue ray from C₁ through x₁ and the rust ray from C₂ through x₂ cross exactly at X, X̂ sits on X, and the gap reads 0.000 mm. Now, why it works, so that it still gives an answer once the rays stop meeting.

• Each camera turns X into a pixel by λx = PX: multiply, then divide by the last number (read 1).
• So each camera knows two things about X, its u and its v. Two cameras give four.
• X has three unknowns; written homogeneously, (X, Y, Z, W), it has four, defined only up to scale. Four equations for three real unknowns is one more than needed. With exact pixels they agree and the four rows have a null vector; with noise they do not, and we take the closest thing to one.

Let's devise the equations step by step. Write the rows of a camera P as P¹ᵀ, P²ᵀ, P³ᵀ. Then PX = (P¹ᵀX, P²ᵀX, P³ᵀX), and the pixel is u = P¹ᵀX / P³ᵀX, v = P²ᵀX / P³ᵀX. Multiply the division away; the book gets the same two rows from read 4's cross product, x × (PX) = 0 (Hartley & Zisserman, Ch. 12 Structure Computation, §12.2, p. 312):

• u, v: the measured pixel, in px.
• Pⁱᵀ: row i of the 3×4 camera P, as in read 4, so PⁱᵀX is one number.
• X: the unknown point, a 4-vector (X, Y, Z, W).

Both lines are linear in X: the unknown scale λ has gone. Numbers are always satisfying, so take camera 1. P₁ = K[I | 0] has rows (500, 0, 320, 0), (0, 500, 240, 0) and (0, 0, 1, 0). With u₁ = 357.5 the first row becomes 357.5 × (0, 0, 1, 0) − (500, 0, 320, 0) = (−500, 0, 37.5, 0). Put in X = (0.3, −0.2, 4, 1): −500 × 0.3 + 37.5 × 4 = 0. The second row is (0, −500, −25, 0), and −500 × (−0.2) − 25 × 4 = 0 as well. The 37.5 and −25 are x₁'s offset from the principal point, as in read 1.

Stack two rows from each camera and we get the whole system:

• A: 4×4, one row per measured coordinate; rows 3 and 4 use camera 2's P₂ = K[R₂ | t₂] from read 2 and x₂ = (u₂, v₂).
• The answer: the singular vector of A with the smallest singular value. It is the same trick as read 4's DLT (the direct linear transform): two rows per measured pixel, then the smallest singular vector, with the unknown now X instead of P (the book calls it "the direct analogue": H&Z Ch. 12 Structure Computation, p. 312).

Why it exists. Each pixel on its own is only a ray. The four rows turn "both pixels came from X" into equations that are linear in X, so one SVD finds the point, the same tool as read 4.

What it assumes. - Both cameras are known exactly, and all the error is in the pixels (H&Z Ch. 12 Structure Computation, p. 310). - x₁ and x₂ really are the same point: the rows trust the match that Epipolar Geometry — A Point Becomes a Line's search handed over. - Undistorted pixels, so that λx = PX holds (Lens Distortion — Bending Straight Lines Back).

Where it breaks. - X on the baseline. For a point on the line through C₁ and C₂, both rays are the baseline itself and meet along their whole length: the point cannot be found (H&Z Ch. 10 3D Reconstruction of Cameras and Structure, p. 263). Our baseline runs along camera 1's x axis, beside it, so camera 1 never sees such a point. - Raw pixel sizes. The rows mix entries in the hundreds with 0s and 1s; the book's advice from read 4 on normalising the pixels first applies here too (H&Z Ch. 12 Structure Computation, p. 313).

NOTE: In read 4 the points were known and the camera was the unknown; here the cameras are known and the point is the unknown. Same SVD, same "smallest singular vector", and the same reason: noise means AX = 0 has no exact answer, so we take the X that makes |AX| smallest with |X| = 1.

With the exact pixels the unit null vector is (0.07248, −0.04832, 0.96645, 0.24161). It is homogeneous, so the last step is read 1's lesson again: divide by the last number.

• X̂: the estimate, in metres, in camera 1's frame (the world frame of this series).
• W: the fourth entry of the null vector.

Dividing by W = 0.24161 gives 0.07248 / 0.24161 = 0.3, −0.04832 / 0.24161 = −0.2 and 0.96645 / 0.24161 = 4. X̂ = (0.3, −0.2, 4): the point is back. This is the linear method of triangulation, read 4's straight-line estimate applied to a point.

Where it breaks. - W near 0, a very far point. Take a point at infinity along x₁'s ray: camera 2 sees it at (447.35, 214.27), and the four rows give W = 0 to rounding. Add 0.5 px to u₂ and X̂ = (−79.4, 53.0, −1059.1) m, a kilometre behind camera 1; take 0.5 px off and it is (79.4, −52.9, 1058.8) m. The book warns against fixing W = 1 when the true W is close to 0 (H&Z Ch. 12 Structure Computation, p. 313); check W, and its sign, before dividing (the OpenCV note in Section 6).

Try this: press no noise; the second tile spells out the same division.

2. Why Noisy Rays Miss

Press Reset. The figure is back at its default: x₂'s v has 0.5 px of noise, so camera 2 measures x₂ at (320.644, 215.874) instead of (320.644, 215.374). Look at the "Near X, 60× closer" picture: the blue and the rust ray no longer cross. They pass each other with a gap.

Back to the field. Your friend's finger is off by a hair. If it is off sideways along the line joining you two, both fingers still sweep through one flat sheet of air and still cross, just nearer or farther than the bird. If it is off up or down out of that sheet, the fingers pass each other and never cross at all.

That sheet is the epipolar plane of read 7: C₁, C₂ and X. Camera 2 sees it edge-on as the line l′. So the noise on x₂ splits into two parts:

• noise that moves x₂ across l′ tilts camera 2's ray out of the epipolar plane. The two rays become skew, and they miss;
• noise along l′ keeps the ray inside the plane. The rays still meet, but at the wrong depth;
• our 0.5 px on v is almost exactly across, because l′ in our rig is tilted only 0.4975° from the image rows.

There is no new equation here (H&Z Ch. 12 Structure Computation, §12.1, pp. 310–311): the four rows are the same, only u₂ or v₂ moves. Let's read the numbers off the figure.

• 0.5 px on v₂ (across). X̂ = (0.3, −0.198, 3.9999), 2.04 mm from X. The depth moves by only 0.07 mm; the error is almost all in height. The rays are 4.056 mm apart at their closest. X̂ projects back 0.254 px from x₁ and 0.250 px from the noisy x₂: the half pixel is shared between the two pictures.
• 0.5 px exactly across l′. Press across l′. Almost the same: 2.03 mm.
• 0.5 px on u₂ (along). Press along l′. The gap shrinks to 0.035 mm, nearly zero, yet the error grows to 16.62 mm, and 16.55 mm of that is depth. X̂ = (0.3012, −0.2008, 4.0166).

So the gap tells you that something is wrong, not how wrong: the along error is much bigger and leaves almost no gap to warn you.

The smallest singular value of A says the same thing in numbers: 0.347 in the across case, 0.00301 in the along case. It is zero for rays that meet; along noise barely moves it.

NOTE: A tiny reprojection error does not mean a good point. In the along case the residuals are 0.002 px in each picture, and the point is still 16.62 mm off, 16.55 mm of it in depth. Matches that slide along the epipolar line are invisible to this check.

Try this: drag the noisy x₂ in the "Camera 2, 64× closer" picture along l′, then across it, and watch the gap and the error trade places.

3. The Midpoint and Its Limits

noise added to x₂ (px)

(0, 0.5)

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

0.5 px on v₂along l′across l′no noisethe worked rigReset

In the "Near X, 60× closer" picture, the short ink segment between the two rays is their common perpendicular: the shortest segment that joins them. The hollow ring sits in its middle, and X̂ from the four rows sits right on that ring.

The midpoint is the method most of us would invent first:

• walk along ray 1 and ray 2 until the two walkers are as close as they can get;
• take the point halfway between them.

• C̃₁, C̃₂: the camera centres, (0, 0, 0) and (1, 0, 0) m.
• d₁, d₂: the ray directions in the world frame, d₁ = K⁻¹x₁ and d₂ = R₂ᵀK⁻¹x₂.
• λ₁, λ₂: how far to walk along each ray, chosen so that the segment between the two walkers is the shortest.

With the exact pixels, d₁ = (0.075, −0.05, 1) and d₂ = (−0.17238, −0.04925, 0.98503). With the 0.5 px on v₂, the walkers stop 4.056 mm apart and the midpoint is 2.04 mm from X. With 0.5 px on u₂ it is 16.62 mm. Both are the same as the linear method, to the digits shown.

Why it exists. Noisy rays miss each other, and "halfway along the shortest gap" is the first rule anyone would try for where they nearly meet.

What it assumes. - The rays are not parallel, so there is one shortest segment between them. - Distances in 3-D mean something: the bullets below say what happens when they do not.

Where it breaks. - Parallel rays. For the point at infinity above, R₂ᵀK⁻¹x₂ points the same way as K⁻¹x₁: the two rays never get closer, no λ₁, λ₂ is best, and the formula divides by zero.

So on our rig the two methods agree. Why not just use the midpoint? Because it measures distance in 3-D.

• On a calibrated rig, 3-D distance means something, and the midpoint is fine.
• When the cameras are known only up to a projective map (from F alone, with no K), straight lines stay straight but distances and midpoints do not. The book calls the midpoint "not projective-invariant" for exactly this reason (H&Z Ch. 12 Structure Computation, p. 311).
• Fig. 12.5 of the book (H&Z Ch. 12 Structure Computation, p. 320) shows it losing to the best method in such a frame as the noise grows.
• The four rows are no better there: fixing |X| = 1 does not survive a change of frame either, so the linear method is not projective-invariant (H&Z Ch. 12 Structure Computation, p. 313).

Distances in the pictures, in pixels, mean the same in any frame. That is where the best answer lives.

4. Correct the Pixels First

Here are the four noise cases side by side.

Table. 1 The linear method on the series rig (x₁ = (357.5, 215), x₂ = (320.644, 215.374), B = 1 m) with half a pixel added to x₂ in four directions. Residuals are picture 1 / picture 2. The midpoint gives the same errors.

noise added to x₂ (px)

(0.00434, 0.49998)

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

0.5 px on v₂along l′across l′no noisethe worked rigReset

Read the last column, here and in the figure's third tile. When the noise is across l′, the rays cannot meet, and every method has to leave some error in the pictures. The question is which pixel error is the right one to leave.

The cleanest answer moves the two measured pixels as little as possible, onto a pair of epipolar lines that match. Call the moved pixels x̄₁ and x̄₂. Once they sit on matching lines, their rays lie in one epipolar plane and meet exactly, and any method gives the same point (H&Z Ch. 12 Structure Computation, eq. 12.1, p. 314):

• x₁, x₂: the measured pixels; x̄₁, x̄₂: the corrected pixels.
• d(·, ·): the distance between two pixels in the picture, in px.
• F: the fundamental matrix of read 7. The constraint says x̄₂ lies on the epipolar line of x̄₁.

This is the reprojection error from Finding the Camera From Known Points — P by Least Squares again: pixels, not millimetres in space. That is why it gives the same answer in any projective frame, and why it has the smallest reprojection error of all answers. Under Gaussian pixel noise the corrected pixels are also the most likely ones (H&Z Ch. 12 Structure Computation, p. 314).

In our v-noise case the correction moves x₁ and x₂ by about as much as the linear method's residuals, 0.254 and 0.250 px, onto a matching pair of lines, and then the rays cross with no gap. On a calibrated rig at half a pixel the linear answer is already very close to the best one.

Why it exists. When the rays miss, some pixel error has to stay. This equation leaves the smallest one, measured in the pictures, where it means the same in any frame (H&Z Ch. 12 Structure Computation, p. 312).

What it assumes. - F, or the two cameras, are exact; only the pixels are noisy (H&Z Ch. 12 Structure Computation, p. 310). - The pixel noise is Gaussian: that is what makes the corrected pixels the most likely ones (H&Z Ch. 12 Structure Computation, p. 314). - The match is right.

Where it breaks. - Noise along l′. The measured pair already sits on matching lines, so the correction moves nothing and the 16.62 mm stays (Table 1, last row, and the NOTE of Section 2). Try this: press along l′ in the figure above. - A wrong match. It is moved onto matching lines too, and gives a confident wrong point: the cost only knows the distance to the lines. Look at how far the pixels moved before trusting the point.

How to find x̄₁ and x̄₂? Hartley and Sturm turned it into a search over the pencil of epipolar lines: one number τ picks a line in picture 1, F gives its partner in picture 2, and the sum of squared distances becomes a function of τ alone. Setting its derivative to zero gives a polynomial of degree six in τ; take its real roots, try each, keep the best [HART97b] (H&Z Ch. 12 Structure Computation, §12.5, pp. 315–319). OpenCV packages it as correctMatches.

Minimise the same pixel error over many cameras and points at once and it is called bundle adjustment: another series.

5. The Angle Between the Rays

pixel noise (px)

0.5

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

short baselinehalfwidethe worked rigReset

Seen from above, each ray is really a thin wedge: the pixel is known only to within the noise, so the ray only to within an angle of noise / f. Where the two wedges overlap is a diamond, and the point can be anywhere inside it. The close-up shows that diamond at 0.5 px.

• With the rays far from parallel the diamond is short.
• As the angle closes the diamond grows long and thin, stretched along the rays. That stretch is depth error.
• The baseline matters through the angle it makes at the point. The book's own words: "A good rule of thumb is that the angle between the rays determines the accuracy of reconstruction. This is a better guide than simply considering the baseline" (H&Z Ch. 12 Structure Computation, §12.6, p. 321, fig. 12.6).

No new equation here. Read 10 will put a formula on the depth spread for a rectified rig.

Our rig's rays meet at X at 14.20°. Keep X where it is and slide camera 2 along the x axis:

camera 2 at	angle between the rays
(0.25, 0, 0) m	3.57°
(0.5, 0, 0) m	7.14°
(1, 0, 0) m (our rig)	14.20°
(2, 0, 0) m	27.28°

Table. 2 The angle at X = (0.3, −0.2, 4) between the two rays as camera 2 slides along the x axis, keeping its 10° turn.

Try this: press short baseline and watch the close-up. The angle closes and the diamond stretches along the rays while its width barely changes; wide shrinks it back.

Two more things:

• Moving straight forward is worst. A camera that moves toward the point sees it along almost the same ray twice; the angle is near zero and the diamond is nearly endless (H&Z Ch. 12 Structure Computation, fig. 12.6, p. 321).
• The diamond is not symmetric. The far half is longer than the near half, because the wedges widen with distance; set the noise to 2 px on the short baseline to see it. The book's fig. 12.7 shows the same lopsidedness: the spread of the point is not a Gaussian (H&Z Ch. 12 Structure Computation, p. 322).

NOTE: A wider baseline buys a wider angle, but the two pictures also look less alike, and matching gets harder. The angle is the guide; the baseline is the knob you turn to get it.

6. In OpenCV

Table. 3 This read in OpenCV 4.x [OPEN24]. points4D comes back in the world frame of P1 and P2: camera 1's frame for our rig.

• triangulatePoints returns homogeneous points, 4 numbers each. Forget the division by W and every point looks wrong by a different scale.
• correctMatches is documented as the book's optimal method: it minimises d(points1, newPoints1)² + d(points2, newPoints2)² subject to newPoints2ᵀ F newPoints1 = 0, the equation of Section 4. Run it before triangulatePoints for the answer with the smallest reprojection error.
• If P1 and P2 come from stereoRectify, the points come back in camera 1's rectified frame, not its original one.

NOTE: The docs ask for all inputs to triangulatePoints to be of float type. And a point at infinity, whose last number is 0, raises no error in convertPointsFromHomogeneous: the docs say it comes back as (0, 0, 0), while OpenCV 4.x itself returns it undivided. Either way, check W yourself before dividing.

7. What Came Next

Every ray in this read started from a camera whose pose we were handed. In practice you often have the matches and K and nothing else: the second camera was a phone moved by hand. Take camera 2's pose away. All that is left is the matches and K. Can the matches alone tell us where camera 2 is? That is From Matches to Motion — Four Cameras, One Right Answer, and the four rows of this read come back there to pick the one right answer out of four. 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. 10 3D Reconstruction of Cameras and Structure; Ch. 12 Structure Computation.
2. [HART97b] R. Hartley, P. Sturm. Triangulation. Computer Vision and Image Understanding 68(2), 1997.
3. [OPEN24] OpenCV 4.x documentation, Camera Calibration and 3D Reconstruction (calib3d): stereoCalibrate, triangulatePoints, convertPointsFromHomogeneous, correctMatches, stereoRectify.