SURF and SIFT Alternative Object Tracking Algorithm for Augmented Reality

Question

After asking here and trying both SURF and SIFT, neither of them seams to be efficient enough to generate interest points fast enough to track a stream from the camera.

SURF, for example, takes around 3 seconds to generate interest points for an image, that's way too slow to track a video coming from a web cam, and it'll be even worse when using it on a mobile phone.

I just need an algorithm that tracks a certain area, its scale, tilt, etc.. and I can build on top of that.

Thanks

Repulsive

Answer 1

I suspect your SURF usage may need some alteration?

Here is a link to an MIT paper on using SURF for augmented reality applications on mobile devices.

Excerpt:

In this section, we present our implementation of the SURF al- gorithm and its adaptation to the mobile phone. Next, we discuss the impact that accuracy has on the speed of the nearest-neighbor search and show that we can achieve an order of magnitude speed- up with minimal impact on matching accuracy. Finally, we dis- cuss the details of the phone implementation of the image matching pipeline. We study the performance, memory use, and bandwidth consumption on the phone.

You might also want to look into OpenCV's algorithms because they are tried and tested.

Depending on the constraints of your application, you may be able to reduce the genericness of those algorithms to look for known POIs and markers within the image.

Part of tracking a POI is estimating its vector from one point in the 2D image to another, and then optionally confirming that it still exists there (through pixel characteristics). The same approach can be used to track (not re-scan the entire image) for POI and POI group/object perspective and rotation changes.

There are tons of papers online for tracking objects on a 2D projection (up to a servere skew in many cases).

Good Luck!

Delatorre

The only thing I can think of that might slow it down is the fact that it's in Java. Other than that, it's clear that generating interest points is what's taking long. – Repulsive

Answer 2

You should try FAST detector

http://svr-www.eng.cam.ac.uk/~er258/work/fast.html

Oberstone

Answer 3

We are using SURF for a project and we found OpenSURF to outmatch OpenCV's SURF implementation in raw speed and performance. We still haven´t tested repeatability and accuracy, but it is way faster.

---

Update: I just wanted to point out that you needn't perform a SURF match step in each frame, you could simply do it every other frame and interpolate the position of the object in the frame you don't execute SURF on.

Embroider

Just wanted to comment that with the latest version of OpenCV the SURF implementation has been rewritten to utilize Intel Threading Blocks. If your execution device has more than one core, the speedup is incredible (much faster than OpenSurf) – Embroider

Answer 4

You can use a simpler algorithm if you would make stricter restrictions on the area you would like to be tracked. As you surely know, ARToolKit is pretty fast, but only tracks black and white markers with a very distinct frame.

If you want a (somewhat) general purpose tracker, you may want to check PTAM. The site (http://www.robots.ox.ac.uk/~gk/PTAM/) is currently down, but here's a snazzy video of it working on an iPhone (http://www.youtube.com/watch?v=pBI5HwitBX4)

Mathematical

I didn't know about PTAM, but from the videos it looks really good. I guess I'll just have to wait till it's up again. I tried searching Google Code Search but.. nothing. – Repulsive

Answer 5

As others have mentioned, three seconds seems unusually long. While testing the SURF implementation in the Mahotas library, I found that it took on average 0.36sec, even with some fairly large images (e.g. 1024x768). And that's with a mix of Python and C, so I'd imagine some other pure-C implementations would be even faster.

Alejoa

Author of mahotas here: Actually, the Python layer is very thin. I would not expect a large increase in speed from pure C. – Lowe

Answer 6

I found this nice comparison of each feature detection algorithms at http://computer-vision-talks.com/2011/01/comparison-of-the-opencvs-feature-detection-algorithms-2/

Have a look. It might be useful!

According to that comparison, and as mirror2image has also suggested, FAST is the best choice. But it depends on what you really want to achieve.

Shalne

Answer 7

One option I've used in constrained embedded systems is to use a simpler interest point detector: FAST or Shi-Tomasi for example. I used Shi-Tomasi, as I was targetting an FPGA and could easily run it at pixel rate with no significant buffering required.

Then use SURF to generate the descriptors for the image patch around the identified features and use those for matching and tracking purposes.

Muskrat