Direct linear transformation (DLT) is an algorithm which solves a set of variables from a set of similarity relations:
for ![{\displaystyle \,k=1,\ldots ,N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68e1d42aadf6846d3b9704d4b2c793f84f055d1b)
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,[1] and homographies.
Introduction
An ordinary system of linear equations
for ![{\displaystyle \,k=1,\ldots ,N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68e1d42aadf6846d3b9704d4b2c793f84f055d1b)
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
![{\displaystyle \mathbf {A} =\mathbf {X} \,\mathbf {Y} ^{T}\,(\mathbf {Y} \,\mathbf {Y} ^{T})^{-1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d76d52600ef10411dca421e8288b7385af83326)
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. [2]
Example
Suppose that
. Let
and
be two known vectors, and we want to find the
matrix
such that
![{\displaystyle \alpha _{k}\,\mathbf {x} _{k}=\mathbf {A} \,\mathbf {y} _{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1836ab366369f559725fc7f005dc86e2b89ac60)
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
![{\displaystyle \mathbf {H} ={\begin{pmatrix}0&-1\\1&0\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d0d476dceea8b50749284028cdaf59f67614e2c)
and multiply both sides of the equation with
from the left
![{\displaystyle {\begin{aligned}(\mathbf {x} _{k}^{T}\,\mathbf {H} )\,\alpha _{k}\,\mathbf {x} _{k}&=(\mathbf {x} _{k}^{T}\,\mathbf {H} )\,\mathbf {A} \,\mathbf {y} _{k}\\\alpha _{k}\,\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {x} _{k}&=\mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {A} \,\mathbf {y} _{k}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/257bc599e3d0f21997708e457938044ff1f5c363)
Since
the following homogeneous equations, which no longer contain the unknown scalars, are at hand
![{\displaystyle \mathbf {x} _{k}^{T}\,\mathbf {H} \,\mathbf {A} \,\mathbf {y} _{k}=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc412bb7591b0ad0af1a5060765ee67c7577cd8a)
In order to solve
from this set of equations, consider the elements of the vectors
and
and matrix
:
,
, and ![{\displaystyle \mathbf {A} ={\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee4042f3dce75ef30b5332bb4f5e639cce5f265d)
and the above homogeneous equation becomes
for ![{\displaystyle \,k=1,\ldots ,N.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f6dc74aa238a4cc1b1267d6f55c0607c2e7c95a)
This can also be written in the matrix form:
for ![{\displaystyle \,k=1,\ldots ,N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68e1d42aadf6846d3b9704d4b2c793f84f055d1b)
where
and
both are 6-dimensional vectors defined as
and ![{\displaystyle \mathbf {a} ={\begin{pmatrix}a_{11}\\a_{21}\\a_{12}\\a_{22}\\a_{13}\\a_{23}\end{pmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a1d0b147ffa8e0b0bdb5f643e7df475c99460ea)
So far, we have 1 equation and 6 unknowns. A set of homogeneous equations can be written in the matrix form
![{\displaystyle \mathbf {0} =\mathbf {B} \,\mathbf {a} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d35677df68c1308a5f6e28247a77eac6ec0a29b)
where
is a
matrix which holds the known vectors
in its rows. The unknown
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 matrix
can rearranged from vector
. 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 ![{\displaystyle \,k=1,\ldots ,N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68e1d42aadf6846d3b9704d4b2c793f84f055d1b)
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
![{\displaystyle M={\frac {p\,(p-1)}{2}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2bd7528f537a85ccbf33039b557b455ea3f3943c)
This means that each value of k provides M homogeneous equations of the type
for
and for ![{\displaystyle \,k=1,\ldots ,N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68e1d42aadf6846d3b9704d4b2c793f84f055d1b)
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
,
, ![{\displaystyle \mathbf {H} _{3}={\begin{pmatrix}0&-1&0\\1&0&0\\0&0&0\end{pmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16711e2c24d284fdac630769095e82072df8ff99)
In this particular case, the homogeneous linear equations can be written as
for ![{\displaystyle \,k=1,\ldots ,N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68e1d42aadf6846d3b9704d4b2c793f84f055d1b)
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
References
- ^ Abdel-Aziz, Y.I.; Karara, H.M. (2015-02-01). "Direct Linear Transformation from Comparator Coordinates into Object Space Coordinates in Close-Range Photogrammetry". Photogrammetric Engineering & Remote Sensing. 81 (2). American Society for Photogrammetry and Remote Sensing: 103–107. doi:10.14358/pers.81.2.103. ISSN 0099-1112.
- ^ 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 links
- Homography Estimation by Elan Dubrofsky (§2.1 sketches the "Basic DLT Algorithm")
- A DLT Solver based on MATLAB by Hsiang-Jen (Johnny) Chien