Full search page →

The normalized eight-point algorithm

Optional · supplementary note 1 of 7 for DLCV 11 · 3D Reconstruction: From Multi-View Geometry to NeRF and Gaussian Splatting. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.

Navigate: this page and this track: Navigate: this page and this track

On this page

Supplementary notes · 7

  1. The normalized eight-point algorithm
  2. Linear triangulation (DLT)
  3. Bundle adjustment in code
  4. The plane-induced homography
  5. The multiresolution hash encoding
  6. Why NeuS weights peak on the surface
  7. Projecting a 3D Gaussian: the local affine approximation

Paper guides · 3

  1. NeRF (Mildenhall et al., 2020)
  2. 3D Gaussian Splatting (Kerbl et al., 2023)
  3. Guide to the Modern view surveys

Deep Learning for Computer Vision

  1. 02 · Deep Image Classification
View the whole course tree →

This note explains how to estimate the fundamental matrix linearly from eight or more matches, and why rescaling the pixel coordinates first is essential.

The linear system. Write FF as a vector f=(F11,F12,…,F33)\mathbf{f} = (F_{11}, F_{12}, \dots, F_{33}). A match x1=(u1,v1,1)\mathbf{x}_1 = (u_1, v_1, 1), x2=(u2,v2,1)\mathbf{x}_2 = (u_2, v_2, 1) satisfies x2⊤Fx1=0\mathbf{x}_2^\top F \mathbf{x}_1 = 0, which is one linear equation a⊤f=0\mathbf{a}^\top \mathbf{f} = 0 with a=x2⊗x1\mathbf{a} = \mathbf{x}_2 \otimes \mathbf{x}_1 (all nine products u2u1,u2v1,u2,v2u1,…,1u_2 u_1, u_2 v_1, u_2, v_2 u_1, \dots, 1). Stacking n≥8n \ge 8 matches gives Af=0A\mathbf{f} = \mathbf{0} with A∈Rn×9A \in \mathbb{R}^{n \times 9}. The least-squares solution with ∥f∥=1\lVert \mathbf{f} \rVert = 1 is the right singular vector of AA for its smallest singular value [7], [8].

The rank-2 step. A true fundamental matrix has rank 2 (all epipolar lines pass through one point, the epipole). The linear solution usually has rank 3. Replace it by the closest rank-2 matrix in the Frobenius norm: compute F=U diag(σ1,σ2,σ3)V⊤F = U \,\mathrm{diag}(\sigma_1, \sigma_2, \sigma_3) V^\top and set σ3=0\sigma_3 = 0 [8]. For an essential matrix the two non-zero singular values must also be equal, which is why the main-text code uses diag(1,1,0)\mathrm{diag}(1, 1, 0).

Why normalize. In pixel coordinates the entries of a\mathbf{a} range from about 1 to about 10510^5 (u2u1u_2 u_1 for pixels in the hundreds). The matrix A⊤AA^\top A is then badly conditioned (see condition number in ML 01c), and noise is amplified in the small singular vector. Hartley [8] showed that a simple fix makes the linear algorithm competitive: translate each image’s points so that their centroid is at the origin and scale them so that their mean distance from the origin is 2\sqrt{2}, with a similarity T1T_1 for image 1 and T2T_2 for image 2. Solve for F^\hat{F} in the normalized coordinates, enforce rank 2, then undo the normalization with F=T2⊤F^ T1F = T_2^\top \hat{F}\, T_1.

A test. The snippet compares both versions on noisy matches (1 px noise) and measures the Sampson error, a first-order approximation of the geometric distance of a match to the epipolar constraint [1], on 1,000 fresh noise-free matches.

Code · Python · 45 lines
import numpy as np

rng = np.random.default_rng(1)
K = np.array([[800.0, 0, 320], [0, 800.0, 240], [0, 0, 1]])
a = np.deg2rad(12)
R = np.array([[np.cos(a), 0, -np.sin(a)], [0, 1, 0], [np.sin(a), 0, np.cos(a)]])  # camera 2 rotation
t = np.array([-1.0, 0.1, 0.1])                                                      # camera 2 translation
X = rng.uniform([-3, -2, 4], [3, 2, 8], (100, 3))
proj = lambda P: (P @ K.T)[:, :2] / (P @ K.T)[:, 2:]
x1 = proj(X) + rng.normal(0, 1.0, (100, 2))           # 1 px noise
x2 = proj(X @ R.T + t) + rng.normal(0, 1.0, (100, 2))

def eight_point(x1, x2, normalize=True):
    """Fundamental matrix from >= 8 matches (pixels); x2h^T F x1h = 0."""
    def T_of(x):                                      # move centroid to 0, mean distance to sqrt(2)
        c = x.mean(0); s = np.sqrt(2) / np.linalg.norm(x - c, axis=1).mean()
        return np.array([[s, 0, -s * c[0]], [0, s, -s * c[1]], [0, 0, 1]])
    T1, T2 = (T_of(x1), T_of(x2)) if normalize else (np.eye(3), np.eye(3))
    a = np.c_[x1, np.ones(len(x1))] @ T1.T
    b = np.c_[x2, np.ones(len(x2))] @ T2.T
    A = np.einsum('ni,nj->nij', b, a).reshape(-1, 9)
    F = np.linalg.svd(A)[2][-1].reshape(3, 3)
    U, S, Vt = np.linalg.svd(F)
    F = U @ np.diag([S[0], S[1], 0.0]) @ Vt           # enforce rank 2
    F = T2.T @ F @ T1                                 # undo the normalization
    return F / np.linalg.norm(F)

def sampson(F, x1, x2):
    """First-order geometric distance of each match to the epipolar constraint (pixels)."""
    a, b = np.c_[x1, np.ones(len(x1))], np.c_[x2, np.ones(len(x2))]
    Fa, Ftb = a @ F.T, b @ F
    num = np.sum(b * Fa, axis=1) ** 2
    return np.sqrt(num / (Fa[:, 0] ** 2 + Fa[:, 1] ** 2 + Ftb[:, 0] ** 2 + Ftb[:, 1] ** 2))

tx = np.array([[0, -t[2], t[1]], [t[2], 0, -t[0]], [-t[1], t[0], 0]])
F_true = np.linalg.inv(K).T @ tx @ R @ np.linalg.inv(K)       # F = K^-T [t]x R K^-1
F_true /= np.linalg.norm(F_true)
X_test = rng.uniform([-3, -2, 4], [3, 2, 8], (1000, 3))       # fresh, noise-free test matches
y1, y2 = proj(X_test), proj(X_test @ R.T + t)
for n in [8, 15, 100]:
    for norm in [False, True]:
        F = eight_point(x1[:n], x2[:n], norm)
        print(f"{n:3d} matches, normalized={str(norm):5s}: mean Sampson error on test matches "
              f"{sampson(F, y1, y2).mean():8.3f} px")
print(f"true F on the same test matches: {sampson(F_true, y1, y2).mean():.2e} px")

Output

  8 matches, normalized=False: mean Sampson error on test matches    3.186 px
  8 matches, normalized=True : mean Sampson error on test matches    3.016 px
 15 matches, normalized=False: mean Sampson error on test matches    6.091 px
 15 matches, normalized=True : mean Sampson error on test matches    1.083 px
100 matches, normalized=False: mean Sampson error on test matches    0.632 px
100 matches, normalized=True : mean Sampson error on test matches    0.181 px
true F on the same test matches: 2.34e-14 px

With 15 or 100 matches the normalized version is several times more accurate in this run; with the minimum of 8 noisy matches both are poor, which is one reason RANSAC samples are followed by a refit on all inliers. Pitfalls: the normalization must be computed per image, the rank-2 step must happen before denormalization, and degenerate configurations (all points on one plane, or no translation between the cameras) leave FF undetermined whatever the algorithm.

References

  1. R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed., Cambridge University Press, 2004. doi
  2. J. L. Schönberger and J.-M. Frahm, “Structure-from-motion revisited,” in Proc. IEEE CVPR, 2016. CVF
  3. J. L. Schönberger, E. Zheng, J.-M. Frahm and M. Pollefeys, “Pixelwise view selection for unstructured multi-view stereo,” in Proc. ECCV, 2016. doi
  4. J. L. Schönberger et al., “COLMAP,” official documentation (general-purpose structure-from-motion and multi-view stereo pipeline). link
  5. B. Mildenhall, P. P. Srinivasan, M. Tancik, J. T. Barron, R. Ramamoorthi and R. Ng, “NeRF: Representing scenes as neural radiance fields for view synthesis,” in Proc. ECCV, 2020; also Communications of the ACM, vol. 65, no. 1, pp. 99–106, 2022. doi · CACM doi · arXiv
  6. B. Kerbl, G. Kopanas, T. Leimkühler and G. Drettakis, “3D Gaussian Splatting for real-time radiance field rendering,” ACM Transactions on Graphics, vol. 42, no. 4, 2023. doi · arXiv
  7. H. C. Longuet-Higgins, “A computer algorithm for reconstructing a scene from two projections,” Nature, vol. 293, pp. 133–135, 1981. doi
  8. R. I. Hartley, “In defense of the eight-point algorithm,” IEEE TPAMI, vol. 19, no. 6, pp. 580–593, 1997. doi
  9. D. Nistér, “An efficient solution to the five-point relative pose problem,” IEEE TPAMI, vol. 26, no. 6, pp. 756–770, 2004. doi
  10. M. A. Fischler and R. C. Bolles, “Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography,” Communications of the ACM, vol. 24, no. 6, pp. 381–395, 1981. doi
  11. D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, vol. 60, no. 2, pp. 91–110, 2004. doi
  12. N. Snavely, S. M. Seitz and R. Szeliski, “Photo tourism: Exploring photo collections in 3D,” ACM Transactions on Graphics, vol. 25, no. 3, pp. 835–846, 2006. doi
  13. B. Triggs, P. F. McLauchlan, R. I. Hartley and A. W. Fitzgibbon, “Bundle adjustment — A modern synthesis,” in Vision Algorithms: Theory and Practice, LNCS 1883, pp. 298–372, Springer, 2000. doi
  14. R. T. Collins, “A space-sweep approach to true multi-image matching,” in Proc. IEEE CVPR, pp. 358–363, 1996. doi
  15. B. Curless and M. Levoy, “A volumetric method for building complex models from range images,” in Proc. SIGGRAPH, pp. 303–312, 1996. doi
  16. Y. Yao, Z. Luo, S. Li, T. Fang and L. Quan, “MVSNet: Depth inference for unstructured multi-view stereo,” in Proc. ECCV, 2018. CVF · doi
  17. N. Max, “Optical models for direct volume rendering,” IEEE Transactions on Visualization and Computer Graphics, vol. 1, no. 2, pp. 99–108, 1995. doi
  18. M. Tancik, P. P. Srinivasan, B. Mildenhall, S. Fridovich-Keil, N. Raghavan, U. Singhal, R. Ramamoorthi, J. T. Barron and R. Ng, “Fourier features let networks learn high frequency functions in low dimensional domains,” in Proc. NeurIPS, 2020. proceedings
  19. T. Müller, A. Evans, C. Schied and A. Keller, “Instant neural graphics primitives with a multiresolution hash encoding,” ACM Transactions on Graphics, vol. 41, no. 4, 2022. doi · arXiv
  20. J. J. Park, P. Florence, J. Straub, R. Newcombe and S. Lovegrove, “DeepSDF: Learning continuous signed distance functions for shape representation,” in Proc. IEEE/CVF CVPR, 2019. CVF
  21. L. Mescheder, M. Oechsle, M. Niemeyer, S. Nowozin and A. Geiger, “Occupancy networks: Learning 3D reconstruction in function space,” in Proc. IEEE/CVF CVPR, 2019. CVF
  22. P. Wang, L. Liu, Y. Liu, C. Theobalt, T. Komura and W. Wang, “NeuS: Learning neural implicit surfaces by volume rendering for multi-view reconstruction,” in Proc. NeurIPS, 2021. proceedings · arXiv
  23. M. Zwicker, H. Pfister, J. van Baar and M. Gross, “EWA volume splatting,” in Proc. IEEE Visualization, 2001. doi
  24. W. E. Lorensen and H. E. Cline, “Marching cubes: A high resolution 3D surface construction algorithm,” in Proc. SIGGRAPH, pp. 163–169, 1987. doi
  25. M. Kazhdan, M. Bolitho and H. Hoppe, “Poisson surface reconstruction,” in Proc. Eurographics Symposium on Geometry Processing, 2006. doi
  26. M. Kazhdan and H. Hoppe, “Screened Poisson surface reconstruction,” ACM Transactions on Graphics, vol. 32, no. 3, 2013. doi
  27. A. Guédon and V. Lepetit, “SuGaR: Surface-aligned Gaussian splatting for efficient 3D mesh reconstruction and high-quality mesh rendering,” in Proc. IEEE/CVF CVPR, 2024. CVF · arXiv
  28. B. Huang, Z. Yu, A. Chen, A. Geiger and S. Gao, “2D Gaussian splatting for geometrically accurate radiance fields,” in Proc. SIGGRAPH (Conference Papers), 2024. doi · arXiv
  29. S. Wang, V. Leroy, Y. Cabon, B. Chidlovskii and J. Revaud, “DUSt3R: Geometric 3D vision made easy,” in Proc. IEEE/CVF CVPR, 2024. CVF · arXiv
  30. V. Leroy, Y. Cabon and J. Revaud, “Grounding image matching in 3D with MASt3R,” in Proc. ECCV, 2024. doi · arXiv
  31. J. Wang, M. Chen, N. Karaev, A. Vedaldi, C. Rupprecht and D. Novotny, “VGGT: Visual geometry grounded transformer,” in Proc. IEEE/CVF CVPR, 2025. CVF · arXiv
  32. A. Pumarola, E. Corona, G. Pons-Moll and F. Moreno-Noguer, “D-NeRF: Neural radiance fields for dynamic scenes,” in Proc. IEEE/CVF CVPR, 2021. CVF
  33. G. Wu, T. Yi, J. Fang, L. Xie, X. Zhang, W. Wei, W. Liu, Q. Tian and X. Wang, “4D Gaussian splatting for real-time dynamic scene rendering,” in Proc. IEEE/CVF CVPR, 2024. CVF · arXiv
  34. Z. Wang, A. C. Bovik, H. R. Sheikh and E. P. Simoncelli, “Image quality assessment: From error visibility to structural similarity,” IEEE Transactions on Image Processing, vol. 13, no. 4, pp. 600–612, 2004. doi
  35. R. Zhang, P. Isola, A. A. Efros, E. Shechtman and O. Wang, “The unreasonable effectiveness of deep features as a perceptual metric,” in Proc. IEEE/CVF CVPR, 2018. CVF
  36. H. Fan, H. Su and L. J. Guibas, “A point set generation network for 3D object reconstruction from a single image,” in Proc. IEEE CVPR, 2017. CVF
  37. R. Jensen, A. Dahl, G. Vogiatzis, E. Tola and H. Aanæs, “Large scale multi-view stereopsis evaluation,” in Proc. IEEE CVPR, pp. 406–413, 2014. doi
  38. A. Knapitsch, J. Park, Q.-Y. Zhou and V. Koltun, “Tanks and Temples: Benchmarking large-scale scene reconstruction,” ACM Transactions on Graphics, vol. 36, no. 4, 2017. doi · benchmark
  39. J. T. Barron, B. Mildenhall, D. Verbin, P. P. Srinivasan and P. Hedman, “Mip-NeRF 360: Unbounded anti-aliased neural radiance fields,” in Proc. IEEE/CVF CVPR, 2022. CVF · arXiv
  40. D. Verbin, P. Hedman, B. Mildenhall, T. Zickler, J. T. Barron and P. P. Srinivasan, “Ref-NeRF: Structured view-dependent appearance for neural radiance fields,” in Proc. IEEE/CVF CVPR, 2022. CVF
  41. C.-H. Lin, W.-C. Ma, A. Torralba and S. Lucey, “BARF: Bundle-adjusting neural radiance fields,” in Proc. IEEE/CVF ICCV, 2021. CVF
  42. S. M. Seitz, B. Curless, J. Diebel, D. Scharstein and R. Szeliski, “A comparison and evaluation of multi-view stereo reconstruction algorithms,” in Proc. IEEE CVPR, vol. 1, pp. 519–528, 2006. doi
  43. Y. Furukawa and C. Hernández, “Multi-view stereo: A tutorial,” Foundations and Trends in Computer Graphics and Vision, vol. 9, no. 1–2, pp. 1–148, 2015. doi
  44. A. Tewari, J. Thies, B. Mildenhall, P. Srinivasan, E. Tretschk, W. Yifan, C. Lassner, V. Sitzmann et al., “Advances in neural rendering,” Computer Graphics Forum, vol. 41, no. 2, pp. 703–735, 2022. doi · arXiv
  45. G. Chen and W. Wang, “A survey on 3D Gaussian splatting,” ACM Computing Surveys, vol. 58, no. 12, 2026. doi · arXiv
  46. scikit-image contributors, “skimage.measure.marching_cubes,” scikit-image documentation (API reference). docs
  47. A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai et al., “An image is worth 16x16 words: Transformers for image recognition at scale,” in Proc. ICLR, 2021. arXiv
  48. A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser and I. Polosukhin, “Attention is all you need,” in Proc. NeurIPS, 2017. proceedings
  49. D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in Proc. ICLR, 2015. arXiv