46

TinEye, the "reverse image search engine", allows you to upload/link to an image and it is able to search through the billion images it has crawled and it will return links to images it has found that are the same image.

However, it isn't a naive checksum or anything related to that. It is often able to find both images of a higher resolution and lower resolution and larger and smaller size than the original image you supply. This is a good use for the service because I often find an image and want the highest resolution version of it possible.

Not only that, but I've had it find images of the same image set, where the people in the image are in a different position but the background largely stays the same.

What type of algorithm could TinEye be using that would allow it to compare an image with others of various sizes and compression ratios and yet still accurately figure out that they are the "same" image or set?

1
  • 1
    Interesting link... spelling police: I believe the site is actually called "TinEye", not "TinyEye". :) Commented Jun 17, 2009 at 6:28

8 Answers 8

45

These algorithms are usually fingerprint-based. Fingerprint is a reasonably small data structure, something like a long hash code. However, the goals of fingerprint function are opposite to the goals of hash function. A good hash function should generate very different codes for very similar (but not equal) objects. The fingerprint function should, on contrary, generate the same fingerprint for similar images.

Just to give you an example, this is a (not particularly good) fingerprint function: resize the picture to 32x32 square, normalize and and quantize the colors, reducing the number of colors to something like 256. Then, you have 1024-byte fingerprint for the image. Just keep a table of fingerprint => [list of image URLs]. When you need to look images similar to a given image, just calculate its fingerprint value and find the corresponding image list. Easy.

What is not easy - to be useful in practice, the fingerprint function needs to be robust against crops, affine transforms, contrast changes, etc. Construction of good fingerprint functions is a separate research topic. Quite often they are hand-tuned and uses a lot of heuristics (i.e. use the knowledge about typical photo contents, about image format / additional data in EXIF, etc.)

Another variation is to use more than one fingerprint function, try to apply each of them and combine the results. Actually, it's similar to finding similar texts. Just instead of "bag of words" the image similarity search uses a "bag of fingerprints" and finds how many elements from one bag are the same as elements from another bag. How to make this search efficient is another topic.

Now, regarding the articles/papers. I couldn't find a good article that would give an overview of different methods. Most of the public articles I know discuss specific improvement to specific methods. I could recommend to check these:

"Content Fingerprinting Using Wavelets". This article is about audio fingerprinting using wavelets, but the same method can be adapted for image fingerprinting.

PERMUTATION GROUPING: INTELLIGENT HASH FUNCTION DESIGN FOR AUDIO & IMAGE RETRIEVAL. Info on Locality-Sensitive Hashes.

Bundling Features for Large Scale Partial-Duplicate Web Image Search. A very good article, talks about SIFT and bundling features for efficiency. It also has a nice bibliography at the end

5
  • @Igor, good answer! Do you have any links or resources you can provide on fingerprint algorithms other than the one you mentioned in your post?
    – mmcdole
    Commented Jun 17, 2009 at 21:01
  • +1. Do you have any reference to relevant papers? I've found a few but I don't know how good they are. Commented Jun 17, 2009 at 21:05
  • @Simucal: I will update my answer with some links to articles. Commented Jun 18, 2009 at 8:00
  • @Vinko: actually, the book that you mentioned seems to be good (but I haven't read it). Commented Jun 18, 2009 at 8:02
  • stackoverflow.com/questions/13507556/…
    – 2vision2
    Commented Nov 22, 2012 at 9:48
19

The creator of the FotoForensics site posted this blog post on this topic, it was very useful to me, and showed algorithms that may be good enough for you and that require a lot less work than wavelets and feature extraction.

http://www.hackerfactor.com/blog/index.php?/archives/529-Kind-of-Like-That.html

aHash (also called Average Hash or Mean Hash). This approach crushes the image into a grayscale 8x8 image and sets the 64 bits in the hash based on whether the pixel's value is greater than the average color for the image.

pHash (also called "Perceptive Hash"). This algorithm is similar to aHash but use a discrete cosine transform (DCT) and compares based on frequencies rather than color values.

dHash Like aHash and pHash, dHash is pretty simple to implement and is far more accurate than it has any right to be. As an implementation, dHash is nearly identical to aHash but it performs much better. While aHash focuses on average values and pHash evaluates frequency patterns, dHash tracks gradients.

1
7

It's probably based on improvements of feature extraction algorithms, taking advantage of features which are scale invariant.

Take a look at

or, if you are REALLY interested, you can shell out some 70 bucks (or at least look at the Google preview) for

1
  • 2
    yep, SIFT, under heavy patent protection though, be aware of that for commercial development. Commented Aug 17, 2009 at 14:43
4

http://tineye.com/faq#how

Based on this, Igor Krivokon's answer seems to be on the mark.

1
  • 2
    Why the downvote? The question was "What algorithm does TinEye use?" I just mentioned that the TinEye FAQ backs up Igor's answer. Commented Sep 18, 2009 at 5:23
3

The Hough Transform is a very old feature extraction algorithm, that you mind find interesting. I doubt it's what tinyeye uses, but it's a good, simple starting place for learning about feature extraction.

There are also slides to a neat talk from some University of Toronto folks about their work at astrometry.net. They developed an algorithm for matching telescoping images of the night sky to locations in star catalogs in order to identify the features in the image. It's a more specific problem than what tinyeye tries to solve, but I'd expect that a lot of the basic ideas that they talk about are applicable to the more general problem.

0

Check out this blog post (not mine) for a very understandable description of a very understandable algorithm which seems to get good results for how simple it is. It basically partitions the respective pictures into a very coarse grid, sorts the grid by red:blue and green:blue ratios, and checks whether the sorts were the same. This naturally works for color images only.

The pros most likely get better results using vastly more advanced algorithms. As mentioned in the comments on that blog, a leading approach seems to be wavelets.

1
  • That's an interesting blog post, but I wouldn't take the algorithm used as an advice on the topic. Commented Jun 17, 2009 at 5:23
-1

They may well be doing a Fourier Transform to characterize the complexity of the image, as well as a histogram to characterize the chromatic distribution, paired with a region categorization algorithm to assure that similarly complex and colored images don't get wrongly paired. Don't know if that's what they're using, but it seems like that would do the trick.

1
  • 1
    Fourier Transforms would most likely be useless since natual images (i.e. photos) basically have the same frequency content (i.e. same magnitude, the phase differs). The rest sounds reasonable though. Commented Aug 2, 2009 at 13:06
-1

What about resizing the pictures to a standard small size and checking for SSIM or luma-only PSNR values? that's what I would do.

2
  • SSIM can be more accurate but it can't be indexed in database, unless you build a very huge table to store each SSIM value between each pair of images. Commented Sep 10, 2015 at 7:25
  • @JianWeihang You can still have the best of both worlds by using an algorithm that makes a very rough fingerprint of the image (like storing just an edge-detection bitmap in very low res), then calculating the SSIM of pairs that have the same fingerprint (or "nearly the same", which is a problem in and of itself). You don't even need to calculate the SSIM against every pair, just one of the ones that are "the same". But then again, it's a hell of a problem and I admire the fact Google and others work with it at such a scale. Commented Oct 8, 2015 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.