17 Structure from Motion

Structure from Motion, abbreviated SfM, reconstructs camera motion and sparse 3D scene structure from a collection of images. Mathematically, SfM combines projective geometry, graph connectivity, robust statistics, nonlinear least squares, and modern feature learning. This chapter develops SfM from two-view geometry to multi-view reconstruction, emphasizing the clean mathematical principles behind practical pipelines such as feature matching, relative pose estimation, triangulation, pose graph construction, incremental reconstruction, global reconstruction, and differentiable learning-based variants.

17.1 Learning goals

After reading this chapter, students should be able to:

describe the SfM problem as joint estimation of camera poses and 3D points;
explain why images form a view graph whose edges carry relative geometric constraints;
derive how pairwise essential matrices give relative rotations and translation directions;
distinguish calibrated SfM, uncalibrated projective reconstruction, and metric reconstruction;
formulate triangulation and camera resectioning as estimation subproblems;
explain incremental SfM and global SfM at a mathematical level;
understand gauge freedom, scale ambiguity, and coordinate choices;
write the multi-view reprojection-error objective;
explain robust estimation with RANSAC, M-estimators, and outlier filtering;
connect classical SfM to modern learned features, neural feature matching, SLAM, NeRF-style camera optimization, and differentiable bundle-adjustment layers.

17.2 16.1 The problem of reconstructing structure from motion

Suppose a static 3D scene is observed by $m$ cameras. Let the unknown camera matrices be

\[ P_i = K_i[R_i\mid t_i], \qquad i=1,\dots,m, \]

and let the unknown 3D scene points be

\[ X_j \in \mathbb{R}^3, \qquad j=1,\dots,n. \]

The observed image measurement of point $X_j$ in camera $i$ is

\[ x_{ij} \in \mathbb{R}^2, \]

when the point is visible in that image. Using homogeneous coordinates, the ideal projection relation is

\[ \tilde x_{ij} \sim P_i \tilde X_j. \]

The Structure from Motion problem is to estimate the cameras and the 3D points from the image measurements:

\[ \{x_{ij}\}_{(i,j)\in\mathcal{O}} \quad \longrightarrow \quad \{P_i\}_{i=1}^m,\; \{X_j\}_{j=1}^n, \]

where $\mathcal{O}$ is the set of observed image-point pairs.

SfM is called structure from motion because camera motion supplies multiple viewpoints. The same physical point is observed from different camera positions, and the change in its image location constrains both the point location and camera motion.

SfM is the global version of two-view geometry. Epipolar geometry gives pairwise constraints; triangulation gives candidate 3D points; bundle adjustment makes all cameras and all points agree simultaneously.

Interactive 16.1. Cameras, points, and tracks. A sparse SfM model is a bipartite relationship between cameras and 3D points. The same 3D point creates an image track across several views.

17.3 16.2 From two-view geometry to multi-view geometry

Chapter 14 studied two calibrated cameras. If image points $x_1$ and $x_2$ are corresponding normalized coordinates, then

\[ x_2^T E x_1 = 0, \]

where the essential matrix has the form

\[ E=[t]_\times R. \]

Here $R\in SO(3)$ is the relative rotation and $t\in\mathbb{R}^3$ is the relative translation direction between two cameras. The skew-symmetric matrix $[t]_\times$ represents the cross product:

\[ [t]_\times a = t\times a. \]

The essential matrix contains the relative pose between two calibrated cameras, except for the unknown scale of $t$. In other words, two-view geometry determines the direction of translation but not its absolute length.

17.3.1 Pairwise relative pose

For two calibrated cameras, write the first camera as

\[ P_1 = [I\mid 0], \]

and the second as

\[ P_2 = [R\mid t]. \]

Then the relative pose $(R,t)$ can be recovered from $E$ up to the standard four-fold ambiguity. The physically valid choice is selected by the cheirality condition: triangulated points should lie in front of both cameras.

This gives a two-view reconstruction:

\[ \{x_{1j},x_{2j}\}_{j=1}^N \quad \longrightarrow \quad R,\; \hat t,\; \{X_j\}_{j=1}^N, \]

where $\hat t$ is a unit translation direction. The unknown baseline length remains a scale ambiguity.

17.3.2 From pairwise poses to a view graph

In a collection of images, we estimate relative geometry for many image pairs. This produces a graph

\[ G=(V,E_G), \]

where each vertex $i\in V$ represents an image, and an edge $(i,k)\in E_G$ indicates that images $i$ and $k$ have enough verified correspondences to estimate relative geometry.

Each edge carries measurements such as:

\[ R_{ik}\approx R_kR_i^T, \qquad \hat t_{ik}\approx \frac{C_k-C_i}{\|C_k-C_i\|_2}, \]

where $C_i$ is the center of camera $i$.

The view graph is central in modern SfM. It tells us which views are geometrically connected and which pairwise constraints can be trusted.

Interactive 16.2. View graph connectivity. Reconstruction needs enough graph connectivity. Weak bridges, missing edges, and noisy pairwise estimates can make the global camera configuration unstable.

17.4 16.3 Feature tracks and measurement matrices

SfM starts from correspondence. A local feature in one image must be matched to the same physical scene point in other images.

A feature track is a set of image observations believed to correspond to one 3D point:

\[ T_j = \{(i,x_{ij}): \text{point } j \text{ is observed in image } i\}. \]

For example, if the same corner is observed in images 2, 5, 6, and 9, then its track is

\[ T_j=\{(2,x_{2j}),(5,x_{5j}),(6,x_{6j}),(9,x_{9j})\}. \]

The set of all tracks determines the sparse observation pattern $\mathcal{O}$.

17.4.1 Track graph view

There are two related graphs:

The view graph, whose vertices are images and whose edges are verified image pairs.
The track graph, a bipartite graph between camera vertices and point vertices.

The track graph has an edge $(i,j)$ when camera $i$ observes point $j$. Bundle adjustment optimizes over this bipartite graph.

17.4.2 Data matrix viewpoint

For an ideal orthographic camera model with complete observations, classical factorization methods arrange image coordinates into a measurement matrix

\[ W = \begin{bmatrix} x_{11} & x_{12} & \cdots & x_{1n} \\ y_{11} & y_{12} & \cdots & y_{1n} \\ \vdots & \vdots & & \vdots \\ x_{m1} & x_{m2} & \cdots & x_{mn} \\ y_{m1} & y_{m2} & \cdots & y_{mn} \end{bmatrix} \in \mathbb{R}^{2m\times n}. \]

Under affine or orthographic projection, after centering each image, this matrix has low rank:

\[ \operatorname{rank}(W)\le 3. \]

This observation leads to the Tomasi–Kanade factorization idea: estimate motion and shape from the low-rank factorization of $W$. Although full perspective SfM is more nonlinear, the low-rank viewpoint is important because it reveals that multi-view geometry has strong algebraic structure.

17.5 16.4 Gauge freedom and scale ambiguity

SfM does not directly recover an absolute coordinate system. If $\{R_i,t_i,X_j\}$ explains the image measurements, then many transformed configurations also explain the same measurements.

17.5.1 Similarity ambiguity in calibrated SfM

For calibrated cameras, a global similarity transformation does not change image projections. Let

\[ X_j' = sQX_j+a, \]

where $s>0$, $Q\in SO(3)$, and $a\in\mathbb{R}^3$. If camera poses are transformed consistently, all image projections remain unchanged.

Thus calibrated SfM determines structure only up to a global similarity transformation: rotation, translation, and scale.

The scale ambiguity is especially important. Two images can determine the direction of translation, but not the magnitude of the baseline. If the whole scene and camera trajectory are scaled by the same factor, the images are unchanged.

17.5.2 Projective ambiguity in uncalibrated SfM

If camera intrinsics are unknown and unconstrained, reconstruction is only projective. A projective transformation $H\in\mathbb{R}^{4\times 4}$ changes points and cameras by

\[ \tilde X_j' = H\tilde X_j, \qquad P_i' = P_iH^{-1}. \]

Then

\[ P_i'\tilde X_j' = P_iH^{-1}H\tilde X_j=P_i\tilde X_j, \]

so the same image measurements are produced. Additional calibration or scene constraints are needed to upgrade a projective reconstruction to an affine or metric reconstruction.

Gauge freedom is not a bug. It is a mathematical symmetry of the projection equations. A numerical optimizer must fix this symmetry, for example by anchoring one camera pose and setting a scale convention.

17.6 16.5 Incremental SfM pipeline

Many practical SfM systems use an incremental pipeline. The core idea is to build the reconstruction gradually.

A typical incremental SfM pipeline is:

detect local features in all images;
match features between image pairs;
verify matches using robust epipolar geometry;
choose an initial image pair with many reliable matches and good baseline;
recover the relative pose and triangulate initial 3D points;
add a new image by estimating its pose from existing 3D-to-2D correspondences;
triangulate new points seen by the new image and previous images;
run local or global bundle adjustment;
repeat until no useful images remain.

The estimation subproblems are:

\[ \text{relative pose estimation}, \qquad \text{triangulation}, \qquad \text{absolute pose estimation}, \qquad \text{bundle adjustment}. \]

Incremental SfM is robust because each new step is supported by the current model. However, it can suffer from drift and path dependence: early errors may influence later reconstruction.

Interactive 16.3. Incremental reconstruction. A reconstruction grows by adding cameras and triangulating new points. The order of image insertion affects stability.

17.7 16.6 Absolute pose from 2D–3D correspondences

Suppose some 3D points $X_j$ are already reconstructed, and a new image observes their 2D locations $x_j$. To add the new image, we estimate its camera pose.

For a calibrated camera, the problem is:

\[ x_j \sim K[R\mid t]\tilde X_j, \qquad j=1,\dots,N. \]

If $K$ is known, we can work with normalized image coordinates. The pose estimation problem becomes

\[ \hat x_j \sim [R\mid t]\tilde X_j. \]

This is called Perspective-n-Point, or PnP.

17.7.1 Reprojection-error formulation

The statistically natural formulation is nonlinear least squares:

\[ \min_{R,t} \sum_{j=1}^N \rho\left(\left\|x_j-\pi(K(RX_j+t))\right\|_2^2\right), \]

where $\pi$ is perspective division and $\rho$ is either the identity loss or a robust loss.

The rotation constraint matters:

\[ R^TR=I, \qquad \det(R)=1. \]

In computation, rotations may be represented by rotation matrices, Euler angles, axis-angle vectors, quaternions, or Lie algebra increments in $\mathfrak{so}(3)$.

17.7.2 Minimal solvers and RANSAC

A minimal PnP solver estimates pose from a small number of correspondences. Because some 2D–3D matches are wrong, pose estimation is usually embedded in RANSAC:

sample a minimal subset;
estimate candidate pose;
count inliers using reprojection error;
refine using all inliers.

The inlier test has the form

\[ \left\|x_j-\pi(K(RX_j+t))\right\|_2 < \tau. \]

This connects directly to the robust estimation ideas from Chapter 14.

17.8 16.7 Triangulation in multi-view SfM

After estimating camera poses, we can triangulate new points. For a point observed in several cameras, we estimate

\[ X_j = \arg\min_X \sum_{i\in\mathcal{V}_j} \left\|x_{ij}-\pi(P_i\tilde X)\right\|_2^2, \]

where $\mathcal{V}_j$ is the set of cameras that observe point $j$.

17.8.1 Linear triangulation

The homogeneous relation

\[ \tilde x_{ij}\times P_i\tilde X=0 \]

gives two independent linear equations for each observation. Stacking the equations over views gives

\[ A\tilde X=0. \]

The linear triangulated point is obtained as the right singular vector corresponding to the smallest singular value of $A$.

17.8.3 Triangulation angle

If the viewing rays are nearly parallel, depth is poorly constrained. The angle between two rays $r_1$ and $r_2$ is

\[ \theta = \arccos\left(\frac{r_1^Tr_2}{\|r_1\|_2\|r_2\|_2}\right). \]

Small $\theta$ means unstable depth. SfM systems often reject triangulated points when the triangulation angle is too small.

17.9 16.8 Bundle adjustment objective

The central optimization problem in SfM is bundle adjustment. The name comes from adjusting bundles of camera rays so they intersect at consistent 3D points.

Let $\theta_i$ denote the parameters of camera $i$ and let $X_j$ denote 3D point $j$. The reprojection residual is

\[ r_{ij}(\theta_i,X_j)=x_{ij}-\pi(P(\theta_i)\tilde X_j). \]

The bundle-adjustment objective is

\[ \min_{\{\theta_i\},\{X_j\}} \sum_{(i,j)\in\mathcal{O}} \rho\left(\|r_{ij}(\theta_i,X_j)\|_2^2\right). \]

If $\rho(s)=s$, this is nonlinear least squares. If $\rho$ grows more slowly than $s$, it downweights outliers.

17.9.1 Sparsity pattern

Each residual $r_{ij}$ depends only on one camera and one 3D point. Therefore the Jacobian is sparse. The normal equations have a block structure:

\[ \begin{bmatrix} H_{cc} & H_{cp} \\ H_{pc} & H_{pp} \end{bmatrix} \begin{bmatrix} \Delta c \\ \Delta p \end{bmatrix} = - \begin{bmatrix} g_c \\ g_p \end{bmatrix}. \]

Here $c$ denotes all camera parameters and $p$ denotes all point parameters. The point-point block $H_{pp}$ is block diagonal because each 3D point is independent once the cameras are fixed.

This special structure is exploited by the Schur complement:

\[ \left(H_{cc}-H_{cp}H_{pp}^{-1}H_{pc}\right)\Delta c = - \left(g_c-H_{cp}H_{pp}^{-1}g_p\right). \]

Bundle adjustment is Chapter 17’s main topic, but it must already appear here because SfM pipelines depend on it.

Interactive 16.4. Reprojection error landscape. Camera and point estimates are coupled. A good model minimizes image-space residuals across all observations.

17.10 16.9 Global SfM

Incremental SfM adds cameras one by one. Global SfM estimates many or all camera poses simultaneously from pairwise relative constraints.

The global strategy has two main stages:

estimate global camera rotations $R_i$ from relative rotations $R_{ik}$;
estimate camera centers $C_i$ from relative translation directions $\hat t_{ik}$.

17.10.1 Rotation averaging

For an edge $(i,k)$ in the view graph, the measured relative rotation approximately satisfies

\[ R_{ik}\approx R_kR_i^T. \]

A natural objective is

\[ \min_{R_1,\dots,R_m\in SO(3)} \sum_{(i,k)\in E_G} \rho\left(d_{SO(3)}(R_{ik},R_kR_i^T)^2\right), \]

where $d_{SO(3)}$ is a distance on the rotation group.

Using the matrix logarithm, one common local distance is

\[ d_{SO(3)}(A,B)=\|\log(A^TB)\|_2. \]

The global rotation is determined only up to a common rotation. Therefore one rotation may be fixed, for example $R_1=I$.

17.10.2 Translation averaging

Relative translation directions constrain camera centers:

\[ \hat t_{ik} \parallel C_k-C_i. \]

Equivalently,

\[ \hat t_{ik}\times(C_k-C_i)=0. \]

A least-squares translation averaging objective is

\[ \min_{C_1,\dots,C_m} \sum_{(i,k)\in E_G} \left\|\hat t_{ik}\times(C_k-C_i)\right\|_2^2. \]

This determines camera centers only up to global translation and scale. We may impose

\[ C_1=0, \qquad \sum_i \|C_i\|_2^2 = 1, \]

or another gauge convention.

Interactive 16.5. Rotation and translation averaging. Pairwise relative motions are noisy. Global SfM seeks camera poses that best satisfy all pairwise constraints at once.

17.11 16.10 Factorization methods under affine cameras

Although most modern SfM systems use perspective cameras, affine factorization is mathematically illuminating.

Under an orthographic or weak-perspective camera model, the image of 3D point $X_j$ in frame $i$ is

\[ x_{ij}=A_iX_j+b_i, \]

where $A_i\in\mathbb{R}^{2\times 3}$ and $b_i\in\mathbb{R}^2$.

After subtracting the centroid in each image, the translation $b_i$ is removed:

\[ \bar x_{ij}=A_iX_j. \]

Stacking all observations gives

\[ W = MS, \]

where

\[ M\in\mathbb{R}^{2m\times 3}, \qquad S\in\mathbb{R}^{3\times n}. \]

Therefore

\[ \operatorname{rank}(W)\le 3. \]

The singular value decomposition gives a rank-three approximation:

\[ W \approx U_3\Sigma_3V_3^T. \]

We can set

\[ \hat M=U_3\Sigma_3^{1/2}, \qquad \hat S=\Sigma_3^{1/2}V_3^T. \]

This factorization is not unique because for any invertible $3\times 3$ matrix $A$,

\[ \hat M\hat S=(\hat MA)(A^{-1}\hat S). \]

Metric constraints on the rows of the motion matrix are used to remove this affine ambiguity.

Interactive 16.6. Low-rank factorization. Under affine projection, the centered measurement matrix has rank at most 3. Noise lifts the rank, but the leading singular values still reveal the 3D structure.

17.12 16.11 Robust statistics in SfM

SfM is statistically difficult because the data contain many outliers:

repeated textures create false matches;
moving objects violate the static-scene assumption;
reflections and transparency violate Lambertian matching assumptions;
incorrect feature tracks merge unrelated physical points;
rolling shutter and lens distortion create model mismatch;
inaccurate intrinsics bias camera geometry.

17.12.1 Inlier model

A simple noise model is

\[ x_{ij}=\pi(P_i\tilde X_j)+\varepsilon_{ij}, \qquad \varepsilon_{ij}\sim\mathcal{N}(0,\sigma^2I_2). \]

Under this Gaussian model, least squares is maximum likelihood. However, when outliers are present, Gaussian least squares can fail badly.

A robust residual model uses a loss function such as Huber or Cauchy:

\[ \min \sum_{(i,j)\in\mathcal{O}} \rho\left(\frac{\|r_{ij}\|_2^2}{\sigma^2}\right). \]

For example, the Huber loss behaves quadratically for small residuals and linearly for large residuals:

\[ \rho_\delta(r)= \begin{cases} \frac{1}{2}r^2, & |r|\le \delta, \\ \delta(|r|-\frac{1}{2}\delta), & |r|>\delta. \end{cases} \]

17.12.2 Track filtering

Practical SfM repeatedly filters tracks using geometric tests:

\[ \|r_{ij}\|_2 < \tau_{\text{reproj}}, \]

positive depth tests,

\[ Z_{ij}>0, \]

and triangulation-angle tests,

\[ \theta_j>\theta_{\min}. \]

These tests are not merely engineering details. They enforce assumptions required for a stable inverse problem.

17.13 16.12 Statistical identifiability and conditioning

SfM is an inverse problem, so identifiability and conditioning matter.

17.13.1 Degenerate configurations

Some camera-scene configurations make reconstruction ambiguous or unstable:

Pure rotation: epipolar geometry does not provide triangulation baseline.
Small baseline: depth uncertainty becomes large.
Planar scenes: homographies can explain matches, making general 3D structure weakly constrained.
Low texture: correspondences are missing or unreliable.
Repeated patterns: feature matching creates many false positives.
Collinear camera centers: some 3D layouts become weakly constrained.
Disconnected view graph: separate components cannot be placed in one coordinate system.

17.13.2 Fisher-information viewpoint

For Gaussian image noise, the local covariance of an estimator is related to the inverse Hessian of the reprojection objective. If $J$ is the Jacobian of residuals with respect to parameters, then locally

\[ \operatorname{Cov}(\hat\theta)\approx \sigma^2(J^TJ)^{-1}. \]

Small singular values of $J$ indicate weakly constrained directions. Gauge freedoms appear as exact null directions unless constraints are imposed.

Interactive 16.7. Baseline and conditioning. Small baselines and narrow triangulation angles produce high depth uncertainty. SfM quality depends as much on geometry as on algorithms.

17.14 16.13 Modern AI components

Classical SfM relies on hand-designed local features, geometric verification, and nonlinear optimization. Modern AI modifies several pieces of the pipeline while preserving the same geometric core.

17.14.1 Learned local features

Instead of using hand-designed descriptors, a network may learn a feature extractor

\[ f_\theta(I) = \{(p_k,d_k,s_k)\}_{k=1}^N, \]

where $p_k$ is a keypoint location, $d_k$ is a descriptor, and $s_k$ is a confidence score. The descriptor objective often encourages matching descriptors to be close and nonmatching descriptors to be far apart.

A contrastive descriptor loss has the form

\[ \mathcal{L}= -y\log \sigma(d_a^Td_b) -(1-y)\log(1-\sigma(d_a^Td_b)), \]

where $y=1$ for matching pairs and $y=0$ for nonmatching pairs.

17.14.2 Learned matching

Modern matchers may use attention to compare sets of descriptors. If $D_1\in\mathbb{R}^{n_1\times d}$ and $D_2\in\mathbb{R}^{n_2\times d}$ are descriptor matrices, a soft matching matrix may begin with similarities

\[ S=\frac{D_1D_2^T}{\sqrt d}. \]

After normalization, $S$ becomes a soft assignment between image features. Geometric verification is still needed, because appearance matching alone can be wrong.

17.14.3 Differentiable SfM

Some systems make projection, triangulation, and pose estimation differentiable. A differentiable geometric loss may be

\[ \mathcal{L}_{\text{geom}} = \sum_{(i,j)\in\mathcal{O}} \left\|x_{ij}-\pi(P_i(\theta)\tilde X_j(\theta))\right\|_1. \]

This allows a neural network to learn features or depth representations using geometric consistency as supervision.

17.14.4 Relation to SLAM and neural rendering

SfM is usually an offline reconstruction problem. SLAM, simultaneous localization and mapping, is the online version: camera poses and maps are updated sequentially as data arrive.

Neural rendering and NeRF-style methods also estimate camera poses and scene representations by minimizing image reconstruction errors. The scene representation changes from sparse points to a continuous radiance field, but the inverse-problem structure remains:

\[ \text{observed images} \quad \longrightarrow \quad \text{camera poses plus scene representation}. \]

17.15 16.14 Python example: synthetic SfM geometry

The following example simulates cameras on a circular path, projects random 3D points, and visualizes the sparse reconstruction problem.

import numpy as np
import matplotlib.pyplot as plt

rng = np.random.default_rng(7243)

# Intrinsic matrix
f = 800.0
cx, cy = 320.0, 240.0
K = np.array([[f, 0, cx],
              [0, f, cy],
              [0, 0, 1]])

# Synthetic 3D points
n_points = 80
X = rng.uniform([-1.5, -1.0, 3.5], [1.5, 1.0, 6.0], size=(n_points, 3))

# Camera centers on a short arc
n_cams = 5
angles = np.linspace(-0.25, 0.25, n_cams)
centers = np.column_stack([2.0 * np.sin(angles),
                           np.zeros(n_cams),
                           2.0 * np.cos(angles) - 1.0])

def look_at_rotation(C, target=np.array([0.0, 0.0, 4.8])):
    z = target - C
    z = z / np.linalg.norm(z)
    x = np.cross(np.array([0.0, 1.0, 0.0]), z)
    x = x / np.linalg.norm(x)
    y = np.cross(z, x)
    # Rows of R map world coordinates into camera coordinates.
    return np.vstack([x, y, z])

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

observations = []
for i, C in enumerate(centers):
    R = look_at_rotation(C)
    uv, depth = project(K, R, C, X)
    noise = rng.normal(0, 0.7, size=uv.shape)
    uv_noisy = uv + noise
    visible = (depth > 0) & (uv_noisy[:, 0] >= 0) & (uv_noisy[:, 0] < 640) & (uv_noisy[:, 1] >= 0) & (uv_noisy[:, 1] < 480)
    observations.append((uv_noisy, visible))

plt.figure(figsize=(6, 5))
for i, (uv, visible) in enumerate(observations):
    plt.scatter(uv[visible, 0], uv[visible, 1], s=12, label=f"camera {i+1}", alpha=0.7)
plt.gca().invert_yaxis()
plt.xlabel("u pixel coordinate")
plt.ylabel("v pixel coordinate")
plt.title("Synthetic image observations from multiple cameras")
plt.legend()
plt.show()

17.16 16.15 Python example: estimating an essential matrix

This example shows the computational logic of two-view initialization. In a real system, feature matching would supply the correspondences.

import cv2
import numpy as np

# pts1 and pts2 are Nx2 arrays of matched pixel coordinates.
# K is the known calibration matrix.

E, inlier_mask = cv2.findEssentialMat(
    pts1,
    pts2,
    cameraMatrix=K,
    method=cv2.RANSAC,
    prob=0.999,
    threshold=1.0
)

num_inliers = int(inlier_mask.sum())
print("Number of geometric inliers:", num_inliers)

_, R, t, pose_mask = cv2.recoverPose(E, pts1, pts2, cameraMatrix=K)
print("Relative rotation:\n", R)
print("Relative translation direction:\n", t.ravel())

The output translation vector is a direction, not a metric baseline. Metric scale must come from additional information, such as known object size, stereo baseline, GPS/IMU, wheel odometry, or manual alignment.

17.17 16.16 Python example: PnP for adding a new image

Once a sparse 3D model exists, a new image can be added by solving PnP.

import cv2
import numpy as np

# X_world: Nx3 array of known 3D points.
# x_image: Nx2 array of corresponding image coordinates in the new image.
# K: known intrinsic matrix.

dist_coeffs = np.zeros(5)

success, rvec, tvec, inliers = cv2.solvePnPRansac(
    objectPoints=X_world.astype(np.float64),
    imagePoints=x_image.astype(np.float64),
    cameraMatrix=K.astype(np.float64),
    distCoeffs=dist_coeffs,
    reprojectionError=4.0,
    confidence=0.999,
    iterationsCount=2000
)

if success:
    R, _ = cv2.Rodrigues(rvec)
    print("PnP inliers:", len(inliers))
    print("Camera rotation:\n", R)
    print("Camera translation:\n", tvec.ravel())
else:
    print("Pose estimation failed.")

17.18 16.17 TensorFlow example: differentiable reprojection loss

The following minimal code sketches a differentiable reprojection loss. It is not a full SfM system, but it shows how geometry can become part of a learning objective.

import tensorflow as tf


def rodrigues_small(w):
    """Small-angle approximation for teaching purposes."""
    wx, wy, wz = tf.unstack(w)
    W = tf.stack([
        [0.0, -wz, wy],
        [wz, 0.0, -wx],
        [-wy, wx, 0.0]
    ])
    return tf.eye(3) + W


def project_points(K, rvec, t, X):
    R = rodrigues_small(rvec)
    Xc = tf.transpose(R @ tf.transpose(X)) + t[None, :]
    uvw = tf.transpose(K @ tf.transpose(Xc))
    uv = uvw[:, :2] / uvw[:, 2:3]
    return uv


def reprojection_loss(K, rvec, t, X, observed_uv):
    pred_uv = project_points(K, rvec, t, X)
    residual = pred_uv - observed_uv
    return tf.reduce_mean(tf.sqrt(tf.reduce_sum(residual**2, axis=1) + 1e-6))

K_tf = tf.constant([[800.0, 0.0, 320.0],
                    [0.0, 800.0, 240.0],
                    [0.0, 0.0, 1.0]])
rvec = tf.Variable([0.01, -0.02, 0.005], dtype=tf.float32)
tvec = tf.Variable([0.1, 0.0, 0.2], dtype=tf.float32)

# X_tf and uv_tf would come from a batch of 3D--2D correspondences.
# loss = reprojection_loss(K_tf, rvec, tvec, X_tf, uv_tf)

In serious implementations, rotations should be represented using stable Lie-group updates rather than the small-angle approximation above.

17.19 16.18 AI-assisted study prompts

Use an AI assistant as a mathematical tutor, not as an answer oracle. Productive prompts include:

Derivation check. “Derive why calibrated two-view SfM recovers translation only up to scale. Identify exactly where scale disappears.”
Gauge freedom. “Explain the difference between similarity ambiguity in calibrated SfM and projective ambiguity in uncalibrated SfM.”
Algorithm design. “Given a set of matched images, write pseudocode for incremental SfM and label every step as geometry, statistics, or optimization.”
Robustness. “Why does RANSAC help in essential-matrix estimation but not solve all SfM outlier problems?”
Statistical thinking. “Model reprojection residuals probabilistically. When is least squares justified? When is a robust loss better?”
Modern AI connection. “Compare a classical SIFT-based SfM pipeline with a learned-feature and attention-matching pipeline. Which mathematical constraints stay the same?”

17.20 16.19 Summary

SfM is one of the central achievements of geometric computer vision. It turns unordered or sequential images into a sparse 3D reconstruction and estimated camera trajectory.

The core mathematical ingredients are:

projective camera models;
pairwise epipolar geometry;
feature tracks and view graphs;
relative pose estimation;
triangulation;
absolute pose estimation;
robust statistics;
nonlinear least squares;
gauge fixing and identifiability;
global or incremental optimization.

The most important conceptual point is that SfM is not a single formula. It is a system of mutually reinforcing estimators. Pairwise geometry proposes constraints; tracks connect observations; triangulation estimates structure; PnP estimates new camera poses; bundle adjustment makes the entire system geometrically consistent.

17.21 Exercises

17.21.1 Conceptual exercises

Explain why two calibrated images can recover the direction of translation but not its magnitude.
What is a feature track? Why are long tracks more useful than isolated pairwise matches?
Explain the difference between the view graph and the track graph.
Why does a disconnected view graph prevent a single global reconstruction?
What is gauge freedom? Give one example in calibrated SfM.
Why is pure camera rotation degenerate for 3D reconstruction?
Compare incremental SfM and global SfM. What are the advantages and disadvantages of each?

17.21.2 Mathematical exercises

Let $P_i=K_i[R_i\mid t_i]$. Show that a global similarity transformation of all cameras and points preserves image measurements.
Starting from $E=[t]_\times R$, show that multiplying $t$ by a nonzero scalar leaves the epipolar constraint unchanged up to scale.
Derive the homogeneous linear triangulation equations from $\tilde x\times P\tilde X=0$.
Suppose $R_{ik}=R_kR_i^T$ exactly for all edges in a connected view graph. Show that the global rotations are determined up to one common rotation.
Derive the translation-direction constraint $\hat t_{ik}\times(C_k-C_i)=0$.
For affine cameras, prove that the centered measurement matrix has rank at most 3.
Let $r(\theta)$ be a vector of reprojection residuals. Derive the Gauss–Newton normal equations for minimizing $\|r(\theta)\|_2^2$.

17.21.3 Python exercises

Simulate two calibrated cameras and random 3D points. Project points into both images and recover the essential matrix using OpenCV.
Add Gaussian image noise and study how triangulation error changes with baseline.
Implement linear triangulation from multiple camera matrices.
Implement a simple PnP experiment using known 3D points and noisy image points.
Build a small view graph from synthetic pairwise overlap data and identify connected components.
Simulate an affine measurement matrix $W=MS$, add noise, and plot its singular values.
Implement robust residual weighting with Huber weights for reprojection residuals.

17.21.4 AI/modeling exercises

Ask an AI assistant to generate pseudocode for incremental SfM. Then annotate each line with the mathematical object being estimated.
Ask an AI assistant to explain why SfM has scale ambiguity. Check the explanation using equations.
Use an AI assistant to compare classical SIFT matching and learned attention-based matching. Identify which parts are appearance learning and which parts are geometric verification.
Design a self-supervised learning loss that uses multi-view reprojection consistency. State all assumptions.
Ask an AI assistant for three failure modes of SfM in urban scenes. For each one, give a mathematical reason.

17.22 References and further reading

Classical and modern treatments of SfM appear in Hartley and Zisserman (2004), Szeliski (2022), Faugeras (1993), and Ma et al. (2004). The affine factorization viewpoint comes from Tomasi and Kanade (1992). Large-scale unordered photo-collection SfM is represented by Snavely et al. (2006) and robust modern pipelines such as Sch"onberger and Frahm (2016). Bundle adjustment and sparse nonlinear least squares are surveyed in Triggs et al. (2000).

Faugeras, Olivier. 1993. Three-Dimensional Computer Vision: A Geometric Viewpoint. MIT Press.

Hartley, Richard, and Andrew Zisserman. 2004. Multiple View Geometry in Computer Vision. 2nd ed. Cambridge University Press. https://www.robots.ox.ac.uk/~vgg/hzbook/.

Ma, Yi, Stefano Soatto, Jana Kosecka, and Shankar S. Sastry. 2004. An Invitation to 3-d Vision: From Images to Geometric Models. Springer.

Sch"onberger, Johannes L., and Jan-Michael Frahm. 2016. “Structure-from-Motion Revisited.” IEEE Conference on Computer Vision and Pattern Recognition, 4104–13.

Snavely, Noah, Steven M. Seitz, and Richard Szeliski. 2006. “Photo Tourism: Exploring Photo Collections in 3D.” ACM SIGGRAPH, 835–46.

Szeliski, Richard. 2022. Computer Vision: Algorithms and Applications. 2nd ed. Springer. https://szeliski.org/Book/.

Tomasi, Carlo, and Takeo Kanade. 1992. “Shape and Motion from Image Streams Under Orthography: A Factorization Method.” International Journal of Computer Vision 9 (2): 137–54.

Triggs, Bill, Philip F. McLauchlan, Richard I. Hartley, and Andrew W. Fitzgibbon. 2000. “Bundle Adjustment – a Modern Synthesis.” Vision Algorithms: Theory and Practice, 298–372.

# Structure from Motion ::: {.hero-box} Structure from Motion, abbreviated **SfM**, reconstructs camera motion and sparse 3D scene structure from a collection of images. Mathematically, SfM combines projective geometry, graph connectivity, robust statistics, nonlinear least squares, and modern feature learning. This chapter develops SfM from two-view geometry to multi-view reconstruction, emphasizing the clean mathematical principles behind practical pipelines such as feature matching, relative pose estimation, triangulation, pose graph construction, incremental reconstruction, global reconstruction, and differentiable learning-based variants. ::: ## Learning goals After reading this chapter, students should be able to: 1. describe the SfM problem as joint estimation of camera poses and 3D points; 2. explain why images form a **view graph** whose edges carry relative geometric constraints; 3. derive how pairwise essential matrices give relative rotations and translation directions; 4. distinguish calibrated SfM, uncalibrated projective reconstruction, and metric reconstruction; 5. formulate triangulation and camera resectioning as estimation subproblems; 6. explain incremental SfM and global SfM at a mathematical level; 7. understand gauge freedom, scale ambiguity, and coordinate choices; 8. write the multi-view reprojection-error objective; 9. explain robust estimation with RANSAC, M-estimators, and outlier filtering; 10. connect classical SfM to modern learned features, neural feature matching, SLAM, NeRF-style camera optimization, and differentiable bundle-adjustment layers. ## 16.1 The problem of reconstructing structure from motion Suppose a static 3D scene is observed by $m$ cameras. Let the unknown camera matrices be $$ P_i = K_i[R_i\mid t_i], \qquad i=1,\dots,m, $$ and let the unknown 3D scene points be $$ X_j \in \mathbb{R}^3, \qquad j=1,\dots,n. $$ The observed image measurement of point $X_j$ in camera $i$ is $$ x_{ij} \in \mathbb{R}^2, $$ when the point is visible in that image. Using homogeneous coordinates, the ideal projection relation is $$ \tilde x_{ij} \sim P_i \tilde X_j. $$ The **Structure from Motion problem** is to estimate the cameras and the 3D points from the image measurements: $$ \{x_{ij}\}_{(i,j)\in\mathcal{O}} \quad \longrightarrow \quad \{P_i\}_{i=1}^m,\; \{X_j\}_{j=1}^n, $$ where $\mathcal{O}$ is the set of observed image-point pairs. SfM is called **structure from motion** because camera motion supplies multiple viewpoints. The same physical point is observed from different camera positions, and the change in its image location constrains both the point location and camera motion. ::: {.math-spine} SfM is the global version of two-view geometry. Epipolar geometry gives pairwise constraints; triangulation gives candidate 3D points; bundle adjustment makes all cameras and all points agree simultaneously. ::: ::: {.interactive-card} **Interactive 16.1. Cameras, points, and tracks.** A sparse SfM model is a bipartite relationship between cameras and 3D points. The same 3D point creates an image track across several views. <div id="cv-ch16-camera-track-demo" class="plotly-demo"></div> ::: ## 16.2 From two-view geometry to multi-view geometry Chapter 14 studied two calibrated cameras. If image points $x_1$ and $x_2$ are corresponding normalized coordinates, then $$ x_2^T E x_1 = 0, $$ where the essential matrix has the form $$ E=[t]_\times R. $$ Here $R\in SO(3)$ is the relative rotation and $t\in\mathbb{R}^3$ is the relative translation direction between two cameras. The skew-symmetric matrix $[t]_\times$ represents the cross product: $$ [t]_\times a = t\times a. $$ The essential matrix contains the relative pose between two calibrated cameras, except for the unknown scale of $t$. In other words, two-view geometry determines the direction of translation but not its absolute length. ### Pairwise relative pose For two calibrated cameras, write the first camera as $$ P_1 = [I\mid 0], $$ and the second as $$ P_2 = [R\mid t]. $$ Then the relative pose $(R,t)$ can be recovered from $E$ up to the standard four-fold ambiguity. The physically valid choice is selected by the **cheirality condition**: triangulated points should lie in front of both cameras. This gives a two-view reconstruction: $$ \{x_{1j},x_{2j}\}_{j=1}^N \quad \longrightarrow \quad R,\; \hat t,\; \{X_j\}_{j=1}^N, $$ where $\hat t$ is a unit translation direction. The unknown baseline length remains a scale ambiguity. ### From pairwise poses to a view graph In a collection of images, we estimate relative geometry for many image pairs. This produces a graph $$ G=(V,E_G), $$ where each vertex $i\in V$ represents an image, and an edge $(i,k)\in E_G$ indicates that images $i$ and $k$ have enough verified correspondences to estimate relative geometry. Each edge carries measurements such as: $$ R_{ik}\approx R_kR_i^T, \qquad \hat t_{ik}\approx \frac{C_k-C_i}{\|C_k-C_i\|_2}, $$ where $C_i$ is the center of camera $i$. The view graph is central in modern SfM. It tells us which views are geometrically connected and which pairwise constraints can be trusted. ::: {.interactive-card} **Interactive 16.2. View graph connectivity.** Reconstruction needs enough graph connectivity. Weak bridges, missing edges, and noisy pairwise estimates can make the global camera configuration unstable. <div id="cv-ch16-view-graph-demo" class="plotly-demo"></div> ::: ## 16.3 Feature tracks and measurement matrices SfM starts from **correspondence**. A local feature in one image must be matched to the same physical scene point in other images. A **feature track** is a set of image observations believed to correspond to one 3D point: $$ T_j = \{(i,x_{ij}): \text{point } j \text{ is observed in image } i\}. $$ For example, if the same corner is observed in images 2, 5, 6, and 9, then its track is $$ T_j=\{(2,x_{2j}),(5,x_{5j}),(6,x_{6j}),(9,x_{9j})\}. $$ The set of all tracks determines the sparse observation pattern $\mathcal{O}$. ### Track graph view There are two related graphs: 1. The **view graph**, whose vertices are images and whose edges are verified image pairs. 2. The **track graph**, a bipartite graph between camera vertices and point vertices. The track graph has an edge $(i,j)$ when camera $i$ observes point $j$. Bundle adjustment optimizes over this bipartite graph. ### Data matrix viewpoint For an ideal orthographic camera model with complete observations, classical factorization methods arrange image coordinates into a measurement matrix $$ W = \begin{bmatrix} x_{11} & x_{12} & \cdots & x_{1n} \\ y_{11} & y_{12} & \cdots & y_{1n} \\ \vdots & \vdots & & \vdots \\ x_{m1} & x_{m2} & \cdots & x_{mn} \\ y_{m1} & y_{m2} & \cdots & y_{mn} \end{bmatrix} \in \mathbb{R}^{2m\times n}. $$ Under affine or orthographic projection, after centering each image, this matrix has low rank: $$ \operatorname{rank}(W)\le 3. $$ This observation leads to the Tomasi--Kanade factorization idea: estimate motion and shape from the low-rank factorization of $W$. Although full perspective SfM is more nonlinear, the low-rank viewpoint is important because it reveals that multi-view geometry has strong algebraic structure. ## 16.4 Gauge freedom and scale ambiguity SfM does not directly recover an absolute coordinate system. If $\{R_i,t_i,X_j\}$ explains the image measurements, then many transformed configurations also explain the same measurements. ### Similarity ambiguity in calibrated SfM For calibrated cameras, a global similarity transformation does not change image projections. Let $$ X_j' = sQX_j+a, $$ where $s>0$, $Q\in SO(3)$, and $a\in\mathbb{R}^3$. If camera poses are transformed consistently, all image projections remain unchanged. Thus calibrated SfM determines structure only up to a global similarity transformation: rotation, translation, and scale. The scale ambiguity is especially important. Two images can determine the direction of translation, but not the magnitude of the baseline. If the whole scene and camera trajectory are scaled by the same factor, the images are unchanged. ### Projective ambiguity in uncalibrated SfM If camera intrinsics are unknown and unconstrained, reconstruction is only projective. A projective transformation $H\in\mathbb{R}^{4\times 4}$ changes points and cameras by $$ \tilde X_j' = H\tilde X_j, \qquad P_i' = P_iH^{-1}. $$ Then $$ P_i'\tilde X_j' = P_iH^{-1}H\tilde X_j=P_i\tilde X_j, $$ so the same image measurements are produced. Additional calibration or scene constraints are needed to upgrade a projective reconstruction to an affine or metric reconstruction. ::: {.math-spine} Gauge freedom is not a bug. It is a mathematical symmetry of the projection equations. A numerical optimizer must fix this symmetry, for example by anchoring one camera pose and setting a scale convention. ::: ## 16.5 Incremental SfM pipeline Many practical SfM systems use an **incremental** pipeline. The core idea is to build the reconstruction gradually. A typical incremental SfM pipeline is: 1. detect local features in all images; 2. match features between image pairs; 3. verify matches using robust epipolar geometry; 4. choose an initial image pair with many reliable matches and good baseline; 5. recover the relative pose and triangulate initial 3D points; 6. add a new image by estimating its pose from existing 3D-to-2D correspondences; 7. triangulate new points seen by the new image and previous images; 8. run local or global bundle adjustment; 9. repeat until no useful images remain. The estimation subproblems are: $$ \text{relative pose estimation}, \qquad \text{triangulation}, \qquad \text{absolute pose estimation}, \qquad \text{bundle adjustment}. $$ Incremental SfM is robust because each new step is supported by the current model. However, it can suffer from drift and path dependence: early errors may influence later reconstruction. ::: {.interactive-card} **Interactive 16.3. Incremental reconstruction.** A reconstruction grows by adding cameras and triangulating new points. The order of image insertion affects stability. <div id="cv-ch16-incremental-demo" class="plotly-demo"></div> ::: ## 16.6 Absolute pose from 2D--3D correspondences Suppose some 3D points $X_j$ are already reconstructed, and a new image observes their 2D locations $x_j$. To add the new image, we estimate its camera pose. For a calibrated camera, the problem is: $$ x_j \sim K[R\mid t]\tilde X_j, \qquad j=1,\dots,N. $$ If $K$ is known, we can work with normalized image coordinates. The pose estimation problem becomes $$ \hat x_j \sim [R\mid t]\tilde X_j. $$ This is called **Perspective-n-Point**, or **PnP**. ### Reprojection-error formulation The statistically natural formulation is nonlinear least squares: $$ \min_{R,t} \sum_{j=1}^N \rho\left(\left\|x_j-\pi(K(RX_j+t))\right\|_2^2\right), $$ where $\pi$ is perspective division and $\rho$ is either the identity loss or a robust loss. The rotation constraint matters: $$ R^TR=I, \qquad \det(R)=1. $$ In computation, rotations may be represented by rotation matrices, Euler angles, axis-angle vectors, quaternions, or Lie algebra increments in $\mathfrak{so}(3)$. ### Minimal solvers and RANSAC A minimal PnP solver estimates pose from a small number of correspondences. Because some 2D--3D matches are wrong, pose estimation is usually embedded in RANSAC: 1. sample a minimal subset; 2. estimate candidate pose; 3. count inliers using reprojection error; 4. refine using all inliers. The inlier test has the form $$ \left\|x_j-\pi(K(RX_j+t))\right\|_2 < \tau. $$ This connects directly to the robust estimation ideas from Chapter 14. ## 16.7 Triangulation in multi-view SfM After estimating camera poses, we can triangulate new points. For a point observed in several cameras, we estimate $$ X_j = \arg\min_X \sum_{i\in\mathcal{V}_j} \left\|x_{ij}-\pi(P_i\tilde X)\right\|_2^2, $$ where $\mathcal{V}_j$ is the set of cameras that observe point $j$. ### Linear triangulation The homogeneous relation $$ \tilde x_{ij}\times P_i\tilde X=0 $$ gives two independent linear equations for each observation. Stacking the equations over views gives $$ A\tilde X=0. $$ The linear triangulated point is obtained as the right singular vector corresponding to the smallest singular value of $A$. ### Nonlinear refinement Linear triangulation is simple, but it minimizes an algebraic error, not image reprojection error. Therefore a common refinement is $$ \min_X \sum_{i\in\mathcal{V}_j} \left\|x_{ij}-\pi(P_i\tilde X)\right\|_2^2. $$ This is a small nonlinear least-squares problem with three unknowns. The Jacobian of the projection determines the conditioning. ### Triangulation angle If the viewing rays are nearly parallel, depth is poorly constrained. The angle between two rays $r_1$ and $r_2$ is $$ \theta = \arccos\left(\frac{r_1^Tr_2}{\|r_1\|_2\|r_2\|_2}\right). $$ Small $\theta$ means unstable depth. SfM systems often reject triangulated points when the triangulation angle is too small. ## 16.8 Bundle adjustment objective The central optimization problem in SfM is **bundle adjustment**. The name comes from adjusting bundles of camera rays so they intersect at consistent 3D points. Let $\theta_i$ denote the parameters of camera $i$ and let $X_j$ denote 3D point $j$. The reprojection residual is $$ r_{ij}(\theta_i,X_j)=x_{ij}-\pi(P(\theta_i)\tilde X_j). $$ The bundle-adjustment objective is $$ \min_{\{\theta_i\},\{X_j\}} \sum_{(i,j)\in\mathcal{O}} \rho\left(\|r_{ij}(\theta_i,X_j)\|_2^2\right). $$ If $\rho(s)=s$, this is nonlinear least squares. If $\rho$ grows more slowly than $s$, it downweights outliers. ### Sparsity pattern Each residual $r_{ij}$ depends only on one camera and one 3D point. Therefore the Jacobian is sparse. The normal equations have a block structure: $$ \begin{bmatrix} H_{cc} & H_{cp} \\ H_{pc} & H_{pp} \end{bmatrix} \begin{bmatrix} \Delta c \\ \Delta p \end{bmatrix} = - \begin{bmatrix} g_c \\ g_p \end{bmatrix}. $$ Here $c$ denotes all camera parameters and $p$ denotes all point parameters. The point-point block $H_{pp}$ is block diagonal because each 3D point is independent once the cameras are fixed. This special structure is exploited by the Schur complement: $$ \left(H_{cc}-H_{cp}H_{pp}^{-1}H_{pc}\right)\Delta c = - \left(g_c-H_{cp}H_{pp}^{-1}g_p\right). $$ Bundle adjustment is Chapter 17's main topic, but it must already appear here because SfM pipelines depend on it. ::: {.interactive-card} **Interactive 16.4. Reprojection error landscape.** Camera and point estimates are coupled. A good model minimizes image-space residuals across all observations. <div id="cv-ch16-reprojection-demo" class="plotly-demo"></div> ::: ## 16.9 Global SfM Incremental SfM adds cameras one by one. **Global SfM** estimates many or all camera poses simultaneously from pairwise relative constraints. The global strategy has two main stages: 1. estimate global camera rotations $R_i$ from relative rotations $R_{ik}$; 2. estimate camera centers $C_i$ from relative translation directions $\hat t_{ik}$. ### Rotation averaging For an edge $(i,k)$ in the view graph, the measured relative rotation approximately satisfies $$ R_{ik}\approx R_kR_i^T. $$ A natural objective is $$ \min_{R_1,\dots,R_m\in SO(3)} \sum_{(i,k)\in E_G} \rho\left(d_{SO(3)}(R_{ik},R_kR_i^T)^2\right), $$ where $d_{SO(3)}$ is a distance on the rotation group. Using the matrix logarithm, one common local distance is $$ d_{SO(3)}(A,B)=\|\log(A^TB)\|_2. $$ The global rotation is determined only up to a common rotation. Therefore one rotation may be fixed, for example $R_1=I$. ### Translation averaging Relative translation directions constrain camera centers: $$ \hat t_{ik} \parallel C_k-C_i. $$ Equivalently, $$ \hat t_{ik}\times(C_k-C_i)=0. $$ A least-squares translation averaging objective is $$ \min_{C_1,\dots,C_m} \sum_{(i,k)\in E_G} \left\|\hat t_{ik}\times(C_k-C_i)\right\|_2^2. $$ This determines camera centers only up to global translation and scale. We may impose $$ C_1=0, \qquad \sum_i \|C_i\|_2^2 = 1, $$ or another gauge convention. ::: {.interactive-card} **Interactive 16.5. Rotation and translation averaging.** Pairwise relative motions are noisy. Global SfM seeks camera poses that best satisfy all pairwise constraints at once. <div id="cv-ch16-averaging-demo" class="plotly-demo"></div> ::: ## 16.10 Factorization methods under affine cameras Although most modern SfM systems use perspective cameras, affine factorization is mathematically illuminating. Under an orthographic or weak-perspective camera model, the image of 3D point $X_j$ in frame $i$ is $$ x_{ij}=A_iX_j+b_i, $$ where $A_i\in\mathbb{R}^{2\times 3}$ and $b_i\in\mathbb{R}^2$. After subtracting the centroid in each image, the translation $b_i$ is removed: $$ \bar x_{ij}=A_iX_j. $$ Stacking all observations gives $$ W = MS, $$ where $$ M\in\mathbb{R}^{2m\times 3}, \qquad S\in\mathbb{R}^{3\times n}. $$ Therefore $$ \operatorname{rank}(W)\le 3. $$ The singular value decomposition gives a rank-three approximation: $$ W \approx U_3\Sigma_3V_3^T. $$ We can set $$ \hat M=U_3\Sigma_3^{1/2}, \qquad \hat S=\Sigma_3^{1/2}V_3^T. $$ This factorization is not unique because for any invertible $3\times 3$ matrix $A$, $$ \hat M\hat S=(\hat MA)(A^{-1}\hat S). $$ Metric constraints on the rows of the motion matrix are used to remove this affine ambiguity. ::: {.interactive-card} **Interactive 16.6. Low-rank factorization.** Under affine projection, the centered measurement matrix has rank at most 3. Noise lifts the rank, but the leading singular values still reveal the 3D structure. <div id="cv-ch16-factorization-demo" class="plotly-demo"></div> ::: ## 16.11 Robust statistics in SfM SfM is statistically difficult because the data contain many outliers: - repeated textures create false matches; - moving objects violate the static-scene assumption; - reflections and transparency violate Lambertian matching assumptions; - incorrect feature tracks merge unrelated physical points; - rolling shutter and lens distortion create model mismatch; - inaccurate intrinsics bias camera geometry. ### Inlier model A simple noise model is $$ x_{ij}=\pi(P_i\tilde X_j)+\varepsilon_{ij}, \qquad \varepsilon_{ij}\sim\mathcal{N}(0,\sigma^2I_2). $$ Under this Gaussian model, least squares is maximum likelihood. However, when outliers are present, Gaussian least squares can fail badly. A robust residual model uses a loss function such as Huber or Cauchy: $$ \min \sum_{(i,j)\in\mathcal{O}} \rho\left(\frac{\|r_{ij}\|_2^2}{\sigma^2}\right). $$ For example, the Huber loss behaves quadratically for small residuals and linearly for large residuals: $$ \rho_\delta(r)= \begin{cases} \frac{1}{2}r^2, & |r|\le \delta, \\ \delta(|r|-\frac{1}{2}\delta), & |r|>\delta. \end{cases} $$ ### Track filtering Practical SfM repeatedly filters tracks using geometric tests: $$ \|r_{ij}\|_2 < \tau_{\text{reproj}}, $$ positive depth tests, $$ Z_{ij}>0, $$ and triangulation-angle tests, $$ \theta_j>\theta_{\min}. $$ These tests are not merely engineering details. They enforce assumptions required for a stable inverse problem. ## 16.12 Statistical identifiability and conditioning SfM is an inverse problem, so identifiability and conditioning matter. ### Degenerate configurations Some camera-scene configurations make reconstruction ambiguous or unstable: 1. **Pure rotation**: epipolar geometry does not provide triangulation baseline. 2. **Small baseline**: depth uncertainty becomes large. 3. **Planar scenes**: homographies can explain matches, making general 3D structure weakly constrained. 4. **Low texture**: correspondences are missing or unreliable. 5. **Repeated patterns**: feature matching creates many false positives. 6. **Collinear camera centers**: some 3D layouts become weakly constrained. 7. **Disconnected view graph**: separate components cannot be placed in one coordinate system. ### Fisher-information viewpoint For Gaussian image noise, the local covariance of an estimator is related to the inverse Hessian of the reprojection objective. If $J$ is the Jacobian of residuals with respect to parameters, then locally $$ \operatorname{Cov}(\hat\theta)\approx \sigma^2(J^TJ)^{-1}. $$ Small singular values of $J$ indicate weakly constrained directions. Gauge freedoms appear as exact null directions unless constraints are imposed. ::: {.interactive-card} **Interactive 16.7. Baseline and conditioning.** Small baselines and narrow triangulation angles produce high depth uncertainty. SfM quality depends as much on geometry as on algorithms. <div id="cv-ch16-conditioning-demo" class="plotly-demo"></div> ::: ## 16.13 Modern AI components Classical SfM relies on hand-designed local features, geometric verification, and nonlinear optimization. Modern AI modifies several pieces of the pipeline while preserving the same geometric core. ### Learned local features Instead of using hand-designed descriptors, a network may learn a feature extractor $$ f_\theta(I) = \{(p_k,d_k,s_k)\}_{k=1}^N, $$ where $p_k$ is a keypoint location, $d_k$ is a descriptor, and $s_k$ is a confidence score. The descriptor objective often encourages matching descriptors to be close and nonmatching descriptors to be far apart. A contrastive descriptor loss has the form $$ \mathcal{L}= -y\log \sigma(d_a^Td_b) -(1-y)\log(1-\sigma(d_a^Td_b)), $$ where $y=1$ for matching pairs and $y=0$ for nonmatching pairs. ### Learned matching Modern matchers may use attention to compare sets of descriptors. If $D_1\in\mathbb{R}^{n_1\times d}$ and $D_2\in\mathbb{R}^{n_2\times d}$ are descriptor matrices, a soft matching matrix may begin with similarities $$ S=\frac{D_1D_2^T}{\sqrt d}. $$ After normalization, $S$ becomes a soft assignment between image features. Geometric verification is still needed, because appearance matching alone can be wrong. ### Differentiable SfM Some systems make projection, triangulation, and pose estimation differentiable. A differentiable geometric loss may be $$ \mathcal{L}_{\text{geom}} = \sum_{(i,j)\in\mathcal{O}} \left\|x_{ij}-\pi(P_i(\theta)\tilde X_j(\theta))\right\|_1. $$ This allows a neural network to learn features or depth representations using geometric consistency as supervision. ### Relation to SLAM and neural rendering SfM is usually an offline reconstruction problem. SLAM, simultaneous localization and mapping, is the online version: camera poses and maps are updated sequentially as data arrive. Neural rendering and NeRF-style methods also estimate camera poses and scene representations by minimizing image reconstruction errors. The scene representation changes from sparse points to a continuous radiance field, but the inverse-problem structure remains: $$ \text{observed images} \quad \longrightarrow \quad \text{camera poses plus scene representation}. $$ ## 16.14 Python example: synthetic SfM geometry The following example simulates cameras on a circular path, projects random 3D points, and visualizes the sparse reconstruction problem. ```{python} #| label: py-ch16-synthetic-sfm #| eval: false import numpy as np import matplotlib.pyplot as plt rng = np.random.default_rng(7243) # Intrinsic matrix f = 800.0 cx, cy = 320.0, 240.0 K = np.array([[f, 0, cx], [0, f, cy], [0, 0, 1]]) # Synthetic 3D points n_points = 80 X = rng.uniform([-1.5, -1.0, 3.5], [1.5, 1.0, 6.0], size=(n_points, 3)) # Camera centers on a short arc n_cams = 5 angles = np.linspace(-0.25, 0.25, n_cams) centers = np.column_stack([2.0 * np.sin(angles), np.zeros(n_cams), 2.0 * np.cos(angles) - 1.0]) def look_at_rotation(C, target=np.array([0.0, 0.0, 4.8])): z = target - C z = z / np.linalg.norm(z) x = np.cross(np.array([0.0, 1.0, 0.0]), z) x = x / np.linalg.norm(x) y = np.cross(z, x) # Rows of R map world coordinates into camera coordinates. return np.vstack([x, y, z]) def project(K, R, C, X): Xc = (R @ (X - C).T).T u = K @ Xc.T u = (u[:2] / u[2]).T return u, Xc[:, 2] observations = [] for i, C in enumerate(centers): R = look_at_rotation(C) uv, depth = project(K, R, C, X) noise = rng.normal(0, 0.7, size=uv.shape) uv_noisy = uv + noise visible = (depth > 0) & (uv_noisy[:, 0] >= 0) & (uv_noisy[:, 0] < 640) & (uv_noisy[:, 1] >= 0) & (uv_noisy[:, 1] < 480) observations.append((uv_noisy, visible)) plt.figure(figsize=(6, 5)) for i, (uv, visible) in enumerate(observations): plt.scatter(uv[visible, 0], uv[visible, 1], s=12, label=f"camera {i+1}", alpha=0.7) plt.gca().invert_yaxis() plt.xlabel("u pixel coordinate") plt.ylabel("v pixel coordinate") plt.title("Synthetic image observations from multiple cameras") plt.legend() plt.show() ``` ## 16.15 Python example: estimating an essential matrix This example shows the computational logic of two-view initialization. In a real system, feature matching would supply the correspondences. ```{python} #| label: py-ch16-essential-ransac #| eval: false import cv2 import numpy as np # pts1 and pts2 are Nx2 arrays of matched pixel coordinates. # K is the known calibration matrix. E, inlier_mask = cv2.findEssentialMat( pts1, pts2, cameraMatrix=K, method=cv2.RANSAC, prob=0.999, threshold=1.0 ) num_inliers = int(inlier_mask.sum()) print("Number of geometric inliers:", num_inliers) _, R, t, pose_mask = cv2.recoverPose(E, pts1, pts2, cameraMatrix=K) print("Relative rotation:\n", R) print("Relative translation direction:\n", t.ravel()) ``` The output translation vector is a direction, not a metric baseline. Metric scale must come from additional information, such as known object size, stereo baseline, GPS/IMU, wheel odometry, or manual alignment. ## 16.16 Python example: PnP for adding a new image Once a sparse 3D model exists, a new image can be added by solving PnP. ```{python} #| label: py-ch16-pnp #| eval: false import cv2 import numpy as np # X_world: Nx3 array of known 3D points. # x_image: Nx2 array of corresponding image coordinates in the new image. # K: known intrinsic matrix. dist_coeffs = np.zeros(5) success, rvec, tvec, inliers = cv2.solvePnPRansac( objectPoints=X_world.astype(np.float64), imagePoints=x_image.astype(np.float64), cameraMatrix=K.astype(np.float64), distCoeffs=dist_coeffs, reprojectionError=4.0, confidence=0.999, iterationsCount=2000 ) if success: R, _ = cv2.Rodrigues(rvec) print("PnP inliers:", len(inliers)) print("Camera rotation:\n", R) print("Camera translation:\n", tvec.ravel()) else: print("Pose estimation failed.") ``` ## 16.17 TensorFlow example: differentiable reprojection loss The following minimal code sketches a differentiable reprojection loss. It is not a full SfM system, but it shows how geometry can become part of a learning objective. ```{python} #| label: py-ch16-tensorflow-reprojection-loss #| eval: false import tensorflow as tf def rodrigues_small(w): """Small-angle approximation for teaching purposes.""" wx, wy, wz = tf.unstack(w) W = tf.stack([ [0.0, -wz, wy], [wz, 0.0, -wx], [-wy, wx, 0.0] ]) return tf.eye(3) + W def project_points(K, rvec, t, X): R = rodrigues_small(rvec) Xc = tf.transpose(R @ tf.transpose(X)) + t[None, :] uvw = tf.transpose(K @ tf.transpose(Xc)) uv = uvw[:, :2] / uvw[:, 2:3] return uv def reprojection_loss(K, rvec, t, X, observed_uv): pred_uv = project_points(K, rvec, t, X) residual = pred_uv - observed_uv return tf.reduce_mean(tf.sqrt(tf.reduce_sum(residual**2, axis=1) + 1e-6)) K_tf = tf.constant([[800.0, 0.0, 320.0], [0.0, 800.0, 240.0], [0.0, 0.0, 1.0]]) rvec = tf.Variable([0.01, -0.02, 0.005], dtype=tf.float32) tvec = tf.Variable([0.1, 0.0, 0.2], dtype=tf.float32) # X_tf and uv_tf would come from a batch of 3D--2D correspondences. # loss = reprojection_loss(K_tf, rvec, tvec, X_tf, uv_tf) ``` In serious implementations, rotations should be represented using stable Lie-group updates rather than the small-angle approximation above. ## 16.18 AI-assisted study prompts Use an AI assistant as a mathematical tutor, not as an answer oracle. Productive prompts include: 1. **Derivation check.** “Derive why calibrated two-view SfM recovers translation only up to scale. Identify exactly where scale disappears.” 2. **Gauge freedom.** “Explain the difference between similarity ambiguity in calibrated SfM and projective ambiguity in uncalibrated SfM.” 3. **Algorithm design.** “Given a set of matched images, write pseudocode for incremental SfM and label every step as geometry, statistics, or optimization.” 4. **Robustness.** “Why does RANSAC help in essential-matrix estimation but not solve all SfM outlier problems?” 5. **Statistical thinking.** “Model reprojection residuals probabilistically. When is least squares justified? When is a robust loss better?” 6. **Modern AI connection.** “Compare a classical SIFT-based SfM pipeline with a learned-feature and attention-matching pipeline. Which mathematical constraints stay the same?” ## 16.19 Summary SfM is one of the central achievements of geometric computer vision. It turns unordered or sequential images into a sparse 3D reconstruction and estimated camera trajectory. The core mathematical ingredients are: - projective camera models; - pairwise epipolar geometry; - feature tracks and view graphs; - relative pose estimation; - triangulation; - absolute pose estimation; - robust statistics; - nonlinear least squares; - gauge fixing and identifiability; - global or incremental optimization. The most important conceptual point is that SfM is not a single formula. It is a system of mutually reinforcing estimators. Pairwise geometry proposes constraints; tracks connect observations; triangulation estimates structure; PnP estimates new camera poses; bundle adjustment makes the entire system geometrically consistent. ## Exercises ### Conceptual exercises 1. Explain why two calibrated images can recover the direction of translation but not its magnitude. 2. What is a feature track? Why are long tracks more useful than isolated pairwise matches? 3. Explain the difference between the view graph and the track graph. 4. Why does a disconnected view graph prevent a single global reconstruction? 5. What is gauge freedom? Give one example in calibrated SfM. 6. Why is pure camera rotation degenerate for 3D reconstruction? 7. Compare incremental SfM and global SfM. What are the advantages and disadvantages of each? ### Mathematical exercises 1. Let $P_i=K_i[R_i\mid t_i]$. Show that a global similarity transformation of all cameras and points preserves image measurements. 2. Starting from $E=[t]_\times R$, show that multiplying $t$ by a nonzero scalar leaves the epipolar constraint unchanged up to scale. 3. Derive the homogeneous linear triangulation equations from $\tilde x\times P\tilde X=0$. 4. Suppose $R_{ik}=R_kR_i^T$ exactly for all edges in a connected view graph. Show that the global rotations are determined up to one common rotation. 5. Derive the translation-direction constraint $\hat t_{ik}\times(C_k-C_i)=0$. 6. For affine cameras, prove that the centered measurement matrix has rank at most 3. 7. Let $r(\theta)$ be a vector of reprojection residuals. Derive the Gauss--Newton normal equations for minimizing $\|r(\theta)\|_2^2$. ### Python exercises 1. Simulate two calibrated cameras and random 3D points. Project points into both images and recover the essential matrix using OpenCV. 2. Add Gaussian image noise and study how triangulation error changes with baseline. 3. Implement linear triangulation from multiple camera matrices. 4. Implement a simple PnP experiment using known 3D points and noisy image points. 5. Build a small view graph from synthetic pairwise overlap data and identify connected components. 6. Simulate an affine measurement matrix $W=MS$, add noise, and plot its singular values. 7. Implement robust residual weighting with Huber weights for reprojection residuals. ### AI/modeling exercises 1. Ask an AI assistant to generate pseudocode for incremental SfM. Then annotate each line with the mathematical object being estimated. 2. Ask an AI assistant to explain why SfM has scale ambiguity. Check the explanation using equations. 3. Use an AI assistant to compare classical SIFT matching and learned attention-based matching. Identify which parts are appearance learning and which parts are geometric verification. 4. Design a self-supervised learning loss that uses multi-view reprojection consistency. State all assumptions. 5. Ask an AI assistant for three failure modes of SfM in urban scenes. For each one, give a mathematical reason. ## References and further reading Classical and modern treatments of SfM appear in @hartley2004multiple, @szeliski2022computer, @faugeras1993three, and @ma2004invitation. The affine factorization viewpoint comes from @tomasi1992shape. Large-scale unordered photo-collection SfM is represented by @snavely2006photo and robust modern pipelines such as @schoenberger2016sfm. Bundle adjustment and sparse nonlinear least squares are surveyed in @triggs2000bundle. <script> (function() { function ready(fn) { if (document.readyState !== 'loading') fn(); else document.addEventListener('DOMContentLoaded', fn); } function linspace(a, b, n) { const out = []; for (let i = 0; i < n; i++) out.push(a + (b - a) * i / Math.max(1, n - 1)); return out; } function renderCameraTrackDemo() { const el = document.getElementById('cv-ch16-camera-track-demo'); if (!el || typeof Plotly === 'undefined') return; const cams = [ [-3.0, 0.0, 0.0], [-1.5, 0.2, 0.2], [0.0, 0.0, 0.0], [1.5, -0.1, 0.1], [3.0, 0.0, 0.0] ]; const pts = [ [-1.2, 1.0, 4.0], [-0.2, -0.8, 4.7], [0.9, 0.6, 5.1], [1.4, -0.4, 3.8] ]; const traces = []; traces.push({ x: cams.map(c => c[0]), y: cams.map(c => c[1]), z: cams.map(c => c[2]), mode: 'markers+text', type: 'scatter3d', name: 'cameras', text: cams.map((_, i) => 'C' + (i + 1)), textposition: 'top center', marker: {size: 5, symbol: 'diamond'} }); traces.push({ x: pts.map(p => p[0]), y: pts.map(p => p[1]), z: pts.map(p => p[2]), mode: 'markers+text', type: 'scatter3d', name: '3D points', text: pts.map((_, i) => 'X' + (i + 1)), textposition: 'top center', marker: {size: 4} }); pts.forEach((p, j) => { const visible = j === 0 ? [0, 1, 2] : j === 1 ? [1, 2, 3, 4] : j === 2 ? [0, 2, 3, 4] : [0, 1, 3]; const x = [], y = [], z = []; visible.forEach(i => { x.push(cams[i][0], p[0], null); y.push(cams[i][1], p[1], null); z.push(cams[i][2], p[2], null); }); traces.push({x, y, z, type: 'scatter3d', mode: 'lines', name: 'track rays X' + (j + 1), showlegend: j === 0}); }); Plotly.newPlot(el, traces, { title: 'Sparse SfM: cameras, points, and feature tracks', margin: {t: 55, r: 10, b: 10, l: 10}, scene: {xaxis: {title: 'X'}, yaxis: {title: 'Y'}, zaxis: {title: 'Z'}, camera: {eye: {x: 1.5, y: -1.7, z: 1.1}}}, legend: {orientation: 'h', y: -0.05} }, {responsive: true, displaylogo: false}); } function renderViewGraphDemo() { const el = document.getElementById('cv-ch16-view-graph-demo'); if (!el || typeof Plotly === 'undefined') return; const n = 8; const angles = linspace(0, 2 * Math.PI * (1 - 1/n), n); const xs = angles.map(a => Math.cos(a)); const ys = angles.map(a => Math.sin(a)); const edges = [[0,1,80],[1,2,120],[2,3,60],[3,4,95],[4,5,110],[5,6,45],[6,7,70],[7,0,30],[0,2,40],[2,5,25],[1,6,15]]; const ex = [], ey = []; edges.forEach(e => { ex.push(xs[e[0]], xs[e[1]], null); ey.push(ys[e[0]], ys[e[1]], null); }); const midx = edges.map(e => (xs[e[0]] + xs[e[1]])/2); const midy = edges.map(e => (ys[e[0]] + ys[e[1]])/2); const weights = edges.map(e => e[2]); Plotly.newPlot(el, [ {x: ex, y: ey, mode: 'lines', name: 'verified image-pair edges'}, {x: xs, y: ys, mode: 'markers+text', text: xs.map((_, i) => 'I' + (i + 1)), textposition: 'top center', name: 'images', marker: {size: 14}}, {x: midx, y: midy, mode: 'markers', name: 'edge strength', marker: {size: weights.map(w => 4 + w/12), opacity: 0.6}, text: weights.map(w => w + ' inliers')} ], { title: 'View graph: images connected by verified pairwise geometry', margin: {t: 55, r: 20, b: 40, l: 40}, xaxis: {visible: false}, yaxis: {visible: false, scaleanchor: 'x'}, showlegend: true, legend: {orientation: 'h', y: -0.12} }, {responsive: true, displaylogo: false}); } function renderIncrementalDemo() { const el = document.getElementById('cv-ch16-incremental-demo'); if (!el || typeof Plotly === 'undefined') return; const cams = [[-3,0],[-2,0.4],[-1,0.1],[0,0.35],[1,-0.1],[2,0.3],[3,0]]; const pts = [[-2.5,2.8],[-1.6,3.4],[-0.8,2.6],[0.3,3.1],[1.2,2.7],[2.2,3.3],[-0.2,3.7]]; const frames = []; const steps = []; for (let k = 1; k <= cams.length; k++) { const cNow = cams.slice(0,k); const pNow = pts.slice(0, Math.min(pts.length, Math.max(1, k))); const raysX = [], raysY = []; cNow.forEach(c => { pNow.forEach(p => { if (Math.abs(c[0]-p[0]) < 2.4) { raysX.push(c[0], p[0], null); raysY.push(c[1], p[1], null); } }); }); frames.push({name: String(k), data: [ {x: raysX, y: raysY, mode: 'lines', name: 'observations'}, {x: cNow.map(c => c[0]), y: cNow.map(c => c[1]), mode: 'markers+text', text: cNow.map((_, i) => 'C' + (i+1)), textposition: 'bottom center', name: 'added cameras'}, {x: pNow.map(p => p[0]), y: pNow.map(p => p[1]), mode: 'markers', name: 'triangulated points'} ]}); steps.push({label: String(k), method: 'animate', args: [[String(k)], {mode: 'immediate', frame: {duration: 350, redraw: true}, transition: {duration: 200}}]}); } Plotly.newPlot(el, frames[0].data, { title: 'Incremental SfM grows cameras and sparse points', margin: {t: 55, r: 20, b: 65, l: 45}, xaxis: {title: 'schematic horizontal position', range: [-3.5, 3.5]}, yaxis: {title: 'schematic depth', range: [-0.6, 4.1]}, sliders: [{active: 0, currentvalue: {prefix: 'number of cameras: '}, steps}], legend: {orientation: 'h', y: -0.22} }, {responsive: true, displaylogo: false}).then(() => Plotly.addFrames(el, frames)); } function renderReprojectionDemo() { const el = document.getElementById('cv-ch16-reprojection-demo'); if (!el || typeof Plotly === 'undefined') return; const xs = linspace(-1.5, 1.5, 70); const ys = linspace(-1.5, 1.5, 70); const z = ys.map(y => xs.map(x => { return Math.pow(x - 0.3, 2) + 0.55 * Math.pow(y + 0.15, 2) + 0.25 * Math.pow(x + y, 2) + 0.12 * Math.sin(4*x) * Math.sin(3*y); })); Plotly.newPlot(el, [{x: xs, y: ys, z: z, type: 'contour', contours: {coloring: 'heatmap'}, colorbar: {title: 'error'}}], { title: 'Schematic reprojection-error landscape', margin: {t: 55, r: 20, b: 50, l: 55}, xaxis: {title: 'camera parameter perturbation'}, yaxis: {title: 'point parameter perturbation'} }, {responsive: true, displaylogo: false}); } function renderAveragingDemo() { const el = document.getElementById('cv-ch16-averaging-demo'); if (!el || typeof Plotly === 'undefined') return; const trueX = [-3,-2,-1,0,1,2,3]; const trueY = [0,0.2,0.15,0.35,0.1,0.25,0.05]; const noisyX = trueX.map((x,i) => x + 0.18*Math.sin(1.7*i)); const noisyY = trueY.map((y,i) => y + 0.25*Math.cos(1.3*i)); const smoothY = trueY.map((y,i) => y + 0.05*Math.cos(i)); Plotly.newPlot(el, [ {x: trueX, y: trueY, mode: 'lines+markers', name: 'unknown true camera path'}, {x: noisyX, y: noisyY, mode: 'markers', name: 'pairwise chaining estimate'}, {x: trueX, y: smoothY, mode: 'lines+markers', name: 'global averaged estimate'} ], { title: 'Global averaging reduces inconsistent pairwise motion noise', margin: {t: 55, r: 20, b: 45, l: 55}, xaxis: {title: 'trajectory coordinate'}, yaxis: {title: 'lateral coordinate'}, legend: {orientation: 'h', y: -0.18} }, {responsive: true, displaylogo: false}); } function renderFactorizationDemo() { const el = document.getElementById('cv-ch16-factorization-demo'); if (!el || typeof Plotly === 'undefined') return; const k = Array.from({length: 12}, (_, i) => i + 1); const clean = k.map(i => i <= 3 ? [9.5, 4.5, 2.2][i-1] : 0.0); const noisy = k.map(i => i <= 3 ? clean[i-1] + 0.2 : 0.35 * Math.exp(-(i-4)/4)); Plotly.newPlot(el, [ {x: k, y: clean, mode: 'markers+lines', name: 'ideal rank-3 affine SfM'}, {x: k, y: noisy, mode: 'markers+lines', name: 'with image noise'} ], { title: 'Singular values of an affine SfM measurement matrix', margin: {t: 55, r: 20, b: 45, l: 55}, xaxis: {title: 'singular value index'}, yaxis: {title: 'singular value'}, legend: {orientation: 'h', y: -0.18} }, {responsive: true, displaylogo: false}); } function renderConditioningDemo() { const el = document.getElementById('cv-ch16-conditioning-demo'); if (!el || typeof Plotly === 'undefined') return; const baseline = linspace(0.05, 2.0, 100); const z = 5.0; const f = 800.0; const sigma = 0.7; const uncertainty = baseline.map(b => (z*z/(f*b))*sigma); Plotly.newPlot(el, [ {x: baseline, y: uncertainty, mode: 'lines', name: 'depth uncertainty'} ], { title: 'Depth uncertainty decreases as baseline increases', margin: {t: 55, r: 20, b: 45, l: 55}, xaxis: {title: 'baseline'}, yaxis: {title: 'approximate depth standard deviation'}, annotations: [{x: 0.35, y: uncertainty[15], text: 'small baseline: ill-conditioned', showarrow: true, arrowhead: 2}] }, {responsive: true, displaylogo: false}); } ready(function() { renderCameraTrackDemo(); renderViewGraphDemo(); renderIncrementalDemo(); renderReprojectionDemo(); renderAveragingDemo(); renderFactorizationDemo(); renderConditioningDemo(); }); })(); </script>