• Organization
• Prerequisites
• Introduction to Computer Vision
• History of Computer Vision

• 1D Transformations

• Primitives and Transformations

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

• Embedding of the projective line \(\mathbb{P}^1\) in \(\mathbb{R}^2\)

• In \(\mathbb{P}^1\) it holds

• In \(\mathbb{P}^1\) it holds

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.

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 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}}\) so that \(\tilde{\mathbf{l}} = (n_x, n_y, d)^\top = (\mathbf{n}, d)^\top\) with \(\|\mathbf{n}\|_2=1\). In this case, \(\mathbf{n}\) is the normal vector perpendicular to the line and \(d\) is its distance to the origin.
  
• An exception it the line at infinity \(\tilde{\mathbf{l}}_\infty=(0,0,1)^\top\) which passes through all ideal points.

The cross product can be writen as the product of a skew-symmetric matrix and a vector: \[ \mathbf{a}\times\mathbf{b} = [\mathbf{a}]_\times \mathbf{b} = \underbrace{\begin{bmatrix} 0 & -a_3 & a_2 \\ a_3 & 0 & -a_1 \\ -a_2 & a_1 & 0 \end{bmatrix}}_{\text{skew-symmetric matrix $[\mathbf{a}]_\times$, i.e. $[\mathbf{a}]_\times^\top = -[\mathbf{a}]_\times$ }} \begin{pmatrix} b_1 \\ b_2 \\ b_3 \end{pmatrix} = \begin{pmatrix} a_2b_3 - a_3b_2 \\ a_3b_1 - a_1b_3 \\ a_1b_2 - a_2b_1 \end{pmatrix} \] with

• \(Rank([\mathbf{a}]_\times) = 2\)
  • \([\mathbf{a}]_\times\) maps to the subspace that is perpendicular to \(\mathbf{a}\)
  • The null vector of \([\mathbf{a}]_\times\) is \(\mathbf{a}\) itself, i.e.  \([\mathbf{a}]_\times\cdot\mathbf{a} = \mathbf{0}\) and \(\mathbf{a}^\top\cdot [\mathbf{a}]_\times = \mathbf{0}^\top\)
• Repeated vector products: \([\mathbf{a}]_\times^2 = \mathbf{a}\cdot\mathbf{a}^\top - (\mathbf{a}^\top\cdot\mathbf{a})\cdot \mathbf{I}\) and \([\mathbf{a}]_\times^3 = -(\mathbf{a}^\top\cdot\mathbf{a})\cdot [\mathbf{a}]_\times\)
  • For \(\|\mathbf{a}\|=1\) it holds \([\mathbf{a}]_\times^3 =-[\mathbf{a}]_\times\)

In homogeneous coordinates, the intersection of two lines is given by \[ \tilde{\mathbf{x}} = \tilde{\mathbf{l}}_1 \times \tilde{\mathbf{l}}_2 = [\tilde{\mathbf{l}}_1]_ {\times} \tilde{\mathbf{l}}_2 \]

In homogeneous coordinates, the line joining two points is also given by \[ \tilde{\mathbf{l}} = \tilde{\mathbf{x}}_1 \times \tilde{\mathbf{x}}_2 = [\tilde{\mathbf{x}}_1]_{\times} \tilde{\mathbf{x}}_2 \]

• The intersection of parallel lines \(\mathbf{l}=(a,b,c)^\top\) and \(\mathbf{l}^\prime=(a,b,c^\prime)^\top\) are points at infinity (vanishing points) \[[\mathbf{l}]_{\times}\mathbf{l^\prime}= \left( \begin{array}{ccc} 0 & -c & b\\ c & 0 & -a\\ -b & a & 0 \end{array} \right) \left( \begin{array}{c} a \\ b \\ c^\prime \end{array} \right) = \left( \begin{array}{c} b(c^\prime - c) \\ a(c-c^\prime ) \\ 0 \end{array} \right) \sim \left( \begin{array}{r} b \\ -a \\ 0 \end{array} \right) \]
  • Vanishing points: \((x_1, x_2, 0)^\top\)
  • Vanishing line: \(\mathbf{l}_\infty = (0,0,1)^\top\)
• An alternative definition of \(\mathbb{P}^2\) is \(\mathbb{P}^2 = \mathbb{R}^2 \cup \mathbf{l}_{\infty}\)
  • Note that \(\mathbb{P}^2\) does not distinguish between vanishing points and other points

The duality principle:

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

• Using homogeneous representations allows to easily chain/invert transformations
• Augmented vectors \(\bar{\mathbf{x}}\) can always be replaced by general homogeneous vectors \(\tilde{\mathbf{x}}\)

• \(\mathbf{R}\in SO(2)\) is an orthonormal matrix with \(\mathbf{R}\mathbf{R}^\top=\mathbf{I}\) and \(\text{det} (\mathbf{R})=1\) (rotation matrix)
• Euclidean transformations preserve Euclidean distances and angles

• \(\mathbf{R}\in SO(2)\) is rotation matrix and \(s\) an arbitrary scale factor
• Similarity transformations preserve angles

• \(\mathbf{A}\in \mathbb{R}^{2\times 2}\) is an arbitrary \(2\times 2\) matrix
• Parallel lines remain parallel under affine transformations

• \(\tilde{\mathbf{H}}\in \mathbb{R}^{2\times 2}\) is an arbitrary homogeneous \(3\times 3\) matrix (i.e. specified only up to scale)
• Perspective transformations preserve straight lines

• A central projection of on plane onto another can be represented by a homography, i.e. \(\mathbf{\tilde{x}^\prime} = \tilde{\mathbf{H}}\mathbf{\tilde{x}}\)

• The transformation that maps points from a known plane to their current (true) coordinates removes the projective distortion for all points of the same plane

Estimate a homography from a set of 2D correspondences:

Let \(\mathcal{X} = \{\tilde{\mathbf{x}}_i, \tilde{\mathbf{x}}^\prime_i\}^{N}_{i=1}\) denote a set of \(N\) 2D-to-2D correspondences related by \(\tilde{\mathbf{x}}^\prime_i = \tilde{\mathbf{H}}\tilde{\mathbf{x}}_i\)

• As the correspondence vectors are homogeneous, they have the same direction but may differ in magnitude. Thus the correspondences are related by \(\tilde{\mathbf{x}}^\prime_i \times \tilde{\mathbf{H}}\tilde{\mathbf{x}}_i = \mathbf{0}\)

• Using \(\tilde{\mathbf{h}}^\top_k\) to denote the \(k\)’th row of \(\tilde{\mathbf{H}}\), this can be rewritten as a linear equation in \(\tilde{\mathbf{h}}\): \[ \underbrace{ \begin{bmatrix} \mathbf{0}^\top & -\tilde{w}_i^\prime\tilde{\mathbf{x}}_i^\top & \tilde{y}_i^\prime\tilde{\mathbf{x}}_i^\top \\ \tilde{w}_i^\prime\tilde{\mathbf{x}}_i^\top & \mathbf{0}^\top & -\tilde{x}_i^\prime\tilde{\mathbf{x}}_i^\top \\ -\tilde{y}_i^\prime\tilde{\mathbf{x}}_i^\top & \tilde{x}_i^\prime\tilde{\mathbf{x}}_i^\top & \mathbf{0}^\top \end{bmatrix}}_{\mathbf{A}_i} \underbrace{ \begin{bmatrix} \tilde{\mathbf{h}}_1 \\ \tilde{\mathbf{h}}_2 \\ \tilde{\mathbf{h}}_3 \end{bmatrix}}_{\tilde{\mathbf{h}}} = \mathbf{0} \]

  • The last row is linearly dependent (up to scale) on the first two and can be dropped.

Each point correspondence yields two equations. Stacking all equations into a \(2N \times 9\) dimensional matrix \(\mathbf{A}\) leads to the following constrained least squares problem \[ \begin{eqnarray*} \tilde{\mathbf{h}}^* &=& \text{argmin}_{\tilde{\mathbf{h}}} \|\mathbf{A}\tilde{\mathbf{h}}\|_2^2 + \lambda ( \|\tilde{\mathbf{h}}\|_2^2 - 1)\\ &=& \text{argmin}_{\tilde{\mathbf{h}}} \tilde{\mathbf{h}}^\top\mathbf{A}^\top\mathbf{A}\tilde{\mathbf{h}} + \lambda ( \tilde{\mathbf{h}}^\top\tilde{\mathbf{h}} - 1) \end{eqnarray*} \]

• \(\tilde{\mathbf{h}}\) can be fixed to \(\|\tilde{\mathbf{h}}\|_2^2=1\) as \(\tilde{\mathbf{H}}\) is homogeneous (defined up to scale) and the trivial solution \(\tilde{\mathbf{h}}=0\) is not of interest

• The solution to this optimization problem is the singular vector corresponding to the smallest singular value of \(\mathbf{A}\) (the last column of \(\mathbf{V}\) when decomposing \(\mathbf{A}=\mathbf{UDV}^\top\))

• The resulting algorithm is called Direct Linear Transformation

If a point \(\tilde{\mathbf{x}}\) is transformed by a perspective 2D transformation \(\tilde{\mathbf{H}}\) as \[ \tilde{\mathbf{x}}^\prime = \tilde{\mathbf{H}}\tilde{\mathbf{x}} \] for a transformed 2D line 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.

• 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

• Source-to-Target Mapping
  • For each point (pixel) \((u,v)\) in the source image \(\mathbf{I}\), calculate the transformed position \((x_1,x_2,x_3)^\top = \mathbf{H} (u,v,1)^\top\) in the target image \(\mathbf{I}^\prime\)
  • Transformed positions usually do not fall on grid points
  • Not all elements in the target image are hit exactly ones
    • Gaps can occur (enlargement) or information is lost (several target pixels are “hit” by the same source pixel)

• Target-to-Source Mapping
  • For each point (pixel) \((u^\prime, v^\prime)\) in the target image \(\mathbf{I}^\prime\), calculate the corresponding position \((x_1,x_2,x_3)^\top = \mathbf{H}^{-1} (u^\prime, v^\prime,1)^\top\) in the source image \(\mathbf{I}\)
  • Interpolate the corresponding intensities \(\mathbf{I}^\prime(u^\prime, v^\prime)\)
    • All pixel values of the target image are evaluated exactly once
  • To apply \(\mathbf{x}^\prime = \mathbf{H}\mathbf{x}\) on the image \(\mathbf{I}\) you need \(\mathbf{H}^{-1}\)

def transform_image(s_img, H):
    """ s_img : source image
        H     : (projective) mapping """
    h, w = s_img.shape
    t_img = np.zeros((h,w)) # make empty target image
    for t_pos in product(range(h), range(w)):
        s_pos =  np.linalg.inv(H) @ np.array(t_pos+(1,))
        t_img.item(t_pos) = interpolate_value(s_img, s_pos)
    return t_img

• When applying (projective) mappings to images e.g. the (u, v) coordinates of the original image I has to be rounded, to calculate the corresponding gray values
  • Rounding leads to (unwanted) step effects (aliasing)

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

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

• As for 2D lines \(\tilde{\mathbf{m}}\) can be normalized so that \(\tilde{\mathbf{m}}=(n_x, n_y, n_z, d)^\top = (\mathbf{n}, d)^\top\), \(\|\mathbf{n}\|_2=1\)
  • \(\mathbf{n}\) is the normal for the plane and \(d\) its distance to the origin

• 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\)

• 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

When are two vectors \(\vec{a}\) and \(\vec{b}\) perpendicular?

Give the homogenous vector for line through the points \(\vec{x}=(1,2)^\top\) and \(\vec{y}=(3,4)^\top\).

Give the homogenous vector for the intersection of the lines \(x-y+1=0\) and \(x-y-1=0\).

A point is transformed by \(\begin{pmatrix} 3 & 0 & 0 \\ 0 & 2 & 0\\ 0 & 0 & 1 \end{pmatrix}\). What is the proper transformation for lines?