1
$\begingroup$

I am given this image:

enter image description here

and asked to determine the transformation matrix that took me from ΑΒΓΔΕ(let's call it ABCDE for convenience) to Α'Β'Γ'Δ'Ε' (A'B'C'D'E').

I am also given the solution, so as to be able to verify my process. From the image, I can easily tell that ABCDE has been scaled by 2, rotated by π, and transposed by some vector, in that order.

Question 1. The solution says that the values for the transposition are dx =10, dy=11. It is unclear to me how these values were extracted.

Question 2. I am unsure as to the order of the transformations. Is there any way to tell for sure? My guess happened to agree with the solution but it was just that, a guess.

Question 3. Possessing the matrices that express each object:

enter image description here

is it possible to extract the transformation matrix if the image was not provided? and if so, how?

I am aware that I am posing multiple questions but they all concern one subject and are very related to each other. Any pointers would be helpful. Thanks.

(My classes are not in English, apologies if the terms do not match up very well)

$\endgroup$
1
  • $\begingroup$ I'd like to point you to this related question: computergraphics.stackexchange.com/questions/12817/…. If the transformation is supposed to be rigid, 5 points are not necessary. 3 points are sufficient to deduce the transform. If we want a transformation that associates the source and target as close as possible, then checkout my answer. $\endgroup$ Jul 4 at 0:27

2 Answers 2

0
$\begingroup$

Regarding question 3:

There are many ways to solve this problem. Some answers are here and here. You can also create a system of equations by writing down the matrix multiplication symbolically.

$$ X \cdot A = B $$

$X$ is the transformation matrix you are looking for, $A$ your matrix before the transformation, and $B$ the matrix after the transformation. So you can write:

$$ \begin{bmatrix} x_{11}&x_{12}&x_{13}\\ x_{21}&x_{22}&x_{23}\\ x_{31}&x_{32}&x_{33} \end{bmatrix} \cdot \begin{bmatrix} a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33} \end{bmatrix} =\begin{bmatrix} b_{11}&b_{12}&b_{13}\\ b_{21}&b_{22}&b_{23}\\ b_{31}&b_{32}&b_{33} \end{bmatrix} $$

with the individual matrix products being:

$$ \begin{matrix} b_{11} =&x_{11}\cdot a_{11} + x_{12}\cdot a_{21} + x_{13}\cdot a_{31}\\ b_{12} =&x_{11}\cdot a_{12} + x_{12}\cdot a_{22} + x_{13}\cdot a_{32}\\ b_{13} =&x_{11}\cdot a_{13} + x_{12}\cdot a_{23} + x_{13}\cdot a_{33}\\\\ b_{21} =&x_{21}\cdot a_{11} + x_{22}\cdot a_{21} + x_{23}\cdot a_{31}\\ b_{22} =&x_{21}\cdot a_{12} + x_{22}\cdot a_{22} + x_{23}\cdot a_{32}\\ b_{23} =&x_{21}\cdot a_{13} + x_{22}\cdot a_{23} + x_{23}\cdot a_{33}\\\\ b_{31} =&x_{31}\cdot a_{11} + x_{32}\cdot a_{21} + x_{33}\cdot a_{31}\\ b_{32} =&x_{31}\cdot a_{12} + x_{32}\cdot a_{22} + x_{33}\cdot a_{32}\\ b_{33} =&x_{31}\cdot a_{13} + x_{32}\cdot a_{23} + x_{33}\cdot a_{33} \end{matrix} $$

or in matrix form:

$$ \begin{matrix} \begin{bmatrix} a_{11}&a_{21}&a_{31}\\ a_{12}&a_{22}&a_{32}\\ a_{13}&a_{23}&a_{33} \end{bmatrix} \cdot \begin{bmatrix} x_{11}\\ x_{12}\\ x_{13} \end{bmatrix} =\begin{bmatrix} b_{11}\\ b_{12}\\ b_{13} \end{bmatrix}\\\\ \begin{bmatrix} a_{11}&a_{21}&a_{31}\\ a_{12}&a_{22}&a_{32}\\ a_{13}&a_{23}&a_{33} \end{bmatrix} \cdot \begin{bmatrix} x_{21}\\ x_{22}\\ x_{23} \end{bmatrix} =\begin{bmatrix} b_{21}\\ b_{22}\\ b_{23} \end{bmatrix}\\\\ \begin{bmatrix} a_{11}&a_{21}&a_{31}\\ a_{12}&a_{22}&a_{32}\\ a_{13}&a_{23}&a_{33} \end{bmatrix} \cdot \begin{bmatrix} x_{31}\\ x_{32}\\ x_{33} \end{bmatrix} =\begin{bmatrix} b_{31}\\ b_{32}\\ b_{33} \end{bmatrix}\\ \end{matrix} $$

Watch out: the matrix here is transposed -> $A^T$

Now you have 9 equations for 9 unknowns that you can solve with Gaussian elimination, LU decomposition, or any other linear solver you are familiar with.

You might say that those are just 3x3 matrices and yours are 3x5. Adding those two columns yourself should be easy, but you actually don't need them to determine the matrix. It would give you an overdetermined system of equations. Just pick 3 columns instead (but the same from both matrices).

Note that if you combine the 3 matrix-vector equations into a single matrix-matrix equation, you basically end up with something similar to this solution. All you need to do is to multiply by the inverse of $A^T$ and then transpose everything. Then you have the same equation.

I wrote a short python script to check if everything is correct that I wrote:

import numpy as np

a = np.array([[2, 5, 1], [1, 3, 1], [1, 1, 1], [3, 1, 1], [3, 3, 1]]).transpose()
b = np.array([[7, 0, 1], [9, 4, 1], [9, 8, 1], [5, 8, 1], [5, 4, 1]]).transpose()

# pick first 3 vectors
a_red = a[:, :3]
b_red = b[:, :3]

# solve for each row vector of x
x_1 = np.linalg.solve(a_red.transpose(), b_red.transpose()[:, 0])
x_2 = np.linalg.solve(a_red.transpose(), b_red.transpose()[:, 1])
x_3 = np.linalg.solve(a_red.transpose(), b_red.transpose()[:, 2])

# combine vectors to the transformation matrix we are looking for
x = np.array([x_1, x_2, x_3])
print(x)

# check if x*a yields b
b_check = np.matmul(x, a)
print(b_check)
assert np.allclose(b, b_check)

The assertion holds and the matrix looks like expected:

$$ \begin{bmatrix} x_{11}&x_{12}&11\\ x_{21}&x_{22}&10\\ 0&0&1 \end{bmatrix} $$

Seems like you swapped the numbers in dx and dy cause I got dx=11 and dy=10. The first two rows of the last column represent the translation vector as described here. The last row is (0, 0, 1) as it should be since we are not doing any transformation into the 3. dimension.

I left out the upper left 2x2 matrices for you to find out. As another hint, $x_{11}=x_{22}$ and $x_{12}=x_{21}$. I think you will manage to figure them out. If you can't, just ask for help or run the python script but I recommend trying it yourself.

Regarding question 2

The usual forward order is scale, rotate, and translate for reasons I won't further explain. But this is not a "rule" and you can not rely on that. It is just the approach that makes the most sense for us humans. However, looking at the graphics and the calculated matrix, they followed this order.

Regarding question 1

Now with the information, I gave you for question 2, it should be obvious. Just pick the point Γ and follow it if you first apply the scaling, then the rotation, and finally the translation. If you manage this, you should also be able to just guess the remaining numbers of the matrix with all the information you got, at least if you understood all the involved substeps and the basic transformation matrices (check this link again). You will also see that dx and dy are indeed swapped in your question.

$\endgroup$
0
$\begingroup$

This kind of problem is usually called shape matching. It is possible to deduce the transformation between two given sets of positions.

You can learn more about the shape matching here

Müller, Matthias, et al. "Meshless deformations based on shape matching." ACM transactions on graphics (TOG) 24.3 (2005): 471-478.

https://dl.acm.org/doi/abs/10.1145/1073204.1073216?casa_token=ByW2rb3f-VgAAAAA:6wMJ5MT3moK_0lRPZtDDxFI0B16Nw8b5hcI-dclZaUV3RDJgeMUYTR7Sk7vE-4qMQ_6wHmlxReh5

(hint: no need to finish the whole paper. Section 3.3 is all you need)


Just apply the paper idea here to your question as a concrete example.

Denote the source point set as $x^0_i$ ($i=1..5$), and target point set as $x_i$. Let $t^0$ be the center of source points, and $t$ be the center of target points.

Let $q_i$ be the source point set minus the center: $q_i = x^0_i-t^0$. Similarly let $p_i$ be the target point set minus the center: $p_i=x_i -t$.

Then suppose we have found a transformation $A = R S$ (rotation and scaling), and the transformation maps our source point set to $A q_i + t^0$. We want its distance to the target as small as possible. That is, minimize this: $$ F = \sum_i (A q_i - p_i)^2 $$

In order to minimize $F$ we want to take derivative of $F$ and set it to 0 and then solve for A. That should give you $$ A = (\sum_i p_i q_i^T)(\sum_i q_i q_i^T)^{-1} $$

That $A$ is the transform associates the source and the target point sets. Further take QR decomposition of $A$ should give you the rotation and scaling.

In your case, (I am dropping z coordinates)

Centers:

t0={2, 13/5}
t={7, 24/5}

Coordinates with center translations removed:

p={{0, 2, 2, -2, -2}, {-24/5, -4/5, 16/5, 16/5, -4/5}}
q={{0, -1, -1, 1, 1}, {12/5, 2/5, -8/5, -8/5, 2/5}}
pq={{-8, 0}, {0, -112/5}}
qq={{4, 0}, {0, 56/5}}
A={{-2, 0}, {0, -2}}

Then the expression A q + t should give you the target point set.


This should give you a general solution to this problem without visualizing it.

For your question on transformation order: you can freely specify the order as you want. (that $A q + t$ thing).

For your question on deriving the translation: it should be the center of target point set, i.e. {7, 24/5} assuming the rotation happens at the center.

If you expand the transformation a bit: $$ \begin{align} A q + t &= A (x^0 - t^0) + t \\ &= A x^0 - A t^0 + t \\ &= A x^0 + (- A t^0 + t) \end{align} $$ The given solution might assume the rotation happens at the origin. In that case the translation is $(-A t^0 + t)$, and it is {11, 10}.

$\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.