Journey of Curiosity Arshad Kazi
← 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

Syllabus

20 of 38 topics written up

  1. 1 Features 6/9
  2. 2 Matching 2/4
  3. 3 Two-view geometry 8/9
  4. 4 Triangulation 4/4
  5. 6 Bundle adjustment 0/4
    • Reprojection error as the objective
    • Levenberg–Marquardt
    • Sparsity and the Schur complement
    • Robust losses
  6. 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.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}$$
  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$$
  3. 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}$$
  4. 1.3 · Finding the keypoint: the maximum among the 26
    $$\hat{\mathbf{x}} = -H^{-1}\nabla D$$
  5. 1.4 · Filtering keypoints based on edges and corners
    $$H = \begin{bmatrix} D_{xx} & D_{xy} \\ D_{xy} & D_{yy} \end{bmatrix}$$
  6. 1.4 · Filtering keypoints based on edges and corners
    $$\frac{\operatorname{Tr}(H)^2}{\det(H)} < \frac{(r+1)^2}{r}$$
  7. 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}$$
  8. 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)$$
  9. 1.6 · Computing the descriptor
    $$8 \text{ bins per region} \times 16 \text{ regions} = 128$$
  10. 1.7 · Matching
    $$d(d_A, d_B) = \sqrt{\sum_{i=1}^{128} \left(d_{A,i} - d_{B,i}\right)^2}$$
  11. 1.7 · Matching
    $$\frac{d_1}{d_2} < 0.8$$
  12. 1.7 · Matching
    $$N = \frac{\log(1-p)}{\log(1-w^n)}$$
  13. 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$$
  14. 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}$$
  15. 2.2 · The linear algebra you need
    $$c \cdot (a \times b) = 0 \quad\Longleftrightarrow\quad a,\ b,\ c \text{ lie in one plane}$$
  16. 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$$
  17. 2.4 · Two cameras, and the running example
    $$P' = R\,P + t, \qquad R = I,\quad t = (-1, 0, 0)$$
  18. 2.5 · The triangle: the core idea
    $$P' \cdot (t \times R P) = 0$$
  19. 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}$$
  20. 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$$
  21. 2.7 · Removing the unknown depth
    $$\boxed{E = [t]_\times R} \qquad\qquad \boxed{x'^\top E\, x = 0}$$
  22. 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$$
  23. 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}$$
  24. 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}$$
  25. 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$$
  26. 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$$
  27. 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$$
  28. 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$$
  29. 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}$$
  30. 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$$
  31. 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}$$
  32. 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$$
  33. 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$$
  34. 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}}$$
  35. 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)$$
  36. 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$$
  37. 3.9 · Taking E apart
    $$R \in \{\, U W V^\top,\; U W^\top V^\top \,\}, \qquad t \in \{\, +u_3,\; -u_3 \,\}$$
  38. 3.11 · Two rays that should meet
    $$s\,d_1 = C_2 + u\,d_2, \qquad C_2 = -R^\top t$$
  39. 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$$
  40. 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}$$
  41. 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$$
  42. 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$$
  43. 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)$$
  44. 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

#

Open

Questions the notes haven't answered yet

  1. Why $\sigma = 1.6$ and 3 levels per octave? What does the repeatability curve look like? day 1
  2. Why does doubling the input image give almost four times as many stable keypoints? day 1
  3. Where does the 0.2 clipping value come from? day 1
  4. Why does RootSIFT (Hellinger kernel) match better than plain SIFT? day 1
  5. How do you choose the RANSAC inlier threshold, and what goes wrong fitting $F$ to a nearly flat scene? day 1
  6. How is the 8-point algorithm derived, and why does it need normalised coordinates? day 1
  7. How do affine-invariant variants handle the large viewpoint changes SIFT can't? day 1
  8. What do learned features (SuperPoint, LightGlue) learn that these hand-made steps miss, and where does SIFT still win? day 1
  9. How exactly is $F$ solved from 8 matches, and why does the SVD give the answer? day 2
  10. Why does normalising the coordinates rescue the eight-point algorithm? What goes wrong without it? day 2
  11. How is the inlier threshold chosen, and how does it depend on image size and SIFT's localisation error? day 2
  12. What goes wrong when the scene is nearly flat, or the camera only rotates, and $F$ isn't defined properly? day 2
  13. How do you get $R$ and $t$ back out of $E$, and how do you choose between its four possible answers? day 2
  14. How does the five-point algorithm work, and is it worth it over eight-point inside RANSAC? day 2
  15. How does triangulation turn a match plus $R$ and $t$ into a 3D point when the rays don't quite meet? day 2
  16. How much better is the five-point algorithm than eight-point inside RANSAC in practice, on real photos? day 3
  17. How do you tell automatically whether a pair is too flat, or too close to pure rotation, to trust its $F$? day 3
  18. How does Nistér's five-point solver reduce to a tenth-degree polynomial? day 3
  19. How do you add a third camera when its position isn't known yet (PnP)? day 3
  20. With only $|t| = 1$ known, how do three or more views get a consistent scale? day 3
  21. How does lens distortion change all of this, and when must it be removed first? day 3