# Finding the “best” way to map set of points to another set

I've got a set of points (currently 4, but I can increase the number for better accuracy), and I want to find the optimal transformation so that they can be mapped to another set of points.

For example, I have (2,2), (2, 4), (4, 2), (4, 4) which makes a 2x2 square if these points were connected. I have another set of points, say (2, 2), (2, 5), (3,2), (5,5) which resembles the shape of a rectangle, but clearly stretched, skewed, translated, or even possibly rotated. Using these two sets of points, how can I find the optimal skew factor, stretch factor, translation magnitudes (x and y) and rotational degree to apply to all points in set A so that they overlay as precisely as possible on set B?

Note: I'm actually trying to write a program to overlay one image onto another. I have selected points on both images that I know should be matched to each other. However, I'm having trouble calculating how to map one set onto the other. Please excuse the incorrect use of any math terms :P

-
You mention skew, stretch, translation, and rotational degree. Are you interested in any affine transformation, or are you requiring that the skew be uniform in every direction? – MartianInvader Jul 20 '11 at 19:13

As such the question is not totally well posed. You shoudl specify what kind of transformation you are looking at. If you have that, this will lead to a natural parametrization of your allowed tranformation. If have yan that, you can (for example) formulate a least squares approach.

In an abstract formulation: Denote the set of allowed transformations by $F$ (that is a class of functions ${f:\mathbf{R}^2\to\mathbf{R}^2}$). Then you may solve $$\min_{f\in F} \sum_{a\in A}|F(a) - b|^2.$$

A pointer: In image processing this problem is the problem of registration and a good math book is called FAIR by Modersitzki. See the website.

-
I know Matlab has a cpcorr method, which is essentially what I'm trying to write in C++...I'm trying to figure out what algorithms they are using – Andrw Jul 20 '11 at 18:57

This is a problem that 'computer vision' deals with and they call it 'estimating homographies' - this also refers to transformation from $\mathbb{R}^n$ to $\mathbb{R}^n$ in general so you might have to add 'planar' or such when you google this. Depending on how many constraints you put on your transformation you can get away with using fewer and fewer points to determine all the parameters of the transformation. For example if you just had an euclidean transformation (that means homogenous scaling, translation and rotation) - for the planar case - you only need three points! (that's an extreme case). For the general case there are many different ways to do this (particualry if the problem is overdermined - so you cannot ask for 'a' solution anymore but have to start asking for the 'best' solution) - a popular method for this is based on the SVD. Recommended reading: multiple view geometry by Richard Hartley and Andrew Zisserman - that book deals with this problem in depth (among others). But you can also find some bits about this on the web.

-
Estimation of homographies usually requires knowledge of point correspondences. As far as I see, this knowledge was not available. – Mårten W Jan 20 '13 at 14:09
@MårtenW Hmm last paragraph in OP: I have selected points on both images that I know should be matched to each other. – Peter Sheldrick Jan 20 '13 at 15:27
@PeterSmith: I don't know how I missed this, but you are of course right. – Mårten W Jan 20 '13 at 15:39