Computer Vision MT25, Homogenous coordinates and homographies

\[\begin{pmatrix} x \\ y \\ 1 \end{pmatrix}\]

(technically this is an element of the equivalence class ${(\lambda x, \lambda y, \lambda) \mid \lambda \in \mathbb R \setminus {0}}$)

\[\begin{pmatrix} 1 & 0 & \delta _ x \\ 0 & 1 & \delta _ y \\ 0 & 0 & 1 \end{pmatrix}\]

\[\begin{pmatrix} s & 0 & 0 \\ 0 & s & 0 \\ 0 & 0 & 1 \\ \end{pmatrix}\]

\[\begin{pmatrix} \cos \theta & -\sin\theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end{pmatrix}\]

\[\begin{pmatrix} 1 & m & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}\]

\[\begin{pmatrix} 1 & 0 & 0 \\ m & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}\]

• Collinearity: points remain collinear if they lie on a straight line,
• Parallelism: lines remain parallel,
• Convexity: convex sets of points remain convex.

\[\begin{pmatrix} a _ {11} & a _ {12} & a _ {13} \\ a _ {21} & a _ {22} & a _ {23} \\ 0 & 0 & 1 \end{pmatrix}^{-1} \begin{pmatrix} x \\ y \\ 1 \end{pmatrix}\]

A transformation of 2D homogeneous coordinates $p$ of the form

\[H\begin{pmatrix}x \\ y \\ z \end{pmatrix} = \begin{pmatrix} h _ {11} & h _ {12} & h _ {13} \\ h _ {21} & h _ {22} & h _ {23} \\ h _ {31} & h _ {32} & h _ {33} \end{pmatrix}\begin{pmatrix}x \\ y \\ z \end{pmatrix}\]

(since these coordinates are actually elements of an equivalence class, the matrix is only defined up to scale, so a homography has $8$ degrees of freedom rather than $9$. Some references rescale to fix $h _ {33} = 1$, but this fails when the true $h _ {33} = 0$, so it is cleaner to keep $h _ {33}$ symbolic and impose $|H| _ F = 1$ instead).

$4$, as long as no $3$ points lie on the same line.

Writing the correspondences down and then collecting them into a linear system, we have

\[\begin{pmatrix} - A _ {x,1} & - A _ {y,1} & -1 & 0 & 0 & 0 & B _ {x,1}A _ {x,1} & B _ {x,1}A _ {y,1} & B _ {x,1} \\ 0 & 0 & 0 & - A _ {x,1} & - A _ {y,1} & -1 & B _ {y,1}A _ {x,1} & B _ {y,1}A _ {y,1} & B _ {y,1} \\ - A _ {x,2} & - A _ {y,2} & -1 & 0 & 0 & 0 & B _ {x,2}A _ {x,2} & B _ {x,2}A _ {y,2} & B _ {x,2} \\ 0 & 0 & 0 & - A _ {x,2} & - A _ {y,2} & -1 & B _ {y,2}A _ {x,2} & B _ {y,2}A _ {y,2} & B _ {y,2} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & - A _ {x,4} & - A _ {y,4} & -1 & B _ {y,4}A _ {x,4} & B _ {y,4}A _ {y,4} & B _ {y,4} \end{pmatrix} \begin{pmatrix} h _ {11}\\ h _ {12}\\ h _ {13}\\ h _ {21}\\ h _ {22}\\ h _ {23}\\ h _ {31}\\ h _ {32}\\ h _ {33} \end{pmatrix} = 0\]

Hence $H$ lies in the null space of this matrix, which can be found via the SVD.

Lines are defined via $ax + by + c = 0$, so taking $l= (a, b, c)^\top$ and $x = (x, y, 1)^\top$, we may write this as

\[l^\top x = 0\]

\[a \times b = \begin{pmatrix} a _ 2 b _ 3 - a _ 3 b _ 2 \\ a _ 3 b _ 1 - a _ 1 b _ 3 \\ a _ 1 b _ 2 - a _ 2 b _ 1 \end{pmatrix} = \begin{bmatrix} 0 & -a _ 3 & a _ 2 \\ a _ 3 & 0 & -a _ 1 \\ -a _ 2 & a _ 1 & 0 \end{bmatrix} \begin{pmatrix} b _ 1 \\ b _ 2 \\ b _ 3 \end{pmatrix} := [a _ \times] b\]

Geometric meaning: $a \times b$ is perpendicular to both $a$ and $b$, with magnitude $ \vert a \vert \, \vert b \vert \,\sin\theta$, equal to the area of the parallelogram spanned by $a$ and $b$.

$u, v$ are equal up to a non-zero scalar multiple.

An affine map has the form $A \pmb x + \pmb t$ for some linear $A$ and translation $\pmb t$. Linear maps preserve linear combinations, and a translation acts uniformly on all points, so two parallel lines $\ell _ 1, \ell _ 2$ are sent to two lines that remain parallel.

A homography includes a perspective component (the bottom row of $H$ is not $(0, 0, 1)$). This causes points at infinity to map to finite points: the vanishing point. Concretely, two lines parallel in the source plane meet at the same point at infinity, but the homography sends that point to a finite vanishing point in the target — so the lines now intersect there. Hence parallelism is not preserved.

What is preserved by a general homography: collinearity, incidence, and the cross-ratio of four collinear points.

• Forward warp $T(x, y) = (x’, y’)$: iterate over each source pixel and write it into the target at $(x’, y’)$. Two problems:
  • Holes: many target pixels are never written (since $T$ may not map any integer source to them).
  • Pile-ups: several source pixels can map to the same target — need to handle collisions.
• Backward warp $T^{-1}(x’, y’) = (x, y)$: iterate over each target pixel and look up its colour from the source. Every target pixel is written exactly once, no holes, no collisions. If the source coordinates are non-integer, interpolate (bilinear, bicubic, etc.).

The backward formulation is just an inverse-and-iterate, and it removes both of the forward-warp pathologies in a single move.

In homogeneous coordinates, each affine transformation is a $3 \times 3$ matrix with bottom row $(0, 0, 1)$. The set of such matrices is closed under matrix multiplication — so composing two affine maps gives another affine map, and we just multiply their matrices.

Ordering: matrix multiplication is non-commutative. For a point $\pmb x$ expressed as a column vector, transformations are applied right-to-left: $R T \pmb x$ means “first translate by $T$, then rotate by $R$”. The example from the lecture:

\[R T = \begin{pmatrix} \cos\theta & -\sin\theta & \delta _ x\cos\theta - \delta _ y\sin\theta \\ \sin\theta & \cos\theta & \delta _ x\sin\theta + \delta _ y\cos\theta \\ 0 & 0 & 1 \end{pmatrix} \ne T R = \begin{pmatrix} \cos\theta & -\sin\theta & \delta _ x \\ \sin\theta & \cos\theta & \delta _ y \\ 0 & 0 & 1 \end{pmatrix}.\]

So “translate then rotate” produces a different image to “rotate then translate”.