Affine transformation

Question

I am trying to solve the below problem. I don't have much knowledge in Affine transformations. Could someone help me answer this question:

Find a 3x3 matrix representing a 2D affine transformation of homogeneous coordinates (i.e. every point [x,y] is represented as a column vector [x, y, 1]), which transforms a square [0,0],[1,0],[1,1],[0,1] into a parallelogram [0,1],[1,1],[2,2],[1,2].

Answer 1

You'll have read the Wikipedia page on the subject, of course.

Once upon an aeon or so ago, I read Foley and van Dam in one of the predecessor versions (this would have been 1983 or 1984), and it covered techniques for manipulating 2D and 3D coordinates with augmented matrices and vectors as described in the question. However, enough time has lapsed since then that I've forgotten all the details (and no longer have the book--too many moves of house). There was also a book by Newman and Sproul, I seem to remember.

A = [ a  b  c ]    B = [ 0  1  1  0 ]   C = [ 0  1  2  1 ]
    [ d  e  f ]        [ 0  0  1  1 ]       [ 1  1  2  2 ]
    [ g  h  1 ]        [ 1  1  1  1 ]       [ 1  1  1  1 ]

The columns of B represent the corners of the square; the columns of C represent the corners of the parallelogram; and the matrix equation A x B = C has to be solved. IIRC, the matrix A has a 1 in the bottom right corner; it is possible that the values c, f, g, and h also have presecribed values (they'd probably be zeroes). The non-zero values apply a linear (affine) transform, scaling, shearing and rotating the input shape.

You'd need to look for similar information in a text book. Or in the Wiki page - I didn't look hard at it (the information above is working from ancient memory).

Answer 2

Things I spotted about this question
1) You need to understand homogeneous co-ordinates
2) You need to know the difference between row and column major - read here
3) You need to know the basic affine transformations - rotate, scale/shear and translate and how to represent them in a matrix - read this page

Interestingly, I think the answer only needs a translate and a shear ( no rotation ).
Looking at the source and dest points, it looks like all dest points are translated +1 in y and sheared by 1 in X ( to give the parallelogram, probably best to draw it out to see what I mean )

So start with a 3 * 3 identity matrix which is

1 0 0
0 1 0
0 0 1

The shear will be
1 1 0
0 1 0
0 0 1

The translate will be
1 0 0
0 1 1
0 0 1

So putting it all together should be

1 1 0
0 1 1
0 0 1

I don't normally use column major so probably worth double checking!

Hope that helps

Answer 3

I just wanted to point out that four points over constrain a 2D affine transformation. In the comment of Jonathan Leffler, you can see this from the fact that you would need to invert a non-square matrix. So, either choose three of the points or set up a least-squares system. The over-constrained, least-squares solution could be solved with the following matrices

A = [ a  b  c ]    B = [ 0  1  1  0 ]   C = [ 0  1  2  1 ]
    [ d  e  f ]        [ 0  0  1  1 ]       [ 1  1  2  2 ]
    [ g  h  1 ]        [ 1  1  1  1 ]       [ 1  1  1  1 ]

so that solving using the normal equations gives

A B = C
(A B)^T = B^T A^T = C^T
B B^T A^T = B C^T
A^T = (B B^T)^-1 B C^T

undoing that transpose gives

A =  ((B B^T)^-1 B C^T)^T