Triangulation (computer vision)

Some of the methods fail to correctly compute an estimate of x (3D point) if it lies in a certain subset of the 3D space, corresponding to some combination of ${\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2}}$. A point in this subset is then a singularity of the triangulation method. The reason for the failure can be that some equation system to be solved is under-determined or that the projective representation of x_est becomes the zero vector for the singular points.

In some applications, it is desirable that the triangulation is independent of the coordinate system used to represent 3D points; if the triangulation problem is formulated in one coordinate system and then transformed into another the resulting estimate x_est should transform in the same way. This property is commonly referred to as invariance. Not every triangulation method assures invariance, at least not for general types of coordinate transformations.

For a homogeneous representation of 3D coordinates, the most general transformation is a projective transformation, represented by a ${\displaystyle 4\times 4}$ matrix ${\displaystyle \mathbf {T} }$. If the homogeneous coordinates are transformed according to

${\displaystyle \mathbf {\bar {x}} \sim \mathbf {T} \,\mathbf {x} }$

then the camera matrices must transform as (C_k)

${\displaystyle \mathbf {\bar {C}} _{k}\sim \mathbf {C} _{k}\,\mathbf {T} ^{-1}}$

to produce the same homogeneous image coordinates (y_k)

${\displaystyle \mathbf {y} _{k}\sim \mathbf {\bar {C}} _{k}\,\mathbf {\bar {x}} =\mathbf {C} _{k}\,\mathbf {x} }$

If the triangulation function ${\displaystyle \tau }$ is invariant to ${\displaystyle \mathbf {T} }$ then the following relation must be valid

${\displaystyle \mathbf {\bar {x}} _{\rm {est}}\sim \mathbf {T} \,\mathbf {x} _{\rm {est}}}$

from which follows that

${\displaystyle \tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1},\mathbf {C} _{2})\sim \mathbf {T} ^{-1}\,\tau (\mathbf {y} '_{1},\mathbf {y} '_{2},\mathbf {C} _{1}\,\mathbf {T} ^{-1},\mathbf {C} _{2}\,\mathbf {T} ^{-1}),}$   for all ${\displaystyle \mathbf {y} '_{1},\mathbf {y} '_{2}}$

For each triangulation method, it can be determined if this last relation is valid. If it is, it may be satisfied only for a subset of the projective transformations, for example, rigid or affine transformations.

The function ${\displaystyle \tau }$ is only an abstract representation of a computation which, in practice, may be relatively complex. Some methods result in a ${\displaystyle \tau }$ which is a closed-form continuous function while others need to be decomposed into a series of computational steps involving, for example, SVD or finding the roots of a polynomial. Yet another class of methods results in ${\displaystyle \tau }$ which must rely on iterative estimation of some parameters. This means that both the computation time and the complexity of the operations involved may vary between the different methods.

Each of the two image points ${\displaystyle \mathbf {y} '_{1}}$ and ${\displaystyle \mathbf {y} '_{2}}$ has a corresponding projection line (blue in the right image above), here denoted as ${\displaystyle \mathbf {L} '_{1}}$ and ${\displaystyle \mathbf {L} '_{2}}$, which can be determined given the camera matrices ${\displaystyle \mathbf {C} _{1},\mathbf {C} _{2}}$. Let ${\displaystyle d\,}$ be a distance function between a (3D line) L and a x (3D point) such that ${\displaystyle d(\mathbf {L} ,\mathbf {x} )}$ is the Euclidean distance between ${\displaystyle \mathbf {L} }$ and ${\displaystyle \mathbf {x} }$. The midpoint method finds the point x_est which minimizes

${\displaystyle d(\mathbf {L} '_{1},\mathbf {x} )^{2}+d(\mathbf {L} '_{2},\mathbf {x} )^{2}}$

It turns out that x_est lies exactly at the middle of the shortest line segment which joins the two projection lines.

The problem to be solved there is how to compute ${\displaystyle (x_{1},x_{2},x_{3})}$ given corresponding normalized image coordinates ${\displaystyle (y_{1},y_{2})}$ and ${\displaystyle (y'_{1},y'_{2})}$. If the essential matrix is known and the corresponding rotation and translation transformations have been determined, this algorithm (described in Longuet-Higgins' paper) provides a solution.

Let ${\displaystyle \mathbf {r} _{k}}$ denote row k of the rotation matrix ${\displaystyle \mathbf {R} }$:

${\displaystyle \mathbf {R} ={\begin{pmatrix}-\mathbf {r} _{1}-\\-\mathbf {r} _{2}-\\-\mathbf {r} _{3}-\end{pmatrix}}}$

Combining the above relations between 3D coordinates in the two coordinate systems and the mapping between 3D and 2D points described earlier gives

${\displaystyle y'_{1}={\frac {x'_{1}}{x'_{3}}}={\frac {\mathbf {r} _{1}\cdot ({\tilde {\mathbf {x} }}-\mathbf {t} )}{\mathbf {r} _{3}\cdot ({\tilde {\mathbf {x} }}-\mathbf {t} )}}={\frac {\mathbf {r} _{1}\cdot (\mathbf {y} -\mathbf {t} /x_{3})}{\mathbf {r} _{3}\cdot (\mathbf {y} -\mathbf {t} /x_{3})}}}$

or

${\displaystyle x_{3}={\frac {(\mathbf {r} _{1}-y'_{1}\,\mathbf {r} _{3})\cdot \mathbf {t} }{(\mathbf {r} _{1}-y'_{1}\,\mathbf {r} _{3})\cdot \mathbf {y} }}}$

Once ${\displaystyle x_{3}}$ is determined, the other two coordinates can be computed as

${\displaystyle {\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}=x_{3}{\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}}$

The above derivation is not unique. It is also possible to start with an expression for ${\displaystyle y'_{2}}$ and derive an expression for ${\displaystyle x_{3}}$ according to

${\displaystyle x_{3}={\frac {(\mathbf {r} _{2}-y'_{2}\,\mathbf {r} _{3})\cdot \mathbf {t} }{(\mathbf {r} _{2}-y'_{2}\,\mathbf {r} _{3})\cdot \mathbf {y} }}}$

In the ideal case, when the camera maps the 3D points according to a perfect pinhole camera and the resulting 2D points can be detected without any noise, the two expressions for ${\displaystyle x_{3}}$ are equal. In practice, however, they are not and it may be advantageous to combine the two estimates of ${\displaystyle x_{3}}$, for example, in terms of some sort of average.

There are also other types of extensions of the above computations which are possible. They started with an expression of the primed image coordinates and derived 3D coordinates in the unprimed system. It is also possible to start with unprimed image coordinates and obtain primed 3D coordinates, which finally can be transformed into unprimed 3D coordinates. Again, in the ideal case the result should be equal to the above expressions, but in practice they may deviate.

A final remark relates to the fact that if the essential matrix is determined from corresponding image coordinate, which often is the case when 3D points are determined in this way, the translation vector ${\displaystyle \mathbf {t} }$ is known only up to an unknown positive scaling. As a consequence, the reconstructed 3D points, too, are undetermined with respect to a positive scaling.