search

image-rs / imageproc

Image processing operations
MIT License
738 stars 145 forks source link

Add SURF features #17

Open theotherphil opened 8 years ago

theotherphil commented 8 years ago

https://en.wikipedia.org/wiki/Speeded_up_robust_features

akonneker commented 8 years ago

The image processing online journal has an open-access article about the SURF method, along with a sample implementation in c: http://www.ipol.im/pub/art/2015/69/

However, it may be best to avoid SURF here, as it is technically patented in the US: http://dsp.stackexchange.com/questions/1288/what-are-some-free-alternatives-to-sift-surf-that-can-be-used-in-commercial-app.

... I hate software patents.

theotherphil commented 8 years ago

Ah, I didn't realise SURF was patented too. That's a shame. I'm pretty clueless on the restrictions on using patented algorithms - there are already several high profile open source implementations of both algorithms online. Maybe we'll shelve this for now and when we have a need for something SIFT-like find a definitely-not-patented alternative.

theotherphil commented 8 years ago

BRISK perhaps? http://www.asl.ethz.ch/people/lestefan/personal/iccv2011.pdf

akonneker commented 8 years ago

Based on that discussion from the SO thread I linked earlier and some discussion from the OpenCV forum, publishing code for the patented technique is fine... but you'd need a license from the patent-holders to use it in any commercial application. Online advice about legal matters is obviously best taken with a grain (or chunk) of salt. Probably best avoided.

In addition to BRISK, I've heard that (A)KAZE is supposed to be good: http://www.robesafe.com/personal/pablo.alcantarilla/kaze.html

It's something I'd like to get to eventually, but it may be a while. So if anybody else wants to implement a good feature detector, they should do it!

kwaegel commented 8 years ago

If you include SIFT/SURF, I'd suggest putting it in a "nonfree" module like OpenCV, to indicate that it is not safe for general use.

That aside, I'd be interested in adding a binary feature descriptor like BRIEF, ORB, AKAZE, or LATCH. BRIEF or ORB are probably the easiest to start with, since you already have a FAST detector implemented. AKAZE, I believe, needs it's own specialized detector.

By far the fastest method is just to directly port some of the detectors over from OpenCV, since Rust is a more-or-less similar language. The MIT license imageproc uses should be compatible with the 3-clause BSD one in OpenCV.

Clean-room reimplementation from the original research papers also works, but would take a bit longer.

theotherphil commented 8 years ago

Good suggestions. BRIEF sounds like a great choice.

I think we should avoid both SIFT and SURF for now, and stick with non-patented stuff.

I'm strongly against just directly copying the OpenCV code, but their implementation of the core numerical bits might give some helpful guidance.

If you fancy implementing any of these methods that would be fantastic. The current implementation of FAST detectors in this library isn't as fast as it could be, but if this causes any issues I'm happy to help speed it up.

theotherphil commented 8 years ago

As fast Hamming distance appears to be crucial, we might want to use this crate: https://crates.io/crates/hamming/.

kwaegel commented 8 years ago

I'll create an issue for adding BRIEF features and see how things go. The algorithm itself seems straightforward, mostly lookup tables of pixel pairs with some pre-smoothing.

Thanks for mentioning the hamming distance crate. Feature matching is orthogonal to descriptor extraction, so I'll create a separate issue to track it.

theotherphil commented 8 years ago

Great! Let me know if there's anything you need from me.