Metric for finding similar images in the database

Question

There are many different algorithms for calculating the similarity between two images, but I can not find anything about how you store this information in the database in order to quickly find similar images.

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

I'm trying to come up with a “ fingerprint ” of images that I can quickly find.

The best I have come up with so far is to generate a histogram of grayscale . With 16 cells and 256 shades of gray, I can easily create a 16-byte print. This works pretty well, but it's not as great as we would like.

Another solution I tried is to resize the images, rotate them so they are oriented the same way, grayscale, normalize the histograms, and then compress them to about 8x8 and reduce the colors to 16 shades of gray. Although the thumbnails were very similar, they were usually turned off by a pixel or two, which means that an exact match might not work.

Without exact correspondence, I do not think that there is an effective way to group similar photos (without comparing each photo with every other photo, i.e. O (n ^ 2)).

So, (1) How can I create, I create a fingerprint / signature that is independent of the requirements mentioned above? Or, (2) if this is not possible, what other metric can I use so that for a given single image I can find the best matches in the database of thousands?

Answer 1

There is one confusion in your question: the “fingerprint” associated with you is clearly not intended to search for similar images (quote):

TinEye usually does not find similar images (that is, another image with the same subject); it finds exact matches, including those that have been cropped, edited, or modified.

Now, I said, I’m just assuming that you know what you are asking for and that you really want to find all similar images, not just edited replicas.

If you want to try to understand this in detail, I would suggest looking for documents from Sivic, Zisserman and Nister, Stewenius . The idea that these two articles (as well as quite a few others have recently) used is to try to apply text search methods to image databases and search the image database in the same way that Google will search for a document (web -page).

The first document I am involved with is a good starting point for this approach, since it mainly addresses the big question: what are the “words” in the images ?. Text search methods focus on words and base their similarity methods on computations, including word count. Thus, the successful presentation of images as collections of visual words is the first step to applying text search methods to image databases.

the second document then broadens the idea of ​​using text technology, introducing a more appropriate search structure. Thanks to this, they provide faster image processing and large image databases. They also offer how to create an image descriptor based on a basic search structure.

The functions used as visual words in both documents should satisfy your invariance restrictions, and the second should definitely be able to work with the required database size (maybe even working with the 1st job will work).

Finally, I recommend looking for new articles from the same authors (I'm sure Nister did something new, just so that the tied paper approach has been enough for me so far), looking at some of my links and generally looking for content-based content indexing and search (CBIR) documents are a very popular subject right now, so there should be a lot.