Automatic tracking algorithm

Question

I'm trying to write a simple tracking routine to track some points on a movie.

Essentially I have a series of 100-frames-long movies, showing some bright spots on dark background. I have ~100-150 spots per frame, and they move over the course of the movie. I would like to track them, so I'm looking for some efficient (but possibly not overkilling to implement) routine to do that.

A few more infos:

• the spots are a few (es. 5x5) pixels in size
• the movement are not big. A spot generally does not move more than 5-10 pixels from its original position. The movements are generally smooth.
• the "shape" of these spots is generally fixed, they don't grow or shrink BUT they become less bright as the movie progresses.
• the spots don't move in a particular direction. They can move right and then left and then right again
• the user will select a region around each spot and then this region will be tracked, so I do not need to automatically find the points.

As the videos are b/w, I though I should rely on brigthness. For instance I thought I could move around the region and calculate the correlation of the region's area in the previous frame with that in the various positions in the next frame. I understand that this is a quite naïve solution, but do you think it may work? Does anyone know specific algorithms that do this? It doesn't need to be superfast, as long as it is accurate I'm happy.

Thank you

nico

Answer 1

Predator (TLD Algorithm) by Zdenek Kalal is also good for Automatic Tracking

See this:

http://www.youtube.com/watch?v=1GhNXHCQGsM

and

http://bit.ly/shahab-vision

Answer 2

Sounds like a job for Blob detection to me.

Answer 3

This has got to be a well reasearched topic and I suspect there won't be any 100% accurate solution.

Some links which might be of use:

Learning patterns of activity using real-time tracking. A paper by two guys from MIT.

Kalman Filter. Especially the Computer Vision part.

Motion Tracker. A student project, which also has code and sample videos I believe.

Of course, this might be overkill for you, but hope it helps giving you other leads.

Answer 4

I'm afraid that blob tracking is not simple, not if you want to do it well.

Start with blob detection as genpfault says.

Now you have spots on every frame and you need to link them up. If the blobs are moving independently, you can use some sort of correspondence algorithm to link them up. See for instance http://server.cs.ucf.edu/~vision/papers/01359751.pdf.

Now you may have collisions. You can use mixture of gaussians to try to separate them, give up and let the tracks cross, use any other before-and-after information to resolve the collisions (e.g. if A and B collide and A is brighter before and will be brighter after, you can keep track of A; if A and B move along predictable trajectories, you can use that also).

Or you can collaborate with a lab that does this sort of stuff all the time.

Answer 5

I would suggest the Pearson's product. Having a model (which could be any template image), you can measure the correlation of the template with any section of the frame.

The result is a probability factor which determine the correlation of the samples with the template one. It is especially applicable to 2D cases. It has the advantage to be independent from the sample absolute value, since the result is dependent on the covariance related with the mean of the samples.

Once you detect an high probability, you can track the successive frames in the neightboor of the original position, and select the best correlation factor.

However, the size and the rotation of the template matter, but this is not the case as I can understand. You can customize the detection with any shape since the template image could represent any configuration.

Here is a single pass algorithm implementation , that I've used and works correctly.

Answer 6

Simple is good. I'd start doing something like:

1) over a small rectangle, that surrounds a spot:
2) apply a weighted average of all the pixel coordinates in the area
3) call the averaged X and Y values the objects position
4) while scanning these pixels, do something to approximate the bounding box size
5) repeat next frame with a slightly enlarged bounding box so you don't clip spot that moves

The weight for the average should go to zero for pixels below some threshold. Number 4 can be as simple as tracking the min/max position of anything brighter than the same threshold.

This will of course have issues with spots that overlap or cross paths. But for some reason I keep thinking you're tracking stars with some unknown camera motion, in which case this should be fine.