User:KYN/Homogeneous representations in 2D

From Wikipedia, the free encyclopedia

In a 2-dimensional space, e.g. R², geometrical objects such as points and lines can be given a representation in terms of homogeneous coordinates. Also transformations on these objects can be given a homogeneous representation. The reason for introducing a homogeneous representation for these objects and transformations is that

A relative large class of transformations can be represented by linear transformation on the homogeneous coordinates, even though the corresponding transformation on the 2D coordinates of, e.g., a point or a line, is not linear. Examples is this are presented below.

Various geometrical relations, e.g., incidence between a point and a line, can be represented in a simple way. Examples is this are presented below.

Usually, a homogeneous representation is defined for points and all other homogeneous representation, e.g., of lines and various transformations, follows from that. The homogeneous representation for points is usually defined by introducing an addition dimension where the corresponding coordinate assumes a constant value. In presentations of this topic the extra dimension is placed either as the first or as the last dimension in the homogeneous representation. Also, the specific value of the constant coordinate in this dimension can, in principle, assume any non-zero value. Most presentations assign a unit value to this coordinate, but it should be noted that for practical or numerical reasons, it may be desirable to choose another value for this dimension.

In this presentation, the extra dimension is placed first and it is given a unit value. It should be noted that any other homogeneous representation of 2D points can be obtained by a suitable linear transformation of the homogeneous coordinates.

[edit] Homogeneous representation of 2D points

A 2D point

$x = \begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix}$

is represented by the 3D vector $\mathbf{x}$ , its homogeneous coordinates, according to

$\mathbf{x} = \begin{pmatrix} 1 \\ x_{1} \\ x_{2} \end{pmatrix}$

To fully enjoy all the benefits of a homogeneous representation, it is sometimes necessary to see $\mathbf{x}$ as an element of a projective space, i.e., any non-zero scaling of $\mathbf{x}$ is considered as an equivalent representation of the 2D point $x$ . This can be described as $\mathbf{x} \sim a \mathbf{x}$ for $a \in \mathbb{R}, a \neq 0$ . A consequence of this projective property is that $x$ can be obtained from $\mathbf{x}$ only after a proper normalization:

$x = \begin{pmatrix} X_{1}/X_{0} \\ X_{2}/X_{0} \end{pmatrix}$

where

$\mathbf{x} = \begin{pmatrix} X_{0} \\ X_{1} \\ X_{2} \end{pmatrix} = \begin{pmatrix} a \\ a x_{1} \\ a x_{2} \end{pmatrix}$

Notice that this transformation from $\mathbf{x}$ to $x$ requires that $X_{0} \neq 0$ . Any such homogeneous coordinate represents a proper 2D point.

[edit] Points at infinity

A special feature of the homogeneous representation of 2D points is that it allows points which are at infinite distance from the origin to be represented in a consistent way. Points at infinity have a homogeneous representation as

$\mathbf{x} = \begin{pmatrix} 0 \\ X_{1} \\ X_{2} \end{pmatrix}$

The transformation from this homogeneous coordinate to a 2D point according to the expression above yields an indefinite vector since we cannot divide by zero. On the other hand, the previous vector can also be seen as the limit value of

$\mathbf{x} = \begin{pmatrix} X_{0} \\ X_{1} \\ X_{2} \end{pmatrix}$

when $X_{0} \rightarrow 0$ . This can be interpreted in a consistent way as a point which lies at infinite distance from the origin and in the direction defined by the vector

$\begin{pmatrix} X_{1} \\ X_{2} \end{pmatrix}$

The term "direction" is somewhat misleading. Since $\mathbf{x}$ is a projective element

$\mathbf{x} = \begin{pmatrix} 0 \\ X_{1} \\ X_{2} \end{pmatrix} \sim - \begin{pmatrix} 0 \\ X_{1} \\ X_{2} \end{pmatrix} = \begin{pmatrix} 0 \\ - X_{1} \\ - X_{2} \end{pmatrix}$

which means that we can find a point at infinity by going in two opposite directions and that the two resulting points in this representation have to be thought of as the same point. Even though this may appear strange from an intuitive point of view, this interpretation of points at infinity is consistent with the geometrical statements which sometimes produce such homogeneous representations. Examples of this are presented below.

[edit] The zero vector

The above transformations from homogeneous coordinates back to either a "proper" 2D point or a point at infinity applies to all 3D vectors $\mathbf{x}$ except the zero vector. What does the zero vector represent as a homogeneous coordinate? The answer is simple: nothing. There is no useful interpretation of the zero vector as a homogeneous representation. This implies that all operations which are applied to the homogeneous coordinates have to be carefully designed in order not to produce the zero vector as a result. Another way to describe it is to say that if an operation produces homogeneous coordinates and the result may be zero, this specific case should be interpreted as the operation fails to produce a meaningful result. Examples of this are presented below.

The same discussion applies to any zero vector, matrix or tensor which may appear as homogeneous representations of various types of geometrical objects.

[edit] Homogeneous representation of 2D lines

Any 2D line can be described as the set of points

$x = \begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix}$

which satisfies the condition

x 1 l 1 + x 2 l 2 = l

where $l_{1}^{2} + l_{2}^{2} = 1$ and $l \geq 0$ . This type of parameterization of a line is chosen since it allows any slope of the line to be described. In fact, $l 1$ and $l 2$ represent the cosine and sine of the slope angle and $l$ is the shortest distance from the line to the origin.

The above equation which characterizes a line can be rewritten as

$\begin{pmatrix} 1 \\ x_{1} \\ x_{2} \end{pmatrix} \cdot \begin{pmatrix} -l \\ l_{1} \\ l_{2} \end{pmatrix} = \mathbf{x} \cdot \begin{pmatrix} -l \\ l_{1} \\ l_{2} \end{pmatrix} =0$

From this expression, it can be seen that if we use the 3D vector

$\mathbf{l} = \begin{pmatrix} -l \\ l_{1} \\ l_{2} \end{pmatrix}$

as a homogeneous representation of the line, then it follows that

the point x lies on the line l is equivalent with $\mathbf{x} \cdot \mathbf{l} = 0$

Furthermore, also $\mathbf{l}$ can be characterized a projective element since a non-zero scaling of $\mathbf{l}$ does not change the above statement about x and l. In this case, the vector $\mathbf{l}$ includes a scale factor which needs to be taken care of in order to recover the parameters of the line. From the relation

$\mathbf{l} = \begin{pmatrix} L_{0} \\ L_{1} \\ L{2} \end{pmatrix} \sim {1 \over \sqrt{L_{1}^{2} + L_{2}^{2}}} \begin{pmatrix} L_{0} \\ L_{1} \\ L{2} \end{pmatrix}$

if follows that

$l = {-L_{0} \over \sqrt{L_{1}^{2} + L_{2}^{2}}}, l_{1} = {L_{1} \over \sqrt{L_{1}^{2} + L_{2}^{2}}}, l_{2} = {L_{2} \over \sqrt{L_{1}^{2} + L_{2}^{2}}}$

Notice that this transformation from $\mathbf{l}$ to the parametes of the line requires that $\sqrt{L_{1}^{2} + L_{2}^{2}} \neq 0$ . Any such homogeneous coordinate represents a proper 2D line.

[edit] The line at infinity

In the same way as there are points at inifnity there is also a line at infinity. However, there are infinitly many points are infinity but only one line. The line at infinity is the result of considering the limit case of $\sqrt{L_{1}^{2} + L_{2}^{2}} \rightarrow 0$ in the transformation rule from $\mathbf{l}$ to the line parameters. The resulting line will have a distance to the origin which goes to infinity and have a homogeneous representation according to

$\mathbf{l} = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}$

Any homogeneous representation of a proper line has this vector as its limit value which means that there is only one line at infinity. It must also be the case that the line at infinity passes through all points at infinity and no other points.

[edit] Representation of 2D points and lines in terms of Plücker coordinates

The vector form defined above for the homogeneous representations of either points or lines has a counter part in representations based on anti-symmetric $3 \times 3$ matrices, referred to as Plücker coordinates. It is straigtfoward to go between these two representations, and using Plücker coordinates it is easy to find the line which intersects two points and, vice versa, the point given by the intersection of two lines.

[edit] From points to lines

Let two distinct points have homogeneous coordinates given by the vectors $\mathbf{x}_{1}, \mathbf{x}_{2}$ . Form the anti-symmetric matrix $\mathbf{L}$ as

$\mathbf{L} = \mathbf{x}_{1} \mathbf{x}_{2}^{T} - \mathbf{x}_{2} \mathbf{x}_{1}^{T}$

Let the elements of the two vectors be given by

$\mathbf{x}_{1} = \begin{pmatrix} X_{01} \\ X_{11} \\ X_{21} \end{pmatrix} \,\,\, \mathbf{x}_{2} = \begin{pmatrix} X_{02} \\ X_{12} \\ X_{22} \end{pmatrix}$

which gives the elements in matrix $\mathbf{L}$ according to

$\mathbf{L} = \begin{pmatrix} 0 & X_{01} X_{12} - X_{02} X_{11} & X_{01} X_{22} - X_{02} X_{21} \\ X_{02} X_{11} - X_{01} X_{12} & 0 & X_{11} X_{22} - X_{12} X_{21} \\ X_{02} X_{21} - X_{01} X_{22} & X_{12} X_{21} - X_{11} X_{22} & 0 \end{pmatrix}$

Notice that the $3 \times 3$ anti-symmetric matrix $\mathbf{L}$ is "three-dimensional" in the sense that it contains only 3 linearly independent elements. We can construct a vector $\mathbf{l}$ as

$\mathbf{l} = \begin{pmatrix} L_{23} \\ L_{31} \\ L_{12} \end{pmatrix} = \begin{pmatrix} X_{11} X_{22} - X_{12} X_{21} \\ X_{02} X_{21} - X_{01} X_{22} \\ X_{01} X_{12} - X_{02} X_{11} \end{pmatrix}$

Let us now interpret $\mathbf{l}$ as the dual homogeneous representation of a 2D line, as described above. Which line is it? To see this, we can investigate its relation to the two points represented by $\mathbf{x}_{1}, \mathbf{x}_{2}$ :

$\mathbf{l} \cdot \mathbf{x}_{1} = \mathbf{l} \cdot \mathbf{x}_{1} = 0$

This implies that the line which $\mathbf{l}$ represents intersects both points. Consequently, we have found a computational approach for determining the dual homogeneous representation of the line which intersects two specific points. In this approach two different representations of the line are used; the dual homogeneous coordinates given by the vector $\mathbf{l}$ and the so-called Plücker coordinates given by the anti-symmetric $3 \times 3$ matrix $\mathbf{L}$ . The mapping from $\mathbf{L}$ to $\mathbf{l}$ described above is one-to-one so we can easily go from one representation to the other and back again as we choose.

It was said above that $\mathbf{x}_{1}, \mathbf{x}_{2}$ represent two distinct points. If the points coincide, then $\mathbf{L} = \mathbf{0} \Rightarrow \mathbf{l} = \mathbf{0}$ . This is an indication that there is no unique line which intersects both points if they coincide.

From this discussion it follows immediately that if the two points are at infinity, with $X 01 = X 02 = 0$ , then the line is also at infinity.

[edit] From lines to points

[edit] Transformations of 2D points

[edit] Translations

[edit] Rotations

[edit] Scaling

[edit] Euclidean transformations

[edit] Affine transformations

[edit] Projective transformations

[edit] Homographies

[edit] Transformations of 2D lines

[edit] Homogeneous and dual homogeneous representations

[edit] Distances

[edit] Point to line

[edit] Point to point

[edit] Conics in 2D

[edit] Dual conics

Retrieved from "http://en.wikipedia.org../../../k/y/n/User%7EKYN_Homogeneous_representations_in_2D_533c.html"