In computer vision triangulation refers to the process of determining a point in 3D space given its projections onto two, or more, images. In order to solve this problem it is necessary to know the parameters of the camera projection function from 3D to 2D for the cameras involved, in the simplest case represented by the camera matrices. Triangulation is sometimes also referred to as reconstruction.
Contents
- Introduction
- Properties of triangulation methods
- Singularities
- Invariance
- Computational complexity
- Mid point method
- References
The triangulation problem is in theory trivial. Since each point in an image corresponds to a line in 3D space, all points on the line in 3D are projected to the point in the image. If a pair of corresponding points in two, or more images, can be found it must be the case that they are the projection of a common 3D point x. The set of lines generated by the image points must intersect at x (3D point) and the algebraic formulation of the coordinates of x (3D point) can be computed in a variety of ways, as is presented below.
In practice, however, the coordinates of image points cannot be measured with arbitrary accuracy. Instead, various types of noise, such as geometric noise from lens distortion or interest point detection error, lead to inaccuracies in the measured image coordinates. As a consequence, the lines generated by the corresponding image points do not always intersect in 3D space. The problem, then, is to find a 3D point which optimally fits the measured image points. In the literature there are multiple proposals for how to define optimality and how to find the optimal 3D point. Since they are based on different optimality criteria, the various methods produce different estimates of the 3D point x when noise is involved.
Introduction
In the following, it is assumed that triangulation is made on corresponding image points from two views generated by pinhole cameras. Generalization from these assumptions are discussed here.
The image to the left illustrates the epipolar geometry of a pair of stereo cameras of pinhole model. A point x (3D point) in 3D space is projected onto the respective image plane along a line (green) which goes through the camera's focal point,
The image to the right shows the real case. The position of the image points
As a consequence, the measured image points are
This observation leads to the problem which is solved in triangulation. Which 3D point xest is the best estimate of x given
All triangulation methods produce xest = x in the case that
Properties of triangulation methods
A triangulation method can be described in terms of a function
where
Before looking at the specific methods, that is, specific functions
Singularities
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
Invariance
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 xest 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
then the camera matrices must transform as (Ck)
to produce the same homogeneous image coordinates (yk)
If the triangulation function
from which follows that
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.
Computational complexity
The function
Mid-point method
Each of the two image points
The midpoint method finds the point xest which minimizes
It turns out that xest lies exactly at the middle of the shortest line segment which joins the two projection lines.