As far as I know, homography or projective transform can be estimated only when the correspondences of points in two planes are available.

RANSAC is a method to estimate parameters of a model from a set of observed data which contains outliers. In the task of homography estimation, the "observed data" means the correspondence of points, NOT the points themselves.

In your case, a crazy solution can be like this:

1. From all possilbe point correspondences between the two planes, randomly sample a sufficient number of correspondences, and regard them as the observed data

2. Use RANSAC to estimate the model and get the minimum model fitting cost

3. Repeat 2. and 3. as many times as possible, and select the model with the lowest minimum model fitting cost

You may notice that this solution is almost not doable in practice. The freedom is too high, i.e. the number of all possible point correspondences between the two planes are too large, such that you have to repeat 2. and 3. a very huge number of times to get a MAYBE correct result.

So, my suggestion is, 1. define a criterion of point correspondence (visual similarity or shape similarity, etc.), 2. find potential correspondences based on this criterion, and 3. use RANSAC (OpenCV or matlab, etc.) to find the homography. This is the only doable solution I can imagine to solve your problem...

I happen to consider your problem before.

As Xiaomeng Wu answered, if you use un-corresponding points between the world plane and the image, the number of possibility of correspondence (PoC) is very huge. It will results in that you cannot verify all results in practice. Thus, my advice is:

1. Use other feature or criterion to reduce the number of primitives as possible as you can.

For example, using lines, color or most special ones you define.

2. For any one PoC, there is a rapid method to judge its reasonability. See my previous work "Automatically obtaining the correspondences of four coplanar points for an uncalibrated camera".

3. To residual PoC, then use RANSAC to compute.

All above steps may help you find a proper way to solve your problem. But it also depends on the complexity of your problem.

Previous answers are correct but I feel that there are two details missing:

1- the main issue is not if you have too many points but how many points will be incorrect. RANSAC will work fine for up to 50% outlier, if you match randomly that number will be above90% for sure. However, you could use RANSAC on the parameters. This is old school and a bit strange, work with few parameters (do you need projective matrix?). The way you do this is randomly create a transform matrix (within reason) and see how many points get correspondences using that matrix. May work :)

2 - you say your points are "widely spaced dots", this does not mater, if for instance you know that the different view points have no inversion ( left is left and right is right) you can force ordering in the matching of your points. Also if you can have a relaxed neighborhood prior (10-20%) of image area for match search then you can try some random putative matches within those restraints. This may limit the search space enough for it to work.

Good luck

I'll study Shen Cai's recent paper before proceeding--it looks good.

I had hoped that for two lists with a small number of points, there would exist a small program to randomly pick 4 points from each, compute the homography to map from list A to list B, transform the remaining points from A and see how many fall sufficiently close to those in B. Then refine the homography using all close pairs if there are enough, or repeat with another random 4 points. I've found homework assignments for more than one computer vision class that appear to ask for such a toy problem (no answers found though), but the next assignment always seems to be to use SIFT or other features to generate putative matches to feed into RANSAC. Maybe the point is to show how slow and limited random matching is, as Xiaoming Wu notes. Pedro Quelhas's idea of selecting points from a smaller neighborhood might help reduce the brute-force computational time.

I'll study Shen Cai's recent paper before proceeding--it looks good.

Otherwise, I'll try to establish putative matches using shape measures, as Xiaoming Wu suggests. I'll consider use of cross-ratios, or P-2 projective and permutation invariant measures, to find possibly matching quads. Unique quad identifiers would be ideal, otherwise some sort of hashing/searching and voting may be needed.

I thank you, and any others who contribute to save me from writing programs.