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

In summary, the conversation discusses a dilemma regarding the transformation of an image using a 3x3 transformation matrix. The individual needs to find the (x-y) coordinates of each corresponding pixel in the original image and is wondering if it is possible to derive the transformation matrix using a set of corresponding points. The conversation also includes a discussion on finding coefficients and solving systems to find the original coordinates of all the pixels. The use of four points instead of three is mentioned, as well as the process of inverse perspective transformation. The conversation concludes with the individual thanking for the help and mentioning that they were able to get the project working properly.
  • #1
mmacferrin
2
0
Hi, I don't know 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
 
Physics news on Phys.org
  • #2
So, the original points were transformed according to
Code:
x' = ax + by + c
y' = dx + ey + f
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).

Unless I screwed up that is :D
 
Last edited:
  • #3
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
 
  • #4
I guess you're trying to do an inverse perspective transformation then.

Let's say that you have the following transformations
Code:
    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

Code:
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

Code:
| 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.
 
  • #5
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?
 
  • #6
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.
 
  • #7
Thanks Lord_Circ. Just got it working properly last night! First big progress on my project in a week!
 
  • #8
Excellent, glad to help!
 
  • #9
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:

Code:
| 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:

Code:
    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.
 

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

1) What is a transformation matrix?

A transformation matrix is a mathematical representation of the relationship between two coordinate systems. It is used to transform points or objects from one coordinate system to another.

2) How can a transformation matrix be derived from a set of known points?

A transformation matrix can be derived by solving a system of equations using the known points and their corresponding coordinates in both coordinate systems. This can be done using methods such as linear algebra or least squares regression.

3) What are some applications of using a transformation matrix?

Transformation matrices are commonly used in computer graphics, computer vision, and robotics. They are also used in various fields of engineering and physics for modeling and analyzing transformations in physical systems.

4) Can a transformation matrix be used to transform points in 3D space?

Yes, a transformation matrix can be used to transform points in any number of dimensions as long as the number of rows and columns in the matrix are equal to the number of dimensions.

5) How do you verify the accuracy of a derived transformation matrix?

The accuracy of a derived transformation matrix can be verified by applying it to a set of test points and comparing the transformed coordinates to the expected coordinates. Additionally, the matrix can be compared to a known or reference transformation matrix if available.

Similar threads

  • Linear and Abstract Algebra
Replies
8
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
61
Replies
12
Views
4K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
881
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
5
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
2K
  • Linear and Abstract Algebra
Replies
5
Views
2K
Back
Top