1

I have an object in 3d space which is represented by the set of vertices. Then I scale this object, rotate it and translate. After these operations I get the second set of vertices with new coordinates. I know the correspondence between the old set and the new set.

Is it possible to derive values of rotation, scale and translation from the comparison of these two sets of vertices?

EDIT: And how to estimate these values if the transformation was not precisely affine, for example my vertex coordinates estimation has an error so I can not solve the system of equations for all vertices of my object to get matrix elements?

Mr.Jimm
  • 13

2 Answers2

3

It is possible to work out the combined transformation. Since you are allowing the possibility of a translation, I will work in homogeneous coordinates. As such, I will write the point $P(x,y,z)$ as the vector $p=(x,y,z,1)^T$. Since you also know the image point $P'$ (or vector $p'$), it is possible to work out the transformation matrix $A$ such that $p'=Ap$. The matrix $A$ is $4\times4$, so we will require $4$ points, in general, to determine the matrix.

As we only have a scaling, rotation and translation, our matrix $A$ will be of the form $$ A=\begin{bmatrix}RS&c\\0^T&1\end{bmatrix}, $$ where $S$ is the $3\times3$ scaling matrix, $R$ is the $3\times3$ rotation matrix and $c$ is the vector we are translating by. This means that there are only be $12$ unknowns in $A$, thus still requiring $4$ points to determine.

If you cannot solve the above equations exactly, one option is to solve them in the least squares sense, so that you are minimising $$ F(A)=\sum\limits_{i=1}^n \left\|p_i'-Ap_i\right\|^2 $$ with respect to $A$.

Given the transformation matrix $A$, it is much harder to determine the scaling matrix $S$ and the rotation matrix $R$. The translation is simple, as this is the last column of the matrix. A general scaling matrix can be written as $S=I-knn^T$, where the components in the direction of the unit vector $n$ are scaled by $k$. A generic form for a rotation matrix can be found here which explicitly relies upon the axis of rotation and the angle. To actually compute $R$ and $S$ I suspect will be difficult.

Daryl
  • 5,598
  • Since the A matrix is 2x2, the vector to multiply is ((x, y, z), 1) i guess? – Mr.Jimm Nov 28 '13 at 12:59
  • And why there are 12 unknowns? 9 for rotation 9 for scaling and 3 for translation, isn't it? – Mr.Jimm Nov 28 '13 at 13:01
  • @MrJinn If you write out the matrix, you see that only the first 3 rows (of 4 columns) have unknowns. To calculate the separate transformation matrices: a scaling matrix only has 4 unknowns, the same as the rotation matrix, three for the "axis" and one for the angle or scale factor. – Daryl Nov 28 '13 at 20:14
1

Hint: Since the transformation is affine, then for the original vector $\vec{x}$ and it's image $\vec{y}$ there is a matrix $A$ and a vector $\vec{b}$ such that $$\vec{y}=A\vec{x}+\vec{b}$$

A standard trick is to transform this to homogeneous coordinates: $$\begin{pmatrix}\vec{y}\\1\end{pmatrix}=\begin{pmatrix}A&\vec{b}\\0&1\end{pmatrix}\begin{pmatrix}\vec{x}\\1\end{pmatrix}$$

$A$ and $\vec{b}$ are the same for every vertex in your set. Notice that this is a problem of the form $\vec{Y}=H\vec{X}$.

Since there are errors but the problem is linear, the best approach to solve this is through least squares. In this approach, you are finding the matrix H such that the norm of $\vec{Y}-H\vec{X}$ is minimized (there is extensive literature on this approach on the web, including wikipedia).

Once you find H, then recovering the rotation matrix, scale and translation is possible.

Kevin
  • 567