Direct linear transformation

Direct linear transformation (DLT) is an algorithm which solves a set of variables from a set of similarity relations:

  for

where and are known vectors, denotes equality up to an unknown scalar multiplication, and is a matrix (or linear transformation) which contains the unknowns to be solved.

This type of relation appears frequently in projective geometry. Practical examples include the relation between 3D points in a scene and their projection onto the image plane of a pinhole camera, and homographies.

IntroductionEdit

An ordinary system of linear equations

    for  

can be solved, for example, by rewriting it as a matrix equation   where matrices   and   contain the vectors   and   in their respective columns. Given that there exists a unique solution, it is given by

 

Solutions can also be described in the case that the equations are over or under determined.

What makes the direct linear transformation problem distinct from the above standard case is the fact that the left and right sides of the defining equation can differ by an unknown multiplicative factor which is dependent on k. As a consequence,   cannot be computed as in the standard case. Instead, the similarity relations are rewritten as proper linear homogeneous equations which then can be solved by a standard method. The combination of rewriting the similarity equations as homogeneous linear equations and solving them by standard methods is referred to as a direct linear transformation algorithm or DLT algorithm. DLT is attributed to Ivan Sutherland. [1]

ExampleEdit

Let   and   be two sets of known vectors and the problem is to find   matrix   such that

    for  

where   is the unknown scalar factor related to equation k.

To get rid of the unknown scalars and obtain homogeneous equations, define the anti-symmetric matrix

 

and multiply both sides of the equation with   from the left

    for  

Since   the following homogeneous equations, which no longer contain the unknown scalars, are at hand

    for  

In order to solve   from this set of equations, consider the elements of the vectors   and   and matrix  :

 ,    ,   and    

and the above homogeneous equation becomes

    for  

This can also be written

    for  

where   and   both are 6-dimensional vectors defined as

    and    

This set of homogeneous equation can also be written in matrix form

 

where   is a   matrix which holds the vectors   in its rows. This means that   lies in the null space of   and can be determined, for example, by a singular value decomposition of  ;   is a right singular vector of   corresponding to a singular value that equals zero. Once   has been determined, the elements of   can be found by a simple rearrangement from a 6-dimensional vector to a   matrix. Notice that the scaling of   or   is not important (except that it must be non-zero) since the defining equations already allow for unknown scaling.

In practice the vectors   and   may contain noise which means that the similarity equations are only approximately valid. As a consequence, there may not be a vector   which solves the homogeneous equation   exactly. In these cases, a total least squares solution can be used by choosing   as a right singular vector corresponding to the smallest singular value of  

More general casesEdit

The above example has   and  , but the general strategy for rewriting the similarity relations into homogeneous linear equations can be generalized to arbitrary dimensions for both   and  

If   and   the previous expressions can still lead to an equation

    for    

where   now is   Each k provides one equation in the   unknown elements of   and together these equations can be written   for the known   matrix   and unknown 2q-dimensional vector   This vector can be found in a similar way as before.

In the most general case   and  . The main difference compared to previously is that the matrix   now is   and anti-symmetric. When   the space of such matrices is no longer one-dimensional, it is of dimension

 

This means that each value of k provides M homogeneous equations of the type

    for       and for  

where   is a M-dimensional basis of the space of   anti-symmetric matrices.

Example p = 3Edit

In the case that p = 3 the following three matrices   can be chosen

 ,    ,    

In this particular case, the homogeneous linear equations can be written as

    for    

where   is the matrix representation of the vector cross product. Notice that this last equation is vector valued; the left hand side is the zero element in  .

Each value of k provides three homogeneous linear equations in the unknown elements of  . However, since   has rank = 2, at most two equations are linearly independent. In practice, therefore, it is common to only use two of the three matrices  , for example, for m=1, 2. However, the linear dependency between the equations is dependent on  , which means that in unlucky cases it would have been better to choose, for example, m=2,3. As a consequence, if the number of equations is not a concern, it may be better to use all three equations when the matrix   is constructed.

The linear dependence between the resulting homogeneous linear equations is a general concern for the case p > 2 and has to be dealt with either by reducing the set of anti-symmetric matrices   or by allowing   to become larger than necessary for determining  

ReferencesEdit

  1. ^ Sutherland, Ivan E. (April 1974), "Three-dimensional data input by tablet", Proceedings of the IEEE, 62 (4): 453–461, doi:10.1109/PROC.1974.9449
  • Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in computer vision. Cambridge University Press. ISBN 978-0-521-54051-3.

External linksEdit