**16-822
Projective Geometry and Homography**
**Anisha Jain (anishaja)**
Overview
===============================================================================
In this assignment, I implement algorithms to rectify images using affine and metric transformations. I also implement a planar homography algorithm to align an image with a reference image using point correspondences.
Affine Rectification
===============================================================================
This implementation performs affine rectification by computing a homography matrix that transforms the input lines such that two pairs of lines (line1, line2 and line3, line4) are parallel. The following steps outline the algorithm used:
1. **Input**: Two pairs of parallel lines are provided as input, each line defined by two points. For example, line1 is defined by the points \((x_{1_1}, y_{1_1})\) and \((x_{1_2}, y_{1_2})\), and similarly for the other lines.
2. **Line Equation**: The line equation for each line is computed using the cross product:
$l_i = x_{i_1} \times x_{i_2}$
where $x_{i_1}$ and $x_{i_2}$ are the homogeneous coordinates of the two points defining the line.
3. **Vanishing Points**: The points at infinity, which represent where parallel lines intersect at infinity, are obtained by the cross product of each pair of lines:
$p_{\infty_1} = l_1 \times l_2, p_{\infty_2} = l_3 \times l_4$
4. **Line at Infinity**: The line at infinity is computed as the cross product of the two points at infinity:
$l_{\infty} = p_{\infty_1} \times p_{\infty_2}$
5. **Homography Matrix**: A homography matrix \( H \) is constructed, which includes the line at infinity. This homography transforms the input image such that the specified lines become parallel. The homography is normalized such that:
$H = I$
$H[2] = l_{\infty}$
$H = H / H[2,2]$
  
 
|Before Rectification|After Rectification|
|---|---|
|0.9868| 0.9999|
|0.9987| 0.9999|
[Cos of angle between test lines]
  
 
|Before Rectification|After Rectification|
|---|---|
|0.9928|0.9999|
|0.9958|0.9995|
[Cos of angle between test lines]
  
 
|Before Rectification|After Rectification|
|---|---|
|0.7842|0.9999|
|0.9999|0.9999|
[Cos of angle between test lines]
  
 
|Before Rectification|After Rectification|
|---|---|
|0.9998|0.9999|
|0.9979|0.9999|
[Cos of angle between test lines]
  
 
|Before Rectification|After Rectification|
|---|---|
|0.9965|0.9999|
|0.9991|0.9999|
[Cos of angle between test lines]
Metric Rectification
===============================================================================
This implementation performs metric rectification by computing a homography matrix that transforms the input lines such that they are perpendicular after rectification.
Using parallel and perpendicular lines
---------------------------------------------------------------------------
In this implementation, we assume that the image is already affine rectified. The following steps outline the algorithm used:
1. **Input**: Two pairs of perpendicular lines are provided as input, each line defined by two points. For example, line1 is defined by the points \((x_{1_1}, y_{1_1})\) and \((x_{1_2}, y_{1_2})\), and similarly for the other lines.
2. **Line Equation**: The line equation for each line is computed using the cross product:
$l_i = x_{i_1} \times x_{i_2}$
where $x_{i_1}$ and $x_{i_2}$ are the homogeneous coordinates of the two points defining the line.
3. **Perpendicularity Constraint**: To ensure that line1 and line2, and line3 and line4 are perpendicular in the transformed image, the algorithm imposes the condition:
\begin{equation}
l_i^T \cdot C_{infty}^{*'} \cdot l_j = 0
\end{equation}
4. **Solving for Transformed Conic at Infinity**: Using the line equations and the constraints, the system of linear equations is solved to obtain the transformed conic at infinity. This is done by solving for \( C^*_{infty} \) using singular value decomposition (SVD). We also exploit the fact that the conic at infinity is symmetric with elements of the last row and column are zero.
\begin{equation}
C^{*'}_{infty} = \begin{bmatrix} a & b/2 & 0 \\
b/2 & c & 0\\
0 & 0 & 0 \end{bmatrix}
\end{equation}
5. **Homography Matrix**: The homography matrix \( H \) is computed by factoring \( C^*_{infty} \) using SVD:
\begin{equation}
C^{*'}_{infty} = H \cdot C^*_{infty} \cdot H^T
\\
C^*_{infty} = \begin{bmatrix} 1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 0 \end{bmatrix}
\\
U, S, V = svd(C^{*'}_{infty})
\\
H = \begin{bmatrix}
\frac{1}{\sqrt{S_1}} & 0 & 0 \\
0 & \frac{1}{\sqrt{S_2}} & 0 \\
0 & 0 & 1
\end{bmatrix} \cdot U^T
\end{equation}
  
  
|Before Rectification|After Rectification|
|---|---|
|0.2526|0.0018|
|0.0881|0.0081|
[Cos of angle between test lines]
  
  
|Before Rectification|After Rectification|
|---|---|
|-0.6685|-0.0211|
|0.0447|0.0096|
[Cos of angle between test lines]
  
  
|Before Rectification|After Rectification|
|---|---|
|0.1677|0.0080|
|0.0349|0.0293|
[Cos of angle between test lines]
  
  
|Before Rectification|After Rectification|
|---|---|
|0.4293|0.0287|
|0.1545|0.0405|
[Cos of angle between test lines]
  
  
|Before Rectification|After Rectification|
|---|---|
|0.1832|0.0344|
|0.2117|0.0060|
[Cos of angle between test lines]
Using only perpendicular lines
---------------------------------------------------------------------------
In this implementation, the image need not be affine rectified. The steps are mostly the same except the below changes:
1. **Input**: We now require more than 4 pairs of perpendicular lines to compute the conic at infinity. The more the number of lines, the better the accuracy of the conic at infinity. I use 5 pairs of perpendicular lines in this implementation.
2. **Solving for Conic at Infinity**: The system of linear equations is solved to obtain the conic at infinity. This is done by solving for \( C^*_{infty} \) using singular value decomposition (SVD). We also exploit the fact that the conic at infinity is symmetric. The conic at infinity is computed as:
\begin{equation}
C^{*'}_{infty} = \begin{bmatrix} a & b/2 & d/2 \\
b/2 & c & e/2 \\
d/2 & e/2 & f \end{bmatrix}
\end{equation}
 
|Before Rectification|After Rectification|
|---|---|
|0.05 | -0.013|
| 0 | -0.05|
| -0.164 | -0.03 |
|0.18 | -0.01|
|0.14 | -0.004 |
[Cos of angle between lines]
 
|Before Rectification|After Rectification|
|---|---|
|0.1449| 0.0076|
|0.0543| 0.0231|
|0.0037| 0.0345|
|-0.1851| 0.1549|
|0.1815| 0.0217|
|0.0121| 0.0770|
[Cos of angle between lines]
Planar Homography from Point Correspondences
===============================================================================
This implementation computes the homography matrix that transforms an image to align with a reference image using point correspondences. The following steps outline the algorithm used:
1. **Input**: The input consists of two images, the source image and the reference image, and a set of point correspondences in the reference image that map to corners of the source image.
2. **Homography Matrix**: The homography matrix is computed by solving the linear system of equations.
\begin{equation}
Ah = 0
\end{equation}
where \( A \) is a matrix of size \( 2n \times 9 \) and \( h \) is a vector of size \( 9 \times 1 \). A is constructed using the point correspondences. Each correspondence pair \((x_i, y_i) \leftrightarrow (x'_i, y'_i)\) is used to construct two rows of A:
\begin{equation}
A = \begin{bmatrix}
-x_i & -y_i & -1 & 0 & 0 & 0 & x_i x'_i & y_i x'_i & x'_i \\
0 & 0 & 0 & -x_i & -y_i & -1 & x_i y'_i & y_i y'_i & y'_i
\end{bmatrix}
\end{equation}
3. **Apply Homography**: The homography matrix is applied to the source image to align it with the reference image.
  
  
Billboard Flashback
---------------------------------------------------------------------------
Spot billboards that are ahead of their time.
*(Hint : There are 8 of them!)*
The original posters can be viewed [here](poster.html).
I annotate some billboards from the original image and overlay my posters on them iteratively.