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
NASA team lays plans to observe new worlds
IHEP in China has ambitions for Higgs factory
Spinach could lead to alternative energy more powerful than Popeye
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