What algorithm does Google use for its “Search By Image” site?

Question

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?

Answer 1

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:

• retrieval using low-level (local) features: color, texture, shape at specific parts of images (an image is a collection of descriptors of local features)
• semantic approaches where an image is, in some way, represented as a collection of objects and their relations

---

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:

• CBIR: 1, 2
• feature extraction/description: 1, 2, 3, 4

---

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:

• binary partition trees and mention of min/max trees: P. Salembier, M.H.F Wilkinson: Connected Operators
• binary partition trees: V. Vilaplana, F. Marques, P. Selembier: Binary Partition Trees for Object Detection
• tree of shapes (component tree): P. Monasse, F. Guichard: Fast Computation of Contrast-Invariant Image Representation, C. Ballester, V. Castellis, P. Monasse: The Tree of Shapes of an Image
• monotonic trees: Y. Song, A. Zhang: Analyzing scenery images by monotonic tree
• edit: further digging shows that tree of shapes and monotonic tree are equivalent, except processing the image in 4-/8- (tree of shapes) or 6-connectivity (monotonic)
• extrema-watershed tree: A. Vichik, R. Keshet, D. Malah: Self-dual morphology on tree semilattices and applications
• constrained connectivity, alpha-trees, ultrametric waterseads: P. Soille, L. Najman: On morphological hierarchical representations for image processing and spatial data clustering

Answer 2

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

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:

1. Convert image to grayscale

2. Make your image zero mean

3. Crush your image down to thumbnail size, say [32x32]
4. Run the two dimensional Discrete Cosine Transform
5. Keep the top left [8 x 8], most significant low frequency components
6. Binarize the block, based on the sign of the components

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

Bag-of-words model

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:

1. Deploy the so called SIFT features, for example using the excellent vlfeat library, which will detect the SIFT feature points and a SIFT descriptor per point. This descriptor is basically a smartly constructed template of the image patch surrounding that feature point. These descriptors are your raw words.
2. Gather SIFT descriptors for all relevant images

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.

1. Take all SIFT descriptors and cluster them, for example with an algorithm like k-means. This will find a pre determined number of clusters with centroids in your descriptor data. These centroids are your new visual words.
2. Now per image and its original found descriptors, you can look at the clusters these descriptors were assigned to. From this, you know wich centroids or visual words 'belong' to your image. These centroids or visual words become the new semantic descriptor of your image which can be stored in an inverted file.

An image query, e.g find me similar images to the query-image, is then resolved as follows:

1. Find the SIFT points and their descriptors in the query image
2. Assign the query descriptors to the centroids you earlier found in the enrollment phase. You now have a set of centroids or visual words that pertain to your query image
3. Match the query visual words to visual words in your inverted file and return the matching images