Multi-View Stereo and Structure from Motion

A pinhole camera maps a 3D point $\mathbf{P} = [X, Y, Z]^\mathsf{T}$ in world coordinates to a 2D image point $\mathbf{x} = [u, v]^\mathsf{T}$ via perspective projection:

$$\tilde{\mathbf{x}} = \mathbf{K}[\mathbf{R} \mid \mathbf{t}]\,\tilde{\mathbf{P}},$$

where $\tilde{\mathbf{x}} \in \mathbb{R}^3$ and $\tilde{\mathbf{P}} \in \mathbb{R}^4$ are homogeneous coordinates, $\mathbf{R} \in SO(3)$ and $\mathbf{t} \in \mathbb{R}^3$ are the camera extrinsics (rotation and translation), and the intrinsic matrix is:

$$\mathbf{K} = \begin{bmatrix} f_x & s & c_x \\ 0 & f_y & c_y \\ 0 & 0 & 1 \end{bmatrix},$$

with focal lengths $f_x, f_y$, principal point $(c_x, c_y)$, and skew $s$ (usually 0).

Given two cameras observing the same 3D point $\mathbf{P}$, the projections $\mathbf{x}_1$ and $\mathbf{x}_2$ in the two images satisfy the epipolar constraint:

$$\tilde{\mathbf{x}}_2^\mathsf{T}\,\mathbf{F}\,\tilde{\mathbf{x}}_1 = 0,$$

where $\mathbf{F} \in \mathbb{R}^{3 \times 3}$ is the fundamental matrix (rank 2, 7 degrees of freedom).

Geometric interpretation: The point $\mathbf{x}_1$ in image 1 constrains the corresponding point $\mathbf{x}_2$ in image 2 to lie on the epipolar line $\ell_2 = \mathbf{F}\,\tilde{\mathbf{x}}_1$. This reduces stereo matching from a 2D search to a 1D search.

When the cameras are calibrated (intrinsics $\mathbf{K}_1, \mathbf{K}_2$ known), the fundamental matrix factors as:

$$\mathbf{F} = \mathbf{K}_2^{-\mathsf{T}}\,\mathbf{E}\,\mathbf{K}_1^{-1},$$

where $\mathbf{E} = [\mathbf{t}]_\times \mathbf{R}$ is the essential matrix (5 DOF), with $[\mathbf{t}]_\times$ the skew-symmetric matrix of the baseline translation.

Structure from Motion jointly estimates 3D scene structure (a sparse point cloud) and camera poses from a collection of unposed images:

1. Feature extraction: Detect and describe keypoints in each image (e.g., SIFT, SuperPoint).
2. Feature matching: Find correspondences between image pairs.
3. Geometric verification: Filter matches using epipolar geometry (the fundamental matrix $\mathbf{F}$ satisfies $\tilde{\mathbf{x}}_2^\mathsf{T} \mathbf{F}\, \tilde{\mathbf{x}}_1 = 0$ for corresponding points).
4. Bundle adjustment: Jointly optimise 3D point positions $\{\mathbf{P}_j\}$ and camera parameters $\{\mathbf{K}_k, \mathbf{R}_k, \mathbf{t}_k\}$ by minimising the reprojection error:

$$\min_{\{\mathbf{P}_j\}, \{\mathbf{R}_k, \mathbf{t}_k\}} \sum_{k,j} \rho\!\left(\|\pi(\mathbf{K}_k, \mathbf{R}_k, \mathbf{t}_k, \mathbf{P}_j) - \mathbf{x}_{k,j}\|^2\right),$$

where $\pi$ is the projection function and $\rho$ is a robust loss (e.g., Huber).

Bundle adjustment is a nonlinear least-squares optimisation that jointly refines 3D point positions and camera parameters. Let $\theta = (\{\mathbf{P}_j\}, \{\mathbf{R}_k, \mathbf{t}_k\})$ denote the unknowns. The cost function is:

$$\min_\theta \sum_{(k,j) \in \mathcal{V}} \rho\!\left(\|\pi_k(\mathbf{P}_j; \theta) - \mathbf{x}_{k,j}\|^2\right),$$

where $\mathcal{V}$ is the set of visibility pairs (point $j$ seen in camera $k$).

The Jacobian of this system has a sparse block structure (each observation depends on exactly one point and one camera), enabling the Schur complement trick: eliminate point variables first, then solve a reduced system over camera variables only.

Levenberg-Marquardt is the standard solver, with cost per iteration $O(|\mathcal{V}|\,c^2 + n_c^3)$, where $c$ is the camera parameter dimension and $n_c$ is the number of cameras.