16-822: Geometry-based Methods in Vision

Assignment 1 - Projective Geometry and Homography

Long Vân Tran Ha (ltranha)

Tuesday, September 24th, 2024

Table of Contents

  • 1. Affine Rectification
  • 2. Metric Rectification
  • 3. Planar Homography from Point Correspondences
  • 4. Metric Rectification from Perpendicular Lines
  • 5. More Planar Homography from Point Correspondences

1. Affine Rectification

Input Image Parallel lines used for rectification on input image Rectified Image Parallel lines used for rectification on rectified image
Parallel test lines on input image Parallel test lines on rectified image Cosine angle (before) Cosine angle (after)
0.9868327646

0.9987191071		 0.9999251970

0.9999383464
0.8964448119

0.9574522354		 0.9999943713

0.9999729375
-0.9878470788

0.9845941271		 -0.9997703795

0.9999978465
0.9672678243

0.9992634847		 0.9999701654

0.9999985592
0.9740823693

-0.9972644472		 0.9989477560

-0.9995454926

Implementation details¶

Step 1: Annotate Parallel Lines¶

  • The input consists of 2 pairs of parallel lines in the image, each lines are represented by two points. Each point is in image pixel coordinates. This gives an array of size $(8, 2)$.

Step 2: Convert Points to Lines and Compute Vanishing Points¶

  1. Homogeneous Coordinates:
    • Each point $(x, y)$ is extended to homogeneous coordinates by adding a 1 at the end: $p = (x, y, 1)^T$.
  2. Compute Lines:
    • For each pair of points, the line that passes through them is computed using the cross product: $\ell = p_1 \times p_2$.
  3. Compute Vanishing Points:
    • For each pair of parallel lines, compute their vanishing point by finding the intersection (cross product) of the two lines: $v = \ell_1 \times \ell_2$.

Step 3: Compute the Homography Matrix¶

  1. Form the Vanishing Line (Horizon):
    • Once the two vanishing points are computed, the projected line at infinity is determined by taking the cross product of these two vanishing points: $\ell = v_1 \times v_2 = (a, b, c)^T$.
  2. Construct the Homography Matrix:
    • The homography matrix is then defined using the components of the vanishing line: $$H = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\a/c & b/c & 1\end{bmatrix}.$$

Step 4: Rectify the Image¶

  • The homography matrix $H$ is applied to each point in the image to rectify it: $x' = H \cdot x$.
  • After applying the homography, the image may be translated to ensure the pixel coordinates are positive and displayable.

Below is a visual mathematical representation of the steps taken to rectify the image.

$$\underset{\ell = v_1 \times v_2 = \begin{pmatrix} a \\ b \\ c \end{pmatrix}}{\underbrace{ \underset{v_1 = \ell_1 \times \ell_2}{\underbrace{ \underset{\ell_1 = p_1 \times p_2}{\underbrace{p_1 \quad p_2}} \quad \underset{\ell_2 = p_3 \times p_4}{\underbrace{p_3 \quad p_4}} }} \quad \underset{v_2 = \ell_3 \times \ell_4}{\underbrace{ \underset{\ell_3 = p_5 \times p_6}{\underbrace{p_5 \quad p_6}} \quad \underset{\ell_4 = p_7 \times p_8}{\underbrace{p_7 \quad p_8}} }} }}$$

$$\Longrightarrow H = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ a/c & b/c & 1 \end{pmatrix}$$

2. Metric Rectification

Input Image Perpendicular lines used for rectification on input image Perpendicular lines used for rectification on affine-rectified image Rectified Image
Perpendicular test lines on input image Perpendicular test lines on metric rectified image Cosine angle (before) Cosine angle (after)
-0.1677181549

-0.0349826608		 0.0080918663

0.0293069327
0.1466290931

0.3993378380		 -0.0193209440

0.0295500630
0.1918709518

-0.1065481960		 -0.0460718686

0.0107468581
-0.0123940208

-0.1386626960		 0.0099076591

-0.0172894159
0.5179772435

-0.2990018435		 0.0053036838

0.0202877325

Implementation details¶

Step 0: Affine Rectification¶

  • The affine rectification is performed first to obtain the affine-rectified image (see 1. Affine Rectification). The affine transformation is denoted as $H_{\text{affine}}$.

Step 1: Annotate Perpendicular Lines¶

  • We annotate 2 pairs of perpendicular lines in the original image, each lines are represented by two points. Each point is in image pixel coordinates. This gives an additional array of size $(8, 2)$.

Step 2: Convert Points and Compute Lines¶

  • Each point is converted into homogeneous coordinates and transformed using the affine transformation matrix (of step 0) in order to map the points to the affine-rectified image: $p_i' = H_{\text{affine}} p_i$.
  • For each pair of transformed points, compute the corresponding line equation using the cross product: $\ell' = p_1' \times p_2'$. This results in four lines, representing two pairs of perpendicular lines in the affine-rectified image.

Step 4: Compute the Transformed Circle Conic¶

  • Because the image is affine-rectified, the transformed circle conic matrix can be represented as: $$C = \begin{pmatrix} a & b & 0 \\ b & c & 0 \\ 0 & 0 & 0 \end{pmatrix}.$$
  • Given two perpendicular lines $\ell = \begin{pmatrix} l_1 \\ l_2 \\ l_3 \end{pmatrix}$ and $m = \begin{pmatrix} m_1 \\ m_2 \\ m_3 \end{pmatrix}$ in the affine-rectified image, they satisfy the relation $\ell^T C m = 0$, i.e. $(l_1m_1, l_1m_2 + l_2m_1, l_2m_2) \begin{pmatrix} a \\ b \\ c \end{pmatrix} = 0$. This leads to the matrix equation: $$A \begin{pmatrix} a \\ b \\ c \end{pmatrix} = 0$$ where $A$ is a $2\times 3$ matrix formed from the coefficients of the 2 pairs of perpendicular lines.
  • The vector $\begin{pmatrix} a \\ b \\ c \end{pmatrix}$ is the null vector of $A$, obtained as the last column of $V$ from the SVD decomposition $A = U \Sigma V^T$.

Step 5: Compute the Rectification Matrix¶

  • Compute the SVD of the conic matrix $C$ derived from Step 4: $C = U \Sigma V^T$ where $\Sigma = \begin{pmatrix} \sigma_1 & 0 & 0 \\ 0 & \sigma_2 & 0 \\ 0 & 0 & 0 \end{pmatrix}$.
  • Compute the rectification matrix as: $$H_{\text{rect}} = \begin{pmatrix} \frac{1}{\sqrt{\sigma_1}} & 0 & 0 \\ 0 & \frac{1}{\sqrt{\sigma_2}} & 0 \\ 0 & 0 & 1 \end{pmatrix} V^T.$$

Step 6: Apply Metric Rectification¶

  • The rectification matrix $H_{\text{rect}}$ is applied to each point in the affine-rectified image to get the metric-rectified image: $x'' = H_{\text{rect}} x'.$
  • An alternative method to avoid losing pixels is to apply the rectification from the original image: $x'' = H_{\text{rect}} \cdot H_{\text{affine}} x$.

Below is a visual mathematical representation of the steps taken to get the metric-rectified image from the affine-rectified image (here $p_i' = H_{\text{affine}} p_i$).

$$\underset{\underset{A}{\underbrace{\begin{pmatrix} \ell_{1x}\ell_{2x} & \ell_{1x}\ell_{2y} + \ell_{1y}\ell_{2x} & \ell_{1y}\ell_{2y} \\ \ell_{3x}\ell_{4x} & \ell_{3x}\ell_{4y} + \ell_{3y}\ell_{4x} & \ell_{3y}\ell_{4y} \end{pmatrix}}} \begin{pmatrix} a \\ b \\ c \end{pmatrix} = 0}{\underbrace{ \underset{\ell_1^T C \ell_2 = 0}{\underbrace{ \underset{\ell_1 = p_1' \times p_2'}{\underbrace{p_1' \quad p_2'}} \quad \underset{\ell_2 = p_3' \times p_4'}{\underbrace{p_3' \quad p_4'}} }} \quad \underset{\ell_3^T C \ell_4 = 0}{\underbrace{ \underset{\ell_3 = p_5' \times p_6'}{\underbrace{p_5' \quad p_6'}} \quad \underset{\ell_4 = p_7' \times p_8'}{\underbrace{p_7' \quad p_8'}} }} }}$$

$$A = U \Sigma V^T \Longrightarrow V_3 = \begin{pmatrix} a \\ b \\ c \end{pmatrix} \Longrightarrow C = \begin{pmatrix} a & b & 0 \\ b & c & 0 \\ 0 & 0 & 0 \end{pmatrix} = U' \begin{pmatrix} \sigma_1 & 0 & 0 \\ 0 & \sigma_2 & 0 \\ 0 & 0 & 0 \end{pmatrix} V'^T$$

$$\Longrightarrow H_{\text{rect}} = \begin{pmatrix} \frac{1}{\sqrt{\sigma_1}} & 0 & 0 \\ 0 & \frac{1}{\sqrt{\sigma_2}} & 0 \\ 0 & 0 & 1 \end{pmatrix} V'^T$$

3. Planar Homography from Point Correspondences

Normal Image Perspective Image Annotated corners in Perspective Image Warped and Overlaid Image

Implementation details¶

Step 1: Annotate Corner Points¶

  • We annotate the four target corner points on the perspective image. Each point is in image pixel coordinates. This gives an array of size $(4, 2)$. This is where the normal image will be transformed to and overlaid on.
  • The four source corner points are known from the normal image, as they are the corners of the image.

Step 2: Compute Homography Matrix¶

  • We transform the source and target points to homogeneous coordinates: $p = (x, y, 1)^T$.
  • Correspondences should satisfy the relation $p' \equiv H p$ (up to scale), i.e. $p' \times H p = 0$. Each correspondence gives 2 independent equations: $$\begin{pmatrix} 0 & 0 & 0 & -x & -y & -1 & y'x & y'y & y' \\ x & y & 1 & 0 & 0 & 0 & -x'x & -x'y & -x' \end{pmatrix} h = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$$ where $h$ is a $9 \times 1$ vector representing the flattened homography matrix $H$.
  • With 4 correspondences, we can form a $8 \times 9$ matrix $A$ and solve the system $Ah = 0$ using SVD decomposition: $A = U \Sigma V^T$.
  • $h$ is the null vector of $A$, obtained as the last column of $V$. The homography matrix $H$ is reshaped from $h$.

Step 3: Apply Homography¶

  • The homography matrix $H$ is applied to each point in the normal image to warp it to the perspective image and overlay it.

Below is a detailed mathematical representation of the steps taken to compute the homography matrix from point correspondences (source $p_i$ to target $p_i'$).

$$\underset{A}{\underbrace{\begin{pmatrix} 0 & 0 & 0 & -x_1 & -y_1 & -1 & y_1x_1 & y_1y_1 & y_1 \\ x_1 & y_1 & 1 & 0 & 0 & 0 & -x_1'x_1 & -x_1'y_1 & -x_1' \\ 0 & 0 & 0 & -x_2 & -y_2 & -1 & y_2x_2 & y_2y_2 & y_2 \\ x_2 & y_2 & 1 & 0 & 0 & 0 & -x_2'x_2 & -x_2'y_2 & -x_2' \\ 0 & 0 & 0 & -x_3 & -y_3 & -1 & y_3x_3 & y_3y_3 & y_3 \\ x_3 & y_3 & 1 & 0 & 0 & 0 & -x_3'x_3 & -x_3'y_3 & -x_3' \\ 0 & 0 & 0 & -x_4 & -y_4 & -1 & y_4x_4 & y_4y_4 & y_4 \\ x_4 & y_4 & 1 & 0 & 0 & 0 & -x_4'x_4 & -x_4'y_4 & -x_4' \end{pmatrix}}} \begin{pmatrix} h_1 \\ h_2 \\ h_3 \\ h_4 \\ h_5 \\ h_6 \\ h_7 \\ h_8 \\ h_9 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}$$

$$A = U \Sigma V^T \Longrightarrow h = V_9 \Longrightarrow H = \begin{pmatrix} h_1 & h_2 & h_3 \\ h_4 & h_5 & h_6 \\ h_7 & h_8 & h_9 \end{pmatrix}$$

4. Metric Rectification from Perpendicular Lines

Input Image Perpendicular lines used for rectification on input image Rectified Image (with annotated lines)
Perpendicular test lines on input image Perpendicular test lines on metric rectified image Cosine angle (before) Cosine angle (after)
0.5504424976

0.5179635357

-0.0676567092		 0.0578087598

0.0077373531

0.0105645764
0.1189395535

0.0383410920

0.0486977644		 -0.0157888552

-0.0248588592

0.0304693068

Implementation details¶

Similarly to the metric rectification of affine-rectified images from perpendicular lines in 2. Metric Rectification, the implementation follows the same steps to compute the rectification matrix $H_{\text{rect}}$ from the annotated perpendicular lines, but the conic matrix is general: $C = \begin{pmatrix} a & b & d \\ b & c & e \\ d & e & f \end{pmatrix}$ as opposed to the special case $C = \begin{pmatrix} a & b & 0 \\ b & c & 0 \\ 0 & 0 & 0 \end{pmatrix}$ (with $d = e = 0$ for affine-rectified images).

Because there are 6 unknowns in the general conic matrix (which is defined up to scale), we need at least 5 pairs of perpendicular lines.

Step 1: Annotate Perpendicular Lines¶

  • We annotate $n\geq 5$ pairs of perpendicular lines in the original image, each lines are represented by two points. Each point is in image pixel coordinates. This gives an array of size $(2n, 2)$.

Step 2: Convert Points and Compute Lines¶

  • Each point is converted into homogeneous coordinates: $p = (x, y, 1)^T$.
  • For each pair of points, compute the corresponding line equation using the cross product: $\ell = p_1 \times p_2$.

Step 3: Compute the Transformed Circle Conic¶

  • The conic matrix $C = \begin{pmatrix} a & b & d \\ b & c & e \\ d & e & f \end{pmatrix}$ satisfies the relation $\ell^T C m = 0$ for two perpendicular lines $\ell = \begin{pmatrix} l_1 \\ l_2 \\ l_3 \end{pmatrix}$ and $m = \begin{pmatrix} m_1 \\ m_2 \\ m_3 \end{pmatrix}$, i.e. $$(l_1m_1 \quad l_1m_2 + l_2m_1 \quad l_2m_2 \quad l_1m_3 + l_3m_1 \quad l_2m_3 + l_3m_2 \quad l_3m_3) \begin{pmatrix} a \\ b \\ d \\ c \\ e \\ f \end{pmatrix} = 0.$$
  • This leads to the matrix equation: $$A \begin{pmatrix} a \\ b \\ d \\ c \\ e \\ f \end{pmatrix} = 0$$ where $A$ is a $2n\times 6$ matrix formed from the coefficients of the $n$ pairs of perpendicular lines.
  • The vector $\begin{pmatrix} a \\ b \\ d \\ c \\ e \\ f \end{pmatrix}$ is the null vector of $A$, obtained as the last column of $V$ from the SVD decomposition $A = U \Sigma V^T$.

Step 4: Compute the Rectification Matrix¶

  • Compute the SVD of the conic matrix $C$ derived from Step 3: $C = U \Sigma V^T$ where $\Sigma = \begin{pmatrix} \sigma_1 & 0 & 0 \\ 0 & \sigma_2 & 0 \\ 0 & 0 & 0 \end{pmatrix}$.
  • Compute the rectification matrix as: $$H_{\text{rect}} = \begin{pmatrix} \frac{1}{\sqrt{\sigma_1}} & 0 & 0 \\ 0 & \frac{1}{\sqrt{\sigma_2}} & 0 \\ 0 & 0 & 1 \end{pmatrix} V^T.$$

Step 5: Apply Metric Rectification¶

  • The rectification matrix $H_{\text{rect}}$ is applied to each point in the original image to get the metric-rectified image.

5. More Planar Homography from Point Correspondences

Normal Image 1 Normal Image 2 Normal Image 3 Perspective Image (with annotated corners) Warped and Overlaid Image

Implementation details¶

The implementation follows the same steps as in 3. Planar Homography from Point Correspondences to compute the homography matrix $H$ from the annotated corner points, but instead of having one object to overlay (4 corners), we have multiple objects ($n$ times 4 corners), each with its own homography matrix.

We also have multiple normal images to overlay on the perspective image for diversity.

The implementation is straightforward, we iterate 3. Planar Homography from Point Correspondences for each object and compute the homography matrix from the corresponding corner points, then apply the homography to the chosen normal image and overlay it on the perspective image.