Algorithms for Motion Tracking?

Keith Handy asks: "I seem to be unable to find algorithms and/or open source programs that will do accurate motion tracking, i.e. you mark a point on an object in frame 36, and the program can follow that point on that object through all the frames following it. This is useful not just for analyzing motion, but also for interpolating/extrapolating frames of video -- so if you had something at only 15 fps, you could generate inbetween frames (which are not just crossfades between the frames) and actually smooth the effect of the motion. Not something so complicated as to get into actual physics -- just something that will indicate where (in 2D only) that part of the object has moved from one frame to the next, for any given point in the whole picture. And for that matter it doesn't have to be 100% accurate, just any means of generating a reasonable motion-flow map." This doesn't strike me as an easy algorithm to develop, but are there any papers online or offline, that might describe an algorithm that can at least track objects in an image?

"In other words, I want something that does this, in order to write code that will do things like this and this. I already know how to write code to blur and warp images, so to be able to track motion would give me (and you) the same capabilities as these expensive plug-ins.

Anyone know any other resources, directions, or existing code I could look into to find out more about how this works, so I can incorporate it into my own programming instead of paying hundreds or thousands of dollars for limited, proprietary use of the technology?"

Comments

Book

[rm-r]

Hmm, not sure about any resources on the net, but I did similar stuff at uni so I can recommend a book. Try Image processing, analysis and machine vision by hlavac et al. It's a very good book with plenty of code-neutral algorithms. Good luck.

Video compression

[cperciva]

I think the best use of this would be in video compression -- if you can recognize the movement of objects between frames, you can encode how much things have moved instead of re-encoding the entire image.

Which is exactly what MPEG does... very crudely. The MPEG solution seems to be to compare a block (8x8?) of pixels with every block in the previous frame.

The fact that MPEG doesn't use anything more sophisticated than this suggests to me that there probably aren't any algorithms which consistently work better.

openCV

[bjpirt]

have a look at openCV (stands for open computer vision), it was originally developed by intel, but was later open souced. runs on both linux and windows and is mainly used for real time motion tracking of live video sources. i'm sure there are some pretty nice algorithms in the source there somewhere. They have their stuff on sourceforge

and a yahoo groups support forum thing here

the original intel pages are here
cheers,
bjpirt

what about intercorrelation ?

[dario_moreno]

Compute the 2D FFT of each frame (in grayscale), then get
the intercorrelation function of two neighbouring
frames. The maxima are more or less where
the objects have moved.

I only used this method on artificially generated
frames, ie 1 frame with translation and noise
added. Still, the intercorrelation sinks quite
fast. On natural images, there must be a lot
of fiddling to do.

KLT Feature Tracker

[The Whinger]

Have a look at the KLT tracker - that will probably do what you want.

An implementation can be found here:

http://vision.stanford.edu/~birch/klt/

tracking motion

[Anonymous Coward]

i don't know if this would suit your needs, but a package called "motion" has been available for quite some time which in fact is oriented to tracking frame differences from a video source:

http://motion.technolust.cx

there are some examples and a sample video which demonstrate tracking "motion."

just use the MPEG algorithm

[dutky]

Other folk have mentioned the MPEG motion compensation algorithm (though I think they got it a bit wrong). The algorithm chops up the current frame into 8x8 pixel block on even block sized boundries (first block at (0,0):(7,7), second block at (0,8):(7,15), and so on). These blocks are then compared against all possible 8x8 pixel blocks, local to the original block, in the adjacent frame (we compare against the blocks shifted by 1, 2, 3, 4, 5, 6, 7, and 8 pixels in both the x and y directions). Essentially, each block is compared against every possible sub block of a 12x12 pixel block centered on the original block's position. The comparisson succeeds if the difference between the two blocks in small enough (this is a threshold that you set).

Once you have done this for every block in the original frame, you have a set of motion vectors from which you can construct an intermediate frame.