Mathematics
Here, I will briefly review the terms and then derive the equation system for homography. If you follow this, you will see why you need to detect at least 4 points which aren’t on the line.
Terms
Correspondence. Imagine have 2 photos of the same object from a slightly different position. Then the point \(p_1\) and \(p_2\) on the respective images are corresponding if they are projecting the same physical point. Sign for correspondence is \(p_1\ \hat{=}\ p_2\).
Homogeneous coordinates. This is a coordinate system used in projective geometry and will be used here from now on as well. 2D vector \(\begin{bmatrix} x\\ y \end{bmatrix}\) in cartesian coordinates is expressed as 3D vector \(\begin{bmatrix} wx\\ wy\\ w \end{bmatrix}, \forall w\neq 0\) in homogeneous coordinates. Similarly, 3D vectors in cartesian coordinates are 4D vectors in homogeneous coordinates. Also, note that \(\begin{bmatrix} w_{1}x\\ w_{1}y\\ w_1 \end{bmatrix}=\begin{bmatrix} w_{2}x\\ w_{2}y\\ w_2 \end{bmatrix}, \forall w_1\neq 0,\ w_2\neq 0\) in homogeneous coordinates.
Matrices are used to represent certain geometric transformations in the homogeneous coordinates. Transformation of the point \(p\) is realized by a simple multiplication so that \(p’=Mp\). In addition, transformations can merged into a single one by the standard matrix multiplication.
Homography Equations
Mr. Wikipedia says that any two images of the same planar surface in space are related by a homography (assuming a pinhole camera model).
In other words, if \(I\) and \(I’\) are 2 images, containing same planar surface, then there exists a 3×3 matrix \(H\) which maps points \(p\) into corresponding points \(p’\), such as \(p’=Hp\). Remember that these points must be on that plane.
Let’s write down the equations in more details.
\[
H=\begin{bmatrix} h_{11} & h_{12} & h_{13} \\ h_{21} & h_{22} & h_{23} \\ h_{31} & h_{32} & h_{33} \end{bmatrix} \\
\begin{bmatrix} w’x’ \\ w’y’ \\ w’ \end{bmatrix}=\begin{bmatrix} h_{11} & h_{12} & h_{13} \\ h_{21} & h_{22} & h_{23} \\ h_{31} & h_{32} & h_{33} \end{bmatrix}\begin{bmatrix} wx \\ wy \\ w \end{bmatrix} \\
\begin{bmatrix} w’x’ \\ w’y’ \\ w’ \end{bmatrix}=\begin{bmatrix} h_{11}wx + h_{12}wy + h_{13}w \\ h_{21}wx + h_{22}wy + h_{23}w \\ h_{31}wx + h_{32}wy + h_{33}w \end{bmatrix}
\]
The goal is to figure out 9 elements of matrix \(H\). Without losing any generality, you can assume that \(w = 1\) and switch to the cartesian coordinates by division. This will make the following equation.
\[
\begin{bmatrix} x’ \\ y’ \end{bmatrix}=\begin{bmatrix} \frac{h_{11}x + h_{12}y + h_{13}}{h_{31}x + h_{32}y + h_{33}} \\ \frac{h_{21}x + h_{22}y + h_{23}}{h_{31}x + h_{32}y + h_{33}} \end{bmatrix}
\]
This equation system has 9 degrees of freedom. Luckily, you can multiply all elements of \(H\) by a non-zero \(k\) without having affecting the solution at all. This removes 1 degree of freedom and opens 2 possible ways for a solution.
First way is to set \(h_{33} = 1\). You can do this as soon as \(h_{33}\neq 0\). Second, more general way, is to impose unit vector constraint such as \(h_{11}^2+h_{12}^2+h_{13}^2+h_{21}^2+h_{22}^2+h_{23}^2+h_{31}^2+h_{32}^2+h_{33}^2=1\). Here I will use the first way because it seems to be more intuitive and better supported by the numerical libraries.
Homography Solution
Setting \(h_{33}=1\) will give the following.
\[
\begin{bmatrix} x’ \\ y’ \end{bmatrix}=\begin{bmatrix} \frac{h_{11}x + h_{12}y + h_{13}}{h_{31}x + h_{32}y + 1} \\ \frac{h_{21}x + h_{22}y + h_{23}}{h_{31}x + h_{32}y + 1} \end{bmatrix}
\]
After separating to the components, multiplying, and reorganizing you will get these 2 equations.
\[
x’=h_{11}x + h_{12}y + h_{13} – h_{31}xx’ – h_{32}yx’ \\
y’=h_{21}x + h_{22}y + h_{23} – h_{31}xy’ – h_{32}yy’
\]
These are the linear equations with 8 unknowns. Therefore, in theory, it is required to have 8 equations (with certain preconditions to make sure the system is not degenerated) to be able to figure out the unknowns.
In practice, we have an estimated 4 corner points of the marker paper. Although there are some errors carried out of the image processing part, these points do not lie on a single line. Therefore it is possible to plug them into equations and use numerical methods to get the approximated solution with minimal error. This is how the equations look like.
\[
\begin{bmatrix}
x_1 & y_1 & 1 & 0 & 0 & 0 & -x_1x_1′ & -y_1x_1′ \\
0 & 0 & 0 &x_1 & y_1 & 1 & -x_1y_1′ & -y_1y_1′ \\
x_2 & y_2 & 1 & 0 & 0 & 0 & -x_2x_2′ & -y_2x_2′ \\
0 & 0 & 0 &x_2 & y_2 & 1 & -x_2y_2′ & -y_2y_2′ \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots
\end{bmatrix}
\begin{bmatrix}
h_{11} \\ h_{12} \\ h_{13} \\ h_{21} \\ h_{22} \\ h_{23} \\ h_{31} \\ h_{32}
\end{bmatrix}
=
\begin{bmatrix}
x_1′ \\ y_1′ \\ x_2′ \\ y_2′ \\ \cdots
\end{bmatrix}
\]
I won’t go into numerics here. I just use the solver provided by the mathematics library to get a solution like this one.
\[
H=\begin{bmatrix} h_{11} & h_{12} & h_{13} \\ h_{21} & h_{22} & h_{23} \\ h_{31} & h_{32} & 1 \end{bmatrix} \\
\]
The source code for homography estimation is located inside the Ar class, method estimateHomography.
Use Case
Homography has several use cases, you can easily find them on the internet. Here just the one relevant to this project. Let’s estimate the homography in the way that detected rectangle corresponds to the fixed rectangle. Then draw the blue square to the fixed rectangle and corresponding square to the original image. The result is right below.
Summary
This chapter covered homography. This allows you to draw into the planar surfaces of the image. In the next chapter, you will learn how to extend homography to get the projection matrix and be able to draw 3D objects lying on top of that plane.
