Direct linear transformation
Encyclopedia
Direct linear transformation (DLT) is an algorithm which solves a set of variables from a set of similarity relations:
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
.
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.
and 
be two sets of known vectors and the problem is to find 
matrix 
such that
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
In order to solve
from this set of equations, consider the elements of the vectors 
and 
and matrix 
:
and the above homogeneous equation becomes
This can also be written
for 
where
and 
both are 6-dimensional vectors defined as
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 
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
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
where
is a M-dimensional basis of the space of 
anti-symmetric matrices.
can be chosen
In this particular case, the homogeneous linear equations can be written as
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 
-
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
Projective geometry
In mathematics, projective geometry is the study of geometric properties that are invariant under projective transformations. This means that, compared to elementary geometry, projective geometry has a different setting, projective space, and a selective set of basic geometric concepts...
. Practical examples include the relation between 3D points in a scene and their projection onto the image plane of a pinhole camera
Pinhole camera model
The pinhole camera model describes the mathematical relationship between the coordinates of a 3D point and its projection onto the image plane of an ideal pinhole camera, where the camera aperture is described as a point and no lenses are used to focus light...
, and homographies
Homography
Homography is a concept in the mathematical science of geometry.A homography is an invertible transformation from a projective space to itself that maps straight lines to straight lines...
.
Introduction
An ordinary linear equation-
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.Example
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 spaceNull space
In linear algebra, the kernel or null space of a matrix A is the set of all vectors x for which Ax = 0. The kernel of a matrix with n columns is a linear subspace of n-dimensional Euclidean space...
of
and can be determined, for example, by a singular value decompositionSingular value decomposition
In linear algebra, the singular value decomposition is a factorization of a real or complex matrix, with many useful applications in signal processing and statistics....
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 cases
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 = 3
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