Fitting an affine transformation

Posted on 2008-10-18
Last Modified: 2012-06-22

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

LVL 84

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.

Author Comment

ID: 22755167
Hi ozo,

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

I've started using this:

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!

Netscaler Common Configuration How To guides

If you use NetScaler you will want to see these guides. The NetScaler How To Guides show administrators how to get NetScaler up and configured by providing instructions for common scenarios and some not so common ones.

LVL 84

Expert Comment

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

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.
    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),
        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
LVL 84

Accepted Solution

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?

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:

I guess it's just a simple matrix problem but I'm not very familiar with it.  That picture comes from this lecture:


Featured Post

Simplifying Server Workload Migrations

This use case outlines the migration challenges that organizations face and how the Acronis AnyData Engine supports physical-to-physical (P2P), physical-to-virtual (P2V), virtual to physical (V2P), and cross-virtual (V2V) migration scenarios to address these challenges.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Manufacturing a NPK fertlizer 7 32
HP Deskjet 2132 3 158
Vertex form of the function 8 72
Calculating bins of different widths using a summery plot in a Nspire CX Cas 2 17
Complex Numbers are funny things.  Many people have a basic understanding of them, some a more advanced.  The confusion usually arises when that pesky i (or j for Electrical Engineers) appears and understanding the meaning of a square root of a nega…
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.
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…

777 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