Multi-View Triangulation Error

To solve this problem, you just need to project a 3D point into each camera, compare with the observed 2D point, and sum the squared pixel errors over all views.

---

1. Background Knowledge

In Structure from Motion (SfM), we estimate both camera poses and 3D scene points from multiple 2D images. Each camera view has known intrinsics $K_i$ (focal length, principal point, etc.) and extrinsics $(R_i, t_i)$ describing its position and orientation relative to a world coordinate system. A 3D point $X$ in world coordinates can be projected into image $i$ via the camera projection model.

The reprojection error measures how consistent a 3D point is with its observed 2D measurements. For each view $i$, we project $X$ into the image to get a predicted pixel $\hat{p}_i = ($\hat{u}$_i,$\hat{v}$_i)$, and compare it with the detected feature point $p_i = (u_i, v_i)$. The squared Euclidean distance $\|$\hat{p}$_i - p_i \|^2$ is the per-view error. Summing these over all views gives the total reprojection error, which is the standard objective minimized in bundle adjustment.

---

2. Algorithm / General Approach

The pattern is:

1. For each camera:

• Transform the 3D point from world coordinates into the camera coordinate frame.
• Apply the pinhole projection model with intrinsics $K_i$ to get image coordinates.
• Convert from homogeneous to 2D pixel coordinates.

2. Compute the squared pixel error between predicted and observed 2D points.
3. Accumulate (sum) these squared errors over all views.

This is a straightforward per-view loop with a constant amount of math per view.

---

3. Step-by-Step Strategy

Assume you are given:

• 3D point $X = (X, Y, Z)$ in world coordinates (often as a 3D vector).
• For each view $i$:
• Intrinsic matrix $K_i$ (3×3).
• Rotation $R_i$ (3×3) and translation $t_i$ (3×1).
• Observed pixel $p_i = (u_i, v_i)$.

Steps:

1. Initialize total error

total_error = 0.0

2. Loop over each view $i$:

• Convert $X$ to a column vector (or use your vector type).

3. Transform to camera coordinates

$$X_{cam} = R_i X + t_i$$

Let $X_{cam} = (X_c, Y_c, Z_c)$.

4. Project using intrinsics

• First to homogeneous image coordinates:

$$x_{img}^{hom} = K_i X_{cam}$$

Let $x_{img}^{hom} = (x', y', z')$.

• Then to 2D pixel coordinates:

$$\hat{u}_i = \frac{x'}{z'}, \quad \hat{v}_i = \frac{y'}{z'}$$

5. Compute per-view squared reprojection error

$$e_i = (u_i - \hat{u}_i)^2 + (v_i - \hat{v}_i)^2$$

du = u_i - u_hat
dv = v_i - v_hat
e_i = du*du + dv*dv
total_error += e_i

6. Return total error

return total_error

That directly implements:

$$E_{total} = \sum_i \| \pi(K_i, R_i, t_i, X) - p_i \|^2$$

---

4. Common Pitfalls

• Homogeneous division mistakes:

• Forgetting to divide by the third coordinate $z'$, or dividing by $Z_c$ before multiplying by $K_i$.

• Mixing up where to apply intrinsics; correct sequence is: world → camera → multiply by $K_i$ → divide by homogeneous depth.

• Coordinate convention mismatches:

• Ensure that $R_i, t_i$ transform world coordinates to camera coordinates. If they are stored as camera-to-world, you must invert them.

• Be consistent with units (pixels vs normalized coordinates). If intrinsics are applied, the result should be in pixel coordinates.

• Sign / depth issues:

• If $Z_c \le 0$ (point behind the camera), the projection is not valid; the problem may specify how to handle such cases. In simple coding tasks, such cases may not appear, but be aware.

• Matrix shapes and ordering:

• Ensure correct dimensions (3×3 times 3×1, etc.).

• Avoid mixing row-major vs column-major conventions; be consistent across your math and library.

---

5. Time & Space Complexity

Let $N$ be the number of views observing this point.

• Time complexity:

• Each view does a constant number of matrix–vector multiplications and scalar operations.

• Overall: $O(N)$.

• Space complexity:

• You only keep a running sum and temporary 3D/2D vectors.

• Overall: $O(1)$ additional space (beyond the given inputs).