What is your best guess how Google Image Search works? I can upload a photo and can search for similar images. What algorithm does it use to identify similar images?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
I don't know which algorithm Google uses. But, since you wanted a best guess, let me give some ideas on how a similar system could be constructed.
The whole field dealing with search-image-base-by-image is called Content Based Image Retrieval (CBIR). The idea is to, somehow, construct an image representation (not necessarily understandable by humans) that contains the information about image content.
Two basic approaches exist:
Low-level local approach is very well researched. The best current approach extracts local features (there's a choice of feature extraction algorithm involved here) and uses their local descriptors (again, choice of descriptors) to compare the images.
In newer works, the local descriptors are clustered first and then clusters are treated as visual words -- the technique is then very similar to Google document search, but using visual words instead of letter-words.
You can think of visual words as equivalents to word roots in language: for example, the words: work, working, worked all belong to the same word root.
One of the drawbacks of these kinds of methods is that they usually under-perform on low-texture images.
I've already given and seen a lot of answers detailing these approaches, so I'll just provide links to those answers:
Semantic approaches are typically based on hierarchical representations of the whole image. These approaches have not yet been perfected, especially for the general image types. There is some success in applying these kind of techniques to specific image domains.
As I am currently in the middle of research of these approaches, I can not make any conclusions. Now, that said, I explained a general idea behind these techniques in this answer.
Once again, shortly: the general idea is to represent an image with a tree-shaped structure, where leaves contain the image details and objects can be found in the nodes closer to the root of such trees. Then, somehow, you compare the sub-trees to identify the objects contained in different images.
Here are some references for different tree representations. I did not read all of them, and some of them use this kind of representations for segmentation instead of CBIR, but still, here they are:
In addition to the answer of penelope, there are two approaches, perceptual hashing and the bag-of-words model whose basic functionality is easily implemented and are therefor nice to play with or to learn from, before venturing into more advanced territory.
Perceptual hashing algorithms aim to construct a hash, that unlike a cryptographic hash, will give similar, or near similar hash values for identical images that have been slightly distorted for example by scaling or JPEG compression. They serve a useful purpose in detection near duplicates in an image collection.
In its most basic form, you can implement this as follows:
The result is a resilient 64 bit hash, because it is based on the low frequency components of the image. A variant on this theme would be to divide each image into 64 subblocks and compare the global image mean to the local subblock mean and write out a 1 or 0 accordingly.
Perceptual hashing is implemented for example by phash
The bag-of-words model aims to semantically identify an image, e.g. all images with dogs in them. It does this by using certain image patches in the same spirit that one would classify a text document based on the occurrence of certain words. One could categorize the words, say "dog" and "dogs" and store them as identifier in an inverted file where the "dog" categorie now points to all documents containing either "dog" or "dogs".
In its most, most simple form, one can do this with images as follows:
You now have a huge collection of SIFT descriptors. The problem is, is that even from near identical images, there will be some mismatch between descriptors. You want to group the identical ones together more or less like treating some words, as "dog" and "dogs" as identical and you need to compensate for errors. This is where clustering comes in to play.
An image query, e.g find me similar images to the query-image, is then resolved as follows: