Direct linear transformation

Direct linear transformation (DLT) is an algorithm which solves a set of variables from a set of similarity relations:
where formula_3 and formula_4 are known vectors, formula_5 denotes equality up to an unknown scalar multiplication, and formula_6 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.
Introduction.
An ordinary system of linear equations
can be solved, for example, by rewriting it as a matrix equation formula_9 where matrices formula_10 and formula_11 contain the vectors formula_3 and formula_4 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, formula_6 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.
Example.
Suppose that formula_16. Let formula_17 and formula_18 be two known vectors, and we want to find the formula_19 matrix formula_6 such that
where formula_22 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 formula_24 from the left
Since formula_26 the following homogeneous equations, which no longer contain the unknown scalars, are at hand
In order to solve formula_6 from this set of equations, consider the elements of the vectors formula_3 and formula_4 and matrix formula_6:
and the above homogeneous equation becomes
This can also be written in the matrix form:
where formula_39 and formula_40 both are 6-dimensional vectors defined as
So far, we have 1 equation and 6 unknowns. A set of homogeneous equations can be written in the matrix form
where formula_44 is a formula_45 matrix which holds the known vectors formula_39 in its rows. The unknown formula_40 can be determined, for example, by a singular value decomposition of formula_44; formula_40 is a right singular vector of formula_44 corresponding to a singular value that equals zero. Once formula_40 has been determined, the elements of matrix formula_6 can rearranged from vector formula_53. Notice that the scaling of formula_40 or formula_6 is not important (except that it must be non-zero) since the defining equations already allow for unknown scaling.
In practice the vectors formula_3 and formula_4 may contain noise which means that the similarity equations are only approximately valid. As a consequence, there may not be a vector formula_40 which solves the homogeneous equation formula_43 exactly. In these cases, a total least squares solution can be used by choosing formula_40 as a right singular vector corresponding to the smallest singular value of formula_61
More general cases.
The above example has formula_62 and formula_63, but the general strategy for rewriting the similarity relations into homogeneous linear equations can be generalized to arbitrary dimensions for both formula_3 and formula_65
If formula_62 and formula_67 the previous expressions can still lead to an equation
where formula_6 now is formula_71 Each "k" provides one equation in the formula_72 unknown elements of formula_6 and together these equations can be written formula_74 for the known formula_75 matrix formula_44 and unknown "2q"-dimensional vector formula_77 This vector can be found in a similar way as before.
In the most general case formula_78 and formula_67. The main difference compared to previously is that the matrix formula_80 now is formula_81 and anti-symmetric. When formula_82 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 formula_87 is a "M"-dimensional basis of the space of formula_81 anti-symmetric matrices.
Example "p" = 3.
In the case that "p" = 3 the following three matrices formula_87 can be chosen
In this particular case, the homogeneous linear equations can be written as
where formula_95 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 formula_96.
Each value of "k" provides three homogeneous linear equations in the unknown elements of formula_6. However, since formula_95 has rank = 2, at most two equations are linearly independent. In practice, therefore, it is common to only use two of the three matrices formula_87, for example, for "m"=1, 2. However, the linear dependency between the equations is dependent on formula_3, 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 formula_44 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 formula_87 or by allowing formula_44 to become larger than necessary for determining formula_77