7

There's a lot of different algorithms for computing the similarity between two images, but I can't find anything on how you would store this information in a database such that you can find similar images quickly.

By "similar" I mean exact duplicates that have been rotated (90 degree increments), color-adjusted, and/or re-saved (lossy jpeg compression).

I'm trying to come up with a "fingerprint" of the images such that I can look them up quickly.

The best I've come up with so far is to generate a grayscale histogram. With 16 bins and 256 shades of gray, I can easily create a 16-byte fingerprint. This works reasonably well, but it's not quite as robust as I'd like.

Another solution I tried was to resize the images, rotate them so they're all oriented the same way, grayscale them, normalize the histograms, and then shrink them down to about 8x8, and reduce the colors to 16 shades of gray. Although the miniature images were very similar, they were usually off by a pixel or two, which means that exact matching can't work.

Without exact-matching, I don't believe there's any efficient way to group similar photos (without comparing every photo to every other photo, i.e., O(n^2)).

So, (1) How can I create I create a fingerprint/signature that is invariant to the requirements mentioned above? Or, (2) if that's not possible, what other metric can I use such that given a single image, I can find it's best matches in a database of thousands?

Community
  • 1
  • 1
mpen
  • 272,448
  • 266
  • 850
  • 1,236
  • Do you need a linear hash (because your database only supports btree indices?) or could you use a GiST compatable solution? (see: http://www.postgresql.org/docs/9.1/static/gist.html) – SingleNegationElimination Apr 22 '12 at 20:59
  • @TokenMacGuy: I haven't settled on anything yet. I'd preferable like to use EntityFramework with it, which I believe limits me to these: http://msdn.microsoft.com/en-us/data/dd363565 – mpen Apr 22 '12 at 21:07
  • In the anime an manga community there's actually a solution that gives you closeness to images in percent. http://saucenao.com/ and the iqdb project http://iqdb.org/ use this. You might be able to ask them. They're using a CUSTOM database though! – sinni800 May 07 '12 at 12:51
  • Hi, I'm facing the same problem. Have you found a solution? If not, could you please show me the full code for generating a grayscale histogram? – Leon Jun 28 '12 at 17:29
  • @Leon: No, I haven't found a solution. I was using OpenCV with C# bindings to make the grayscale histogram. – mpen Jun 28 '12 at 23:12

1 Answers1

4

There's one little confusing thing in your question: the "fingerprint" you linked to is explicitly not meant to find similar images (quote):

TinEye does not typically find similar images (i.e. a different image with the same subject matter); it finds exact matches including those that have been cropped, edited or resized.

Now, that said, I'm just going to assume you know what you are asking, and that you actually want to be able to find all similar images, not just edited exact copies.

If you want to try and get into it in detail, I would suggest looking up papers by Sivic, Zisserman and Nister, Stewenius. The idea these two papers (as well as quite a bit of others lately) have been using is to try and apply text-searching techniques to image databases, and search the image database in a same manner Google would search it's document (web-page) database.

The first paper I have linked to is a good starting point for this kind of approach, since it addresses mainly the big question: What are the "words" in the images?. Text searching techniques all focus on words, and base their similarity measures on calculations including word counts. Successful representation of images as collections of visual words is thus the first step to applying text-searching techniques to image databases.

The second paper then expands on the idea of using text-techniques, presenting a more suitable search structure. With this, they allow for a faster image retrieval and larger image databases. They also propose how to construct an image descriptor based on the underlying search structure.

The features used as visual words in both papers should satisfy your invariance constraints, and the second one definitely should be able to work with your required database size (maybe even the approach from the 1st paper would work).

Finally, I recommend looking up newer papers from the same authors (I'm positive Nister did something new, it's just that the approach from the linked paper has been enough for me until now), looking up some of their references and just generally searching for papers concerning Content based image (indexing and) retrieval (CBIR) - it is a very popular subject right now, so there should be plenty.

penelope
  • 8,251
  • 8
  • 45
  • 87
  • If you read my second paragraph, I state the same thing (as TinEye). That's exactly what I mean by "similar" (as oppose to identical, which means *not* cropped, edited, resized, never mind 'same subject matter'). Here TinEye is a bit ambiguous, because those aren't "exact" matches either; which is why I didn't choose that word and chose to elaborate. – mpen May 09 '12 at 15:15
  • Also, I don't want text-based searching. At least not presently. I'll have to take a look at those papers later and see if I can pull our anything relevant, but from what you're saying, it doesn't sound like what I'm after. – mpen May 09 '12 at 15:23
  • @Mark Why do you have an aversion towards a method just because a similar one is used in a different field, if it suits your problems? If the kind of results this procedures give are not the type you need, then I understand, but if the input to the procedure is the one you're using (images, very large img databases) and the output is the desired one (that part is for you to consider) than I don't see why not to trust leading computer vision experts who deal with CBIR and try it their way. – penelope May 09 '12 at 16:15
  • I'm not averse to it, and I'll certainly look into what you said more, but it sounds to me like text-based searches and image-based searches are two very different things. I'm not sure whether or not this is relevant yet until I dive into it. – mpen May 09 '12 at 16:26
  • @Mark You should definitely look into it more - the main idea behind both works has come from the textual document searches, but is specifically adapted and re-tailored to fit the new context, image retrieval. I never did much work with text, but I work with computer vision and image processing daily and this kind of re-application of known techniques from other fields are very popular and successful lately – penelope May 10 '12 at 08:54