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
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 as a vector . A match , satisfies , which is one linear equation with (all nine products ). Stacking matches gives with . The least-squares solution with is the right singular vector of 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 and set [8]. For an essential matrix the two non-zero singular values must also be equal, which is why the main-text code uses .
Why normalize. In pixel coordinates the entries of range from about 1 to about ( for pixels in the hundreds). The matrix 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 , with a similarity for image 1 and for image 2. Solve for in the normalized coordinates, enforce rank 2, then undo the normalization with .
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 pxWith 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 undetermined whatever the algorithm.
References
- R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed., Cambridge University Press, 2004. doi
- J. L. Schönberger and J.-M. Frahm, “Structure-from-motion revisited,” in Proc. IEEE CVPR, 2016. CVF
- 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
- J. L. Schönberger et al., “COLMAP,” official documentation (general-purpose structure-from-motion and multi-view stereo pipeline). link
- 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
- 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
- H. C. Longuet-Higgins, “A computer algorithm for reconstructing a scene from two projections,” Nature, vol. 293, pp. 133–135, 1981. doi
- R. I. Hartley, “In defense of the eight-point algorithm,” IEEE TPAMI, vol. 19, no. 6, pp. 580–593, 1997. doi
- D. Nistér, “An efficient solution to the five-point relative pose problem,” IEEE TPAMI, vol. 26, no. 6, pp. 756–770, 2004. doi
- 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
- D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, vol. 60, no. 2, pp. 91–110, 2004. doi
- 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
- 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
- R. T. Collins, “A space-sweep approach to true multi-image matching,” in Proc. IEEE CVPR, pp. 358–363, 1996. doi
- B. Curless and M. Levoy, “A volumetric method for building complex models from range images,” in Proc. SIGGRAPH, pp. 303–312, 1996. doi
- 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
- N. Max, “Optical models for direct volume rendering,” IEEE Transactions on Visualization and Computer Graphics, vol. 1, no. 2, pp. 99–108, 1995. doi
- 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
- 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
- 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
- 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
- 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
- M. Zwicker, H. Pfister, J. van Baar and M. Gross, “EWA volume splatting,” in Proc. IEEE Visualization, 2001. doi
- W. E. Lorensen and H. E. Cline, “Marching cubes: A high resolution 3D surface construction algorithm,” in Proc. SIGGRAPH, pp. 163–169, 1987. doi
- M. Kazhdan, M. Bolitho and H. Hoppe, “Poisson surface reconstruction,” in Proc. Eurographics Symposium on Geometry Processing, 2006. doi
- M. Kazhdan and H. Hoppe, “Screened Poisson surface reconstruction,” ACM Transactions on Graphics, vol. 32, no. 3, 2013. doi
- 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
- 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
- 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
- V. Leroy, Y. Cabon and J. Revaud, “Grounding image matching in 3D with MASt3R,” in Proc. ECCV, 2024. doi · arXiv
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- C.-H. Lin, W.-C. Ma, A. Torralba and S. Lucey, “BARF: Bundle-adjusting neural radiance fields,” in Proc. IEEE/CVF ICCV, 2021. CVF
- 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
- 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
- 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
- G. Chen and W. Wang, “A survey on 3D Gaussian splatting,” ACM Computing Surveys, vol. 58, no. 12, 2026. doi · arXiv
- scikit-image contributors, “skimage.measure.marching_cubes,” scikit-image documentation (API reference). docs
- 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
- 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
- D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in Proc. ICLR, 2015. arXiv