Solved

Fitting an affine transformation

Posted on 2008-10-18
7
530 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
Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

 
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

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Representing TIME in Excel 8 44
invest money into checking/savings account 4 107
Percentage 6 50
Calculating Probability 18 62
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…
Article by: Nicole
This is a research brief on the potential colonization of humans on Mars.
This video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: …
When you create an app prototype with Adobe XD, you can insert system screens -- sharing or Control Center, for example -- with just a few clicks. This video shows you how. You can take the full course on Experts Exchange at http://bit.ly/XDcourse.

708 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

13 Experts available now in Live!

Get 1:1 Help Now