# AR By Hand – Part 3 – Homography

Homography estimation as a step towards full AR system.
Welcome in part 3 of this AR series. In the previous chapter, you could read about how to detect and track white A4 paper. The result was 4 points in the image corresponding to the corners. This chapter will use these points to build a homography. That’s the next step towards the AR experience.
This article goes first through the mathematics behind homography, and then shows the use case relevant to this project.

## 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.

### Anomaly detection using the Bag-of-words model

A practical method of finding anomalies within the set of activities using the Bag-of-words model.

### Unit-Level Performance tuning in Java

How to simply improve performance of your java applications. Everything purely in IDE, without even starting the whole app.

### Bitcoin and JUnit

How to unit test bitcoin with Java and JUnit.

### Brittle POJO

POJO pattern is pretty popular in Java world. This article demonstrates what’s wrong with that.