Solved

Fitting an affine transformation

Posted on 2008-10-18
7
540 Views
Last Modified: 2012-06-22
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
Comment
Question by:DJ_AM_Juicebox
  • 4
  • 3
7 Comments
 

Author Comment

by:DJ_AM_Juicebox
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 84

Expert Comment

by:ozo
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

by:DJ_AM_Juicebox
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 84

Expert Comment

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

Author Comment

by:DJ_AM_Juicebox
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
 
    See also TFORMINV, MAKETFORM, FLIPTFORM, CP2TFORM.
0
 
LVL 84

Accepted Solution

by:
ozo earned 500 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

by:DJ_AM_Juicebox
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
Migrating to Microsoft Office 365 is becoming increasingly popular for organizations both large and small. If you have made the leap to Microsoft’s cloud platform, you know that you will need to create a corporate email signature for your Office 365…
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.

920 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now