
Lecture 13
Computer Science Department, Colorado School of Mines
By the end of this lecture, you should be able to:

\[\lambda\,\mathbf{x} = \mathbf{K}\,\big[\,{}^{c}\mathbf{R}_{w} \mid {}^{c}\mathbf{t}_{w}\,\big]\;{}^{w}\mathbf{X}\]
| Problem | Pixels \(\mathbf{x}\) | Intrinsics \(\mathbf{K}\) | Extrinsics \({}^{c}\mathbf{R}_{w},\ {}^{c}\mathbf{t}_{w}\) | 3D points \({}^{w}\mathbf{X}\) |
|---|---|---|---|---|
| Projection (simulate a camera) | unknown | known | known | known |
| Camera calibration | known | unknown | unknown | known |
| Two-view geometry | known | known | unknown | unknown |
| Triangulation | known | known | known | unknown |
| Term | Definition |
|---|---|
| Baseline | Line through the camera centers \({}^{w}\mathbf{C}_1\), \({}^{w}\mathbf{C}_2\) |
| Epipolar plane | Plane through the baseline and \({}^{w}\mathbf{X}\) |
| Epipolar lines \({}^{1}\ell\), \({}^{2}\ell\) | Where the epipolar plane cuts each image plane |
| Epipoles \({}^{1}\mathbf{e}\), \({}^{2}\mathbf{e}\) | Where the baseline cuts each image plane |



\[ \mathbf{F}\,{}^{1}\mathbf{x} = \underbrace{{}^{2}\ell}_{(a,\,b,\,c)^{\top}} \qquad\Longrightarrow\qquad \bbox[border: 2px solid #c53030; padding: 2px 6px]{\underbrace{{}^{2}\mathbf{x}^{\top}\,\mathbf{F}\,{}^{1}\mathbf{x} = 0}_{a\,u_2\,+\,b\,v_2\,+\,c\,=\,0}} \;\;{\color{#c53030}{\begin{array}{l}\textbf{fundamental matrix}\\ \textbf{constraint}\end{array}}} \]
\[{}^{1}\mathbf{x} = (341.1,\ 157.0,\ 1)^{\top},\qquad{}^{2}\mathbf{x} = (411.9,\ 165.0,\ 1)^{\top}\]
\[\mathbf{F} = \begin{bmatrix} 0 & 1.26{\times}10^{-4} & -5.64{\times}10^{-3} \\ 1.57{\times}10^{-4} & -1.31{\times}10^{-5} & -0.19 \\ -4.91{\times}10^{-3} & 0.11 & 1.00 \end{bmatrix}\]
\[\begin{aligned} {}^{2}\ell &= \mathbf{F}\,{}^{1}\mathbf{x} = (0.105,\ -0.994,\ 120.7)^{\top} \\ \text{line }{}^{2}\ell &:\ \ 0.105\,u -0.994\,v +120.7 = 0 \end{aligned}\]
\[\begin{aligned} {}^{2}\mathbf{x}^{\top}\mathbf{F}\,{}^{1}\mathbf{x} = {}^{2}\mathbf{x}^{\top}\,{}^{2}\ell &= 0.105\cdot411.9 -0.994\cdot165.0 +120.7 \\ &= 0.00 \end{aligned}\]

\[ \big({\color{#2f855a}{\mathbf{K}^{-1}\,{}^{2}\mathbf{x}}}\big)^{\top} \underbrace{\big({\color{#805ad5}{{}^{2}\mathbf{t}_{1}}} \times {\color{#2b6cb0}{{}^{2}\mathbf{R}_{1}\,\mathbf{K}^{-1}\,{}^{1}\mathbf{x}}}\big)}_{\mathbf{n}} = 0 \] \[ \Longrightarrow\quad {}^{2}\mathbf{x}^{\top}\, \underbrace{\mathbf{K}^{-\top}\,[{}^{2}\mathbf{t}_{1}]_{\times}\,{}^{2}\mathbf{R}_{1}\,\mathbf{K}^{-1}}_{\mathbf{F}}\; {}^{1}\mathbf{x} = 0 \]
\[ \mathbf{t}\times\mathbf{v} = [\mathbf{t}]_{\times}\,\mathbf{v}, \qquad [\mathbf{t}]_{\times} = \begin{bmatrix} 0 & -t_z & t_y \\ t_z & 0 & -t_x \\ -t_y & t_x & 0 \end{bmatrix} \]
The fundamental matrix \(\mathbf{F}\) is the epipolar constraint for uncalibrated cameras, in pixel coordinates: \[ {}^{2}\mathbf{x}^{\top}\, \underbrace{\mathbf{K}^{-\top}\,[{}^{2}\mathbf{t}_{1}]_{\times}\,{}^{2}\mathbf{R}_{1}\,\mathbf{K}^{-1}}_{\mathbf{F}}\; {}^{1}\mathbf{x} = 0 \]
The middle part of \(\mathbf{F}\) is the essential matrix: \[\mathbf{E} = [{}^{2}\mathbf{t}_{1}]_{\times}\,{}^{2}\mathbf{R}_{1}\]
It is the epipolar constraint for calibrated cameras, in normalized coordinates \(\hat{\mathbf{x}} = \mathbf{K}^{-1}\mathbf{x}\) (ray directions): \[ \bbox[border: 2px solid #c53030; padding: 2px 6px]{{}^{2}\hat{\mathbf{x}}^{\top}\,\mathbf{E}\,{}^{1}\hat{\mathbf{x}} = 0} \;\;{\color{#c53030}{\begin{array}{l}\textbf{essential matrix}\\ \textbf{constraint}\end{array}}} \]
It contains only the relative pose of the two cameras, nothing about the scene or the intrinsics.
For the same point as before:
\[\mathbf{K} = \begin{bmatrix} 500 & 0 & 320 \\ 0 & 500 & 240 \\ 0 & 0 & 1 \end{bmatrix}\]
\[\begin{aligned} {}^{1}\mathbf{x} &= (341.1,\ 157.0,\ 1)^{\top} \\ {}^{2}\mathbf{x} &= (411.9,\ 165.0,\ 1)^{\top} \\[4pt] {}^{1}\hat{\mathbf{x}} &= \mathbf{K}^{-1}\,{}^{1}\mathbf{x} = (0.042,\ -0.166,\ 1)^{\top} \\ {}^{2}\hat{\mathbf{x}} &= \mathbf{K}^{-1}\,{}^{2}\mathbf{x} = (0.184,\ -0.150,\ 1)^{\top} \end{aligned}\]
\[\mathbf{E} = \begin{bmatrix} 0 & -1.29 & -0.5 \\ -1.61 & 0.13 & 2.83 \\ -0.67 & -2.97 & 0 \end{bmatrix}\]
\[{}^{2}\hat{\mathbf{x}}^{\top}\mathbf{E}\,{}^{1}\hat{\mathbf{x}} = 0.00\]

pts1, pts2, \(N\times2\) arrays in the same order.Results on these images (K from the dataset):
\[\mathbf{F} = \begin{bmatrix} 4.01{\times}10^{-8} & 5.08{\times}10^{-6} & -1.69{\times}10^{-3} \\ 1.13{\times}10^{-7} & 5.48{\times}10^{-6} & -0.03 \\ 1.46{\times}10^{-4} & 0.02 & 1.00 \end{bmatrix}\]
\[\mathbf{E} = \begin{bmatrix} -8.05{\times}10^{-4} & -0.02 & 3.15{\times}10^{-3} \\ 0.12 & -4.67{\times}10^{-4} & -0.70 \\ 0.01 & 0.71 & 1.70{\times}10^{-3} \end{bmatrix}\]
import cv2
import numpy as np
# Two views of the same scene.
img1 = cv2.imread("assets/13_two_view_geometry/frame1.JPG", cv2.IMREAD_GRAYSCALE)
img2 = cv2.imread("assets/13_two_view_geometry/frame2.JPG", cv2.IMREAD_GRAYSCALE)
# Intrinsics of the camera
K = np.array([[3409.58, 0.0, 3115.16],
[ 0.0, 3409.44, 2064.73],
[ 0.0, 0.0, 1.0]])
K[:2] *= 0.2
# 1. Detect and match features: SIFT with Lowe's ratio test.
sift = cv2.SIFT_create()
kp1, des1 = sift.detectAndCompute(img1, None)
kp2, des2 = sift.detectAndCompute(img2, None)
knn = cv2.BFMatcher(cv2.NORM_L2).knnMatch(des1, des2, k=2)
good = [m for m, n in knn if m.distance < 0.75 * n.distance]
# 2. Matched pixels, N x 2, in the same order.
pts1 = np.float32([kp1[m.queryIdx].pt for m in good])
pts2 = np.float32([kp2[m.trainIdx].pt for m in good])
# 3. Estimate F (uncalibrated) and E (calibrated).
F, _ = cv2.findFundamentalMat(pts1, pts2, cv2.FM_8POINT)
E, _ = cv2.findEssentialMat(pts1, pts2, K)
print(f"{len(good)} matches")
print("F =\n", F / F[2, 2])
print("E =\n", E)OpenCV’s cv2.findFundamentalMat(..., cv2.FM_8POINT) implements the eight-point algorithm to estimate the fundamental matrix (Hartley & Zisserman, 2004, §11.1.1). The steps are:
One row per match. With \({}^{1}\mathbf{x} = (u_1, v_1, 1)^{\top}\), \({}^{2}\mathbf{x} = (u_2, v_2, 1)^{\top}\) and \(\mathbf{f} = (F_{11}, F_{12}, \dots, F_{33})^{\top}\), the constraint \({}^{2}\mathbf{x}^{\top}\mathbf{F}\,{}^{1}\mathbf{x} = 0\) is linear in \(\mathbf{f}\): \[ \big[\,u_2u_1,\ u_2v_1,\ u_2,\ v_2u_1,\ v_2v_1,\ v_2,\ u_1,\ v_1,\ 1\,\big]\;\mathbf{f} = 0 \]
Solve. Stack \(N \ge 8\) rows into \(\mathbf{A}\) (\(N\times 9\)). \(\mathbf{f}\) is the right singular vector of \(\mathbf{A}\) with the smallest singular value, as in the DLT of Lecture 12.
Force rank 2. A true \(\mathbf{F}\) has \(\det\mathbf{F} = 0\): that is what makes all epipolar lines meet at the epipole. With noise, the solution has rank 3. With \(\mathbf{F} = \mathbf{U}\,\mathrm{diag}(\sigma_1, \sigma_2, \sigma_3)\,\mathbf{V}^{\top}\), set \(\sigma_3 = 0\): the closest rank-2 matrix.
Normalize first. Pixel values make the entries of \(\mathbf{A}\) range from 1 to \(\sim\!10^{5}\), which makes the solution sensitive to noise. Shift each image’s points to zero mean and scale them to mean distance \(\sqrt{2}\) (transforms \(\mathbf{T}_1\), \(\mathbf{T}_2\)), solve, then undo: \(\mathbf{F} = \mathbf{T}_2^{\top}\,\tilde{\mathbf{F}}\,\mathbf{T}_1\).

| Algorithm | Estimates | Needs \(\mathbf{K}\)? | Matches | Solutions | OpenCV |
|---|---|---|---|---|---|
| Eight-point | \(\mathbf{F}\) | No | 8 or more | 1 | findFundamentalMat(..., cv2.FM_8POINT) |
| Seven-point | \(\mathbf{F}\) | No | exactly 7 | 1 or 3 | findFundamentalMat(..., cv2.FM_7POINT) |
| Five-point | \(\mathbf{E}\) | Yes | 5 or more | up to 10 | findEssentialMat(..., K) |

Of the 1035 SIFT matches, 148 are wrong: they do not fit the scene’s true epipolar geometry.
Why use as few matches as possible? In practice, some matches are wrong
Every match used in an algorithm must be correct to estimate \(\mathbf{F}\) or \(\mathbf{E}\) correctly.
The more matches we use, the more likely it is that at least one of them is wrong.
How can we robustly estimate \(\mathbf{F}\) or \(\mathbf{E}\) from a set of matches that contains some wrong ones?
RANSAC Algorithm
Fitting a line with RANSAC.

Image 2 is a sideways shift of image 1: the model is a translation, \({}^{2}\mathbf{x} = {}^{1}\mathbf{x} + \mathbf{t}\). Each match gives its own estimate \(\mathbf{t}_j = {}^{2}\mathbf{x}_j - {}^{1}\mathbf{x}_j\).
Correct matches all agree: their arrows are parallel and equally long. Wrong matches point anywhere.
Least squares averages all \(\mathbf{t}_j\), so the wrong matches pull it away: \(\mathbf{t}_{\text{LS}} = (-148,\ 15)\) px instead of \(\mathbf{t} = (-400,\ 0)\) px.
RANSAC for F (or E)

Trials \(N\) needed for \(p = 0.99\):
| Model | \(s\) | 10% | 20% | 30% | 40% | 50% |
|---|---|---|---|---|---|---|
| Translation | 1 | 2 | 3 | 4 | 6 | 7 |
| Line | 2 | 3 | 5 | 7 | 11 | 17 |
| \(\mathbf{E}\), 5-point | 5 | 6 | 12 | 26 | 57 | 146 |
| \(\mathbf{F}\), 7-point | 7 | 8 | 20 | 54 | 163 | 588 |
| \(\mathbf{F}\), 8-point | 8 | 9 | 26 | 78 | 272 | 1,177 |
Columns: outlier ratio \(\varepsilon\).

1.0: threshold \(\tau\) in pixels. 0.999: probability \(p\) of sampling at least one all-inlier set.mask is 1 for the inliers. findEssentialMat uses RANSAC by default.Compared with the ground truth:
| Method | Matches used | Median error |
|---|---|---|
| Eight-point, all matches | 1035 | 7.56 px |
| RANSAC, \(\mathbf{F}\) | 866 (851 correct) | 0.24 px |
| RANSAC, \(\mathbf{E}\) | 870 (869 correct) | 0.08 px |
Median error: distance of the correct matches to their estimated epipolar lines.

In homogeneous coordinates; divide \(\mathbf{H}\,{}^{1}\mathbf{x}\) by its third entry.
| Fundamental matrix \(\mathbf{F}\) | Homography \(\mathbf{H}\) | |
|---|---|---|
| Maps \({}^{1}\mathbf{x}\) to | a line \({}^{2}\ell\) | a point \({}^{2}\mathbf{x}\) |
| Holds for | any scene | one plane, or a rotating camera |
\[{}^{1}\mathbf{x} = (578.3,\ 172.0,\ 1)^{\top}\]
\[\mathbf{H} = \begin{bmatrix} 0.781 & 7.975{\times}10^{-3} & 42.418 \\ -0.057 & 0.898 & 31.333 \\ -1.865{\times}10^{-4} & 2.647{\times}10^{-6} & 1.000 \end{bmatrix}\]
\[\begin{aligned} \mathbf{H}\,{}^{1}\mathbf{x} &= (495.2,\ 152.9,\ 0.893)^{\top} \\ {}^{2}\mathbf{x} &= \Big(\tfrac{495.2}{0.893},\ \tfrac{152.9}{0.893}\Big) = (554.8,\ 171.3) \end{aligned}\]


The basic solver for \(\mathbf{H}\) is the direct linear transform (DLT), the same as linear camera calibration. OpenCV’s cv2.findHomography uses DLT. The steps are:
Two rows per match. With \({}^{1}\mathbf{x} = (u_1, v_1, 1)^{\top}\), \({}^{2}\mathbf{x} = (u_2, v_2, 1)^{\top}\) and \(\mathbf{h}_i^{\top}\) the rows of \(\mathbf{H}\), the constraint gives \(u_2 = \frac{\mathbf{h}_1^{\top}\,{}^{1}\mathbf{x}}{\mathbf{h}_3^{\top}\,{}^{1}\mathbf{x}}\) and \(v_2 = \frac{\mathbf{h}_2^{\top}\,{}^{1}\mathbf{x}}{\mathbf{h}_3^{\top}\,{}^{1}\mathbf{x}}\). Multiplying out, both are linear in \(\mathbf{h} = (\mathbf{h}_1; \mathbf{h}_2; \mathbf{h}_3)\): \[ \begin{bmatrix} {}^{1}\mathbf{x}^{\top} & \mathbf{0}^{\top} & -u_2\,{}^{1}\mathbf{x}^{\top} \\ \mathbf{0}^{\top} & {}^{1}\mathbf{x}^{\top} & -v_2\,{}^{1}\mathbf{x}^{\top} \end{bmatrix} \mathbf{h} = \mathbf{0} \]
Solve. Stack \(N \ge 4\) matches into \(\mathbf{A}\) (\(2N\times 9\)). \(\mathbf{h}\) is the right singular vector of \(\mathbf{A}\) with the smallest singular value. Four matches (no three collinear) give exactly one \(\mathbf{H}\).
Normalize first, as in the eight-point algorithm: transform each image’s points to zero mean and mean distance \(\sqrt{2}\) (\(\mathbf{T}_1\), \(\mathbf{T}_2\)), solve, then undo: \(\mathbf{H} = \mathbf{T}_2^{-1}\,\tilde{\mathbf{H}}\,\mathbf{T}_1\).

RANSAC error: the distance from \({}^{2}\mathbf{x}_j\) to the mapped pixel: \[ d_j = \big\lVert\, {}^{2}\mathbf{x}_j - \pi\big(\mathbf{H}\,{}^{1}\mathbf{x}_j\big) \big\rVert < \tau, \qquad \pi(x, y, w) = \big(\tfrac{x}{w},\ \tfrac{y}{w}\big) \]
Median \(d_j\): 0.24 px for the wall matches, but 33 px for the 141 correct matches off the wall (red): they fit \(\mathbf{F}\), not this \(\mathbf{H}\).
import cv2
import numpy as np
# Two views of the same scene.
img1 = cv2.imread("assets/13_two_view_geometry/frame1.JPG", cv2.IMREAD_GRAYSCALE)
img2 = cv2.imread("assets/13_two_view_geometry/frame2.JPG", cv2.IMREAD_GRAYSCALE)
# 1. Detect and match features: SIFT with Lowe's ratio test.
sift = cv2.SIFT_create()
kp1, des1 = sift.detectAndCompute(img1, None)
kp2, des2 = sift.detectAndCompute(img2, None)
knn = cv2.BFMatcher(cv2.NORM_L2).knnMatch(des1, des2, k=2)
good = [m for m, n in knn if m.distance < 0.75 * n.distance]
# 2. Matched pixels, N x 2, in the same order.
pts1 = np.float32([kp1[m.queryIdx].pt for m in good])
pts2 = np.float32([kp2[m.trainIdx].pt for m in good])
# 3. Estimate H with RANSAC: inlier threshold 2 px.
H, mask = cv2.findHomography(pts1, pts2, cv2.RANSAC, 2.0)
inliers = mask.ravel() == 1
# 4. Map image-1 pixels to image 2: divide H 1x by its third entry.
mapped = cv2.perspectiveTransform(pts1[inliers].reshape(-1, 1, 2), H).reshape(-1, 2)
error = np.linalg.norm(mapped - pts2[inliers], axis=1)
print(f"{inliers.sum()} of {len(good)} matches are inliers")
print("H =\n", H / H[2, 2])
print(f"median error of the inliers: {np.median(error):.2f} px")
# From E: R, unit-length t, and inlier mask.
n, R, t, mask = cv2.recoverPose(E, pts1, pts2, K)
# From F: convert to E first.
E = K.T @ F @ K
# From H: up to 4 candidates (R, t/d, n).
n, Rs, ts, ns = cv2.decomposeHomographyMat(H, K)
ok = cv2.filterHomographyDecompByVisibleRefpoints(Rs, ns, norm_pts1, norm_pts2)recoverPose tests the 4 candidates and keeps the one with the most points in front of both camerasdecomposeHomographyMat decomposes the homography into up to 4 candidates.filterHomographyDecompByVisibleRefpoints keeps only the candidates that are consistent with the visible points in both images.
OpenCV’s cv2.triangulatePoints uses the linear (DLT) method. The steps are:
Two rows per camera. Camera \(i\) has projection matrix \(\mathbf{P}_i = \mathbf{K}\,[\mathbf{R}_i \mid \mathbf{t}_i]\) with rows \(\mathbf{p}_{i1}^{\top}, \mathbf{p}_{i2}^{\top}, \mathbf{p}_{i3}^{\top}\). From \(\lambda_i\,{}^{i}\mathbf{x} = \mathbf{P}_i\mathbf{X}\) with \({}^{i}\mathbf{x} = (u_i, v_i, 1)^{\top}\), eliminating \(\lambda_i\) gives two equations, linear in the homogeneous point \(\mathbf{X}\): \[ \big(u_i\,\mathbf{p}_{i3}^{\top} - \mathbf{p}_{i1}^{\top}\big)\,\mathbf{X} = 0, \qquad \big(v_i\,\mathbf{p}_{i3}^{\top} - \mathbf{p}_{i2}^{\top}\big)\,\mathbf{X} = 0 \]
Solve. Stack the rows of both cameras into \(\mathbf{A}\) (\(4\times4\)), so \(\mathbf{A}\mathbf{X} = \mathbf{0}\). \(\mathbf{X}\) is the right singular vector of \(\mathbf{A}\) with the smallest singular value; divide it by its fourth entry.
Refine (optional). This minimizes an algebraic error. A nonlinear refinement can then minimize the reprojection error in both images.

X4 is homogeneous (4×N): divide by its last row.import cv2
import numpy as np
# Two views of the same scene, and the camera intrinsics.
img1 = cv2.imread("assets/13_two_view_geometry/frame1.JPG", cv2.IMREAD_GRAYSCALE)
img2 = cv2.imread("assets/13_two_view_geometry/frame2.JPG", cv2.IMREAD_GRAYSCALE)
K = np.array([[3409.58, 0.0, 3115.16],
[ 0.0, 3409.44, 2064.73],
[ 0.0, 0.0, 1.0]])
K[:2] *= 0.2
# 1. Detect and match features: SIFT with Lowe's ratio test.
sift = cv2.SIFT_create()
kp1, des1 = sift.detectAndCompute(img1, None)
kp2, des2 = sift.detectAndCompute(img2, None)
knn = cv2.BFMatcher(cv2.NORM_L2).knnMatch(des1, des2, k=2)
good = [m for m, n in knn if m.distance < 0.75 * n.distance]
pts1 = np.float32([kp1[m.queryIdx].pt for m in good])
pts2 = np.float32([kp2[m.trainIdx].pt for m in good])
# 2. Essential matrix with RANSAC.
E, mask = cv2.findEssentialMat(pts1, pts2, K, cv2.RANSAC, 0.999, 1.0)
# 3. Relative pose: R and unit t; mask keeps the points in front of both cameras.
n, R, t, mask = cv2.recoverPose(E, pts1, pts2, K, mask=mask)
inliers = mask.ravel() > 0
# 4. Triangulate, with camera 1 as the reference frame.
P1 = K @ np.hstack([np.eye(3), np.zeros((3, 1))])
P2 = K @ np.hstack([R, t])
X4 = cv2.triangulatePoints(P1, P2, pts1[inliers].T, pts2[inliers].T)
X = (X4[:3] / X4[3]).T # N x 3, in baseline units
# 5. Depths in each camera (both positive).
depth1 = X[:, 2]
depth2 = (X @ R.T + t.ravel())[:, 2]
print(f"{inliers.sum()} triangulated points")
print("R =\n", R, "\nt =", t.ravel())
print(f"depth range: {depth1.min():.2f} to {depth1.max():.2f} baselines")
findEssentialMat → recoverPose → triangulatePoints; findFundamentalMat and findHomography for the uncalibrated and planar cases.Computer Vision; Colorado School of Mines | Kaveh Fathian