0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I don't really understand what exactly you want to achieve. Okay, you want to somehow project a rectangle (somewhere), and calculate/code the projection yourself. Usually, I would say, search for "projection matrix", but since you posted some formulas (without much explanation) I thought you might be looking for something more complex and I have no clue what. So please specify your exact problem. Also, specify why exactly you need an SVD? This is a quite expensive/complicated operation and I know only a small number of use cases, where it is the right tool. $\endgroup$ – wychmaster Apr 12 at 18:35
  • $\begingroup$ @wychmaster , I updated my question. I try to find out a method how to apply projective transform. The method explained in the video is very complex. Could you explain when we need to use SVD? $\endgroup$ – justadeveloper Apr 12 at 18:48
  • $\begingroup$ I'm not 100% sure I understood what you want, but if you just want to project a mesh onto the screen you should google "perspective transformation matrix". It will work for 2d meshes as well, as long as you set a value for the third dimension. $\endgroup$ – zoran404 Apr 12 at 20:23
  • $\begingroup$ I watched the video you linked. The guy is like a typical academic tutor. Certainly knows his stuff and how to use it, but he isn't really good at teaching it (in my opinion), since he does not explain well, why he does what. After some research, I think I got the basics. I have written an answer that might help you. $\endgroup$ – wychmaster Apr 13 at 15:05
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.