20

TinEye, Google and others offer a "reverse image search" -- you can upload a photo and within seconds it will find similar photos.

Is there an open-source version of these algorithms?

I know about "SIFT" and other algorithms for finding "visually similar" photos, but they only work for comparing one photo directly to another. i.e., to find similar photos to a given photo is an O(n) operation, to find all visually similar photos would be O(n^2) -- both of which are prohibitively slow.

I need a feature descriptor that is indexable by a [relational] database to reduce the result set to something more manageable.

By "visually similar" I mean very similar. i.e, a photo that has been lightly touched up/recolored in Photoshop, slightly cropped or resized, photos taken in rapid succession of the same scene, or flipped or rotated images.

mpen
  • 272,448
  • 266
  • 850
  • 1,236
  • 1
    Did you take a look at Linear Discriminant Analysis (LDA) / Principal Component Analysis (PCA)? If I remember correctly, they were at some point used for image processing / face recognition and whatnot. Their strong point consists exactly of reducing feature description to something more manageable :) in this case, pixel info – i Code 4 Food May 21 '13 at 04:10
  • @Arthur: I'm implementing "AN IMAGE SIGNATURE FOR ANY KIND OF IMAGE" right now, I'll take a look at that one next if this one doesn't pan out. Thanks :-) Face recognition I don't need though. – mpen May 21 '13 at 04:34
  • I built an image similarity engine a few years back. You certainly can store features in relational databases but my recommendation would be to consider using an inverted index as your query engine. It gives you an order of magnitude more speed and flexibility when it comes to the delivery of your data. – Richard Marr May 24 '13 at 08:37
  • @RichardMarr: Reading the wikipedia on [inverted index](http://en.wikipedia.org/wiki/Inverted_index).. would I implement the inverted index as a separate lookup table in a relational database, or are you suggesting a non-relational database or flatfile for this? – mpen May 24 '13 at 18:39
  • 2
    @Mark I used a custom distributed server built on Lucene. These days you could do the same thing with Solr or Elasticsearch as they now support the partitioning you need to keep query times low with large numbers of visual words. MoreLikeThis queries and CustomScore queries are your friends. We managed to get visual similarity queries down to around 5-30 milliseconds across a few million images. – Richard Marr May 28 '13 at 09:10
  • @RichardMarr: Can you also provide the metric of how large the index, i.e. how many images it supported on each machine – saurabheights Dec 19 '15 at 06:16
  • 2
    @user1874627 we operated a few hundred thousand images per index, so depending on your hardware configuration between maybe 250k and 1m images per machine... but this was 2007-8. These days I'd either look at more SSDs, RAM drives, etc. as well as looking at cheaper horizontal scale options. Image complexity, feature choice, conversion of feature vectors to visual words, and query granularity are all dials you can tweak. – Richard Marr Dec 21 '15 at 23:27

2 Answers2

17

A valid approach you can consider is the Bag-of-Words model.

Basically you can do an offline computation of the target images. You can extract from those images a bunch of features in order to create a codebook with algorithms like k-means clustering. Searching for the nearest images will lead to the applications of an algorithm like Nearest neighbor search in the space of the codebook.

For the neighbour search you can use FLANN

Take a look also at: Visual similarity search algorithm

This is only a possibility and, truth must be told, this topic is really challenging and litterature on it is really huge.

Just some references:

Community
  • 1
  • 1
Nicola Pezzotti
  • 2,317
  • 1
  • 16
  • 26
  • The part I'm most interested in is how do we perform a nearest neighbour search on a relational database with vectors of ~500 dimensions? – mpen May 24 '13 at 00:39
  • 1
    FLANN doesn't answer the DB part of the question ;) I'm sure that would be great once all the data is in memory, but I can't read a million records into memory every time someone performs a search. Unless maybe I keep all the data in memory between requests... my signatures are ~500 bytes I think, so I could store quite a few depending on the memory requirements of FLANN. – mpen May 24 '13 at 18:43
  • 2
    You will use FLANN for search in codebook space. You need to link to a each codebook word a number of records in your DB. Then you can pick up some random images linked to that word or do some more in depth search. You can also build a hierarchy of codebook to further enhance your search – Nicola Pezzotti May 26 '13 at 21:34
2

Take a look at http://vision.caltech.edu/malaa/software/research/image-search/ it uses LSH algorithm and some kind of kd-tree. Also this task is called CBIR or image duplicate search.

mrgloom
  • 20,061
  • 36
  • 171
  • 301