📘

Triangulate 3D Point from Two Views

HardMultiple Cameras 📚 Computer Vision 1

Given two camera projection matrices $P_1$ (3x4) and $P_2$ (3x4), and corresponding 2D points $\mathbf{x}_1 = [u_1, v_1]$ and $\mathbf{x}_2 = [u_2, v_2]$ in each image, triangulate the 3D point $\mathbf{X} = [X, Y, Z]$ using the Direct Linear Transform (DLT) method.

Algorithm (DLT Triangulation):

For each 2D point $\mathbf{x} = [u, v]$ and its projection matrix $P$ , we have: $\mathbf{x} \times (P \cdot \mathbf{X}) = 0$

This gives us a system of linear equations. From each view, we extract two independent equations:

$u_i \cdot P_i^{3T} - P_i^{1T} = 0$ $v_i \cdot P_i^{3T} - P_i^{2T} = 0$

where $P_i^{jT}$ is the $j$ -th row of $P_i$ .

Build the $4 \times 4$ matrix $A$ :

$A = \begin{pmatrix} u_1 P_1^{3T} - P_1^{1T} \\ v_1 P_1^{3T} - P_1^{2T} \\ u_2 P_2^{3T} - P_2^{1T} \\ v_2 P_2^{3T} - P_2^{2T} \end{pmatrix}$

Solve via SVD of $A$ : the solution is the last column of $V$ (last row of $V^T$ ), converted from homogeneous coordinates.

Round each coordinate to 4 decimal places.

Example:

Input:

P1 = [[1, 0, 0, 0],
      [0, 1, 0, 0],
      [0, 0, 1, 0]]
P2 = [[1, 0, 0, -1],
      [0, 1, 0, 0],
      [0, 0, 1, 0]]
x1 = [0.5, 0.5]
x2 = [0.0, 0.5]

Output:

[1.0, 1.0, 2.0]

Reasoning:

We first construct the $4 \times 4$ matrix $A$ using the given projection matrices $P_1$ , $P_2$ , and the corresponding 2D points $\mathbf{x}_1 = [0.5, 0.5]$ and $\mathbf{x}_2 = [0.0, 0.5]$ .
The matrix $A$ is built by extracting two independent equations from each view: $u_i \cdot P_i^{3T} - P_i^{1T} = 0$ and $v_i \cdot P_i^{3T} - P_i^{2T} = 0$ , resulting in $A = \begin{pmatrix} 0.5 \cdot [0, 0, 1, 0] - [1, 0, 0, 0] \\ 0.5 \cdot [0, 0, 1, 0] - [0, 1, 0, 0] \\ 0.0 \cdot [0, 0, 1, 0] - [1, 0, 0, -1] \\ 0.5 \cdot [0, 0, 1, 0] - [0, 1, 0, 0] \end{pmatrix}$ .
We then solve for the 3D point $\mathbf{X}$ by finding the last column of $V$ (last row of $V^T$ ) via SVD of $A$ , which gives us the solution in homogeneous coordinates.
The final output is obtained by converting the solution from homogeneous coordinates to Euclidean coordinates and rounding each coordinate to 4 decimal places, resulting in $\mathbf{X} = [1.0, 1.0, 2.0]$ .

Constraints:

P1, P2: 3x4 projection matrices as lists of lists
x1, x2: 2D points as [u, v]
Use numpy for SVD
Return: [X, Y, Z] rounded to 4 decimal places
The 3D point is in front of both cameras

More from Computer Vision 1

Semi-Global Matching Cost AggregationHard Compute Depth Map from DisparityMedium Stereo Rectification CheckEasy Oriented BRIEF DescriptorHard Gaussian Scale SpaceMedium

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.