Triangulation

Figure 10.2: Example of triangulation. Given the camera calibration, the world point $\mathbf {x}$ can be recovered by observing its projection in at least two images ( $\mathbf {p_1}, \mathbf {p_2}, \ldots$). However, because of noise, the resulting lines do not pass through point $\mathbf {x}$ and may not intersect one another. The maximum-likelihood solution requires minimizing the sum of the squared errors between the observed point $\mathbf {p}_i$ and the predicted point $\hat {\mathbf {p}}_i$.

By examining Figure 10.2, it is easy to see that the solution to the triangulation problem is the intersection point of the epipolar lines generated by the two images. This problem can easily be extended to the case of $n$ cameras whose relative poses are known. If the absolute pose is unknown, it can be obtained directly from the images themselves using techniques such as the Essential matrix (Section 10.4).

Because of inaccuracies in identifying corresponding points (calibration errors could also be considered separately), the lines formed by the optical rays are generally skew. In this case, it is necessary to find the closest solution under some cost function: a least-squares solution is always possible with $n \geq 2$, as well as with techniques such as Forward Intersections or the Direct Linear Transfer (DLT).

Every optical ray subtended by image pixel $(u_i,v_i)$, with $i=1, \ldots, n$ denoting the i-th view, must satisfy equation (10.9). The intersection point (Forward Intersections) of all these rays is the solution of a potentially overdetermined linear system with $3+n$ unknowns in $3n$ equations:

$$\left\{ \begin{array}{rl} \mathbf{x}&= \lambda_1 \mathbf{v}_... ...x}&= \lambda_n \mathbf{v}_n + \mathbf{t}_n \end{array}\right.$$ (10.13)

where $\mathbf{v}_i = \mathbf{R}^{-1}_i \mathbf{K}^{-1}_i \begin{pmatrix}u_i &v_i&1 \end{pmatrix}^{\top}$ denotes the direction of the optical ray in world coordinates. The unknowns are the world point to be estimated, $\mathbf {x}$, and the distances along the optical axis, $\lambda_i$.

The closed-form solution, limited to the case of only two lines, is given in Section 1.6.8. This technique can be applied when one camera is aligned with the axes and the second is positioned relative to the first according to relation (10.5).

Using the properties of the cross product, the same expression can be obtained with perspective projection matrices and image points expressed as homogeneous coordinates:

$$\left\{ \begin{array}{l} \left[ \mathbf{p}_{1} \right]_{\tim... ...right]_{\times} \mathbf{P}_n \mathbf{x} = 0 \end{array}\right.$$ (10.14)

where $[\cdot]_{\times}$ is the cross product written in matrix form. Each of these constraints provides three equations, but only two are linearly independent. All these constraints can ultimately be rearranged into a homogeneous system of the form

$$\mathbf{A} \mathbf{x} = 0$$ (10.15)

where $\mathbf{A}$ is a matrix $2n \times 4$, with $n$ denoting the number of views in which point $\mathbf {x}$ is observed. The solution of homogeneous system (10.15) can be obtained by singular value decomposition. This approach is called the Direct Linear Transform (DLT), by analogy with the calibration technique.

Minimization in world coordinates, however, is not optimal from the standpoint of noise minimization. In the absence of further information about the structure of the observed scene, the optimal estimate (Maximum Likelihood Estimation) is always the one that minimizes the error in image coordinates (reprojection), but it requires greater computational effort and the use of nonlinear techniques, since the cost function to be minimized is

$$\argmin_\mathbf{x} \sum_{i=1}^{n} \Vert \mathbf{p}_i - \hat{\mathbf{p}}_i \Vert^2$$ (10.16)

with $\hat{\mathbf{p}}_i \equiv \mathbf{P}_i \mathbf{x}$, where $\mathbf{P}_i$ is the projection matrix of the i-th image (Figure 10.2).

This is a nonlinear, nonconvex problem: multiple local minima may be present, and the linear solution must be used as the starting point for the minimization.

A further class of techniques, which exploit the information obtained from epipolar constraints and use it to estimate the position of points unaffected by noise without having to recover the three-dimensional point, is presented in Section 10.4.4.