0
$\begingroup$

While working through a paper concerning computer generated holograms I have come across a affine transform of a triangle. Hence I am not that familiar with affine transforms I do not exactly understand how they obtained the final form of the transform.


Lets suppose we have a triangle with three noncollinear vertices at $(s_1,t_1)$, $(s_2,t_2)$ and $(s_3,t_3)$. Furthermore I want to transform these vertices to a basic triangle with the vertices $(0,0)$,$(0,1)$ and $(1,1)$ by using a affine transform of the form

$$\begin{bmatrix}s\\t\end{bmatrix}~=~\begin{bmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}+\begin{bmatrix}a_{31}\\a_{32}\end{bmatrix}$$

Form hereon I am struggling with determining the coefficients $a_{ij}$. Setting up the pairwise correspondence $(0,0)\to(s_1,t_1)$,$(1,0)\to(s_2,t_2)$ and $(1,1)\to(s_3,t_3)$ and solving the system of six equations yields to

$$\begin{bmatrix}s\\t\end{bmatrix}~=~\begin{bmatrix}s_2-s_1&s_3-s_2-s_1\\t_2-t_1&t_3-t_2-t_1\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}+\begin{bmatrix}s_1\\t_1\end{bmatrix}$$

This formula looks ridiculous simple compared to the final form given within the paper

$$\begin{bmatrix}s\\t\end{bmatrix}~=~\frac1{J}\begin{bmatrix}(t_3-t_2)&(s_2-s_3)\\(t_1-t_2)&(s_2-s_1)\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}+\frac1{J}\begin{bmatrix}-((t_3-t_2)s_1+(s_2-s_3)t_1)\\-((t_1-t_2)s_1+(s_2-s_1)t_1)\end{bmatrix}$$

with $J$ the Jacobian determinat defined as $a_{11}a_{22}-a_{12}a_{21}$.

To be honest I have no idea to arrive at this transform or how to reshape my solution to look alike the "right" one. Further I do not exactly know how I can compute something at all with this equation since $J$ is defined in terms of the original coefficients $a_{ij}$ and so for example $a_{11}$ would be given by

$$a_{11}=\frac{t_3-t_2}{a_{11}a_{22}-a_{12}a_{21}}$$

which is kind of recursive. Hence I have got for equations of this type and four variables it would be possible to determine each coefficient individually but I do not think that this is the right way to approach to this.

Could someone explain to me where I did made a mistake that leads to the wrong solution or how to transform my own attempt to look alike the one given in the article. I would appreciate if someone could show me how to set up the final formula starting by the general defintion of an affine transform and the given pairwise correspondences.

Thanks in advance.

$\endgroup$
  • $\begingroup$ @amd First of all thank you for your response. I have just checked the formula I cited in the original paper again. I guess it could be that I messed up the pariwise correspondence since the authors states $(0,1)\to(s_2,t_2)$ instead of $(1,0)\to(s_2,t_2)$ which he used previously within a sketch. I guess this may be the crucial point but I do not exactly know. Could you maybe provide a way how to arrive at the right solution? $\endgroup$ – mrtaurho Sep 22 '18 at 20:02
  • $\begingroup$ Sorry. The transformation from the paper is correct after all. I made a transcription error myself when I checked it. $\endgroup$ – amd Sep 22 '18 at 20:28
1
$\begingroup$

Your guess as to what went wrong is correct: you’ve computed the transformation that maps the basic triangle onto the arbitrary one—the inverse of the map that’s needed.† Try plugging in any of the vertices into your formula to see this: you won’t get $(0,0)$, $(1,0)$ or $(1,1)$. The transformation in the paper goes in the correct direction. In fact, it’s precisely the inverse of yours. To get from your solution to the correct one, solve the two equations that it represents for $x$ and $y$. (Their roles are reversed in the two formulas.) Alternatively, start from scratch with the correct direction: From $(s1,t1)\to(0,0)$ you get $$s_1 a_{11}+t_1 a_{12}+a_{31} = 0 \\ s_1 a_{21} + t_1 a_{22} + a_{32} = 0$$ and so on for the other three point pairs. Solve the resulting system of 6 equations as you did before.

As for the $J$ in that formula, it’s the determinant of the matrix in your formula, which appears naturally when that matrix is inverted. The $a$’s in the definition of $J$ are meant to be elements of a generic $2\times2$ matrix. In this particular instance, they’re the elements of the matrix in your formula, i.e., $a_{11}=s_2-s_1$ and so on, giving $$J = (s_2-s_1)(t_3-t_2-t_1)-(t_2-t_1)(s_3-s_2-s_1).$$

If you’re familiar with matrices, it’s fairly easy to invert your formula directly. That transformation consists of a linear transformation followed by a translation, i.e., it has the form $\mathbf p = M\mathbf x+\mathbf p_1$, so to invert it you undo each of those components in reverse order: $\mathbf x = M^{-1}(\mathbf p-\mathbf p_1) = M^{-1}\mathbf p-M^{-1}\mathbf p_1$ Applying this to your transformation after swapping $(x,y)$ and $(s,t)$, we translate back: $$\begin{bmatrix}x\\y\end{bmatrix} - \begin{bmatrix}s_1\\t_1\end{bmatrix} = \begin{bmatrix}s_2-s_1&s_3-s_2\\t_2-t_1&t_3-t_2\end{bmatrix}\begin{bmatrix}s\\t\end{bmatrix}$$ then invert the linear part of the transformation $$\begin{bmatrix}s_2-s_1&s_3-s_2\\t_2-t_1&t_3-t_2\end{bmatrix}^{-1} \left( \begin{bmatrix}x\\y\end{bmatrix} - \begin{bmatrix}s_1\\t_1\end{bmatrix} \right) = \begin{bmatrix}s\\t\end{bmatrix}.$$ Now invert the matrix and distribute the multiplication: $$\begin{bmatrix}s\\t\end{bmatrix} = \frac1J\begin{bmatrix} (t_3-t_2) & (s_2-s_3) \\ (t_1-t_2) & (s_2-s_1) \end{bmatrix} \begin{bmatrix}x\\y\end{bmatrix} - \frac1J\begin{bmatrix} (t_3-t_2)s_1 + (s_2-s_3)t_1 \\ (t_1-t_2)s_1 + (s_2-s_1)t_1 \end{bmatrix},$$ with $J$ as above.

If you use homogeneous coordinates, then there’s a conceptually simple way to construct the required transformation. Recalling that the columns of a transformation matrix are the images of the basis vectors, we can see that the matrix $$\begin{bmatrix} x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \\ 1&1&1\end{bmatrix}$$ maps the standard basis onto the points $(x_1,y_1)$, $(x_2,y_2)$ and $(x_3,y_3)$. So, to map the given triangle onto the basic one, we can first map its vertices onto the standard basis, then map that onto the standard triangle. The resulting transformation is given by the matrix product $$\begin{bmatrix}0&1&1\\0&0&1\\1&1&1\end{bmatrix} \begin{bmatrix}s_1&s_2&s_3\\t_1&t_2&t_3\\1&1&1\end{bmatrix}^{-1}.$$ If you do this correctly, the last row of the resulting matrix will be $[0,0,1]$, which tells you that you have an affine transformation as required. You can use this same method to construct the affine transformation between any two triangles: just put the appropriate destination vertex coordinates into the left-hand matrix.

† Actually, there’s a mistake somewhere in your calculations because your transformation doesn’t map $(1,1)$ to $(s_3,t_3)$, but that’s not the important thing here.

$\endgroup$
  • $\begingroup$ Well, thank you again amd. This is quite the response I had in my mind. Clear and structured and therefore quite helpful. I always like to know where something comes from so I am glad you provide such a comprehensibly answer. Could you maybe explain me to which triangle this transform converts a given triangle when it is not the one wiht $(0,0)$,$(1,0)$ and $(1,1)$? $\endgroup$ – mrtaurho Sep 22 '18 at 20:45
  • $\begingroup$ @mrtaurho The map you came up with takes those points to $(s_1,t_1)$, $(s_2,t_2)$, $(s_3,t_3)$, respectively. If you want to find the images of those points, plug them into your formula and see what you get. $\endgroup$ – amd Sep 22 '18 at 20:48
  • $\begingroup$ Ah, okay. Thank you again. I guess this will be quite helpful for me to proceed with. $\endgroup$ – mrtaurho Sep 22 '18 at 20:49

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.