Stereo Rectification

Stereo rectification resamples the two images of a stereo pair so that every pair of corresponding epipolar lines becomes one and the same horizontal row. Stereo matching then reduces to a one-dimensional search along a row, whose result is the disparity. Stereo vision explains why this configuration is wanted; this article covers how the transformations are computed, applied, and checked.

Problem

Given two images with known epipolar geometry, find a homography for each so that all epipolar lines become horizontal and corresponding lines share a $y$ coordinate: both epipoles go to the point at infinity $\mathbf{i} = (1, 0, 0)^\top$. Among the many such pairs, choose one that distorts the images little.

Inputs and Outputs

• Calibrated: the intrinsics $K, K'$, the relative pose $(R, \mathbf{t})$, and the distortion coefficients from camera calibration. Output: a rotation per camera, a common intrinsic matrix $K_n$, the rectified projection matrices, and the resampling homographies or lookup maps.
• Uncalibrated: the fundamental matrix $F$, plus point matches and image sizes for some methods. Output: two homographies $H, H'$.

Intuition

Rotating a camera about its center does not change which rays it sees, only the plane on which it records them, so the new image is a homography of the old one whatever the depth of the scene. Rectification keeps both camera centers fixed and turns both cameras, in software, to a common orientation with the $x$ axis along the baseline. With identical intrinsics, they form the ideal parallel rig, whose epipolar lines are the image rows.

Mathematical Formulation

The notation follows the epipolar geometry article: $P = K[\,I \mid \mathbf{0}\,]$, $P' = K'[\,R \mid \mathbf{t}\,]$, camera centers $\mathbf{C} = \mathbf{0}$ and $\mathbf{C}' = -R^\top\mathbf{t}$, and $\mathbf{x}'^\top F \mathbf{x} = 0$.

What a rectified pair looks like

A pair is rectified when its fundamental matrix is, up to scale,

$$F_\text{rect} = [\mathbf{i}]_\times = \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & -1 \\ 0 & 1 & 0 \end{bmatrix}, \qquad \mathbf{x}'^\top [\mathbf{i}]_\times \mathbf{x} = y - y' = 0 .$$

Both epipoles are $\mathbf{i}$, and the epipolar constraint says exactly that matching points share a row. If the images are warped by $\mathbf{x} \mapsto H\mathbf{x}$ and $\mathbf{x}' \mapsto H'\mathbf{x}'$, the fundamental matrix becomes $H'^{-\top} F H^{-1}$, so the rectification condition is

$$H'^{-\top} F H^{-1} \simeq [\mathbf{i}]_\times .$$

The condition leaves several degrees of freedom. For example, a common vertical scale and shift of both images, or an independent horizontal scale, shear, and shift of either image, keeps corresponding rows together and the pair rectified. The methods below differ in how they spend this freedom.

Calibrated rectification

Fusiello, Trucco, and Verri (2000) construct the rectified cameras directly. Both keep their centers and receive the same orientation $R_n$ and the same intrinsics $K_n$:

$$P_n = K_n [\,R_n \mid -R_n\mathbf{C}\,], \qquad P'_n = K_n [\,R_n \mid -R_n\mathbf{C}'\,].$$

The rows of $R_n$ are the new camera axes, expressed in the first camera’s frame:

$$\mathbf{r}_1 = \frac{\mathbf{C}' - \mathbf{C}}{\lVert \mathbf{C}' - \mathbf{C} \rVert}, \qquad \mathbf{r}_2 = \frac{\mathbf{k} \times \mathbf{r}_1}{\lVert \mathbf{k} \times \mathbf{r}_1 \rVert}, \qquad \mathbf{r}_3 = \mathbf{r}_1 \times \mathbf{r}_2,$$

where $\mathbf{k}$ is the old optical axis of the first camera, $(0, 0, 1)^\top$ in this frame. Then $R_n(\mathbf{C}' - \mathbf{C}) = (B, 0, 0)^\top$ for baseline length $B$: the standard parallel rig. Fusiello et al. write $\mathbf{C} - \mathbf{C}'$; the sign only flips the new $x$ axis, and this choice gives $R_n = I$ for a rig that is already rectified. Fusiello’s code sets $K_n$ to the average of the two intrinsic matrices, with zero skew.

Since $P_n$ and $P$ share a center, a pixel transforms by the homography formed from their left $3 \times 3$ blocks:

$$H = K_n R_n K^{-1}, \qquad H' = K_n R_n R^\top K'^{-1}.$$

The two images must share at least the vertical focal length and vertical principal point of $K_n$, or rows stop corresponding. Different horizontal principal points only shift every disparity by a constant.

Uncalibrated rectification

Without calibration, Hartley (1999) builds the pair in two steps.

1. Send one epipole to infinity, nearly rigidly. Choose a point $\mathbf{u}_0$, typically the image center. Let $T$ translate $\mathbf{u}_0$ to the origin, let $R_\theta$ rotate the epipole $\mathbf{e}'$ onto the $x$ axis at $(f, 0, 1)^\top$, and let

   $$G = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1/f & 0 & 1 \end{bmatrix},$$

   which sends $(f, 0, 1)^\top$ to infinity. Then $H' = G R_\theta T$ maps $\mathbf{e}'$ to $\mathbf{i}$ and is, to first order, a rigid motion near $\mathbf{u}_0$.

2. Find the matching transformation. Write $F = [\mathbf{e}']_\times M$. Hartley shows that the homographies $H$ that match $H'$, in the sense of mapping corresponding epipolar lines to the same row, are exactly $H = A H' M$ with

   $$A = \begin{bmatrix} a & b & c \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}.$$

   The parameters $a, b, c$ are chosen to minimize the horizontal disparities of the matched points, $\sum_i (a\hat{u}_i + b\hat{v}_i + c - \hat{u}'_i)^2$, where $(\hat{u}_i, \hat{v}_i)$ and $(\hat{u}'_i, \hat{v}'_i)$ are the matches transformed by $H'M$ and $H'$. This is a linear least-squares problem.

Loop and Zhang (1999) decompose each rectifying homography into a projective part, a similarity, and a shear. The projective parts send the epipoles to infinity and are chosen jointly to be as close to affine as possible over all pixels, by minimizing the variation of the homogeneous coordinate $w$ the pixels receive. The similarities make the epipolar lines horizontal and align the rows, and the shears, which change only $x$, preserve, as far as possible, the perpendicularity and aspect ratio of the lines joining the midpoints of the image edges.

Algorithm

For a calibrated rig, the usual pipeline is:

1. Calibrate both cameras and their relative pose, including lens distortion.
2. Compute $R_n$ from the baseline and choose $K_n$ (focal length, principal points, output size).
3. For every pixel $(u, v)$ of each rectified image, find its source: $\mathbf{x}_n = K_n^{-1}(u, v, 1)^\top$, rotate it back into the original camera’s frame, apply the forward lens distortion model, multiply by the original $K$, and store the result in two lookup maps per camera.
4. For every frame, resample each image at its map positions with interpolation, a backward image warp.

Steps 1–3 run once per rig. Combining undistortion and rectification in one map is necessary as well as efficient: a homography cannot straighten epipolar lines that distortion has curved, and one resampling blurs less than two. OpenCV’s initUndistortRectifyMap builds this joint map from a rectifying rotation and a new camera matrix, and remap applies it.

Parameters

• Rotation about the baseline. Any rotation of $R_n$ about $\mathbf{r}_1$ preserves rectification. Fusiello ties $\mathbf{r}_2$ to the first camera’s optical axis. OpenCV’s stereoRectify source instead first rotates the two cameras by half the relative rotation each, in opposite directions, to a common orientation, and then applies one shared rotation that aligns the baseline with $x$, splitting the relative rotation evenly between the two images.
• Common intrinsics and output size. A longer focal length in $K_n$ magnifies and crops; a shorter one keeps the whole field of view but leaves invalid borders and lowers resolution. OpenCV’s stereoRectify exposes this as the free scaling parameter alpha: alpha=0 zooms and shifts the images so that only valid pixels are visible, alpha=1 retains all source pixels, and intermediate values interpolate. It also returns a valid-pixel rectangle per image and accepts a larger output size, which its documentation says can preserve detail under strong radial distortion.
• Principal points. OpenCV’s CALIB_ZERO_DISPARITY flag gives both images the same principal point, so points at infinity have zero disparity; otherwise the images may be shifted to maximize the useful area, and the returned disparity-to-depth matrix Q carries the offset.

Complexity

Computing the transformations is negligible: a few matrix products in the calibrated case, a small linear least-squares problem for Hartley’s method. Applying them costs one interpolated lookup per output pixel, $O(WH)$ per image.

Implementation

The code rectifies two synthetic cameras with different intrinsics, a 12 cm baseline, and a few degrees of relative rotation, and measures the vertical disparity $|y - y'|$ of projected 3D points before and after.

import numpy as np
from scipy.spatial.transform import Rotation

rng = np.random.default_rng(1)

# Two cameras: P = K [I | 0], P' = K' [R | t]. Slightly different intrinsics,
# a 12 cm baseline mostly along x, and a few degrees of relative rotation.
K1 = np.array([[700.0, 0, 320], [0, 705.0, 240], [0, 0, 1]])
K2 = np.array([[690.0, 0, 330], [0, 695.0, 235], [0, 0, 1]])
R = Rotation.from_euler("xyz", [2.0, -4.0, 1.5], degrees=True).as_matrix()
C1 = np.zeros(3)
C2 = np.array([0.12, 0.01, 0.005])          # second centre, first-camera frame
t = -R @ C2                                 # so that C' = -R^T t

def project(K, R, C, X):
    x = (X - C) @ R.T @ K.T
    return x[:, :2] / x[:, 2:]

def rectify(K1, R1, C1, K2, R2, C2):
    """Fusiello-style calibrated rectification. Ri are world-to-camera
    rotations and Ci camera centres. Returns pixel homographies H1, H2 and the
    common rotation Rn and intrinsics Kn of the rectified cameras."""
    r1 = (C2 - C1) / np.linalg.norm(C2 - C1)   # new x axis: along the baseline
    r2 = np.cross(R1[2], r1)                   # new y axis: _|_ to old z and new x
    r2 /= np.linalg.norm(r2)
    r3 = np.cross(r1, r2)                      # new z axis completes the frame
    Rn = np.vstack([r1, r2, r3])
    Kn = (K1 + K2) / 2
    Kn[0, 1] = 0.0                             # common intrinsics, no skew
    # Same centre, new orientation: x_new ~ Kn Rn Ri^T Ki^{-1} x_old
    H1 = Kn @ Rn @ R1.T @ np.linalg.inv(K1)
    H2 = Kn @ Rn @ R2.T @ np.linalg.inv(K2)
    return H1, H2, Rn, Kn

def apply_h(H, x):
    xh = np.hstack([x, np.ones((len(x), 1))]) @ H.T
    return xh[:, :2] / xh[:, 2:]

X = rng.uniform([-1.5, -1.0, 2.0], [1.5, 1.0, 10.0], size=(200, 3))
x1 = project(K1, np.eye(3), C1, X)
x2 = project(K2, R, C2, X)

H1, H2, Rn, Kn = rectify(K1, np.eye(3), C1, K2, R, C2)
y1, y2 = apply_h(H1, x1), apply_h(H2, x2)

print("vertical disparity |y - y'| (px)    max       mean")
print(f"  original images             {np.abs(x1[:, 1] - x2[:, 1]).max():9.3f} {np.abs(x1[:, 1] - x2[:, 1]).mean():9.3f}")
print(f"  rectified images            {np.abs(y1[:, 1] - y2[:, 1]).max():9.1e} {np.abs(y1[:, 1] - y2[:, 1]).mean():9.1e}")

# Disparity in the rectified pair against f B / Z, with Z measured along the new axis.
B = np.linalg.norm(C2 - C1)
Z = (X - C1) @ Rn[2]
d = y1[:, 0] - y2[:, 0]
print(f"  max |d - f B / Z| (px)      {np.abs(d - Kn[0, 0] * B / Z).max():9.1e}")

# Same rotations, but each camera keeps its own intrinsics: rows no longer agree.
H1o = K1 @ Rn @ np.linalg.inv(K1)
H2o = K2 @ Rn @ R.T @ np.linalg.inv(K2)
z1, z2 = apply_h(H1o, x1), apply_h(H2o, x2)
print(f"  own intrinsics, no common K {np.abs(z1[:, 1] - z2[:, 1]).max():9.3f} {np.abs(z1[:, 1] - z2[:, 1]).mean():9.3f}")

# Rectify with a calibration whose relative rotation is off by 0.1 degree.
dR = Rotation.from_euler("x", 0.1, degrees=True).as_matrix()
G1, G2, _, _ = rectify(K1, np.eye(3), C1, K2, dR @ R, C2)
w1, w2 = apply_h(G1, x1), apply_h(G2, x2)
print(f"  0.1 deg rotation error      {np.abs(w1[:, 1] - w2[:, 1]).max():9.3f} {np.abs(w1[:, 1] - w2[:, 1]).mean():9.3f}")

Output:

vertical disparity |y - y'| (px)    max       mean
  original images                55.387    33.014
  rectified images              2.3e-13   4.4e-14
  max |d - f B / Z| (px)        3.7e-13
  own intrinsics, no common K    10.114     5.043
  0.1 deg rotation error          1.465     1.228

Matching points that differed by up to 55 pixels vertically share a row after rectification, and the horizontal disparity equals $fB/Z$, as for an ideal parallel rig. Rotation alone is not enough: if each camera keeps its own intrinsics, rows drift apart by up to 10 pixels. A relative pitch error of only 0.1° (about the $x$ axis, at a focal length near 700 pixels) leaves vertical disparities above a pixel, enough to hurt a matcher that searches a single row.

Properties and Behavior

• Exact for any scene. The homographies depend only on the cameras, so rectification holds for every scene point if the calibration or $F$ is accurate and distortion has been removed. Only calibrated rectification yields a metric parallel rig.

Checking rectification

The practical test is the vertical disparity of matched features: match features in the rectified pair, keep the inliers, and inspect $y - y'$. In a well-rectified pair it stays near zero, within the matcher’s sub-pixel accuracy. Its pattern suggests a cause: a near-constant offset points to a vertical principal-point mismatch or a relative pitch error (a pitch error $\theta$ shifts rows by about $f\theta$, so the two look alike), an offset that changes linearly across the image to a roll about the optical axis, and residuals that grow toward the corners to uncorrected distortion. Errors in calibration become vertical disparities that most dense matchers do not search, so the check is worth repeating whenever the rig may have been bumped or flexed.

Limitations

• Epipoles inside or near the image. A homography that sends an epipole to infinity sends a whole line through it to infinity. If the epipole lies inside the image, that line cuts the image and the warped image splits into two unbounded parts; just outside, the image is stretched enormously. Hartley (1999) analyzes when the homography is well behaved on the image (quasi-affine) and suggests resampling a smaller window otherwise. Forward motion, as for a camera on a vehicle, puts the epipole near the image center, and planar rectification is then unusable. In Fusiello’s construction the same case appears as $\mathbf{k} \times \mathbf{r}_1 = \mathbf{0}$, when the baseline is parallel to the optical axis.

Variants

• Vertical rigs. OpenCV’s stereoRectify also handles cameras stacked vertically, aligning epipolar lines with columns instead of rows. Its stereoRectifyUncalibrated implements Hartley’s method, according to its documentation.
• Polar rectification. Pollefeys, Koch, and Van Gool (1999) reparameterize each image in polar coordinates around its epipole: each row of the rectified image is an angular sector, and distance along the epipolar line becomes the column. Using the oriented fundamental matrix, they keep only half epipolar lines, and they choose the angular step so that no pixel is compressed. This handles any camera motion, including an epipole inside the image, at the cost of a nonlinear resampling stored as a lookup table. Cylindrical rectification, by Roy, Meunier, and Cox, was an earlier answer to the same problem.