RANSAC is an algorithm that finds the inliers in a set of data with many gross outliers. For it to work, there must be an underlying model that can be fit to some of the data points. RANSAC repeatedly instantiates this model, using small, random subsets of the data, until a model is found that is consistent with a large subset of the data.
It works as follows:
I applied RANSAC to the problem of recovering original camera position (otherwise known as camera pose) from a picture containing some particular colored markers. RANSAC and a method for determining camera pose from 4 coplanar points were both discussed in the original paper.
To determine pose using 4 coplanar points, their locations must be known both in the image plane and in the plane in 3D space (known as the object plane). I used several pictures of the same grid, and drew colored markers in each picture at the same grid locations in each (see original images below). The reason RANSAC is needed is that there are more markers than there are distinct colors.
As can be seen, there are 2 blue markers, and 4 red markers. When a blue marker is identified in the image, it's image coordinates become known, but it's object coordinates could be either 5-down, 0-over, or 6-down, 1-over. In other words, the program sees a blue marker, but doesn't know which one it is. The problem is worse with the red markers. Every time any red marker is found, 4 data points are generated with identical image coordinates, but each has the object coordinates of one possible red marker.
All in all, there are 12 markers in each image, but because colors are duplicated there are 36 possible image-coord / object-coord pairs. That means each pair has a 1/3 probability of being a good one. My program searches for 4 good pairs, ones that give rise to a camera pose that then in turn sees at least 11 points in the right place in the image when they are projected using that pose. It then uses all the points to determine a final camera pose. It works like this:
RANSAC: Was described above.
Computing pose from a homography:
Finding colored markers: I rely on the hue of each color being fairly predictable.
Detected marker locations. The larger colored circles are the markers, which are part of the original image, and their detected locations are shown by the small circles near their edges.
Final set in agreement with all 12 points. The blue circles show the reprojected data point locations (their radii are the error bounds).
Recovered camera pose. The small blue squares are the markers, reoriented to be level. The large blue square is the object plane. The red square is the image plane of the camera that took the picture, and the red line passing through it is the direction in which the camera is looking.
Consensus set and result for another image
This image was perspective-warped with the Gimp before recovering pose.
This image was also perspective-warped before recovering pose.
M.A. Fischler and R.C. Bolles. "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography." Communications of the ACM. June 1981. Vol. 24, No. 6.