3D Computer Vision (SoSe2024)

Primitives and Transformations in 3D

Prof. Dr. Ulrich Schwanecke

RheinMain University of Applied Sciences

🚀 by Decker

Last lecture

Last lecture

  • 1D Transformations

  • Primitives and Transformations

    • Homogeneous Coordinates
    • Points, Lines and Planes
    • 2D Transformations
    • Homography Estimation

Today’s Lecture

Today’s Lecture

  • The 3D Projective Space \(\mathbb{P}^3\)
    • Points, Planes,
    • Straight Lines, …
    • … and their transformations

Reminder

Points

Points in 1D/2D/3D can be written in inhomogeneous coordinates as \[ x \in \mathbb{R}\quad \text{or} \quad \mathbf{x}=\begin{pmatrix}x \\ y \end{pmatrix} \in \mathbb{R}^2\quad \text{or} \quad \mathbf{x}=\begin{pmatrix}x \\ y \\ z \end{pmatrix} \in \mathbb{R}^3 \] or in homogenous coordinates as \[ \tilde{\mathbf{x}}=\begin{pmatrix}\tilde{x} \\ \tilde{w} \end{pmatrix} \in \mathbb{P}^1\quad \text{or} \quad \tilde{\mathbf{x}}=\begin{pmatrix}\tilde{x} \\ \tilde{y} \\ \tilde{w} \end{pmatrix} \in \mathbb{P}^2\quad \text{or} \quad \tilde{\mathbf{x}}=\begin{pmatrix}\tilde{x} \\ \tilde{y} \\ \tilde{z} \\ \tilde{w} \end{pmatrix} \in \mathbb{P}^3 \] where \(\mathbb{P}^n = \mathbb{R}^{n+1} \setminus \{\mathbf{0}\}\) is called projective space. Homogeneous vectors that differ only by scale are considered equivalent and define an equivalence class, thus homogeneous vectors are defined only up to scale.

Points

An inhomogeneous vector \(\mathbf{x}\) is converted to a homogeneous vector \(\tilde{\mathbf{x}}\) as follows \[ \tilde{\mathbf{x}}= \begin{pmatrix}\tilde{x} \\ \tilde{w} \end{pmatrix} = \begin{pmatrix} x \\ 1 \end{pmatrix} =\bar{x} \quad \text{or} \quad \tilde{\mathbf{x}}= \begin{pmatrix}\tilde{x} \\ \tilde{y} \\ \tilde{w} \end{pmatrix} = \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} = \begin{pmatrix} \mathbf{x} \\ 1 \end{pmatrix} = \bar{\mathbf{x}} \quad \text{or} \quad \tilde{\mathbf{x}}= \begin{pmatrix}\tilde{x} \\ \tilde{y} \\ \tilde{z} \\ \tilde{w} \end{pmatrix} = \begin{pmatrix} x \\ y \\ z \\  1 \end{pmatrix} = \begin{pmatrix} \mathbf{x} \\ 1 \end{pmatrix} = \bar{\mathbf{x}} \] with the augmented vector \(\bar{\mathbf{x}}\). To convert in opposite direction one has to divide by \(\tilde{w}\): \[ \bar{\mathbf{x}} = \begin{pmatrix} \mathbf{x} \\ 1 \end{pmatrix} = \begin{pmatrix} x \\ y \\ z \\ 1 \end{pmatrix} = \frac{1}{\tilde{w}} \tilde{\mathbf{x}} = \frac{1}{\tilde{w}} \begin{pmatrix} \tilde{x} \\ \tilde{y} \\ \tilde{z} \\ \tilde{w} \end{pmatrix} = \begin{pmatrix} \tilde{x} / \tilde{w} \\ \tilde{y} / \tilde{w} \\ \tilde{z} / \tilde{w} \\ 1 \end{pmatrix} \] Homogeneous points whose last element is \(\tilde{w} = 0\) can’t be represented with inhomogeneous coordinates. They are called ideal points or points at infinity.

2D Lines

2D lines can also be expressed using homogeneous coordinates \(\tilde{\mathbf{l}}=(a,b,c)^\top\) \[ \{\tilde{\mathbf{x}} \;|\; \tilde{\mathbf{l}}\tilde{\mathbf{x}} = 0 \} \quad\Leftrightarrow\quad \{x,y \;|\; ax + by + c = 0 \} \]

  • We can normalize \(\tilde{\mathbf{l}}\) to \(\tilde{\mathbf{l}} = (n_x, n_y, d)^\top = (\mathbf{n}, d)^\top\) with \(\|\mathbf{n}\|_2=1\) (Hesse normal form)
    • In this case, \(\mathbf{n}\) is the normal vector perpendicular to the line and \(d\) is its distance to the origin.
  • An exception is the line at infinity \(\tilde{\mathbf{l}}_\infty=(0,0,1)^\top\) which passes through all ideal points.

Duality (in 2D)

The duality principle:

For every proposition of two-dimensional projective geometry there exists a dual proposition which is obtained by interchanging the role of points and lines in the original proposition.

  • For example, dual are

\[ \begin{array}{ccc} \tilde{\mathbf{x}} & \longleftrightarrow & \tilde{\mathbf{l}}\\[3mm] \tilde{\mathbf{x}}^T\tilde{\mathbf{l}}=0 & \longleftrightarrow & \tilde{\mathbf{l}}^T\tilde{\mathbf{x}}=0\\[3mm] \tilde{\mathbf{x}}=\tilde{\mathbf{l}}\times\tilde{\mathbf{l}}^\prime & \longleftrightarrow & \tilde{\mathbf{l}}=\tilde{\mathbf{x}}\times\tilde{\mathbf{x}}^\prime \end{array} \]

Overview of 2D Transformations


Transformation Matrix # DOF Preserves
translation \([\mathbf{I\quad t}]_{2\times 3}\) 2 orientation
rigid (Euclidean) \([\mathbf{R\quad t}]_{2\times 3}\) 3 length
similarity \([s\mathbf{R\quad t}]_{2\times 3}\) 4 angles
affine \([\mathbf{A\quad t}]_{2\times 3}\) 6 parallelism
projective \([\mathbf{H}]_{3\times 3}\) 8 straight lines

  • Transformations form nested set of groups (closed under composition, inverse)
  • \(2\times 3\) matrices are extended with a third \([\mathbf{0}^\top 1]\) row for homogeneous transforms

The Projective Space \(\mathbb{P}^3\)

3D Planes

3D planes can also be represented with homogeneous coordinates \(\tilde{\mathbf{m}}=(a,b,c,d)^\top\) as

\[ \{\tilde{\mathbf{x}} \;|\; \tilde{\mathbf{m}}^\top\bar{\mathbf{x}}=0\} \quad\Leftrightarrow\quad \{x,y,z \;|\; ax+by+cz+d=0 \} \]

  • \(\tilde{\mathbf{m}}\) can be normalized: \(\tilde{\mathbf{m}}=(n_x, n_y, n_z, d)^\top = (\mathbf{n}, d)^\top\), \(\|\mathbf{n}\|_2=1\) (Hesse normal form)
    • \(\mathbf{n}\) is the normal vector the plane and \(d\) its distance to the origin
images/PlaneHNF.png

  • An exception is the plane at infinity \(\tilde{\mathbf{m}}=(0, 0, 0, 1)^\top\) which passes through all ideal points (=points at infinity) for which \(\tilde{w}=0\)

Plane given by Three Points in \(\mathbb{P}^3\)

  • For a plane \(\tilde{\mathbf{m}}\) that contains the three points \(\tilde{\mathbf{x}}_1,\tilde{\mathbf{x}}_2,\tilde{\mathbf{x}}_3\) (in general position) it must hold \(\tilde{\mathbf{x}}^\top_1\tilde{\mathbf{m}}=\tilde{\mathbf{x}}^\top_2\tilde{\mathbf{m}}=\tilde{\mathbf{x}}^\top_3\tilde{\mathbf{m}}=0\) or \[ \begin{bmatrix} \tilde{\mathbf{x}}^\top_1\\ \tilde{\mathbf{x}}^\top_2\\ \tilde{\mathbf{x}}^\top_3 \end{bmatrix} \tilde{\mathbf{m}} = 0 \]

  • Thus the plane \(\tilde{\mathbf{m}}\) that contains the three points \(\tilde{\mathbf{x}}_1,\tilde{\mathbf{x}}_2,\tilde{\mathbf{x}}_3\) is the right null space of \[ \begin{bmatrix} \tilde{\mathbf{x}}^\top_1\\ \tilde{\mathbf{x}}^\top_2\\ \tilde{\mathbf{x}}^\top_3 \end{bmatrix} = \begin{pmatrix} x_{1_1} & x_{1_2} & x_{1_3} & x_{1_4} \\ x_{2_1} & x_{2_2} & x_{2_3} & x_{2_4} \\ x_{3_1} & x_{3_2} & x_{3_3} & x_{3_4} \end{pmatrix} \]

  • Does that relate to calculating the straight line through two points?

Reminder: Straight Line given by Two Points in \(\mathbb{P}^2\)

  • A line \(\tilde{\mathbf{l}}\) in \(\mathbb{P}^2\) through \(\tilde{\mathbf{x}}_1,\tilde{\mathbf{x}}_2\) (in general position) is given by the right null space of \[ \begin{bmatrix} \tilde{\mathbf{x}}^\top_1\\ \tilde{\mathbf{x}}^\top_2 \end{bmatrix} = \begin{pmatrix} x_{1_1} & x_{1_2} & x_{1_3} \\ x_{2_1} & x_{2_2} & x_{2_3} \end{pmatrix} \] which can be calculated directly by the cross product, i.e. \(\tilde{\mathbf{l}} = \tilde{\mathbf{x}}_1\times \tilde{\mathbf{x}}_2\)

  • As any point \(\tilde{\mathbf{x}}\) on the line \(\tilde{\mathbf{l}}\) is a linear combination of \(\tilde{\mathbf{x}}_1,\tilde{\mathbf{x}}_2\) it must hold \[ \textrm{det} \begin{bmatrix} \tilde{\mathbf{x}}^\top\\ \tilde{\mathbf{x}}^\top_1\\ \tilde{\mathbf{x}}^\top_2 \end{bmatrix} = \textrm{det} \begin{pmatrix} x_{_1} & x_{_2} & x_{_3} \\ x_{1_1} & x_{1_2} & x_{1_3} \\ x_{2_1} & x_{2_2} & x_{2_3} \end{pmatrix} = 0 \]

  • Laplace expansion results in \(0=x_{_1}D_{23} - x_{_2}D_{13} + x_{_3}D_{12}\) with \(D_{ij}=\textrm{det}\begin{pmatrix} x_{1_i} & x_{1_j}\\ x_{2_i} & x_{2_j}\end{pmatrix}\), i.e. \(\tilde{\mathbf{l}} = (D_{23}, -D_{13}, D_{12})^\top\)

Plane given by Three Points in \(\mathbb{P}^3\)

  • As any point \(\tilde{\mathbf{x}}\) on the plane \(\tilde{\mathbf{m}}\) is a linear combination of \(\tilde{\mathbf{x}}_1,\tilde{\mathbf{x}}_2,\tilde{\mathbf{x}}_3\), it must hold \[ \textrm{det} \begin{bmatrix} \tilde{\mathbf{x}}^\top \\ \tilde{\mathbf{x}}^\top_1\\ \tilde{\mathbf{x}}^\top_2\\ \tilde{\mathbf{x}}^\top_3 \end{bmatrix} = \textrm{det} \begin{pmatrix} x_{_1} & x_{_2} & x_{_3} & x_{_4} \\ x_{1_1} & x_{1_2} & x_{1_3} & x_{1_4} \\ x_{2_1} & x_{2_2} & x_{2_3} & x_{2_4} \\ x_{3_1} & x_{3_2} & x_{3_3} & x_{3_4} \end{pmatrix} = 0 \]

  • Laplace expansion results in \[ 0 = x_{_1}D_{234} - x_{_2}D_{134} + x_{_3}D_{124} + x_{_4}D_{123} \quad\textrm{ with }\quad D_{ijk}= \textrm{det} \begin{pmatrix} x_{1_i} & x_{1_j} & x_{1_k}\\ x_{2_i} & x_{2_j} & x_{2_k}\\ x_{3_i} & x_{3_j} & x_{3_k} \end{pmatrix} \] and thus \(\tilde{\mathbf{m}}=(D_{234}, -D_{134}, D_{124}, -D_{123})^\top\)

Example: Plane given by Three non-vanishing Points in \(\mathbb{P}^3\)

  • For the plane \(\tilde{\mathbf{m}}\) through the three non-vanishing points \[ \tilde{\mathbf{x}}_1 = \begin{pmatrix} \mathbf{x}_1 \\ 1 \end{pmatrix}, \quad \tilde{\mathbf{x}}_2 = \begin{pmatrix} \mathbf{x}_2 \\ 1 \end{pmatrix}, \quad \tilde{\mathbf{x}}_3 = \begin{pmatrix} \mathbf{x}_3 \\ 1 \end{pmatrix} \] it holds e.g. \[ D_{234} = \textrm{det} \begin{pmatrix} x_{1_2} & x_{1_3} & 1\\ x_{2_2} & x_{2_3} & 1\\ x_{3_2} & x_{3_3} & 1 \end{pmatrix} = \textrm{det} \begin{pmatrix} x_{1_2}-x_{3_2} & x_{1_3}-x_{3_3} & 0\\ x_{2_2}-x_{3_2} & x_{2_3}-x_{3_3} & 0\\ x_{3_2} & x_{3_3} & 1 \end{pmatrix} = ((\mathbf{x}_1 - \mathbf{x}_3) \times (\mathbf{x}_2 - \mathbf{x}_3))_1 \] and thus \[ \tilde{\mathbf{m}} = \begin{bmatrix} (\mathbf{x}_1 - \mathbf{x}_3)\times (\mathbf{x}_2 - \mathbf{x}_3)\\ -\mathbf{x}^\top_3(\mathbf{x}_1\times \mathbf{x}_2) \end{bmatrix} \]

Duality (in 3D)

The duality principle:

For every proposition of three-dimensional projective geometry there exists a dual proposition which is obtained by interchanging the role of points and planes in the original proposition.

  • Dual are

\[ \begin{array}{ccc} \tilde{\mathbf{x}} & \longleftrightarrow & \tilde{\mathbf{m}}\\[3mm] \tilde{\mathbf{x}}^T\tilde{\mathbf{m}}=0 & \longleftrightarrow & \tilde{\mathbf{m}}^T\tilde{\mathbf{x}}=0\\[3mm] \tilde{\mathbf{x}}\text{ is right null space of }[\tilde{\mathbf{m}}_1,\tilde{\mathbf{m}}_2,\tilde{\mathbf{m}}_3]^\top & \longleftrightarrow & \tilde{\mathbf{m}}\text{ is right null space of }[\tilde{\mathbf{x}}_1,\tilde{\mathbf{x}}_2,\tilde{\mathbf{x}}_3]^\top \end{array} \]

Straight Lines are dual to Straight Lines

Straight Lines in Projective Space \(\mathbb{P}^3\)

  • Representing a straight line in 3D is problematic
    • Straight lines in 3D have 4 DOF
    • Thus they would have to be represented by a homogeneous vector with five elements
    • Are there more suitable representations?
  • Usual representations for straight lines in space are
    • Linear combination of two points
    • Plücker matrices
    • Plücker coordinates
images/Line_Parametrization_3D.svg

Straight Lines in \(\mathbb{P}^3\) as Linear Combination of Points

  • A straight line \(\mathbf{l}\) can be represented as the space spanned by the matrix \(\tilde{\mathbf{W}}\), consisting of points (on a straight line) \(\mathbf{a}\) and \(\mathbf{b}\) \[ \tilde{\mathbf{W}} = \begin{bmatrix} \tilde{\mathbf{a}}^\top \\ \tilde{\mathbf{b}}^\top \end{bmatrix} \]

    • The span of \(\tilde{\mathbf{W}}^\top\) ist the bundle of points \(\lambda\tilde{\mathbf{a}} + \mu\tilde{\mathbf{b}}\) on the straight line \(\mathbf{l}\)
    • The span of the 2-dimensional right null space of \(\tilde{\mathbf{W}}\) is the bundle of planes with the straight line \(\mathbf{l}\) as axis

images/bundle_of_planes.png

Straight Lines in \(\mathbb{P}^3\) as Linear Combination of Planes

  • The dual representation as the right null space of the matrix \[ \tilde{\mathbf{W}}^\ast = \begin{bmatrix} \tilde{\mathbf{p}}^\top \\ \tilde{\mathbf{q}}^\top \end{bmatrix} \] contains the planes \(\mathbf{p}\) and \(\mathbf{q}\), that intersect in the straight line \(\mathbf{l}\)

    • The span of \({\tilde{\mathbf{W}}^\ast}^\top\) ist the bundle of planes \(\lambda^\prime\tilde{\mathbf{p}} + \mu^\prime\tilde{\mathbf{q}}\) with the axis \(\mathbf{l}\)
    • The span of the 2-dimensional right null space of \(\tilde{\mathbf{W}}^\ast\) is the bundle of points on the straight line \(\mathbf{l}\) as axis

images/bundle_of_planes.png
  • Relationship between the two representations: \(\tilde{\mathbf{W}}^\ast\tilde{\mathbf{W}}^\top = \tilde{\mathbf{W}}{\tilde{\mathbf{W}}^\ast}^\top = \mathbf{0}_{2\times 2}\)

Example

  • The \(x\)-axis …

    • … is spannend by the point \(\mathbf{a}=(0,0,0)^\top\) and the direction of the \(x\)-axis \(\mathbf{b}=(1,0,0)^\top\) and thus \[ \tilde{\mathbf{W}}=\begin{pmatrix}0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{pmatrix} \]

    • … is the right null space of the \(xy\)-plane \(\tilde{\mathbf{p}}=(0,0,1,0)^\top\) and the \(xz\)-plane \(\tilde{\mathbf{p}}=(0,1,0,0)^\top\) and thus \[ \tilde{\mathbf{W}}^\ast=\begin{pmatrix}0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0\end{pmatrix} \]

Union and Intersection of Points, Lines and Planes

  • The plane \(\tilde{\mathbf{m}}\), given by the union of the straight line \(\tilde{\mathbf{W}}\) with the point \(\tilde{\mathbf{x}}\) is the right null space of the matrix \(\tilde{\mathbf{M}}\), containing \(\tilde{\mathbf{W}}\) and \(\tilde{\mathbf{x}}\), i.e. \[ \tilde{\mathbf{M}}\tilde{\mathbf{m}} = \mathbf{0}\quad\textrm{ with }\quad \tilde{\mathbf{M}} = \begin{bmatrix}\tilde{\mathbf{W}} \\ \tilde{\mathbf{x}}^\top\end{bmatrix} \]
images/union_of_line_and_point.png
  • The point \(\tilde{\mathbf{x}}\), given by the intersection of the plane \(\tilde{\mathbf{m}}\) and the straight line \(\tilde{\mathbf{W}}^\ast\) is the right null space of the matrix \(\tilde{\mathbf{M}}\), containing \(\tilde{\mathbf{W}}^\ast\) and \(\tilde{\mathbf{m}}\), i.e. \[ \tilde{\mathbf{M}}\tilde{\mathbf{x}} = \mathbf{0}\quad\textrm{ with }\quad \tilde{\mathbf{M}} = \begin{bmatrix}\tilde{\mathbf{W}}^\ast \\ \tilde{\mathbf{m}}^\top\end{bmatrix} \]
images/intersection_of_plane_and_line.png

Example

  • The plane \(\tilde{\mathbf{m}}\), given by the union of the straight line \(\tilde{\mathbf{W}}=\begin{pmatrix}0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{pmatrix}\) and the point \((0,0,1)^\top\) is the right null space of \[ \tilde{\mathbf{M}}=\begin{pmatrix}0 & 0 & 0 & 1 \\1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1\end{pmatrix}\quad\text{which results in } \tilde{\mathbf{m}} = (0,1,0,0)^\top \]

  • The point \(\tilde{\mathbf{p}}\), given by the intersection of the plane \(z=1\) and the straight line \(\tilde{\mathbf{W}}^\ast=\begin{pmatrix}0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0\end{pmatrix}\) is the right null space of \[ \tilde{\mathbf{M}}=\begin{pmatrix}0 & 0 & 1 & 0 \\0 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1\end{pmatrix}\quad\text{which results in } \tilde{\mathbf{p}} = (1,0,0,0)^\top \]

Plücker Coordinates

  • For the line given by the two points \(\mathbf{a},\mathbf{b}\) it holds \(\tilde{\mathbf{W}} = \begin{bmatrix}\tilde{\mathbf{a}}^\top\\ \tilde{\mathbf{b}}^\top\end{bmatrix}, \; \textrm{rank}(\tilde{\mathbf{W}}) = 2\)

  • For two other points \(\mathbf{a}^\prime,\mathbf{b}^\prime\) on the same line \(\mathbf{l}\) it holds \[ \tilde{\mathbf{W}}^\prime = \begin{bmatrix}\tilde{\mathbf{a}^\prime}^\top\\ \tilde{\mathbf{b}^\prime}^\top\end{bmatrix}, \; \textrm{rank}(\tilde{\mathbf{W}}^\prime) = 2\;\textrm{ and }\; \tilde{\mathbf{W}}^\prime = \Lambda\tilde{\mathbf{W}}\; \textrm{ with } \Lambda = \begin{pmatrix}\lambda_{11} & \lambda_{12} \\ \lambda_{21} & \lambda_{22}\end{pmatrix}, \; \textrm{det}(\Lambda) \not= 0 \]

  • In particular we get \[ \begin{pmatrix} a^\prime_{i} & b^\prime_{i}\\ a^\prime_{j} & b^\prime_{j} \end{pmatrix} = \begin{pmatrix} \lambda_{1,1} & \lambda_{1,2}\\ \lambda_{2,1} & \lambda_{2,2} \end{pmatrix} \begin{pmatrix} a_{i} & b_{i}\\ a_{j} & b_{j} \end{pmatrix} \;\Longrightarrow\; \textrm{det}\begin{pmatrix} a^\prime_{i} & b^\prime_{i}\\ a^\prime_{j} & b^\prime_{j} \end{pmatrix} =\textrm{det}\Lambda\cdot \underbrace{\textrm{det}\begin{pmatrix} a_{i} & b_{i}\\ a_{j} & b_{j} \end{pmatrix}}_{=:l_{ij}},\;\; i,j=1,\ldots, 4 \]

  • As \(l_{ii}=0\), \({4 \choose 2} = 6\) independent quantities remain: \((l_{12} :l_{13} :l_{14} :l_{23} :l_{24} :l_{34})\)

Plücker Matrix

  • The Plücker Matrix \(\tilde{\mathbf{L}}\) describes the straight line through the two points \(\mathbf{a}, \mathbf{b}\): \[ \tilde{\mathbf{L}} = \tilde{\mathbf{a}}\tilde{\mathbf{b}}^\top - \tilde{\mathbf{b}}\tilde{\mathbf{a}}^\top = \begin{pmatrix} 0 & l_{12} & l_{13} & l_{14} \\ -l_{12} & 0 & l_{23} & l_{24} \\ -l_{13} & -l_{23} & 0 & l_{34} \\ -l_{14} & -l_{24} & -l_{34} & 0 \end{pmatrix}, \; i.e. \; l_{ij} = a_i b_j - b_i a_j \]

  • Example: Representing the \(x\)-axis as Plücker matrix, defined by the two points \(\tilde{\mathbf{a}}=(0,0,0,1)^\top\) and \(\tilde{\mathbf{b}}=(1,0,0,0)^\top\): \[ \tilde{\mathbf{L}} = \begin{pmatrix}0 \\ 0 \\ 0 \\ 1\end{pmatrix} (1,0,0,0) - \begin{pmatrix}1 \\ 0 \\ 0 \\ 0\end{pmatrix} (0,0,0,1) = \begin{pmatrix} 0 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix} \]

Properties of Plücker Matrices

  • \(\tilde{\mathbf{L}}\) is a skew symmetric homogeneous \(4 \times 4\) Matrix

  • \(\textrm{rank}(\mathbf{L}) = 2\)

    • \(2\)-dim null space is the bundle of planes defined by the straight line (it holds \(\tilde{\mathbf{L}}{\tilde{\mathbf{W}}^\ast}^\top = \mathbf{0}_{4\times 2}\))

  • 4 DOF

    • 6 independet entries - homogenity - det(\(\tilde{\mathbf{L}}=0\))

  • \(\tilde{\mathbf{L}} = \tilde{\mathbf{a}}\tilde{\mathbf{b}}^\top - \tilde{\mathbf{b}}\tilde{\mathbf{a}}^\top\)

    • gereralization of the crossproduct to 4D space (6 subdeterminants of \([\tilde{\mathbf{a}},\tilde{\mathbf{b}}]\))

  • \(\tilde{\mathbf{L}}\) is independent of the choice of \(\mathbf{a}, \mathbf{b}\) on the line, as for any \(\tilde{\mathbf{c}} = \tilde{\mathbf{a}} + \mu \tilde{\mathbf{b}}\) it holds \[ \tilde{\mathbf{L}}^\prime = \tilde{\mathbf{a}}\tilde{\mathbf{c}}^\top - \tilde{\mathbf{c}}\tilde{\mathbf{a}}^\top = \tilde{\mathbf{a}}(\tilde{\mathbf{a}}^\top + \mu\tilde{\mathbf{b}}^\top) - (\tilde{\mathbf{a}} + \mu\tilde{\mathbf{b}})\tilde{\mathbf{a}}^\top = \tilde{\mathbf{a}}\tilde{\mathbf{b}}^\top - \tilde{\mathbf{b}}\tilde{\mathbf{a}}^\top = \tilde{\mathbf{L}} \]

  • If \(\tilde{\mathbf{x}}^\prime=\tilde{\mathbf{H}}\tilde{\mathbf{x}}\) is a point transform, the Plücker Matrix is transformed by \(\tilde{\mathbf{L}}^\prime=\tilde{\mathbf{H}}\tilde{\mathbf{L}}\tilde{\mathbf{H}}^\top\)

Dual Plücker Matrices

  • The dual Plücker matrix \(\tilde{\mathbf{L}}^\ast = \tilde{\mathbf{p}}\tilde{\mathbf{q}}^\top - \tilde{\mathbf{q}}\tilde{\mathbf{p}}^\top\) describes the intersection of planes \(\tilde{\mathbf{p}},\tilde{\mathbf{q}}\)

  • Transformation ot the dual Plücker matrix \(\tilde{\mathbf{L}}^\ast\) with the homography \(\tilde{\mathbf{H}}\) is given by \((\tilde{\mathbf{H}}^{-1})^\top\tilde{\mathbf{L}}^\ast\tilde{\mathbf{H}}^{-1}\)

  • Relationship between the Plücker matrix \(\tilde{\mathbf{L}}\) and its dual \(\tilde{\mathbf{L}}^\ast\): \[ l_{12}:l_{13}:l_{13}:l_{23}:l_{42}:l_{34} = l_{34}^\ast:l_{42}^\ast:l_{23}^\ast:l_{14}^\ast:l_{13}^\ast:l_{12}^\ast \]

  • Union and Incidence

    • Plane through point and straight line: \(\tilde{\mathbf{m}}=\tilde{\mathbf{L}}^\ast\tilde{\mathbf{x}}\)
    • Point on straight line: \(\tilde{\mathbf{L}}^\ast\tilde{\mathbf{x}} = \mathbf{0}\)
    • Intersection between plane and straight line: \(\tilde{\mathbf{x}}=\tilde{\mathbf{L}}\tilde{\mathbf{m}}\)
    • Straight line in plane: \(\tilde{\mathbf{L}}^\ast\tilde{\mathbf{m}} = \mathbf{0}\)
    • Coplanar straight lines: \([\tilde{\mathbf{L}}_1,\tilde{\mathbf{L}}_2,...]\tilde{\mathbf{x}} = \mathbf{0}\)

Example: Intersection and the Plücker Matrix

  • For the intersection \(\tilde{\mathbf{x}}\) of the \(x\)-axis with the plane \(x=1\) it holds \(\tilde{\mathbf{x}} = \tilde{\mathbf{L}}\tilde{\mathbf{m}}\) and thus

\[ \tilde{\mathbf{x}} = \begin{pmatrix} 0 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 0\\ -1 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \end{pmatrix} \]

Plücker Coordinates for non-vanishing Points

  • For non-vanishing points \(\mathbf{a},\mathbf{b}\), i.e. \(\tilde{\mathbf{a}}=(a_1,a_2,a_3,1)^\top, \tilde{\mathbf{b}}=(b_1,b_2,b_3,1)^\top\) it holds \[ (l_{41}, l_{42}, l_{43})^\top = \mathbf{b}-\mathbf{a} \quad\textrm{and}\quad (l_{23}, l_{31}, l_{12})^\top = \mathbf{a}\times\mathbf{b} \]

  • The \(l_{ij}\) can be interpreted as a homogeneous vector \[ \tilde{\mathbf{l}} = (l_{41}, l_{42}, l_{43},l_{23}, l_{31}, l_{12})^\top \in \mathbb{P}^5 \]

    • They are called Plücker coordinates if the condition \(\textrm{det}(L)=0\) holds, i.e. if \[ (l_{41}, l_{42}, l_{43}) (l_{23}, l_{31}, l_{12})^\top = l_{41}l_{23} + l_{42}l_{31} + l_{43}l_{12} = 0 \] (only then the vector represents a straight line)

Properties for Plücker Coordinates

  • For the two straight lines \(\tilde{\mathbf{l}}^1 = ( \underbrace{l_{41}^1,l_{42}^1,l_{43}^1}_{\mathbf{u}_1},\underbrace{l_{23}^1,l_{31}^1,l_{12}^1}_{\mathbf{v}_1} ),\; \tilde{\mathbf{l}}^2 = ( \underbrace{l_{41}^2,l_{42}^2,l_{43}^2}_{\mathbf{u}_2},\underbrace{l_{23}^2,l_{31}^2,l_{12}^2}_{\mathbf{v}_2})\) through points \(\mathbf{a}_1,\mathbf{b}_1\) and \(\mathbf{a}_2,\mathbf{b}_2\) it holds:

    • \(\tilde{\mathbf{l}}^1\) and \(\tilde{\mathbf{l}}^2\) are coplanar (intersect) iff, the four points are coplanar, i.e. iff \[ \begin{eqnarray*} \textrm{det}( \mathbf{\tilde a_1}, \mathbf{\tilde b_1}, \mathbf{\tilde a_2}, \mathbf{\tilde b_2} ) &=& l^1_{41}l^2_{23} + l^1_{42}l^2_{31} + l^1_{43}l^2_{12} + l^1_{23}l^2_{41} + l^1_{31}l^2_{42} + l^1_{12}l^2_{43}\\ &=& \mathbf{u}_1\mathbf{v}_2+ \mathbf{u}_2\mathbf{v}_1 =0 \end{eqnarray*} \]

      • If \(\mathbf{u}_1\mathbf{v}_1+\mathbf{u}_2\mathbf{v}_2<0\) then \(\tilde{\mathbf{l}}^1\) passes \(\tilde{\mathbf{l}}^2\) counter clockwise

      • If \(\mathbf{u}_1\mathbf{v}_1+\mathbf{u}_2\mathbf{v}_2>0\) then \(\tilde{\mathbf{l}}^1\) passes \(\tilde{\mathbf{l}}^2\) counter clockwise

Euclidean Transformations in \(\mathbb{P}^3\)

  • Euclidean transformations in \(\mathbb{P}^3\) have 6 DOF

    • Translation around the vector \(\mathbf{T}=(t_x, t_y, t_z)^\top\), with homogeneous transformation matrix \[ \begin{pmatrix} 1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1 \end{pmatrix} = \begin{bmatrix} \mathbf{I} & \mathbf{T} \\ \mathbf{0}^\top & 1 \end{bmatrix} \]

    • (Euler) Rotations around the \(x,y,z\)-Axis, i.e. \(\mathbf{R}=\mathbf{R}_z\mathbf{R}_y\mathbf{R}_x\) with homogeneous transformation matrix \[ \begin{pmatrix} r_{11} & r_{12} & r_{13} & 0 \\ r_{21} & r_{22} & r_{23} & 0 \\ r_{31} & r_{32} & r_{33} & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} = \begin{bmatrix} \mathbf{R} & \mathbf{0} \\ \mathbf{0}^\top & 1 \end{bmatrix} \]

    • General homogeneous representation of Euclidean transformations \[ \mathbf{\tilde{x}}^\prime = \mathbf{H}_{E}\mathbf{\tilde{x}} = \begin{bmatrix}\mathbf{R} & \mathbf{T} \\ \mathbf{0}^\top & 1\end{bmatrix}\mathbf{\tilde{x}}\quad\text{with}\quad \mathbf{R}^\top\mathbf{R} = \mathbf{I}\quad\text{and}\quad \text{det}(\mathbf{R}) = 1 \]

Rotations in \(\mathbb{R}^3\)

images/Rotations_in_3D.png

Rotations in \(\mathbb{R}^3\) at a given Point \(\mathbf{p}\)

  1. Translate object such that the point \(\mathbf{p}\) goes to the origin (using matrix \(\mathbf{T}\))
  2. Rotate object (using matrix \(\mathbf{R}\))
  3. Translate object back to point \(\mathbf{p}\) (using matrix \(\mathbf{T}^{-1}\))

\[ \mathbf{M} = \mathbf{T}^{-1}\cdot \mathbf{R} \cdot \mathbf{T} = \begin{bmatrix}\mathbf{I} & \mathbf{p} \\ \mathbf{0}^\top & 1\end{bmatrix} \begin{bmatrix}\mathbf{R} & \mathbf{0} \\ \mathbf{0}^\top & 1\end{bmatrix} \begin{bmatrix}\mathbf{I} & -\mathbf{p} \\ \mathbf{0}^\top & 1\end{bmatrix} = \begin{bmatrix}\mathbf{R} & (\mathbf{I}-\mathbf{R})\mathbf{p} \\ \mathbf{0}^\top & 1\end{bmatrix} \]

Euler Rotations

  • Rotations around the \(x,y,z\) axis are called Euler Rotations and \(\alpha, \beta, \gamma\) Euler Angles
  • Drawbacks of Euler Rotations
    • Order matters \(R(\alpha)\cdot R(\beta)\cdot R(\gamma) \not= R(\gamma)\cdot R(\beta)\cdot R(\alpha)\)
    • Not unique, i.e. \(R(\alpha)\cdot R(\beta)\cdot R(\gamma)=R(\alpha\pm\pi)\cdot R(\beta\pm\pi)\cdot R(\gamma\pm\pi)\)
    • Gimbal Lock
      • Rotations of \(\pi / 2\) can lead to interference of two axis
    • Unsuitable for animation and optimization
      • No meaningful interpolation of two orientations

images/GimbalLock.png

Angle-Axis Rotations

images/Angle_Axis_Rotations.png

Some Recap of (Rotation with) Complex Numbers

images/Rotation_with_complex_numbers.png

Quaternions

images/Quaternions.png

Some important Properties of Quaternions

  • Addition (associative, commutative, neutral element is \(\mathbf{0}=[0,(0,0,0)]\)) \(\mathbf{q}_1+\mathbf{q}_2 = [s_1+s_2, \mathbf{v}_1+\mathbf{v}_2]\)

  • Multiplication (not commutative, neutral element is \(\mathbf{1}=[1,(0,0,0)]\)) \(\mathbf{q}_1\cdot\mathbf{q}_2 = [s_1\cdot s_2 - \langle \mathbf{v}_1,\mathbf{v}_2\rangle,\; s_1\mathbf{v}_2 + s_2\mathbf{v}_1 + \mathbf{v}_1\times \mathbf{v}_2]\)

  • Distributive
    \(\mathbf{q}(\mathbf{r}+\mathbf{s}) = \mathbf{q}\mathbf{r}+\mathbf{q}\mathbf{s} \quad\text{ and }\quad (\mathbf{r}+\mathbf{s})\mathbf{q} = \mathbf{r}\mathbf{q}+\mathbf{s}\mathbf{q}\)

  • Length
    \(\|\mathbf{q}\| = \sqrt{s^2+x^2+y^2+z^2}\)

  • Conjugate
    \(\bar{\mathbf{q}} = [s, -\mathbf{v}]\quad \text{ with }\quad \mathbf{q}\cdot\bar{\mathbf{q}} = s^2 + \|\mathbf{v}\|^2 = \|\mathbf{q}\|^2\)

  • Inverse
    \(\mathbf{q}^{-1} = \|\mathbf{q}\|^{-2}\cdot\bar{\mathbf{q}}\quad (\|\mathbf{q}\|=1\;\Longrightarrow\; \mathbf{q}^{-1} = \bar{\mathbf{q}})\)

Quaternions and Rotation

  • A rotation around the axis \(\mathbf{v}\) and the the angle \(\varphi\) can be described by a unit quaternion \[ \mathbf{q} = \left[\cos\frac{\varphi}{2},\sin\frac{\varphi}{2}\cdot \mathbf{v}\right], \; \|\mathbf{q}\| = 1 \]

  • Rotating a point \(\mathbf{p}\) with a quaternion \(\mathbf{q}\) is done by \[ R(\mathbf{p}) = \mathbf{q}\cdot\mathbf{p}_q\cdot\bar{\mathbf{q}}\;\text{ with }\; \mathbf{p}_q = [0, \mathbf{p}] \]

  • Quaternions \(\mathbf{q}\) and \(-\mathbf{q}\) (opposite direction and angle) describe the same roation, as \[ -\mathbf{q}\cdot\mathbf{p}_q\cdot\overline{-\mathbf{q}} = -1\cdot\mathbf{q}\cdot\mathbf{p}_q\cdot\overline{(-1\cdot\mathbf{q})} = -1\cdot\mathbf{q}\cdot\mathbf{p}_q\cdot-1\cdot\bar{\mathbf{q}} = \mathbf{q}\cdot\mathbf{p}_q\cdot\bar{\mathbf{q}} \]

  • Concatenation of rotations \[ R_2(R_1(\mathbf{p})) = \mathbf{q}_2\cdot(\mathbf{q}_1\cdot\mathbf{p}_q\cdot\bar{\mathbf{q}}_1)\cdot\bar{\mathbf{q}}_2 = (\mathbf{q}_2\cdot\mathbf{q}_1)\cdot\mathbf{p}_q\cdot\overline{(\mathbf{q}_1\cdot\mathbf{q}_2)} \]

SLERP (Spherical Linear intERPolation)

images/SLERP.png

Similarity Transformations in \(\mathbb{P}^3\)

  • Euclidean transformations and isotropic scaling (7 DOF)
    • Homogenous matrix vector representation
    \[ \begin{pmatrix} x^\prime \\ y^\prime \\ z^\prime \\ 1 \end{pmatrix} = \begin{bmatrix} \begin{pmatrix} s & 0 & 0 \\ 0 & s & 0 \\ 0 & 0 & s \end{pmatrix} \cdot \begin{pmatrix} r_{11} & r_{12} & r_{13} \\ r_{21} & r_{22} & r_{23} \\ r_{31} & r_{32} & r_{33} \end{pmatrix} & \mathbf{T} \\ \mathbf{0}^\top & 1 \end{bmatrix} \begin{pmatrix} x \\ y \\ z \\ 1 \end{pmatrix} \] or \(\mathbf{\tilde{x}}^\prime = \mathbf{H}_S\mathbf{\tilde{x}} =\begin{bmatrix}s\mathbf{R} & \mathbf{T} \\ \mathbf{0}^\top & 1\end{bmatrix}\mathbf{\tilde{x}}\;\;\) with \(\;\;\mathbf{R}^\top\mathbf{R} =\mathbf{I}\;\;\) (and \(\;\text{det}(\mathbf{R}) = 1)\)

Special Affine Transformations in \(\mathbb{P}^3\)

  • Similarity transformations and anisotropic scaling (9 DOF)
    • Homogenous matrix vector representation \[ \begin{pmatrix} x^\prime \\ y^\prime \\ z^\prime \\ 1 \end{pmatrix} = \begin{bmatrix} \begin{pmatrix} s_x & 0 & 0 \\ 0 & s_y & 0 \\ 0 & 0 & s_z \end{pmatrix} \cdot \begin{pmatrix} r_{11} & r_{12} & r_{13} \\ r_{21} & r_{22} & r_{23} \\ r_{31} & r_{32} & r_{33} \end{pmatrix} & \mathbf{T} \\ \mathbf{0}^\top & 1 \end{bmatrix} \begin{pmatrix} x \\ y \\ z \\ 1 \end{pmatrix} \]

Special Affine Transformations in \(\mathbb{P}^3\)

images/Special_Affine_Trafo_2.png

Affine Transformations in \(\mathbb{P}^3\)

  • General affine transformation (12 DOF)
    • Homogeneous matrix vector representation \[ \begin{pmatrix} x^\prime \\ y^\prime \\ z^\prime \\ 1 \end{pmatrix} = \begin{pmatrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \\ 1 \end{pmatrix} \] can be written in the form (see also camera models) \[ \begin{pmatrix} x^\prime \\ y^\prime \\ z^\prime \\ 1 \end{pmatrix} = \begin{bmatrix} \begin{pmatrix} b_{11} & b_{12} & b_{13} \\ 0 & b_{22} & b_{23} \\ 0 & 0 & b_{33} \end{pmatrix} \cdot & [\mathbf{R}\;\; \mathbf{T}] \\ \mathbf{0}^\top & 1 \end{bmatrix} \begin{pmatrix} x \\ y \\ z \\ 1 \end{pmatrix} \] or \(\mathbf{\tilde{x}}^\prime = \mathbf{H}_A\mathbf{\tilde{x}} =\begin{bmatrix}\mathbf{A} & \mathbf{T} \\ \mathbf{0}^\top & 1\end{bmatrix}\mathbf{\tilde{x}}\)

Projective Transformations in \(\mathbb{P}^3\)

  • General projective transformation (15 DOF)
    • Homogeneous matrix vector representation \[ \begin{pmatrix} x^\prime \\ y^\prime \\ z^\prime \\ w^\prime \end{pmatrix} = \begin{pmatrix} p_{11} & p_{12} & p_{13} & p_{14} \\ p_{21} & p_{22} & p_{23} & p_{24} \\ p_{31} & p_{32} & p_{33} & p_{34} \\ p_{41} & p_{42} & p_{43} & 1 \end{pmatrix} \begin{pmatrix} x \\ y \\ z \\ w \end{pmatrix} \] can be written in the form \[ \begin{pmatrix} x^\prime \\ y^\prime \\ z^\prime \\ w^\prime \end{pmatrix} = \begin{bmatrix} \begin{pmatrix} b_{11} & b_{12} & b_{13} \\ 0 & b_{22} & b_{23} \\ 0 & 0 & b_{33} \end{pmatrix} \cdot & [\mathbf{R}\;\; \mathbf{T}] \\ \begin{matrix} p_{41} & p_{42} & p_{43} \end{matrix} & 1 \end{bmatrix} \begin{pmatrix} x \\ y \\ z \\ w \end{pmatrix} \] or \(\mathbf{\tilde{x}}^\prime = \mathbf{H}\mathbf{\tilde{x}} =\begin{bmatrix}\mathbf{A} & \mathbf{T} \\ p_{41}\;\; p_{42}\;\; p_{43} & 1\end{bmatrix}\mathbf{\tilde{x}}\)

Overview of 3D Transformations


Transformation Matrix # DOF Preserves
translation \([\mathbf{I\quad t}]_{3\times 4}\) 3 orientation
rigid (Euclidean) \([\mathbf{R\quad t}]_{3\times 4}\) 6 length
similarity \([s\mathbf{R\quad t}]_{3\times 4}\) 7 angles
affine \([\mathbf{A\quad t}]_{3\times 4}\) 12 parallelism
projective \([\mathbf{H}]_{4\times 4}\) 15 straight lines
  • 3D transformations are defined analogously to 2D transformations
  • \(3\times 4\) matrices are extended with a fourth \([\mathbf{0}^\top 1]\) row for homogeneous transforms

Transformations on Co-Vectors

If a point \(\tilde{\mathbf{x}}\) is transformed by a perspective 2D (3D) transformation \(\tilde{\mathbf{H}}\) as \[ \tilde{\mathbf{x}}^\prime = \tilde{\mathbf{H}}\tilde{\mathbf{x}} \] for a transformed 2D line (3D Plane) it must hold \[ 0= {\tilde{\mathbf{l}}^\prime}^\top \tilde{\mathbf{x}}^\prime = {\tilde{\mathbf{l}}^\prime}^\top \tilde{\mathbf{H}}\tilde{\mathbf{x}} = (\tilde{\mathbf{H}}^\top \tilde{\mathbf{l}}^\prime)^\top \tilde{\mathbf{x}} = \tilde{\mathbf{l}}^\top\tilde{\mathbf{x}} \] and therefore \[ \tilde{\mathbf{l}}^\prime = \tilde{\mathbf{H}}^{-\top}\tilde{\mathbf{l}} \]

Thus, the action of a projective transformation on a co-vector such as a 2D line or 3D plane can be represented by the transposed inverse of the matrix.

The transformation on a 3D line \(\tilde{\mathbf{L}}\) is given by \(\tilde{\mathbf{H}}\tilde{\mathbf{L}}\tilde{\mathbf{H}}^\top\)

Plane at infinity

  • If points on \(\tilde{\mathbf{m}}_\infty = (0,0,0,1)^\top\) are mapped by an affine transformation \(\tilde{\mathbf{H}}\) it holds \[ \tilde{\mathbf{m}}_\infty^\prime = (\tilde{\mathbf{H}}^{-1})^\top \tilde{\mathbf{m}}_\infty = \begin{bmatrix} \mathbf{A}^{-\top} & 0 \\ -\mathbf{T}^{\top}\mathbf{A}^{-\top} & 1 \end{bmatrix} \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} = \tilde{\mathbf{m}}_\infty \]

  • The plane at infinity \(\tilde{\mathbf{m}}_\infty = (0,0,0,1)^\top\) is fixed under \(\mathbf{H}\), iff \(\mathbf{H}\) is an affine transform

  • Properties of the plane at infinity

    • Canonical position \(\tilde{\mathbf{m}}_\infty = (0,0,0,1)^\top\)
    • Contains the directions (vanishing points)
    • Two planes are parallel iff their intersection line \(\tilde{\mathbf{l}}_\infty=(x_1, x_2, x_3, 0)^\top\) is in \(\tilde{\mathbf{m}}_\infty\)
    • A straight line is parallel to a straight line (or a plane) iff its intersection is in \(\tilde{\mathbf{m}}_\infty\)