Matching descriptor to database of descriptors

Question

I'm trying to find a fast way to match descriptors from a database. My program works the following way:

1) Populates a database with descriptors of images (using proper feature detection algorithms)

2) Load an image

3) Extracts descriptor for that image and compares it to all descriptors in the DB, so it can find a proper match.

As you can imagine, it's very heavy to compute a comparison of 32 descriptors millions of times. I've used a hashing function, but that only works for two descriptors that are exactly the same, thus only matching two exactly identical images.

What do you suggest I use to speed up this search?

Cheers

EDIT:

I've decided to start by approaching a Neural Network solution. Here's a pretty good link for anyone who wants to get started on the subject.

Answer 1

What you are trying to accomplish is essentially called machine learning/classification. Directly comparing is really hopeless given the size of your database.

Just in case you are not aware of the terminology. The database that you have is called the learning-dataset. You need to use a machine learning algorithm like SVM (support vector machine), K-NN (K-nearest neighbours), Neural networks etc to learn a model. This model is later on used to predict the outcomes of an new and fresh instance, ie. the vector you want to compare your database with.

I would strong suggest the use of SVM, since it is the state of the art classifier in machine learning literature. There is an implementation of it called "SVM light". http://svmlight.joachims.org/. It is also possible to do ranking with SVM-light. please have a look at that as well.

You can also try and use neural networks. I use neural network toolbox in matlab for this (nprtools) which is pretty neat.