Triangulation

Triangulation is based on the principle of intersecting lines of sight. Given a 3D point P, its projection onto the image plane of a camera defines a ray in 3D space originating from the camera's optical center and passing through the image point. With two or more calibrated cameras (known intrinsic and extrinsic parameters), the 3D location of P is found at the intersection of these rays. In practice, due to noise, rays rarely intersect perfectly, so the solution is the 3D point that minimizes the total reprojection error.

A single 3D point requires a minimum of two views for triangulation. This is the core of stereo vision. However, more views significantly improve accuracy and robustness. Key considerations include:

• Baseline: The distance between camera centers. A larger baseline improves depth accuracy but can make feature matching harder.
• Degenerate Configurations: Triangulation fails if the 3D point and the two camera centers are co-linear, as the rays lie on the same line and do not provide a unique intersection.
• Multi-View Triangulation: Systems like Structure from Motion (SfM) use dozens or hundreds of images, using least-squares optimization to find the optimal 3D point that best fits all observations.

Triangulation is fundamentally dependent on correct feature matching. An error in identifying which 2D pixel in Image A corresponds to the same physical point in Image B will cause the triangulated 3D point to be incorrect. This makes outlier rejection critical. Algorithms like RANSAC are often used in conjunction with triangulation to filter mismatched points before computing the final 3D structure. The precision of the 2D pixel locations (sub-pixel accuracy) also directly impacts the accuracy of the resulting 3D coordinate.

Different algorithms solve the triangulation problem, trading off speed and accuracy.

• Linear Triangulation (DLT-based): Solves a linear system using the Direct Linear Transform. It's fast but does not minimize the true geometric reprojection error, making it suboptimal.
• Midpoint Method: Finds the midpoint of the shortest line segment connecting the two rays. A simple, non-iterative approximation.
• Optimal (Non-Linear) Triangulation: Formulates the problem as minimizing the sum of squared reprojection errors. This is solved iteratively (e.g., with Gauss-Newton or Levenberg-Marquardt) and provides the statistically optimal solution under Gaussian noise assumptions. It is the standard in bundle adjustment.

Triangulation is not a standalone process but a core module within larger 3D reconstruction systems.

• In Structure from Motion (SfM), triangulation creates the initial sparse point cloud after camera pose estimation (e.g., via Perspective-n-Point or Essential Matrix decomposition). This sparse cloud is then refined by bundle adjustment.
• In Visual Odometry (VO) and Simultaneous Localization and Mapping (SLAM), triangulation is used to map new landmarks (3D points) as the camera moves. These landmarks are then used for subsequent camera pose estimation, creating a recursive estimation loop. Visual Inertial Odometry (VIO) fuses this with IMU data to fix scale ambiguity.

A critical characteristic of triangulation in monocular (single-camera) sequences is scale ambiguity. When triangulating from images taken by the same moving camera, the computed 3D structure and camera translation are only recovered up to an unknown scaling factor. The absolute scale of the scene cannot be determined from images alone. This is resolved by:

• Introducing an object of known size into the scene.
• Using sensor fusion with an Inertial Measurement Unit (IMU) in VIO.
• Using a stereo camera rig with a known fixed baseline, which provides metric scale inherently.

The geometric relationship between two views of a scene. It defines the epipolar constraint, which states that for a point in one image, its corresponding point in the second image must lie on a specific line called the epipolar line. This constraint is mathematically encoded by the fundamental matrix (for uncalibrated cameras) or the essential matrix (for calibrated cameras). It is the theoretical foundation that makes feature matching and triangulation possible by drastically reducing the search space for correspondences.

The process of establishing correspondences between distinctive keypoints (like SIFT, ORB, or SuperPoint features) detected in two or more overlapping images. This is the critical data input for triangulation.

• Descriptors: High-dimensional vectors representing the visual appearance around a keypoint.
• Matching Algorithms: Use nearest-neighbor search (often with ratio tests) or learned matchers (like SuperGlue) to find pairs.
• Outlier Rejection: Robust estimators like RANSAC are used to filter incorrect matches using geometric constraints from epipolar geometry.

The inverse problem to triangulation. Given a set of n known 3D points and their 2D projections in an image, PnP estimates the camera pose (extrinsics) of that image. This is essential for camera localization and is a core component of Visual Odometry (VO) and SLAM systems. Common algorithms include EPnP and solvePnP (which often uses an iterative method). Once a camera is localized via PnP, it can be used to triangulate new 3D points from matches with other views.

A non-linear optimization that jointly refines all estimated parameters: 3D point positions, camera poses, and often camera intrinsics. It minimizes the total reprojection error across all images. While triangulation provides an initial estimate, bundle adjustment is necessary for accurate, globally consistent results. It corrects for error accumulation and is the final, computationally intensive step in Structure from Motion (SfM) pipelines. Modern implementations use sparse linear algebra (e.g., Schur complement) for efficiency.

The overarching photogrammetry pipeline that uses triangulation as its core mechanism. SfM takes an unordered image collection and automatically reconstructs a sparse 3D point cloud and the camera poses for each image. The standard pipeline is:

1. Feature Detection & Matching across all images.
2. Geometric Verification (e.g., using epipolar geometry) to establish view graphs.
3. Incremental Reconstruction: Starting from a seed pair, triangulate points, use PnP to add new cameras, triangulate more points, and run bundle adjustment.

A linear algorithm used to solve for transformation matrices from point correspondences. In the context of triangulation, the Linear Least-Squares Triangulation method is a direct application of DLT principles. Given the projection matrices for two cameras and a point correspondence, it sets up a system of linear equations (from the cross product x × (PX) = 0) to solve for the 3D point X. While sensitive to noise, it provides a closed-form solution that is often used as an initialization for non-linear refinement.