Correspondence -- matching them ~ VIRTUAL VIEW

Recently I'm doing the correspondence work for the target tracking with one camera tracking system. For the multi-camera tracking systems the location and transformation are always 'friendly' to be found, but by the single camera, things seem always antagonistic. Based on the camera image, on which the detected points are, we should show out the orginal 3D location of the target related to an assigned coordinate system. So far there are already an amount of algorithms cooperating with each other to reconstructe the object.

According to the picture above, what we can obtain from a camera detecting system is just the projected image coordinate in camera coordinate system, like (x1,y1), (x2,y2) ..... while to achieve the 3D Target coordinate as the following object sounds a long way to go!

So with the previous knowledge about the target geometry and the detected image, what we first should tell is the correspondence between the actual marker to be measured and the available projected images. That is to say we should be able to distinguish the different projected points in the image, and match them exactly to proper markers.

At first let's discuss the number of the possible correspondences, supposing there are N markers of a target and the camera detected M marker-images (but inside there could be noise image which should not be considered), and assume all of the markers ought to be seen by camera, So the number of possible correspondences is

Num = M!/(M-N)!

If we think a little more complicated that not all markers can be detected, so we should think about the subset of such combination, and of course the formula can be more 'frightful'! Supposing the size of subset is S,

Num = N!xM!/[(N-S)!x(M-N)!]

And the value of S is logically not decided, so with all possible S, the possible number of the correspondence is:

Num=SUM{N!xM!/[(N-S)!x(M-N)!]} for all 3<=S<=N Based on this nice formula let's check a short example, with N = 5, M = 6 tracking situation, the number of possible correspondence is 3720. Seems not bad, right? But with the increase of N the amount of correspondence will increase exponentially. Horrible!!

The problem is truly complex but there are also helpful solutions. And my next job is to find the available algorithms, implement them, compare them and develop them. So far as I have found: The softPOSIT algorithm developed by DeMenthon is able to calculate the correspondence automatically, and the advantage is avoiding going through all possible correspondences; The RANSAC paradigm developed by Fischler which is a method to find the maximal number of samples that fit into the desired model, and it effectively rejects outliers and clutter. The obvious advantage is that only a fraction of the subsets of S, with the minimum number of s points, has to be tried in order to find the maximum set, because it always choose the best one for the next step calculation, it saves a lot. Some of the narrowing search space tools are also quite important, like clustering method to group the samples in order to reduce the search, extrapolation which is used after one correspondence has been found to extrapolate the rest markers, and some of the similar approximations.

And enjoy a funny video about the visualisation of correspondence: