10
$\begingroup$

Related to: Newly Developed With Details - Describing orthographic projection using simple 2D transformations

Given an arbitrary 2D linear transform (which may include shear, i.e. the vectors or the basis may not form a straight angle), it is possible to decompose it into transforms that are only horizontal/vertical scaling (i.e. matrices of the form $\pmatrix{s_x&0\\0&s_y}$) and pure rotation (i.e. matrices of the form $\pmatrix{\cos \theta&-\sin\theta\\\sin\theta&\cos\theta}$).

The minimal number of steps to do so is probably 3:

  1. Rotate it so that the next scaling step will give it the correct shape.
  2. Scale it to give it the proper shape.
  3. Rotate it into the final position.

In other words, it seems to be always possible to find parameters $\theta, s_x, s_y, \phi$ such that:

$$M = \pmatrix{m_{00}&m_{01}\\m_{10}&m_{11}} = \pmatrix{\cos\phi&-\sin\phi\\\sin\phi&\cos\phi} \pmatrix{s_x&0\\0&s_y} \pmatrix{\cos\theta&-\sin\theta\\\sin\theta&\cos\theta}$$

I don't know if it's always possible to do so. I have the hunch that it is. I could not figure out how; I got a big system of nonlinear equations when I tried by myself. That decomposition has 4 d.o.f. as does the original linear transform, which hints that if it's correct, then it's minimal (you can't do it with 2 rotations or 2 scalings, and you don't have enough d.o.f. with 1 rotation + 1 scaling).

I tried with Inkscape and trial and error, and I could not find any rhomboid I couldn't transform into a square, but I might have not tried hard enough.

My questions:

  1. Is that decomposition always possible? Already answered by Rahul in a comment (thanks!): it's called Singular Value Decomposition)
  2. If so, how to calculate $\theta, s_x, s_y, \phi$?
  3. If not, how can it be done in the least number of steps? (Mooted by the answer to question 1).
  4. (New question) I found a solution with 4 (sometimes 5) steps, posted in the linked question but it was somewhat convoluted. However, the SVD seems to be complex to calculate. Should I just go with my 4-5 step solution, or is there a simple enough way to perform the decomposition? I've found this answer: https://scicomp.stackexchange.com/questions/8899/robust-algorithm-for-2x2-svd but it looked kind of overkill and I don't understand how to use the code for this case. I also didn't understand how to use the analytical result for the 2x2 case from the Wikipedia page, so if it's easier, an explanation on using it would help too.
$\endgroup$
  • 1
    $\begingroup$ Yes, this is known as the singular value decomposition, and it works in higher dimensions as well! $\endgroup$ – Rahul Jul 9 '14 at 23:01
  • $\begingroup$ Thank you, that answers my first question and makes my third question moot. But it looks like a huge amount of theory to go through and absorb in order to solve this problem. Can you or someone else please explain how to use that theory or whatever is needed, in order to find the decomposition for the present case? Or should I better go with my 4-5 step recipe? $\endgroup$ – Pedro Gimeno Jul 9 '14 at 23:25
  • $\begingroup$ @Rahul Your reply has helped me found this page: metamerist.blogspot.com/2006/10/… which almost completely answers the question. I'm trying to convert it into a complete solution now. Thanks. $\endgroup$ – Pedro Gimeno Jul 10 '14 at 0:43
  • $\begingroup$ Ah, an extremely clean derivation is given in Jim Blinn's article "Consider the lowly $2\times 2$ matrix" linked to at the bottom of the blog post. I'll quote the calculation below for the benefit of people who don't have access to the article. $\endgroup$ – Rahul Jul 10 '14 at 1:07
11
$\begingroup$

Jim Blinn gives a direct computation of the singular value decomposition for the $2\times 2$ case in his article "Consider the lowly $2\times 2$ matrix", which I summarize below:

We want the decomposition $$\begin{bmatrix}A&B\\C&D\end{bmatrix}=\begin{bmatrix}\cos\beta&\sin\beta\\-\sin\beta&\cos\beta\end{bmatrix}\begin{bmatrix}w_1&0\\0&w_2\end{bmatrix}\begin{bmatrix}\cos\gamma&\sin\gamma\\-\sin\gamma&\cos\gamma\end{bmatrix}.$$ Define $E$, $F$, $G$, and $H$ so that $$\begin{bmatrix}A&B\\C&D\end{bmatrix}=\begin{bmatrix}E&H\\-H&E\end{bmatrix}+\begin{bmatrix}F&G\\G&-F\end{bmatrix}.$$ Then $$\begin{align} \frac{w_1+w_2}2&=\sqrt{E^2+H^2},\\ \frac{w_1-w_2}2&=\sqrt{F^2+G^2},\\ \gamma-\beta&=\tan^{-1}(G/F), \\ \gamma+\beta&=\tan^{-1}(H/E). \\ \end{align}$$

As Blinn says, "You can take it from here."

$\endgroup$
  • 3
    $\begingroup$ It works wonderfully! Thanks. The input matrix is transposed though, so let me spell the solution out. E=(m00+m11)/2; F=(m00-m11)/2; G=(m10+m01)/2; H=(m10-m01)/2; Q=sqrt(E^2+H^2); R=sqrt(F^2+G^2); sx=Q+R; sy=Q-R; a1=atan2(G,F); a2=atan2(H,E); theta=(a2-a1)/2; phi=(a2+a1)/2. The requested parameters are then theta, sx, sy, phi, i.e. rotate by theta, scale by sx,sy, rotate by phi. No division by zero or sqrt(negative) hazard. Excellent. $\endgroup$ – Pedro Gimeno Jul 10 '14 at 20:17

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.