Direct linear transformation

Direct linear transformation

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

 \mathbf{x}_{k} \propto \mathbf{A} \, \mathbf{y}_{k}   for  \, k = 1, \ldots, N

where  \mathbf{x}_{k} and  \mathbf{y}_{k} are known vectors,  \, \propto denotes equality up to an unknown scalar multiplication, and  \mathbf{A} 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.

Contents

Introduction

An ordinary linear equation

 \mathbf{x}_{k} = \mathbf{A} \, \mathbf{y}_{k}   for  \, k = 1, \ldots, N

can be solved, for example, by rewriting it as a matrix equation  \mathbf{X} = \mathbf{A} \, \mathbf{Y} where matrices  \mathbf{X} and  \mathbf{Y} contain the vectors  \mathbf{x}_{k} and  \mathbf{y}_{k} in their respective columns. Given that there exists a unique solution, it is given by

 \mathbf{A} = \mathbf{X} \, \mathbf{Y}^{T} \, (\mathbf{Y} \, \mathbf{Y}^{T})^{-1} .

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,  \mathbf{A} 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  \mathbf{x}_{k} \in \mathbb{R}^{2} and  \mathbf{y}_{k} \in \mathbb{R}^{3} be two sets of known vectors and the problem is to find  2 \times 3 matrix  \mathbf{A} such that

 \alpha_{k} \, \mathbf{x}_{k} = \mathbf{A} \, \mathbf{y}_{k}   for  \, k = 1, \ldots, N

where  \alpha_{k} \neq 0 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

 \mathbf{H} = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}

and multiply both sides of the equation with  \mathbf{x}_{k}^{T} \, \mathbf{H} from the left

 \alpha_{k} \, \mathbf{x}_{k}^{T} \, \mathbf{H} \, \mathbf{x}_{k} = \mathbf{x}_{k}^{T} \, \mathbf{H} \, \mathbf{A} \, \mathbf{y}_{k}   for  \, k = 1, \ldots, N .

Since  \mathbf{x}_{k}^{T} \, \mathbf{H} \, \mathbf{x}_{k} = 0, the following homogeneous equations, which no longer contain the unknown scalars, are at hand

 0 = \mathbf{x}_{k}^{T} \, \mathbf{H} \, \mathbf{A} \, \mathbf{y}_{k}   for  \, k = 1, \ldots, N .

In order to solve  \mathbf{A} from this set of equations, consider the elements of the vectors  \mathbf{x}_{k} and  \mathbf{y}_{k} and matrix  \mathbf{A} :

 \mathbf{x}_{k} = \begin{pmatrix} x_{1k} \\ x_{2k} \end{pmatrix} ,    \mathbf{y}_{k} = \begin{pmatrix} y_{1k} \\ y_{2k} \\ y_{3k} \end{pmatrix} ,   and    \mathbf{A} = \begin{pmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23} \end{pmatrix}

and the above homogeneous equation becomes

 0 = a_{11} \, x_{2k} \, y_{1k} - a_{21} \, x_{1k} \, y_{1k} + a_{12} \, x_{2k} \, y_{2k} - a_{22} \, x_{1k} \, y_{2k} + a_{13} \, x_{2k} \, y_{3k} - a_{23} \, x_{1k} \, y_{3k}   for  \, k = 1, \ldots, N.

This can also be written

 0 = \mathbf{b}_{k}^{T} \, \mathbf{a}   for  \, k = 1, \ldots, N

where  \mathbf{b}_{k} and  \mathbf{a} both are 6-dimensional vectors defined as

 \mathbf{b}_{k} = \begin{pmatrix} x_{2k} \, y_{1k} \\ -x_{1k} \, y_{1k} \\ x_{2k} \, y_{2k} \\ -x_{1k} \, y_{2k} \\ x_{2k} \, y_{3k} \\ -x_{1k} \, y_{3k} \end{pmatrix}   and    \mathbf{a} = \begin{pmatrix} a_{11} \\ a_{21} \\ a_{12} \\ a_{22} \\ a_{13} \\ a_{23} \end{pmatrix}.

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

 \mathbf{0} = \mathbf{B} \, \mathbf{a}

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

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

More general cases

The above example has  \mathbf{x}_{k} \in \mathbb{R}^{2} and  \mathbf{y}_{k} \in \mathbb{R}^{3} , but the general strategy for rewriting the similarity relations into homogeneous linear equations can be generalized to arbitrary dimensions for both  \mathbf{x}_{k} and  \mathbf{y}_{k}.

If  \mathbf{x}_{k} \in \mathbb{R}^{2} and  \mathbf{y}_{k} \in \mathbb{R}^{q} the previous expressions can still lead to an equation

 0 = \mathbf{x}_{k}^{T} \, \mathbf{H} \, \mathbf{A} \, \mathbf{y}_{k}   for    \, k = 1, \ldots, N

where  \mathbf{A} now is  2 \times q. Each k provides one equation in the 2q unknown elements of  \mathbf{A} and together these equations can be written  \mathbf{B} \, \mathbf{a} = \mathbf{0} for the known  N \times 2 \, q matrix  \mathbf{B} and unknown 2q-dimensional vector  \mathbf{a}. This vector can be found in a similar way as before.

In the most general case  \mathbf{x}_{k} \in \mathbb{R}^{p} and  \mathbf{y}_{k} \in \mathbb{R}^{q} . The main difference compared to previously is that the matrix  \mathbf{H} now is  p \times p and anti-symmetric. When p > 0 the space of such matrices is no longer one-dimensional, it is of dimension

 M = \frac{p\,(p-1)}{2}.

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

 0 = \mathbf{x}_{k}^{T} \, \mathbf{H}_{m} \, \mathbf{A} \, \mathbf{y}_{k}   for    \, m = 1, \ldots, M   and for  \, k = 1, \ldots, N

where  \mathbf{H}_{m} is a M-dimensional basis of the space of  p \times p anti-symmetric matrices.

Example p = 3

In the case that p = 3 the following three matrices  \mathbf{H}_{m} can be chosen

 \mathbf{H}_{1} = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & -1 \\ 0 & 1 & 0 \end{pmatrix} ,    \mathbf{H}_{2} = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ -1 & 0 & 0 \end{pmatrix} ,    \mathbf{H}_{3} = \begin{pmatrix} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} .

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

 \mathbf{0} = [\mathbf{x}_{k}]_{\times} \, \mathbf{A} \, \mathbf{y}_{k}   for    \, k = 1, \ldots, N

where  [\mathbf{x}_{k}]_{\times} 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  \mathbb{R}^{3} .

Each value of k provides three homogeneous linear equations in the unknown elements of  \mathbf{A} . However, since  [\mathbf{x}_{k}]_{\times} has rank = 2, at most two equations are linearly independent. In practice, therefore, it is common to only use two of the three matrices  \mathbf{H}_{m} , for example, for m=1, 2. However, the linear dependency between the equations is dependent on  \mathbf{x}_{k} , 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  \mathbf{B} 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  \mathbf{H}_{m} or by allowing  \mathbf{B} to become larger than necessary for determining  \mathbf{a}.

References

  • Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in computer vision. Cambridge University Press. ISBN 978-0-521-54051-3. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Linear complex structure — In mathematics, a complex structure on a real vector space V is an automorphism of V that squares to the minus identity, −I. Such a structure on V allows one to define multiplication by complex scalars in a canonical fashion so as to regard V as… …   Wikipedia

  • Linear regression — Example of simple linear regression, which has one independent variable In statistics, linear regression is an approach to modeling the relationship between a scalar variable y and one or more explanatory variables denoted X. The case of one… …   Wikipedia

  • Direct Digital Control (Regelungstechnisches Verfahren) — Direct Digital Control (abgekürzt DDC) ist ein Verfahren, Regelkreise mit darin teilweise enthaltenen Übertragungsgliedern von digitalen Prozessorsystemen (inklusive AD und DA Wandler modellierende Glieder) zu konstruieren und ihre Eigenschaften… …   Deutsch Wikipedia

  • Transformation problem — In 20th century discussions of Karl Marx s economics the transformation problem is the problem of finding a general rule to transform the values of commodities (based on labour according to his labour theory of value) into the competitive prices… …   Wikipedia

  • Transformation (genetics) — An unrelated process called malignant transformation occurs in the progression of cancer. In molecular biology transformation is the genetic alteration of a cell resulting from the direct uptake, incorporation and expression of exogenous genetic… …   Wikipedia

  • Transformation optics — Electromagnetism Electricity · …   Wikipedia

  • Linear filter — A linear filter applies a linear operator to a time varying input signal. Linear filters are very common in electronics and digital signal processing (see the article on electronic filters), but they can also be found in mechanical engineering… …   Wikipedia

  • Projection (linear algebra) — Orthogonal projection redirects here. For the technical drawing concept, see orthographic projection. For a concrete discussion of orthogonal projections in finite dimensional linear spaces, see vector projection. The transformation P is the… …   Wikipedia

  • Affine transformation — In geometry, an affine transformation or affine map or an affinity (from the Latin, affinis , connected with ) between two vector spaces (strictly speaking, two affine spaces) consists of a linear transformation followed by a translation::x… …   Wikipedia

  • Lorentz transformation — A visualisation of the Lorentz transformation (full animation). Only one space coordinate is considered. The thin solid lines crossing at right angles depict the time and distance coordinates of an observer at rest with respect to that frame; the …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”