Register to reply

Trying to derive a transformation Matrix from a set of known points

by mmacferrin
Tags: derive, matrix, transformation
Share this thread:
mmacferrin
#1
Dec6-09, 12:41 PM
P: 2
Hi, I dunno if this should go in a Math forum or a Programming forums, but y'all here seem quite handy with mathematics, so I'll give it a shot. If this is totally not what y'all are about, just let me know.

I have two computer images... one of them is an "original" image. The other one is a transformed version of the original image... it has been rotated, sheared and translated in a software program. I need to work on the transformed image, but I need the (x-y) coordinates of each corresponding pixel in the original image to finish my calculations.

I know the image was rotated and sheared with a 3x3 Transformation matrix. If I had the matrix, I could derive the second image from the first (or vice-versa using the inverse matrix) myself. But I don't have that. I don't know exactly how much it was rotated, sheared, or translated, so I can't just derive the matrices from a set of known transformations. What I do have is a set of corresponding points (the corners, et al) in each image, and their corresponding (x,y) coordinates. So here's my dilemma:

Using a set of corresponding transformed points ((x,y) -> (x',y'), three or more of them), can I derive the Transformation matrix that was used to turn one image into the other? If I can derive the matrix, I can solve for the original coordinates of all the pixels (all 18-million of 'em) and get the calculations done that I need to do.

Can anyone help? I'm familiar with linear algebra... just not familiar enough to derive this without a whole lotta head scratching. Anything is appreciated!

- Mike
Phys.Org News Partner Science news on Phys.org
Apple to unveil 'iWatch' on September 9
NASA deep-space rocket, SLS, to launch in 2018
Study examines 13,000-year-old nanodiamonds from multiple locations across three continents
Lord Crc
#2
Dec6-09, 04:48 PM
P: 88
So, the original points were transformed according to
x' = ax + by + c
y' = dx + ey + f
In order to find the coefficients, pick three points and solve the system
|x_1 y_1 1| |a|   |x'_1|
|x_2 y_2 1| |b| = |x'_2|
|x_3 y_3 1| |c|   |x'_3|
And similarly with d,e,f and y's (you only have to invert the matrix once of course).

Unless I screwed up that is :D
mmacferrin
#3
Dec6-09, 10:28 PM
P: 2
I think that's pretty much what I've been looking for. Thanks!

The only complication I have now is that (after further looking) it may not actually be an affine transformation that happened to the image. In other words, the square didn't get turned into a rotated, translated parallelogram (with a linear affine matrix), it was unevenly distorted, making an irregular trapezoid of sorts.

I got a bit of help in another (programming) forum though that I think solves it. I need 4 points, not three, to solve for the terms in the equations:

Ax + By + Cxy + D = x'
Ex + Fy + Gxy + H = y'

It means my transformations won't be using a linear matrix, but that's okay, it's still an accurate pixel conversion, as far as I can tell. Thank you for the help!

- Mike

Lord Crc
#4
Dec7-09, 01:35 AM
P: 88
Trying to derive a transformation Matrix from a set of known points

I guess you're trying to do an inverse perspective transformation then.

Let's say that you have the following transformations
    a_1*x + a_2*y + a_3
u = -------------------
    a_7*x + a_8*y + 1

    a_4*x + a_5*y + a_6
v = -------------------
    a_7*x + a_8*y + 1
Here (u,v) are the original coordinates, the ones you're trying to recover.

Rearranging the above we get

a_1*x + a_2*y + a_3 - a_7*xu - a_8*yu = u
a_4*x + a_5*y + a_6 - a_7*xv - a_8*yv = v
So, assuming we have four pair of points (x_1, y_1), (u_1, v_1) etc we get

| x_1  y_1  1   0    0   0  -x_1*u_1  -y_1*u_1 | | a_1 |   | u_1 |
| x_2  y_2  1   0    0   0  -x_2*u_2  -y_2*u_2 | | a_2 |   | u_2 |
| x_3  y_3  1   0    0   0  -x_3*u_3  -y_3*u_3 | | a_3 |   | u_3 |
| x_4  y_4  1   0    0   0  -x_4*u_4  -y_4*u_4 | | a_4 |   | u_4 |
|  0    0   0  x_1  y_1  1  -x_1*v_1  -y_1*v_1 | | a_5 | = | v_1 |
|  0    0   0  x_2  y_2  1  -x_2*v_2  -y_2*v_2 | | a_6 |   | v_2 |
|  0    0   0  x_3  y_3  1  -x_3*v_3  -y_3*v_3 | | a_7 |   | v_3 |
|  0    0   0  x_4  y_4  1  -x_4*v_4  -y_4*v_4 | | a_8 |   | v_4 |
Unless I made a mistake that is :) A bit nastier but not that horrible.
shizny
#5
Feb22-10, 05:50 PM
P: 2
Lord Circ... please excuse my noobieism here but in your post about finding the a , b, c, d, e, f coefficients you have

---
In order to find the coefficients, pick three points and solve the system
Code:

|x_1 y_1 1| |a| |x'_1|
|x_2 y_2 1| |b| = |x'_2|
|x_3 y_3 1| |c| |x'_3|

And similarly with d,e,f and y's (you only have to invert the matrix once of course).

---
So to get the d, e, and f is all I have to do is change x'_1, x`_2... to y'_1, y'_2 ? so I would have


|x_1 y_1 1| |d| |y'_1|
|x_2 y_2 1| |e| = |y'_2|
|x_3 y_3 1| |f| |y'_3|

and solve again for d e f, or do I have to transpose / adjust the values in the leftmost matrix as well?
Lord Crc
#6
Feb23-10, 09:43 AM
P: 88
Your first part is correct, you change the right hand side (x'_1 -> y'_1 etc) and the unknowns (a -> d etc), but leave the matrix alone.
shizny
#7
Feb23-10, 09:45 AM
P: 2
Thanks Lord_Circ. Just got it working properly last night!!! First big progress on my project in a week!!!
Lord Crc
#8
Feb23-10, 10:49 AM
P: 88
Excellent, glad to help!
HKragh
#9
Jul22-12, 06:38 PM
P: 12
I know this is an old thread, but I have used its content for something I'm working on at the moment. And after a lot of problems, I found some other references, and want to make a reply for future reference. The above matrix equation (written by Lord Crc) should've said:

| x_1  y_1  1   0    0   0  -x_1*u_1  -y_1*u_1 | | a_1 |   | u_1 |
|  0    0   0  x_1  y_1  1  -x_1*v_1  -y_1*v_1 | | a_2 |   | v_1 |
| x_2  y_2  1   0    0   0  -x_2*u_2  -y_2*u_2 | | a_3 |   | u_2 |
|  0    0   0  x_2  y_2  1  -x_2*v_2  -y_2*v_2 | | a_4 |   | v_2 |
| x_3  y_3  1   0    0   0  -x_3*u_3  -y_3*u_3 | | a_5 | = | u_3 |
|  0    0   0  x_3  y_3  1  -x_3*v_3  -y_3*v_3 | | a_6 |   | v_3 |
| x_4  y_4  1   0    0   0  -x_4*u_4  -y_4*u_4 | | a_7 |   | u_4 |
|  0    0   0  x_4  y_4  1  -x_4*v_4  -y_4*v_4 | | a_8 |   | v_4 |
(coefficients doesn't change, the rest (8x8 and 1x8) has changed according to this system: row 1-4 becomes row 1-3-5-7, and row 5-8 becomes row 2-4-6-8)

I had some problems with the coefficients being wrong, which made this equation put out wrong values:

    a_1*x + a_2*y + a_3
u = -------------------
    a_7*x + a_8*y + 1

    a_4*x + a_5*y + a_6
v = -------------------
    a_7*x + a_8*y + 1
After the reordering of rows, it works perfectly in my code.


Register to reply

Related Discussions
Need help with fourier transformation to derive oseen tensor. Advanced Physics Homework 6
Why derive Regular Singular Points? Differential Equations 1
Matrix transformation Precalculus Mathematics Homework 1
Transformation Matrix Calculus & Beyond Homework 0
Did i do this matrix transformation right? Calculus & Beyond Homework 2