Apply Projective Transformation 2D Rectangle

Question

I want to write code from scratch about Projective Transformation in order to apply this transformation to 2d rectangular. I searched about this transformation, but I could not figure out completely. These are some formulas I have seen:

   x' = xH
   y' = yH
   A.H = 0
   A = UΣV^T

According to these formulas,SVD is calculated from A matrix, and then H is obtained from V. Then target points should be found by H. But this is a bit confusing. Could you explain it? Also is there any alternative solution like composition of transformations like Similarity Transform which can be obtained by multiplying rotation, translation and scale matrixes?

EDIT

I watched this youtube video (https://www.youtube.com/watch?v=54Qtu3S9HJU) . It explains how calculate homography by the equations above after 12 minutes.This method seems very complex. I want to learn how exactly we calculate homography and obtain another rectangle by applying Projective Transfrom?

Answer 1

Since homography is not my topic, I can't really tell if I am missing some important edge cases, but after some research, I think I got the basics. I will use the same variable names, the guy in the video uses on slide 15 (slide numbers are in the bottom right corner on the red background).

You start by defining 4 points in the plane $X$ where you say you know their projected points in plane $x$. You assume, that the transformation between $X$ and $x$ is linear and can be described by a matrix $H$. Means $$x = HX$$

Now you want to calculate the Matrix $H$ that perfoms the projection:

$$H = \begin{bmatrix}h_1&h_2&h_3\\h_4&h_5&h_6\\h_7&h_8&h_9\end{bmatrix}$$

$h_1$ to $h_9$ are unknowns. So how do you get them? Well, you have 4 times:

$p_i' = Hp_i$

where $p_i'$ and $p_i$ are the projected and the original points. This full equation looks like this:

$$\begin{bmatrix}x_i'\\y_i'\\1\end{bmatrix}= \begin{bmatrix}h_1&h_2&h_3\\h_4&h_5&h_6\\h_7&h_8&h_9\end{bmatrix}\begin{bmatrix}x_i\\y_i\\1\end{bmatrix}$$

Perform the multiplication and you will get this:

$$\begin{bmatrix}x_i'\\y_i'\\1\end{bmatrix}= \begin{bmatrix}x_ih_1+y_ih_2+h_3\\x_ih_4+y_ih_5+h_6\\x_ih_7+y_ih_8+h_9\end{bmatrix}$$

You can also write this in some kind of nested vector fashion:

$$\begin{bmatrix}x_i'\\y_i'\\1\end{bmatrix}= \begin{bmatrix}\bar{h_1}^T p\\\bar{h_2}^T p\\\bar{h_3}^T p\end{bmatrix} = \begin{bmatrix}p^T\bar{h_1}\\p^T\bar{h_2}\\p^T\bar{h_3}\end{bmatrix}$$

where $$\begin{matrix}\bar{h_1} = \begin{bmatrix}h_1\\h_2\\h_3\end{bmatrix}&\bar{h_2} = \begin{bmatrix}h_4\\h_5\\h_6\end{bmatrix}&\bar{h_1} = \begin{bmatrix}h_7\\h_8\\h_9\end{bmatrix}\end{matrix}$$

Now here comes the trick (got it from this link). If $p'$ is equal to the vector $Hp$ their cross product must be the zero vector $\bar{0}$:

$$p' \times Hp = \bar{0}$$

Applying the cross product will give you three equations:

$$\begin{matrix}y_i'p^T\bar{h_3} - p^T\bar{h_2} &= 0 \\ p^T\bar{h_1} - x_i' p^T\bar{h_3} &= 0\\x_i' p^T\bar{h_2}-y_i' p^T\bar{h_1}&=0\end{matrix}$$

Write this as a matrix equation and you get:

$$\begin{bmatrix}\bar{0}^T &-p^T&y_i'p^T\\p^T&\bar{0}^T&-x_i'p^T\\-y_i' p^T&x_i' p^T&\bar{0}^T\end{bmatrix} \begin{bmatrix}\bar{h_1}\\\bar{h_2}\\\bar{h_3}\end{bmatrix}= \begin{bmatrix}0\\0\\0\end{bmatrix}$$

Now, if you look at the matrix, you might notice, that the 3 columns are not linear independent. $-y_i'$ times the first column minus $x_i'$ times the second one, yields the third column. So you can drop one.

If you drop the last column and replace all the vectors with their corresponding entries, you get:

$$\begin{bmatrix}0&0&0 &-x_i&-y_i&-1&y_i'x_i&y_i'y_i&y_i'\\x_i&y_i&1&0&0&0&-x_ix_i'&-y_ix_i'&-x_i'\end{bmatrix} \begin{bmatrix}h_1\\h_2\\h_3\\h_4\\h_5\\h_6\\h_7\\h_8\\h_9\end{bmatrix}= \begin{bmatrix}0\\0\end{bmatrix}$$

You can multiply the second row by $-1$ and swap it with the first one (that does not change the solution of the system) to get the exact same formula as presented in the video on the slide 17.

If you apply the formula to all 4 points you get the system:

$$\begin{bmatrix} 0&0&0 &-x_1&-y_1&-1&y_1'x_1&y_1'y_1&y_1'\\ x_1&y_1&1&0&0&0&-x_1x_1'&-y_1x_1'&-x_1' \\ 0&0&0 &-x_2&-y_2&-1&y_2'x_2&y_2'y_2&y_2'\\ x_2&y_2&1&0&0&0&-x_2x_2'&-y_2x_2'&-x_2' \\ 0&0&0 &-x_3&-y_3&-1&y_3'x_3&y_3'y_3&y_3'\\ x_3&y_3&1&0&0&0&-x_3x_3'&-y_3x_3'&-x_3' \\ 0&0&0 &-x_4&-y_4&-1&y_4'x_4&y_4'y_4&y_4'\\ x_4&y_4&1&0&0&0&-x_4x_4'&-y_4x_4'&-x_4' \\ \end{bmatrix} \begin{bmatrix}h_1\\h_2\\h_3\\h_4\\h_5\\h_6\\h_7\\h_8\\h_9\end{bmatrix}= \begin{bmatrix}0\\0\end{bmatrix}$$

The problem is now, that you have 9 unknowns but just 8 formulas. According to the answers in this question, one possible solution is to constraint $h_9$ to be 1 and solve the resulting linear system. However, another way is to solve it as an underdetermined least-squares problem. This might be done using the SVD. However, as I said in the comments, this is a rather complicated algorithm. An easier one is to use QR decomposition, which can be a substep of the SVD, but this is also not too easy to code yourself. Since you don't seem to be that experienced in advanced linear algebra, you might try the constraint technique first, before trying the SVD.

You can also use more than 4 points, but then you get an overdetermined system, which can be solved with the SVD, QR decomposition or any other least-squares solver.