Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

# Fitting an affine transformation

Posted on 2008-10-18
Medium Priority
578 Views
Hi,

I'm trying to implement the "RANSAC" algorithm for fitting a bunch of points in one image to points in another image.

I need some help figuring out a method which will let me determine an affine transform used to get a point in one image, to a point in another image.

The RANSAC algorithm goes something like this (this is just background)::

1) Run a SIFT descriptor extractor on each of the images, get back an array of 128d descriptors and their x,y location in the images.
2) Run a match filter - take each descriptor from image1, try to find a single match for it from image2.
3) Now this is where I need help - I have a point in image1 that is (supposedly) a match for a point in image2. How can I find the affine transformation which gets it from image1 to image2 (or vice versa).

I don't understand this because the two images can be wildly different. For instance, image 1 is a large scene of a table with fruit on it. I might find some descriptors for pixels in an apple on the table. Image 2 is just a cropped image of the apple itself, rotated and scaled up. Will an affine transform even make sense between the pixels on the apple on the table, and the cropped image of the apple scaled up and rotated?

Thanks for any help
0
Question by:DJ_AM_Juicebox
• 4
• 3

Author Comment

ID: 22751407
I think I understand the problem more now - when I run the SIFT descriptor, I will get several points on the apple in both images. I can randomly pick a few points from the apple (say 3), and try to find an affine transform that satisfies all 3 pairs of picked points. I guess this will be able to tell me rotation, scaling, and translation.

That makes more sense. How does one solve for an affine transform though?

Thanks
0

LVL 85

Expert Comment

ID: 22755094
There are many affine transforms that take a a point in one image to a point in another image
(there is a unique translation that takes a a point in one image to a point in another image with no rotation or scaling)
There is a unique similarity transform that takes two points in one image to two points in another image.
There is a unique affine transform that takes three non-collinear points in one image to three non-colinear points in ahother.
0

Author Comment

ID: 22755167
Hi ozo,

That makes sense. How do I find that transform though?

I've started using this:

http://elonen.iki.fi/code/misc-notes/affine-fit/

this is what I want, right? I mean I have the 3 points in one image, and their matches in the other images, so I hope this is the right thing to do!

Thanks
0

LVL 85

Expert Comment

ID: 22755222
Without having tested it, it looks like it could work.
0

Author Comment

ID: 22755656
Ok so now I realize my points have not only an x and y location, but also a scale and rotation to them:

pt1 =  { x,  y,  scale,  rotation };

I'm completely at a loss as how to calculate the transform between 3 of those to 3 of their matches in the other image.

Any ideas what to look at? Matlab has something called tformfwd() but the example provided shows it figuring out the transform for points with x,y values only. I'm not sure if it can take into account scale and rotation attached to each point:

TFORMFWD Apply forward spatial transformation.
If U is a matrix, X = TFORMFWD(U,T) applies the forward transformation
defined in T to each row of U.  T is a TFORM struct created with
MAKETFORM, FLIPTFORM, or CP2TFORM.  U is an M-by-T.ndims_in matrix; each
row of U represents a point in T's input space.  X is an
M-by-T.ndims_out matrix; each row of X represents a point in T's output
space, and is the forward transformation of the corresponding row of U.

If U is an (N+1)-dimensional array (including an implicit trailing
singleton dimension if T.ndims_in is 1), then TFORMFWD applies the
transformation to each point U(P1,P2,...,PN,:).  SIZE(U,N+1) must equal
T.ndims_in.  X is an (N+1)-dimensional array containing the results of
each transformation in X(P1,P2,...PN,:).  SIZE(X,I) equals SIZE(U,I) for
I = 1,...,N and SIZE(X,N+1) equals T.ndims_out.

Example
-------
Create an affine transformation that maps the triangle with vertices
(0,0), (6,3), (-2,5) to the triangle with vertices (-1,-1), (0,-10),
(-2,5):

u = [0 0; 6 3; -2 5];
x = [-1 -1; 0 -10; 4 4];
tform = maketform('affine',u,x);

Validate the mapping by applying TFORMFWD to u:

tformfwd(u,tform)  % Result should equal x

0

LVL 85

Accepted Solution

ozo earned 2000 total points
ID: 22755683
I'm not sure what { x,  y,  scale,  rotation } mean in your data, but  could you just apply the scale and rotation to x and y before calculating the transform?
0

Author Comment

ID: 22755718
Yeah so I have image 1 and image 2.

Then I run this SIFT descriptor thing which gives me a bunch of feature points in both images. Each is a single point with an { x, y, scale, rotation } value assigned to it. The x,y values are just its pixel location in the image, the scale and the rotation i am not too sure about.

This is part of a larger algorithm called RANSAC.

I cannot find a detailed description on this one step, the rest seems straightforward. I find some slides from universities but they don't explain how to solve this part. Here is an example of such a slide:

http://i373.photobucket.com/albums/oo174/testinfo/someinfo.png

I guess it's just a simple matrix problem but I'm not very familiar with it.  That picture comes from this lecture:  http://www.cse.psu.edu/~rcollins/CSE486/lecture15_6pp.pdf

Thanks
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
When we purchase storage, we typically are advertised storage of 500GB, 1TB, 2TB and so on. However, when you actually install it into your computer, your 500GB HDD will actually show up as 465GB. Why? It has to do with the way people and computersâ€¦
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaacâ€¦
###### Suggested Courses
Course of the Month10 days, 4 hours left to enroll