Full search page →

Linear triangulation (DLT)

Optional · supplementary note 2 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 writes out the linear triangulation used in the main text, explains why its answer is not the optimal one, and measures how the baseline controls its error.

The equations. Write the unknown point in homogeneous form X~=(X,Y,Z,1)⊤\tilde{\mathbf{X}} = (X, Y, Z, 1)^\top and let pik⊤\mathbf{p}_i^{k\top} be the kk-th row of the projection matrix PiP_i of camera ii. The pinhole model says λi(ui,vi,1)⊤=PiX~\lambda_i (u_i, v_i, 1)^\top = P_i \tilde{\mathbf{X}}, so the depth is λi=pi3⊤X~\lambda_i = \mathbf{p}_i^{3\top} \tilde{\mathbf{X}}. Substituting it into the first two rows removes the unknown depth and leaves two linear equations per image:

AX~=0,A=[u1p13⊤−p11⊤v1p13⊤−p12⊤u2p23⊤−p21⊤v2p23⊤−p22⊤],A \tilde{\mathbf{X}} = \mathbf{0}, \qquad A = \begin{bmatrix} u_1 \mathbf{p}_1^{3\top} - \mathbf{p}_1^{1\top} \\ v_1 \mathbf{p}_1^{3\top} - \mathbf{p}_1^{2\top} \\ u_2 \mathbf{p}_2^{3\top} - \mathbf{p}_2^{1\top} \\ v_2 \mathbf{p}_2^{3\top} - \mathbf{p}_2^{2\top} \end{bmatrix},

where (ui,vi)(u_i, v_i) is the observed pixel in image ii and AA is a 4×44 \times 4 matrix. This is the direct linear transformation (DLT) method [1]. With noise, AA has no exact null vector. The unit vector that minimizes ∥AX~∥\lVert A \tilde{\mathbf{X}} \rVert is the right singular vector of AA for its smallest singular value; dividing it by its last entry gives the Euclidean point. Each additional view adds two more rows to AA and nothing else changes.

Why it is not optimal. The quantity minimized, ∥AX~∥\lVert A \tilde{\mathbf{X}} \rVert, is an algebraic error: it has no direct meaning in pixels, and it changes if the image coordinates are rescaled. With Gaussian pixel noise, the sensible goal is the reprojection error, the sum of squared pixel distances between the projections of X\mathbf{X} and the observations. Hartley and Zisserman [1] describe methods that minimize it directly. In practice the DLT answer is the starting point, and bundle adjustment then refines all points and cameras together.

Edge cases. (i) When the baseline is short or the point is far away, the two rays are almost parallel, AA is close to rank 2, and the depth becomes very uncertain. (ii) A point at infinity has last homogeneous coordinate 0, so the final division fails; such points must be kept in homogeneous form or removed. (iii) A wrong match can produce a point behind a camera, so after dividing by the last entry, check that the depth pi3⊤X~\mathbf{p}_i^{3\top} \tilde{\mathbf{X}} is positive in every view (the cheirality check of the main text).

A test. The snippet triangulates one point 6 units in front of camera 1, seen by two cameras with 0.5 px noise, for three baselines. It compares the spread of the depth error with the first-order formula δZ≈Z2δd/(fB)\delta Z \approx Z^2 \delta d / (fB) of the main text; the disparity error, a difference of two independent 0.5 px errors, has standard deviation 0.520.5\sqrt{2} px.

Code · Python · 31 lines
import numpy as np
import cv2

rng = np.random.default_rng(0)
K = np.array([[800.0, 0, 320], [0, 800.0, 240], [0, 0, 1]])
X_true = np.array([0.3, -0.2, 6.0])                     # one point, 6 units in front of camera 1

def triangulate_dlt(P1, P2, x1, x2):
    """Linear triangulation: four equations A X = 0 in the homogeneous point X (4-vector)."""
    A = np.stack([x1[0] * P1[2] - P1[0], x1[1] * P1[2] - P1[1],
                  x2[0] * P2[2] - P2[0], x2[1] * P2[2] - P2[1]])
    Xh = np.linalg.svd(A)[2][-1]                         # right singular vector, smallest singular value
    return Xh[:3] / Xh[3]                                # homogeneous -> Euclidean

def proj(P, X):
    x = P @ np.append(X, 1.0)
    return x[:2] / x[2]

P1 = K @ np.hstack([np.eye(3), np.zeros((3, 1))])
for B in [2.0, 0.5, 0.1]:                                # camera 2 sits B to the right, same orientation
    P2 = K @ np.hstack([np.eye(3), [[-B], [0.0], [0.0]]])
    dz = []
    for _ in range(2000):
        x1 = proj(P1, X_true) + rng.normal(0, 0.5, 2)      # 0.5 px noise in each image
        x2 = proj(P2, X_true) + rng.normal(0, 0.5, 2)
        dz.append(triangulate_dlt(P1, P2, x1, x2)[2] - X_true[2])
    predicted = X_true[2] ** 2 * (0.5 * np.sqrt(2)) / (800 * B)   # Z^2 * std(disparity error) / (f B)
    print(f"baseline {B:3.1f}: ray angle {np.degrees(np.arctan2(B, 6)):5.2f} deg | "
          f"depth error std {np.std(dz):.4f} (first-order prediction {predicted:.4f})")
Xcv = cv2.triangulatePoints(P1, P2, x1.reshape(2, 1), x2.reshape(2, 1)).ravel()
print(f"difference from cv2.triangulatePoints: {np.abs(Xcv[:3] / Xcv[3] - triangulate_dlt(P1, P2, x1, x2)).max():.1e}")

Output

baseline 2.0: ray angle 18.43 deg | depth error std 0.0158 (first-order prediction 0.0159)
baseline 0.5: ray angle  4.76 deg | depth error std 0.0617 (first-order prediction 0.0636)
baseline 0.1: ray angle  0.95 deg | depth error std 0.3166 (first-order prediction 0.3182)
difference from cv2.triangulatePoints: 2.0e-13

The measured spread matches the first-order prediction. Shrinking the baseline from 2 to 0.1 units, which makes the angle between the rays smaller than one degree, multiplies the depth error by 20. The last line shows that OpenCV’s cv2.triangulatePoints returns the same point up to rounding.

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