Epipolar Geometry, Stereo Vision, and Depth Estimation

One camera cannot tell a small nearby object from a large distant one. Two cameras can, because the same point lands at different horizontal positions in each. That shift is called disparity, and turning it into millimetres takes one short formula.

Prerequisites: Camera calibration — stereo depth is only as good as the intrinsics feeding it.

The problem: a delivery robot on a pavement

A small delivery robot rolls along a pavement. It must stop for obstacles — a bollard at 3 m is fine to plan around, a person stepping out at 1 m is not. A single camera detects the person perfectly well but cannot say whether they are 1 m or 5 m away. A tall adult far off and a child up close produce nearly identical boxes.

Two cameras, 120 mm apart, solve it. The person appears in both, but at different horizontal positions, and the size of that difference is the distance.

graph TD
  A["Left camera"] --> C["Rectify both<br/>using calibration"]
  B["Right camera"] --> C
  C --> D["Search along matching rows<br/>for each pixel"]
  D --> E["Disparity map d(x,y)"]
  E --> F["Z = f·B / d"]
  F --> G["Depth in millimetres"]

The epipolar constraint

Take a point in the left image. Where can it be in the right image?

The camera only knows the direction the point lies in, not how far. So the point could be anywhere along a ray going out from the left camera. Project that entire ray into the right image and it becomes a line — the epipolar line.

This is enormously useful. Instead of searching a whole 1920×1080 image for the match, you search one line. That is roughly 2 million candidates reduced to about 1,900, a thousandfold saving, and it also removes most opportunities for a wrong match.

Algebraically, for a point $x$ in the left image and its match $x'$ in the right:

$x'^T F x = 0$

$F$ is the fundamental matrix A 3x3 matrix relating corresponding points between two uncalibrated views. Fx gives the epipolar line in the second image on which the match must lie. . When both cameras are calibrated, the closely related essential matrix $E = K'^T F K$ additionally lets you recover the actual rotation and translation between the two cameras.

The key difference from the last post: a homography maps a point to a point, but only when the scene is flat. $F$ maps a point to a line, which works for any scene, because the depth ambiguity is exactly what the line represents.

Rectification: making the lines horizontal

Epipolar lines are generally slanted, which makes scanning them awkward. Rectification warps both images so that all epipolar lines become horizontal image rows.

After rectification, a point at row 412 in the left image has its match at row 412 in the right image. Matching becomes: scan left along one row.

import cv2, numpy as np

# From stereo calibration
retval, K1, d1, K2, d2, R, T, E, F = cv2.stereoCalibrate(
    obj_points, img_points_L, img_points_R,
    K1, d1, K2, d2, image_size,
    flags=cv2.CALIB_FIX_INTRINSICS)

R1, R2, P1, P2, Q, roi1, roi2 = cv2.stereoRectify(
    K1, d1, K2, d2, image_size, R, T, alpha=0)

map1x, map1y = cv2.initUndistortRectifyMap(K1, d1, R1, P1, image_size, cv2.CV_32FC1)
map2x, map2y = cv2.initUndistortRectifyMap(K2, d2, R2, P2, image_size, cv2.CV_32FC1)

left_rect  = cv2.remap(left,  map1x, map1y, cv2.INTER_LINEAR)
right_rect = cv2.remap(right, map2x, map2y, cv2.INTER_LINEAR)

Verify rectification before trusting anything downstream. Draw horizontal lines across both rectified images side by side. A feature crossed by a line in the left image must be crossed by the same line in the right. If it is off by even two rows, block matching will fail everywhere and the disparity map will look like noise.

Block matching, worked out

For each pixel in the left image, take a small window around it and slide it along the corresponding row of the right image, scoring each position. The score is the sum of absolute differences (SAD): add up the absolute difference at every pixel in the window.

Here is a real 5-pixel window and the candidates it is compared against:

Compute the $d = 3$ case term by term:

$|20-22| + |80-78| + |140-142| + |90-88| + |30-32| = 2+2+2+2+2 = 10$

And $d = 2$:

$|20-78| + |80-142| + |140-88| + |90-32| + |30-26| = 58+62+52+58+4 = 234$

The shape of that curve is the confidence measure. A deep narrow dip means one clear answer. If the curve were flat around 200 everywhere, the window has no distinguishing texture and any disparity you pick is a guess. Good stereo implementations reject those pixels rather than reporting a made-up number.

Sub-pixel refinement

Integer disparity is coarse. Fit a parabola through the minimum and its two neighbours:

$d_{sub} = d + \frac{S(d-1) - S(d+1)}{2\left[S(d-1) - 2S(d) + S(d+1)\right]}$

With $S(2) = 234$, $S(3) = 10$, $S(4) = 231$:

$d_{sub} = 3 + \frac{234 - 231}{2(234 - 20 + 231)} = 3 + \frac{3}{890} = 3.003$

Barely a change here because the match is nearly exact, but on real data sub-pixel refinement typically improves depth accuracy by a factor of four. OpenCV returns disparity scaled by 16 for exactly this reason — the bottom four bits are the fractional part.

From disparity to depth

Here is the formula everything has been building toward:

$Z = \frac{f \cdot B}{d}$

$f$ is focal length in pixels, $B$ is the baseline in millimetres, $d$ is disparity in pixels, and $Z$ comes out in millimetres.

With $f = 800$ px and $B = 120$ mm, a disparity of 40 px gives:

$Z = \frac{800 \times 120}{40} = \frac{96{,}000}{40} = 2400 \text{ mm} = 2.4 \text{ m}$

Halve the disparity to 20 px and the distance doubles to 4.8 m. Disparity and depth are inversely proportional, and that inverse relationship causes the single biggest practical problem in stereo.

Accuracy collapses with distance

Differentiate $Z = fB/d$ with respect to $d$:

$\left|\frac{dZ}{dd}\right| = \frac{fB}{d^2}$

The depth error per pixel of disparity error grows as $1/d^2$. Work it out:

For the delivery robot this is decisive. At 1.2 m, where a person stepping out matters, depth is accurate to 15 mm. At 19 m it is accurate to about 4 m, which is useless. Stereo is a close-range sensor. Design around that rather than trying to tune your way out of it.

Choosing the baseline

$Z = fB/d$ means a wider baseline gives a larger disparity for the same distance, which improves accuracy. But there is a limit: the maximum disparity your matcher can search sets a minimum distance.

With a search range of 128 pixels:

A 500 mm baseline is four times more accurate at 10 m but cannot see anything closer than 3.1 m at all. For a pavement robot that must react to a person at 1 m, 120 mm is the right choice.

Running it in OpenCV

# StereoSGBM is almost always better than StereoBM
min_disp, num_disp, block = 0, 128, 5   # num_disp must be a multiple of 16

matcher = cv2.StereoSGBM_create(
    minDisparity=min_disp,
    numDisparities=num_disp,
    blockSize=block,
    P1=8  * 3 * block**2,      # smoothness penalty, 1-pixel change
    P2=32 * 3 * block**2,      # smoothness penalty, larger change
    disp12MaxDiff=1,           # left-right consistency check
    uniquenessRatio=10,        # reject shallow SAD minima
    speckleWindowSize=100,
    speckleRange=32,
)

disp = matcher.compute(left_rect, right_rect).astype(np.float32) / 16.0

f, B = 800.0, 120.0
with np.errstate(divide="ignore"):
    depth_mm = np.where(disp > 0.5, f * B / disp, 0)

Two guards matter there. disp > 0.5 avoids dividing by near-zero, which would produce absurd distances. uniquenessRatio=10 rejects any pixel whose best SAD is not at least 10% better than the runner-up — the flat-curve case from earlier.

Where stereo fails

The textureless case has an elegant industrial fix: active stereo. Project a random infrared dot pattern onto the scene so even a blank wall has texture to match. The pattern only needs to be random, not known, because it is being matched between two cameras rather than decoded. Most commercial depth cameras work this way.

Practice task

Two identical webcams clamped to a rigid bar, about 120 mm apart.

1. Calibrate each camera separately, then run stereoCalibrate and stereoRectify.
2. Draw 20 horizontal lines across the rectified pair. Confirm features align on the same rows. Do not continue until they do.
3. Compute the disparity map with SGBM defaults and view it as a colour map.
4. Place a box at exactly 1 m. Read its disparity and compute $Z = fB/d$. Compare with the tape measure.
5. Repeat at 2 m, 3 m, and 5 m. Tabulate measured versus true and compute the percentage error at each.
6. Sweep blockSize over 3, 5, 9, and 15. Note how noise and edge sharpness trade off.
7. Point the pair at a blank wall. Look at the disparity map, then tape a newspaper to the wall and look again.

Step 5 is the one to keep. Plot percentage error against distance and you will reproduce the $1/d^2$ curve from your own hardware. That plot tells you exactly where your system’s usable range ends, which no amount of parameter tuning will extend.

Summary

A point in one image constrains its match in the other to a single line, the epipolar line, described by $x'^T F x = 0$. Rectification warps both images so those lines become horizontal rows, turning a 2D search into a 1D scan.

Block matching slides a window along that row and scores each position by SAD. You computed six candidates by hand and found a minimum of 10 at $d=3$ against 230+ everywhere else, then refined it to 3.003 with a parabola fit. The depth of that dip is your confidence: a flat curve means no texture and the pixel should be rejected, not guessed.

Depth is $Z = fB/d$. With $f=800$ px and $B=120$ mm, a disparity of 40 px is 2.4 m. Error grows as $fB/d^2$: 15 mm at 1.2 m, 60 mm at 2.4 m, 960 mm at 9.6 m, and 3.8 m at 19.2 m. A wider baseline improves the far end but raises the minimum distance in exact proportion. Stereo is a short-range sensor, and the formula tells you precisely how short.

What comes next

Stereo gives depth from two cameras at one instant. Optical flow and motion tracking gives motion from one camera across two instants — the same matching problem, one axis rotated. The two combine directly: stereo says how far, flow says how fast, and together they say whether the robot needs to stop.