Estimation of the correspondence -- RANSAC

In the previous article I have mentioned the problem of the correspondence determination between the real markers and the image points. I have calculated the possible correspondences for N markers and M marker-images. But how to finally determine the correct correspondence is far more difficult than that. Here I will introduce one of the most popular way for the correspondence or the parameter estimation applications in computer vision -- RANSAC, which is an abbreviation for "RANdom SAmple Consensus". It was first published by Fischler and Bolles in 1981. It is advantageously used to estimate parameters of a mathematical model from a number of observed data with a iterative method. And the data is divided into inliers and outliers. The so-called inliers are the suitable candidates which suffice the mathematical model, while the outliers are the traitors.

According to the content of this method, RANSAC is a non-deterministic algorithm, the final result is just reasonalbe with certain probability. Besides elimination of the outliers, RANSAC is also able to establish a parameterized model for a set of the inliers. In wikipedia there is a example to demonstrate this theory with a 2D line model. But for our camera tracking correspondence it is not so lucky with such a simple model of so limited parameters. Let's look at the abstract idea of this algorithem:

Given:
1) D = {Xi} D is set of data points, |D| = N
2) f(Y): Y--> p Y is a sample from D, and f is the function to compute the model
parameters p with this sample
3) C(X,Y) it's the cost function to evaluate the result for a single point x

To achieve:
p* parameters of the model maximizing the cost function

Algorithm:

n:=o

--initialized cost function C* = 0
repeat until cost function C(x,y) is smaller than threshold

--select randomly set Yi from the whole database D

--based on the requirement calculate the parameters pk

--compute the cost function Ck

--if C* is smaller than Ck, then C*=Ck, p*=pk

end

In our situation,
a)the to be determined parameters are the rotations and translations of the markers and the correspondence result, that is to say which marker-image corresponds to which real marker.
b)the set of data is all possible projection images of the object onto the image plane.
c)the cost function can be the sum of the distances between the projected marker-images and the closest detected images on the sensor

And based on these Hypothesis and algorithm, the correspondence problem could be solved possibly.

Posted in: tracking technology,Virtual Reality