Triangulate 3D Point from Two Views

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

Example:

Constraints:

Test Results