← Blogs
In progress Since November 3, 2026 3 days · 78 min
Structure from Motion
How do overlapping photos become a 3D model with geometry alone? Working through the classical pipeline one stage at a time: features, matching, two-view geometry, triangulation, structure from motion, bundle adjustment, dense reconstruction.
Coverage
4 of 7 stages covered · next: Structure from motion
Day
1 Features
2 Matching
3 Two-view geometry
4 Triangulation
5 Structure from motion
6 Bundle adjustment
7 Dense reconstruction
01 SIFT: detecting and matching keypoints across images I ScaleII RotationIII DescribeIV Match
02 Epipolar geometry: why a match has to sit on a line I GoalII ToolsIII CameraIV SetupV EpipolarVI AlgebraVII EssentialVIII Lines Fundamental Picture RANSAC Summary
03 From matches to cameras to points: estimating F, taking E apart, triangulating I GoalII Eight-pointIII RANSACIV EssentialV DecomposeVI TriangulationVII Summary
04 Not written yet
Syllabus
20 of 38 topics written up
- 1 Features 6/9
- Gaussian scale space and DoG
- Extrema across space and scale
- Sub-pixel localisation
- Edge rejection with the Hessian
- Orientation assignment
- The SIFT descriptor
- Harris corners and the structure tensor
- Binary features: ORB
- Learned features: SuperPoint
- 2 Matching 2/4
- Nearest neighbours and the ratio test
- RANSAC
- Approximate search: k-d trees, FLANN
- Learned matching: SuperGlue, LightGlue
- 3 Two-view geometry 8/9
- 4 Triangulation 4/4
- 5 Structure from motion 0/4
- Building tracks across many views
- Incremental SfM
- Registering new cameras: PnP
- Global SfM
- 6 Bundle adjustment 0/4
- Reprojection error as the objective
- Levenberg–Marquardt
- Sparsity and the Schur complement
- Robust losses
- 7 Dense reconstruction 0/4
- Plane-sweep stereo
- PatchMatch multi-view stereo
- Depth-map fusion
- Meshing: Poisson reconstruction
Formulas
Every equation so far, in the order it came up
- 1.1 · Creating Gaussian spaces $$L(x, y, \sigma) = G(x, y, \sigma) * I(x, y), \qquad G = \frac{1}{2\pi\sigma^2}\, e^{-(x^2+y^2)/2\sigma^2}$$
- 1.1 · Creating Gaussian spaces $$D(x, y, \sigma) = L(x, y, k\sigma) - L(x, y, \sigma) \;\approx\; (k-1)\,\sigma^2 \nabla^2 G * I$$
- 1.3 · Finding the keypoint: the maximum among the 26 $$D(\mathbf{x}) \approx D + \nabla D^{\top}\mathbf{x} + \tfrac{1}{2}\,\mathbf{x}^{\top} H\,\mathbf{x}$$
- 1.3 · Finding the keypoint: the maximum among the 26 $$\hat{\mathbf{x}} = -H^{-1}\nabla D$$
- 1.4 · Filtering keypoints based on edges and corners $$H = \begin{bmatrix} D_{xx} & D_{xy} \\ D_{xy} & D_{yy} \end{bmatrix}$$
- 1.4 · Filtering keypoints based on edges and corners $$\frac{\operatorname{Tr}(H)^2}{\det(H)} < \frac{(r+1)^2}{r}$$
- 1.4 · Filtering keypoints based on edges and corners $$\frac{(\alpha+\beta)^2}{\alpha\beta} = \frac{(r\beta + \beta)^2}{r\beta^2} = \frac{(r+1)^2}{r}$$
- 1.5 · Handling rotational invariance $$m(x, y) = \sqrt{L_x^2 + L_y^2} \qquad \theta(x, y) = \operatorname{atan2}(L_y, L_x)$$
- 1.6 · Computing the descriptor $$8 \text{ bins per region} \times 16 \text{ regions} = 128$$
- 1.7 · Matching $$d(d_A, d_B) = \sqrt{\sum_{i=1}^{128} \left(d_{A,i} - d_{B,i}\right)^2}$$
- 1.7 · Matching $$\frac{d_1}{d_2} < 0.8$$
- 1.7 · Matching $$N = \frac{\log(1-p)}{\log(1-w^n)}$$
- 2.2 · The linear algebra you need $$a \cdot b = a_x b_x + a_y b_y + a_z b_z = a^\top b$$
- 2.2 · The linear algebra you need $$a \times b = \begin{bmatrix} a_y b_z - a_z b_y \\ a_z b_x - a_x b_z \\ a_x b_y - a_y b_x \end{bmatrix}$$
- 2.2 · The linear algebra you need $$c \cdot (a \times b) = 0 \quad\Longleftrightarrow\quad a,\ b,\ c \text{ lie in one plane}$$
- 2.3 · How a camera turns 3D into 2D $$x = \frac{P}{Z} = \begin{bmatrix} X/Z \\ Y/Z \\ 1 \end{bmatrix} \qquad\Longleftrightarrow\qquad P = Z\,x$$
- 2.4 · Two cameras, and the running example $$P' = R\,P + t, \qquad R = I,\quad t = (-1, 0, 0)$$
- 2.5 · The triangle: the core idea $$P' \cdot (t \times R P) = 0$$
- 2.6 · Turning the cross product into a matrix $$t \times v = \begin{bmatrix} t_y v_z - t_z v_y \\ t_z v_x - t_x v_z \\ t_x v_y - t_y v_x \end{bmatrix} = \underbrace{\begin{bmatrix} 0 & -t_z & t_y \\ t_z & 0 & -t_x \\ -t_y & t_x & 0 \end{bmatrix}}_{[t]_\times} \begin{bmatrix} v_x \\ v_y \\ v_z \end{bmatrix}$$
- 2.7 · Removing the unknown depth $$(Z' x')^\top [t]_\times R\,(Z x) = Z\, Z' \big( x'^\top [t]_\times R\, x \big) = 0$$
- 2.7 · Removing the unknown depth $$\boxed{E = [t]_\times R} \qquad\qquad \boxed{x'^\top E\, x = 0}$$
- 2.9 · From ideal coordinates to real pixels $$K = \begin{bmatrix} f & 0 & c_x \\ 0 & f & c_y \\ 0 & 0 & 1 \end{bmatrix}, \qquad p = K\,x$$
- 2.9 · From ideal coordinates to real pixels $$(K^{-1}p')^\top E\,(K^{-1}p) = p'^\top \underbrace{K^{-\top} E\, K^{-1}}_{F}\, p = 0 \qquad\Longrightarrow\qquad \boxed{p'^\top F\, p = 0}$$
- 3.2 · One match, one equation $$Fp = \begin{bmatrix} F_{11}u + F_{12}v + F_{13} \\ F_{21}u + F_{22}v + F_{23} \\ F_{31}u + F_{32}v + F_{33} \end{bmatrix}$$
- 3.2 · One match, one equation $$p'^\top F p = u'(F_{11}u + F_{12}v + F_{13}) + v'(F_{21}u + F_{22}v + F_{23}) + (F_{31}u + F_{32}v + F_{33}) = 0$$
- 3.2 · One match, one equation $$\underbrace{\begin{bmatrix} u'u & u'v & u' & v'u & v'v & v' & u & v & 1 \end{bmatrix}}_{a^\top \text{, known}} \; \underbrace{\begin{bmatrix} F_{11} \\ F_{12} \\ \vdots \\ F_{33} \end{bmatrix}}_{f \text{, unknown}} = 0$$
- 3.3 · Stack the matches, solve with the SVD $$A = \begin{bmatrix} a_1^\top \\ a_2^\top \\ \vdots \\ a_N^\top \end{bmatrix}, \qquad \min_{|f| = 1} |A f| \quad\Longrightarrow\quad f = \text{last column of } V$$
- 3.4 · Forcing rank 2 $$F = U \begin{bmatrix} \sigma_1 & & \\ & \sigma_2 & \\ & & \sigma_3 \end{bmatrix} V^\top \quad\longrightarrow\quad F_{\text{rank 2}} = U \begin{bmatrix} \sigma_1 & & \\ & \sigma_2 & \\ & & 0 \end{bmatrix} V^\top$$
- 3.5 · Normalise first $$\hat p = T p, \qquad T = \begin{bmatrix} s & 0 & -s\,c_x \\ 0 & s & -s\,c_y \\ 0 & 0 & 1 \end{bmatrix}$$
- 3.5 · Normalise first $$\hat p'^\top \hat F \hat p = 0 \;\Longrightarrow\; (T'p')^\top \hat F\, (Tp) = p'^\top \underbrace{T'^\top \hat F\, T}_{F}\, p = 0$$
- 3.6 · The eight-point algorithm inside RANSAC $$d_{\text{Sampson}}^2 = \frac{(p'^\top F p)^2}{(Fp)_1^2 + (Fp)_2^2 + (F^\top p')_1^2 + (F^\top p')_2^2}$$
- 3.7 · From F back to E $$F = K'^{-\top} E K^{-1} \;\Longrightarrow\; K'^\top F K = K'^\top K'^{-\top}\, E\, K^{-1} K = E$$
- 3.7 · From F back to E $$E = U \begin{bmatrix} \sigma_1 & & \\ & \sigma_2 & \\ & & \sigma_3 \end{bmatrix} V^\top \;\longrightarrow\; U \begin{bmatrix} 1 & & \\ & 1 & \\ & & 0 \end{bmatrix} V^\top$$
- 3.8 · Two facts about the cross-product matrix $$[e_z]_\times = \begin{bmatrix} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} = \underbrace{\begin{bmatrix} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{W,\ \text{turn } 90°}\underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix}}_{\text{flatten}}$$
- 3.8 · Two facts about the cross-product matrix $$[t]_\times = [U e_z]_\times = U\,[e_z]_\times\,U^\top = U\, W\, \text{diag}(1,1,0)\, U^\top \qquad (u_3 = t)$$
- 3.9 · Taking E apart $$E = [t]_\times R = U\, \text{diag}(1,1,0)\, \underbrace{W\, U^\top R}_{V^\top} \quad\Longrightarrow\quad R = U W^\top V^\top$$
- 3.9 · Taking E apart $$R \in \{\, U W V^\top,\; U W^\top V^\top \,\}, \qquad t \in \{\, +u_3,\; -u_3 \,\}$$
- 3.11 · Two rays that should meet $$s\,d_1 = C_2 + u\,d_2, \qquad C_2 = -R^\top t$$
- 3.12 · The midpoint method $$(Q_1 - Q_2)\cdot d_1 = 0, \quad (Q_1 - Q_2)\cdot d_2 = 0, \qquad Q_1 = s\,d_1,\ Q_2 = C_2 + u\,d_2$$
- 3.12 · The midpoint method $$\begin{bmatrix} d_1\cdot d_1 & -d_1\cdot d_2 \\ d_1\cdot d_2 & -d_2\cdot d_2 \end{bmatrix} \begin{bmatrix} s \\ u \end{bmatrix} = \begin{bmatrix} C_2\cdot d_1 \\ C_2\cdot d_2 \end{bmatrix}$$
- 3.13 · Linear triangulation (DLT) $$u = \frac{c^1 \cdot \mathbf X}{c^3 \cdot \mathbf X} \;\Longrightarrow\; u\,(c^3 \cdot \mathbf X) - c^1 \cdot \mathbf X = 0, \qquad v\,(c^3 \cdot \mathbf X) - c^2 \cdot \mathbf X = 0$$
- 3.13 · Linear triangulation (DLT) $$B = \begin{bmatrix} u\,c_1^{3\top} - c_1^{1\top} \\ v\,c_1^{3\top} - c_1^{2\top} \\ u'\,c_2^{3\top} - c_2^{1\top} \\ v'\,c_2^{3\top} - c_2^{2\top} \end{bmatrix}, \qquad B\, \mathbf X = 0$$
- 3.14 · Reprojection error: the honest measure $$\text{err}(X)^2 = \big|\,x - \pi(C_1 \mathbf X)\,\big|^2 + \big|\,x' - \pi(C_2 \mathbf X)\,\big|^2, \qquad \pi(a, b, c) = (a/c,\ b/c)$$
- 3.15 · How accurate is a triangulated point? $$Z = \frac{f b}{d} \quad\Longrightarrow\quad \frac{dZ}{dd} = -\frac{f b}{d^2} = -\frac{Z^2}{f b} \quad\Longrightarrow\quad |\Delta Z| \approx \frac{Z^2}{f b}\, |\Delta d|$$
Index
Everything written, tangents included, A to Z
#
- Why √2? 3
C
E
F
- Two facts about the cross-product matrix 3
- How far off the line, in pixels? 2
- Filtering keypoints based on edges and corners 1
- Finding the keypoint: the maximum among the 26 1
- Forcing rank 2 3
- Four answers, one real 3
- Why the fourth coordinate: points at infinity 3
- From F back to E 3
- From ideal coordinates to real pixels 2
O
P
R
S
- What's inside K, and what F loses 2
- The same rows from a cross product 3
- Seven points are enough, if you use the rank 3
- The shape of $[t]_\times$, and why it matters later 2
- What is SIFT, anyway? 1
- Why two singular values have to be equal 3
- Why the smallest singular direction minimises |Af| 3
- Stack the matches, solve with the SVD 3
T
W
Open
Questions the notes haven't answered yet
- Why $\sigma = 1.6$ and 3 levels per octave? What does the repeatability curve look like? day 1
- Why does doubling the input image give almost four times as many stable keypoints? day 1
- Where does the 0.2 clipping value come from? day 1
- Why does RootSIFT (Hellinger kernel) match better than plain SIFT? day 1
- How do you choose the RANSAC inlier threshold, and what goes wrong fitting $F$ to a nearly flat scene? day 1
- How is the 8-point algorithm derived, and why does it need normalised coordinates? day 1
- How do affine-invariant variants handle the large viewpoint changes SIFT can't? day 1
- What do learned features (SuperPoint, LightGlue) learn that these hand-made steps miss, and where does SIFT still win? day 1
- How exactly is $F$ solved from 8 matches, and why does the SVD give the answer? day 2
- Why does normalising the coordinates rescue the eight-point algorithm? What goes wrong without it? day 2
- How is the inlier threshold chosen, and how does it depend on image size and SIFT's localisation error? day 2
- What goes wrong when the scene is nearly flat, or the camera only rotates, and $F$ isn't defined properly? day 2
- How do you get $R$ and $t$ back out of $E$, and how do you choose between its four possible answers? day 2
- How does the five-point algorithm work, and is it worth it over eight-point inside RANSAC? day 2
- How does triangulation turn a match plus $R$ and $t$ into a 3D point when the rays don't quite meet? day 2
- How much better is the five-point algorithm than eight-point inside RANSAC in practice, on real photos? day 3
- How do you tell automatically whether a pair is too flat, or too close to pure rotation, to trust its $F$? day 3
- How does Nistér's five-point solver reduce to a tenth-degree polynomial? day 3
- How do you add a third camera when its position isn't known yet (PnP)? day 3
- With only $|t| = 1$ known, how do three or more views get a consistent scale? day 3
- How does lens distortion change all of this, and when must it be removed first? day 3