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
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 and let be the -th row of the projection matrix of camera . The pinhole model says , so the depth is . Substituting it into the first two rows removes the unknown depth and leaves two linear equations per image:
where is the observed pixel in image and is a matrix. This is the direct linear transformation (DLT) method [1]. With noise, has no exact null vector. The unit vector that minimizes is the right singular vector of for its smallest singular value; dividing it by its last entry gives the Euclidean point. Each additional view adds two more rows to and nothing else changes.
Why it is not optimal. The quantity minimized, , 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 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, 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 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 of the main text; the disparity error, a difference of two independent 0.5 px errors, has standard deviation 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-13The 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
- 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