# 2D Projective transformations

###### tags: `cvdl2020`

2D projective geometry is the study of properties of the projective plane $P^2$ that are invariant under a group of transformation known as **projectivities**. That is, an invertible mapping from points in $P^2$ to points in $P^2$ that maps lines to lines.

:::success
A projectivity is an invertible mapping $h$ from $P^2$ to itself such that three points $x_1, x_2, x_3$ lie on the same line if and only if $h(x_1),h(x_2),h(x_3)$ do.
:::

A formal mathematical definition is math would be

:::success
A mapping $h: P^2 \rightarrow P^2$ is a projectivity if and only if there exists a non-singular 3x3 matrix $H$ such that, for any point in $P^2$ represented by a vector $x$, it's true that $h(x)=Hx$
:::

Any points in $P^2$ is represented by a homogeneous 3-vector $x$, and $Hx$ is a linear mapping of homogenoeous coordinates.

:::success
In short, Any **invertible** linear transformation of homogeneous coordinates is a **projectivity**.
:::

:::success
Projectivities form a **group（群）** since the inverse of a projectivity is also a projectivity, and so is the composition of two projectivities.
:::

### Projective transformation (=Perspective transform)

A planar projective transformation is a linear transformation on homogeneous 3-vector represented by a **non-singular** 3x3 matrix.
$$
\begin{pmatrix}
x_1' \\
x_2' \\
x_3' \\
\end{pmatrix} =
\begin{bmatrix}
h_{11} & h_{12} & h_{13} \\
h_{21} & h_{22} & h_{23} \\
h_{31} & h_{32} & h_{33} \\
\end{bmatrix}
\begin{pmatrix}
x_1 \\
x_2 \\
x_3 \\
\end{pmatrix}
$$
or briefly,
$$x'=Hx$$

Notice that the matrix H in this equation maay be changed by multiplication by an arbitrary non-zero scale factor without altering the projective transformation.
:::info
Both $x$ and $x'$ are homogeneous coordinate so $x$ can **absorb** any scaling factor derived from matrix $H$
$$
H \sim
\begin{bmatrix}
h_{11}/h_{33} & h_{12}/h_{33} & h_{13}/h_{33} \\
h_{21}/h_{33} & h_{22}/h_{33} & h_{23}/h_{33} \\
h_{31}/h_{33} & h_{32}/h_{33} & 1 \\
\end{bmatrix}
$$
:::

Consqeuently, we say that H is a **homogeneous matrix**. There're **8** independent ratios among the **9** elements of $H$, and it follows that a projective transformation has **8 dof**.

### Example: Removing the projective distortion from a perspective image of a plane
Shape is distorted under perspective imaging. In general, parallel lines on a scene place aren't parallel in the image but instead converge to a finite point. It's possible to undo the projective transformation by computing the inverse transformation and applying it to the image. The process is as follow:

Selecting a section of image corresponding to a planar section of the world. Let the inhomogeneous coordinate of a pair of matching points $x$ and $x'$ in the world and image place be $(x,y)$ and $(x',y')$ respectively.

The projective transformation can be written in inhomogeneous form as:
$$
\begin{pmatrix}
x_1' \\
x_2' \\
x_3' \\
\end{pmatrix} =
\begin{bmatrix}
h_{11} & h_{12} & h_{13} \\
h_{21} & h_{22} & h_{23} \\
h_{31} & h_{32} & h_{33} \\
\end{bmatrix}
\begin{pmatrix}
x \\
y \\
1 \\
\end{pmatrix} =
\begin{bmatrix}
x h_{11} + y h_{12} + h_{13} \\
x h_{21} + y h_{22} + h_{23} \\
x h_{31} + y h_{32} + h_{33} \\
\end{bmatrix}
$$

$$
x' = \frac{x_1'}{x_3'} = \frac{ h_{11} x + h_{12} y + h_{13} }{ h_{31} x + h_{32} y + h_{33} } \\
y' = \frac{x_2'}{x_3'} = \frac{ h_{21} x + h_{22} y + h_{23} }{ h_{31} x + h_{32} y + h_{33} } \\
$$

Each point correspondence $(x,y)$ <-> $(x',y')$ generates two equations for the elements of $H$ as follow:

$$
x' ( h_{31} x + h_{32} y + h_{33} ) = h_{11} x + h_{12} y + h_{13} \\
y' ( h_{31} x + h_{32} y + h_{33} ) = h_{21} x + h_{22} y + h_{23} \\
$$

Notice that these are linear equations for elemnts in $H$. **4** point of correspondence lead to **8** of such linear equations in the entries of $H$, which are sufficient to solve $H$ (since $H$ has 8 dof) up to an insignificant multiplicatiev factor.

The only restriction is that the 4 points must be in "general position", which means that not 3 points are collinear.

The inverse of the transformation $H$ computed in this way is then applied to the whole image to undo the effect of perspective distortion on the selected plane.

Remarks concerning this example are:
- The computation of the rectifying transformation $H$ in this way does not require knowledge of **any** of the camera's parameters or the pose of the plane
- It's not necessary to know coordinates for **4** points in order to remove projective distortion. Other methods require less points of correspondence.

### Transformation of lines
Given $x_1,x_2,x_3$ lie on a line $l$ so $l^T x_i = 0 \ \forall i=1,2,3,...$. Let $H$ be a non-singular 3x3 matrix, and $Hx_i$ be the set of points being transformed. Then, one can verify that all points lies on a transformed line $l' = H^{-T}l$ since $l'^T \ Hx_i = (H^{-T}l)^T \ Hx_i = l^T \ H^{-1} \ Hx_i = 0$

:::success
Under the point transformation $x'=Hx$, a line will be transformed as $l'=H^{-T} \ l$
:::

:::info
Point transform: $x'=H \ x$
Line transform: $l'=H^{-T} \ l$
:::

### Hierarchy of transformation
#### Isometries
Isometries are transformations of the plane $R^2$ that preserve the **Euclidean distance**.

- Orientation-preserving transformation
Also called **Euclidean transformation**, is a composition of translation and rotation.

$$
\begin{pmatrix}
x' \\
y' \\
1' \\
\end{pmatrix} =
\begin{bmatrix}
cos \theta & sin \theta & t_x \\
sin \theta & cos \theta & t_y \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{pmatrix}
x \\
y \\
1 \\
\end{pmatrix}
$$

Or can be written in the following form:

$$
x' = H_{E} =
\begin{bmatrix}
R & t \\
0^T & 1 \\
\end{bmatrix} x
$$

where $R$ si rotation matrix such that $RR^T=R^TR=I$, and $|R|=1$, $t$ is a translation 2-vector

- Orientation-reversing

$$
\begin{pmatrix}
x' \\
y' \\
1' \\
\end{pmatrix} =
\begin{bmatrix}
-cos \theta & sin \theta & t_x \\
-sin \theta & cos \theta & t_y \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{pmatrix}
x \\
y \\
1 \\
\end{pmatrix}
$$

:::info
An isometry is orientation-preserving is the upper left hand 2x2 matrix has determinant 1. Orientation-preserving isometrics form a **group**, orientation-reversing ones **does not**.
:::

#### Similarity transformations
A similarity transform is an isometry composed with an isotropic scaling.
It's also called **equi-form** transformation because it preserves **shape**

$$
\begin{pmatrix}
x' \\
y' \\
1' \\
\end{pmatrix} =
\begin{bmatrix}
s cos \theta & s sin \theta & t_x \\
s sin \theta & s cos \theta & t_y \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{pmatrix}
x \\
y \\
1 \\
\end{pmatrix}
$$

$$
x' = H_{S} =
\begin{bmatrix}
sR & t \\
0^T & 1 \\
\end{bmatrix} x
$$

#### Affine transformations
An affine transform is a non-singular linear transformation followed by a translation.

$$
\begin{pmatrix}
x' \\
y' \\
1' \\
\end{pmatrix} =
\begin{bmatrix}
a_{11} & a_{12} & t_x \\
a_{21} & a_{22} & t_y \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{pmatrix}
x \\
y \\
1 \\
\end{pmatrix}
$$

$$
x' = H_{A} =
\begin{bmatrix}
A & t \\
0^T & 1 \\
\end{bmatrix} x
$$

The affine matrix A can always be decomposed as $$A = R(\theta)R(-\phi)DR(\phi)$$ where $R(\theta)$ and $R(\phi)$ are rotations by $\theta$ and $\phi$ respectively, and D is a diagonal matrix

$$D =
\begin{bmatrix}
\lambda_1 & 0 \\
0 & \lambda_2 \\
\end{bmatrix}
$$

This decomposition comes from SVD where $A=UDV^T=(UV^T)(VDV^T)=R(\theta)(R(-\phi)DR(\phi))$ where $U,V$ are othogonal matrices.

:::info
The essence of an affinity is the scaling in orthogonal directions, oriented at a particular angle.
:::

A affinity is orientation-preserving or reversing acccording to whether $det(A)$ is positive or negative respectively. Since $det(A)=\lambda_1 \lambda_2$ this property depends only on the sign of the scalings.

#### Perspective transformations
It's a general non-singular linear transformation of **homogeneous** coordinates.

$$
\begin{pmatrix}
x' \\
x' \\
1 \\
\end{pmatrix} =
\begin{bmatrix}
h_{11} & h_{12} & h_{13} \\
h_{21} & h_{22} & h_{23} \\
h_{31} & h_{32} & h_{33} \\
\end{bmatrix}
\begin{pmatrix}
x \\
y \\
1 \\
\end{pmatrix}
$$

$$
x' = H_{P} =
\begin{bmatrix}
A & t \\
v^T & 1 \\
\end{bmatrix} x
$$

The matrix has nine elements with only thrie ratio significant, so the transformation is specified by eight parameters.

A projective transformation can be decomposed into a chain of transformations (not unique), where each matrix in the chain represents a transformation higher in the hierarchy than the previous one.

$$ H = H_{S}H_{A}H_{P} =
\begin{bmatrix}
sR & t \\
0^T & 1\\
\end{bmatrix}
\begin{bmatrix}
K & 0 \\
0^T & 1\\
\end{bmatrix}
\begin{bmatrix}
I & 0 \\
v^T & \mu\\
\end{bmatrix} =
\begin{bmatrix}
A & t \\
v^T & \mu\\
\end{bmatrix}
$$

### The line at infinity (affine transform)
Under a projective transformation line at infinity $l_{\infty}$ are mapped to a finite line. However, if the transformation is an **affinity**, then **$l_{\infty}$ is not mapped to a finite line, but remains at infinity**. This is evident directly from the line transformation:

$$l^{'}_{\infty} = H_{A}^{-T} l_{\infty} =
\begin{bmatrix}
A^{-T} & 0 \\
-t^T A^{-T} & 1 \\
\end{bmatrix}
\begin{pmatrix}
0 \\
0 \\
1 \\
\end{pmatrix} =
\begin{pmatrix}
0 \\
0 \\
1 \\
\end{pmatrix} = l_{\infty}
$$


:::success
The line at infinity $l_{\infty}$ is a fixed line under the projective transformation H if and only if H is an **affinity**.
:::