I have a square with the length of the sides being 1. This square is transformed by an unknown transformation matrix in the 3D space and then projected back to the plane (the projection is known). I know the coordinates of the 4 angles of the transformed, projected square.
How do I find the unknown transformation matrix?
UPDATE: sorry I forgot to add that the projection is perspective.
Best Answer
I would guess that you're supposed to use "homogeneous coordinates", and that the "3D" matrix you're supposed to compute is the matrix of a projective transformation. When we use homogeneous coordinates, a coordinate vector for a point in a plane has three components rather than two. This may seem unintuitive or unappealing, but there are advantages to homogeneous coordinates: 1) "points at infinity" can be assigned coordinates as easily as ordinary points ; 2) every projective transformation is given by multiplication by a $3 \times 3$ matrix. (There are other advantages too; mathematicians have discovered that homogeneous coordinates are a natural and elegant way to assign coordinates to points in a projective plane.)
Suppose we have a projective transformation that is represented by a matrix $H \in \mathbb R^{3 \times 3}$, so that point with coordinate vector $x$ maps to a point with coordinate vector $Hx$. If we have four points $x_1,\ldots,x_4$ in "general position" and we know these four points map to $y_1,\ldots, y_4$, then we can use this information to compute $H$.
We cannot simply say that $y_i = H x_i \, \,$, because one quirky thing about homogeneous coordinates is that if $y$ is a coordinate vector for a point in a projective plane, then any nonzero scalar multiple of $y$ is also a coordinate vector for the same point. This might seem weird but it's something we must get used to.
The most we can say is that $y_i$ is a (nonzero) scalar multiple of $H x_i$. An equivalent way to say the same thing is \begin{equation} y_i \times H x_i = 0 \end{equation} where $\times$ denotes the cross product.
Notice that this equation is linear in the components of $H$ ! For each $i$, we have three linear equations for the components of $H$. However, it turns out that one of those three equations is redundant, so each $i$ really only gives us two equations. All together, we have eight linear equations.
$H$ is found by finding a nonzero solution of this system of eight equations. Note that this only determines $H$ up to a scalar multiple. However, that's to be expected, because in homogeneous coordinates, any nonzero scalar multiple of $H$ represents the same projective transformation as $H$.