4

I would like to find a way which would allow to compare a SIFT descriptor of an image (query) with descriptors in a SQL database which contains lots of descriptors of differents pictures.

In fact, my final purpose is to do an application which allow to compare one picture with lots of picture in a database (not in my device) but in a SQL database.

The first thing i thought was to stock each descriptors on the SQL database and compare each descriptors to another one using the Brute Force method or the FlanneBased method. The problem is that,in a SQL database, it would take a long time to compute a matching because of the "mathematics" behind the matching (Euclidean distance for example is sqrt(a²+b² +...) ) and it's not possible to do that kind of comparison in an huge database.

For example a SIFT descriptor contains 128 numbers if i'm not mistaken so imagine the time comparing each number of each descriptors together.

If there another way to do that stuff ? I know in a SQL database, requests are efficient when you use something like "SELECT a FROM b WHERE ..."

Therefore i wonder if there is a way to stock SIFT descriptors in an efficiently way ? For example i thought about "to crypte" the descriptors into a kind of big string chain and each chain would be unique and therefore i could compare them together but i don't know if it's a good solution.

I've already read this post : Comparing SIFT features stored in a mysql database but it didn't help me. Thank you.

Community
  • 1
  • 1
lilouch
  • 1,054
  • 4
  • 23
  • 43
  • possible duplicate of [Comparing SIFT features stored in a mysql database](http://stackoverflow.com/questions/3505674/comparing-sift-features-stored-in-a-mysql-database) – marol Aug 04 '14 at 14:09
  • 1
    try locally sensitive hashing: https://www.ceremade.dauphine.fr/~cohen/mypapers/auclairAMR07.pdf or other hashing methods – Micka Aug 04 '14 at 14:10
  • and have a look at this: http://stackoverflow.com/questions/5751114/nearest-neighbors-in-high-dimensional-data – Micka Aug 04 '14 at 14:16
  • Marol, yeah i saw this post but it didn't help me. Concerning the paper,i'll read it. Hashing allows to do what i want ? – lilouch Aug 05 '14 at 07:59

2 Answers2

1

If I were you, I would prefer comparing the descriptors in the code, rather than in SQL. SQL isn't meant for that. I would do the following:-

1. Pre-load N descriptors from SQL onto memory.
2. Compare distances to query descriptor, descriptor by descriptor.
3. If distance<threshold, push to possiblematches.
4. When you reach N/2 descriptors, push the next N.
5. Compare all matches, choose the best one or the best D descriptors, as per your requirement.

However, for this, I'd rather use OpenCV¡s inbuilt FileStorage class which provides I/O onto XML and YAML files; it solves the headache of manually parsing descriptor values.

The Nomadic Coder
  • 580
  • 1
  • 4
  • 16
  • Is it fast ? Because i doing an application and i would like to compare in a faster way picture in a server and not inside the "device". So for example i take a picture, i compute its descriptors and after that, i pre-load descriptors from SQL ? That's it ? – lilouch Aug 05 '14 at 08:03
  • The speed would depend on the number of descriptors you have in your database. However, OpenCV has different approximate distance measures also, such as FLANN (which is faster than just calculating euclidean distances). In case you are very particular on running it on your server, you could write a simple PHP script which does the same. As you're just calculating distances, it's not very difficult – The Nomadic Coder Aug 05 '14 at 09:33
  • Okey. If i follow your algortihm, i don't understand this part" However, for this, I'd rather use OpenCV¡s inbuilt FileStorage class which provides I/O onto XML and YAML files; it solves the headache of manually parsing descriptor values" . Why do i need an xml file ? Sorry, i'm a bit confusing. – lilouch Aug 07 '14 at 08:09
  • That was before I realised that you wanted to run it on the server. If you would like to push your data to a server, its possible that SQL is the best option (as it handles speed/security/etc. pretty much automatically). OpenCV's file storage module (http://docs.opencv.org/modules/core/doc/xml_yaml_persistence.html) just provides an easy to way to persistently save OpenCV structures. – The Nomadic Coder Aug 07 '14 at 09:23
0

It is not optimal to use a SQL database to compare SIFT. OpenCV proposes some keypoint matchers that are more efficient. You can find an example in ./samples/cpp/matcher_simple.cpp with SURF descriptors that is easily adaptable to SIFT. Basicaly, the core is

BFMatcher matcher(NORM_L2);
vector<DMatch> matches;
matcher.match(descriptors1, descriptors2, matches);

As far as I remember, some matchers (e.g Flann) only works with descriptors of certain type (CV_32F).

xiawi
  • 1,772
  • 4
  • 19
  • 21
  • Thank but i know how to do a matching ! Actually i do an application and i need to compute the matching in fly with a server and not inside the device, you know ? – lilouch Aug 05 '14 at 08:00
  • 1
    You can match within the server, it is the most efficient approach. Look at http://lear.inrialpes.fr/pubs/2008/JDS08/jegou_hewgc08.pdf for instance. For a very large database, aggregate the SIFT into a VLAD, compress them and use asymetric search in compressed domain: http://hal.inria.fr/inria-00633013/PDF/jegou_aggregate.pdf . For an average-size databaze, you can use an inverted index with a large vocabulary (and then use your SQL database to implement the inverted index): http://www.robots.ox.ac.uk/~vgg/publications/2007/Philbin07/philbin07.pdf . – xiawi Aug 05 '14 at 12:39
  • Thank you ! wow for a beginner it seems difficult but i'll read these papers and try to understand. But now i did a lot of researche i don't know which way is more efficient between your approach (papers) and do a hash of my descriptors and then compare them. – lilouch Aug 05 '14 at 12:54
  • Indeed these papers are quite technical. For your case, if by " lots of picture" you mean less than 100,000 anyway, I'd say you can look at the (Philbin et al. 2007 approach). In that case, let just see it as a classical inverted index with bag of words, but replace the words with the SIFT (thus use flann L2 distance to match the descriptor of an image with the codebook). – xiawi Aug 06 '14 at 13:11
  • I've already implemented BoW with SIFT descriptors and it works "The problem" with BoW is, i have to train it with lots of class (in my case more 100 ) and it takes lots of time so i don't think it will be a good solution, that's why i changed the way to process,that is to say compute the descriptors and store them in a database by hashing the descriptor (question of efficiency) and then with a query, do the same in order to compare it with the database. Yes i mean less than 100 000 i think. But according to [this post](http://stackoverflow.com/q/2146542/3201833) i can't do an hash.. – lilouch Aug 07 '14 at 07:43
  • I though you tried to do retrieval, not classification (but retrieval with labels is equiv. to KNN though). Anyway, regarding hash, it depends what you consider as a hash: the paper (Jegou et al, PAMI 2012) produces a hash for each image, that results from aggregation (and compression) of local descriptors. If you compress enough, you don't even need inverted index. As well, look at the third answer (Stephan) of [this post](http://stackoverflow.com/questions/2074956/logo-recognition-in-images) – xiawi Aug 07 '14 at 09:18
  • Yeah i want to do retrieval picture but BoW is for classification no ? That's why when i used BoW i have to train it with for my classes. but maybe i'm wrong and if i want to do retrieval i don't need any classes and i just have to compute the BoW with all my database ? Indeed, i have a big descriptor and me an hash allow yo reduce the descriptor into a string (lenght of 10 for exemple) and after i can easily compute the hamming distance between all my "fingerprint". – lilouch Aug 07 '14 at 09:40
  • BoW can be used for classif, but the retrieval with inverted index rely on BoW description (i.e BoW is the implicit "forward index"). Regarding hashing, you need here a "perceptual hash" that is not subject to the "avalanche effect". – xiawi Aug 07 '14 at 13:12
  • Okey can you explain me the framework to do a retrieval picture with BoW please ? Because i know how to use it for a classification but just for retrieval, i have some difficulties. Do i have to compute all the descriptors for all the database and then put them to a big cv::Mat. After that, do the same for the query and finally use an nearest neighbo algorithm ? Thank – lilouch Aug 08 '14 at 12:04