?
Solved

Fitting an affine transformation

Posted on 2008-10-18
7
Medium Priority
?
564 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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

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

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

Question has a verified solution.

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

A Guide to the PMT, FV, IPMT and PPMT Functions In MS Excel we have the PMT, FV, IPMT and PPMT functions, which do a fantastic job for interest rate calculations.  But what if you don't have Excel ? This article is for programmers looking to re…
Have you ever thought of installing a power system that generates solar electricity to power your house? Some may say yes, while others may tell me no. But have you noticed that people around you are now considering installing such systems in their …
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.
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
Suggested Courses

764 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