How the Google Image Search Engine Works

How the Google Image Search Engine Works

In this post, I will cover how the Google’s Image Search Engine works.

how google images work

In this article we will learn:

  • What is Google Images;
  • Wow it differs from Google Web Search;
  • Introduction to how the Google Images algorithm works;
  • Deeper dive into the engineering behind Google Images based on patent research
Contents hide

What is the Image Search Engine?

Google’s Image Search Engine, also known as Google Images, is the search engine that is used for searching images online.

How to Access Google Images?

There are 3 ways to access Google Images:

  • On google.com, select “Images” in the top right corner;
  • Use the direct URL images.google.com;
  • Perform for a query in web search and select “images” from the menu.

What Does the Image Search Engine Do?

The image search engine is the part of the image search system that crawls and indexes images, receives search queries for images, ranks images and returns search results in response to the image query.

What is the Difference Between Google Search and Google Image Search?

The difference between Google’s Web Search Engine and Image Search Engine lies in the way the information retrieval is made to serve results to a user query.

Google’s Web Search Engine searches for multiple types of text-based documents across the web and supplements its search results using alternate proprietary search engines such as the image search engine.

Google’s Image Search Engine searches for media matching queries, making it more dependant on filenames, metadata and other text associated with images.

How Does the Google Image Search Engine Algorithm Works?

The Google Image Search engine algorithm is in a way more simplistic than web search as it involve less moving parts, but can also be more complex as it requires a lot of processing power to return relevant media to queries without text-based content.

The core of the image search engine algorithm relies on matching search queries to text associated with images.

Example of text associated with images:

  • Filename
  • Image metadata such as the EXIF metadata
  • Text from the webpage in which the image was linked from
  • Text from the webpage that the image links to
  • Anchor text of hyperlinks to the image
Example of text content related to images
Identifying text content related to images

Once the initial ranking of the image search results is generated, the top images are re-processed to provide more relevant image search results.

In that re-processing, images that are the most similar to all the other images in the subset are given more relevancy and images that are too different are re-ranked lower, or even removed.

Additional element can come in to make the results more relevant such as:

  • Removing or giving more weight to images with faces based on the likelihood that the query is intended to find a person’s image
  • Removing or giving more weight to images with specific landmarks or objects based on the likelihood that the query is intended to
  • Giving more weight to higher quality images
Ranking based on image similarity
Ranking based on image similarity

High Level Overview of the Image Search Engine

At its core, the Image Search Engine includes:

  • Image Indexing Component
  • Search Component
  • Database
  • Refinement Component
implementation of an image search engine
Implementation of an image search engine taken from “Selection of an Image or Images Most Representative of a Set of Images

How the Google Image Search Engine Works?

  1. The Image indexing component receives and parse the HTML of a document

    The web crawler provide documents to the indexing component that parses the documents for text and images. It then stores images, links to images and descriptive text in the database

  2. The Search Component receives queries, search the database and return results

    The generation of results is based on a comparison of the search query to the descriptive text associated with images.

  3. The Refinement Component ranks the results based on the features of the images

    The ranking is made such as the images that are most representative of the initial image search results are rank above lower quality ones.

A Deep Dive into the Image Search Engine

Now that we have a broad understanding of what the Image Search Engine does, we will dive deeper into the specifics of how it works.

To do so, we will cover the foundations by looking at the main patent behind Google’s Image Search Engine.

Main Patent Behind Google Search Engine

The main patent behind the Google Image Search Engine is a patent named “Ranking of images and image labels” by Yushi Jing and Shumeet Baluja.

Patent Details

Name Ranking of images and image labels
Assignee Google LLC
Filed 2011-05-09
Assigned 2011, 2017
Status Active
Expiration 2028-06-30
Appl No. 13/103,258
Inventor(s) Yushi Jing, Shumeet Baluja
Patent US8326091B1

Highlights of How the Image Search Engine Works

To summarize the entire article:

To rank well in Google Image, an image has to contain relevant terms in its meta data and surrounding text, be high-quality. Also, the image should be similar enough to the other images so that Google knows it is relevant, but not too similar so that Google knows that it provides value.

Some highlights:

  • Terms are associated with images and used to be matched against the query
  • Google uses TF-IDF to evaluate the relevancy of a term to an Image
  • The more relevant terms are associated with images, the likelier the images are to be retrieved during search
  • The more similar an image is to all the images ranked for a query, the better it will rank
  • In opposition, uniqueness of the image is calculated as part of the image quality score, be balanced.
  • Similarity is estimated using feature similarity and co-click data
  • Not all image features weigh the same depending on the query
  • The higher quality an image is, the better it will rank
  • Small alterations of images may lead to duplicates being considered as unique
  • Landmarks, objects and persons are often raised in patents, making these elements important to Google when analyzing images.

Core Components of the Image Search Engine

From the moment the user performs a search query to the moment when image search results are shown in the browser, many separate things happen.

Separate modules (or softwares) within the image search engine are involved in the processing of the query, the processing of images and the ranking of search results.

As shown in the image below, the image search engine uses all these separate module in its algorithm.

  1. Image Crawling Module
  2. Image Terms Module
  3. Image Features Module
  4. Image Similarity Module
  5. Probabilities Module
  6. Image Indexing Module
  7. Image Search Server
  8. Scoring and Ranking Module
  9. Image Repository / Index
image 8 739x1024 1
Engineering behind the Image Search Engine from the “Ranking of Images and Image Labels” patent

What is the Image Crawling Module?

The image crawling module is the module from the Image Search Engine that crawls content hosts (web pages) for images and associated content. The image crawler downloads copies of the images and store them for further processing by the image search engine.

What is the Image Terms Module and How Does it Work?

The Image Terms Module is the module from the Image Search Engine that extracts terms from metadata (e.g. filename, EXIF metadata, …) and content associated with an image and determines which terms may associated with the images.

Terms associated with an image can also be referred to as “label” or “keyword”.

What is the Process Flow of Assigning Terms to Images

The Image Term Module receives images, evaluate their similarity and likelihood of being co-selected. Then, an image score is given

process to assign terms with an image
Process to assign terms, determine their score, and compute the final score of an image

Below, we’ll explain how it works specifically.

Where do Terms Come From?

The image terms module extracts terms from:

  1. Metadata associated with an image.
  2. Content associated with the image
  3. User testing

What Information Can Be Found in the Metadata?

The metadata of the image can contain terms such as:

  • Timestamp,
  • Camera make and model,
  • Orientation,
  • Aperture,
  • Focal length,
  • Metering mode,
  • ISO speed,
  • Geolocation,
  • File size,
  • File creation date,
  • Image resolution information
  • Title,
  • Description,
  • Categories,
  • Keywords

For more details on image metadata extraction read the “Automatic curation of digital images” patent.

What Information Can be in the Content Associated With an Image?

The content associated with the image can include information such as:

  • a text of a web page in which the image is associated,
  • anchor text of hyperlinks to the image,
  • text of a web page to which the image is the anchor of a links to that page

How Google can Gather Additional Information Through User Testing

Google can also gather terms for images through user testing. To do so, it shows images to users and ask them to provide terms for the given images

How the Relevancy of a Term to an Image is Evaluated

Each term associated with an image is scored to evaluate its relevancy. To do so, Google uses term frequency-inverse document frequency (TF-IDF) to calculate if the term is relevant to an image or if it is generic to all other images.

If a query does not satisfy a threshold, it is removed.

image 22

For instance, words like “the”, “that” and “a” are very common across all documents, so by definition not specific to a single document. Thus, their score is low, do not satisfy a threshold and removed.

What is the Image Features Module and How Does it Work?

The Image Feature Module is the module from the Image Search Engine that identifies the features of the images.

The image features are the features that Google can use to determine the degree of similarity between images.

Examples of image features:

  • Color
  • Brightness
  • Intensity
  • Texture
  • Shape
  • Edges

The features can be extracted using Wavelet based techniques (e.g. wavelet transform).

The image feature module can also assign weights for each of the feature.

For example, images of flowers may require more weight on the color feature whereas images of tables may require more weight on the shape feature.

Once this is done, it sends the features to the Image Similarity Module.

What is the Image Similarity Module and How it Works

Google’s image Similarity Module is the module from the Image Search Engine that compares the features between pairs of images to determine the degree of similarity between the images.

High-level view of the Image Similarity Module

How it works at a high level is by comparing features (color, shape, etc.) between pairs of images.

image 23 1024x590 1

What Features Can Be Analysed?

Images can be analyzed in different ways.

Entire images can be analyzed, or alternatively, only specific elements of images may be compared (e.g. face, landmark, object).

Regardless, features are determined and compared.

In each case, a feature can be either a:

  • Global feature: Analysis of a feature for the entire image
  • Local feature: Analysis of a feature for each portions of an image

Detailed view of the Image Similarity Module

How the image similarity module works specifically is that it identifies objects of interests and splits an image in sections of geometric shapes (e.g. squares, circles, …).

The identification of object of interests is done with the registration algorithm and the process of splitting and identify frequencies in the image is called wavelet transform.

Selecting the Objects of Interests

To save computing resources, Google my identify objects of interests and compute the feature analysis only for the specific part of the image.

image 25
How objects of interests may be selected according to “System and method for enabling image recognition and searching of remote content on display“.

Alternatively, Google may also use the SIFT technique to identify objects of interest.

sift object of interest
Identifying objects of interests from “Distinctive Image Features from Scale-Invariant Keypoints”

Selecting Features

What feature should be used to compare images?

Some features such as the shape are more appropriate for photos containing products, whereas the color more appropriate for photos of flowers.

How to choose which is are the most important features describing a set of images?

Google uses the scale-invariant feature transform (SIFT) technique that identifies the features that are the most resistant to image noise.

Splitting the Image in Sections

Using wavelet-based techniques, Google splits images in sections and evaluates one section of the image at a time.

Then, one feature after the other, it evaluates the feature for each section of the image and create a histogram with the data.

After, it compares the histograms to see how similar each image are.

Example of how color histograms are created
Example of how color histograms are created

Comparing Histograms

Many techniques can be used to compare color histograms.

The technique mentioned in the patent consists of looping through each bin and adding the absolute difference between the selected bin of one image and the other.

Example of how histogram comparison is made at Google
Example of how histogram comparison is made at Google

The image similarity module is being discussed in more details in a separate patent which I covered in How Google Selects the Most Representative Image of a Set.

Defining Similarity based on Image Location

Similarity of images can also be compared based on the relationship between the pages or locations from which they were crawled.

For example, images from the same website can be considered more similar than images found in pages of independent websites.

Combining Image Similarity Module and Image Features Module

Once both computations are made by the image similarity module and the image features module, an algorithm computes both element together to get an image similarity score.

image 27

What is the Probabilities Module?

The probabilities module is the module from Google’s Image Search Engine that calculates the transitional probabilities between pairs of images.

The transitional probability, also known as the probability of navigation, is the probability that a user will select and image given another image.

How is the Transitional Probability Calculated?

The transitional probability, also know as co-click probability, is calculated using the the image term ranking function.

The image term ranking function is a probability distribution that represents the likelihood that a user will select image B after viewing Image A.

In other words, how likely is it that a user will co-select, or co-click, on two images?

The probability is based on two assumptions:

  • Users are more likely to co-select similar images than dissimilar images
  • Users are likely to ignore images that are too similar.

We see that pattern in the probability distribution where both highly different images (Image similarity = 0) and identical images (Image similarity = 1) have very low transitional probability.

Probability distribution of the image term ranking function
Probability distribution (or beta-similarity) of the image term ranking function

How the Transitional Probability can be Enhanced?

The transitional probability, or co-click probability, function can be improved for the image relationships to be evaluated more accurately.

For example, it can be augmented with:

  • Usage data from each user, or many users
  • Image quality score
  • Structural-context similarity score
  • Click and co-click data estimation of likelihood of an image being viewed before or after another

What is Google’s Image Indexing Module?

Google’s image indexing module is the module from the Image Search Engine that indexes images to be displayed to the user.

It assigns an index along with terms associated with each image in a way that can easily be searched by the image search server.

What is the Image Search Server and What Does it Do?

Google’s image search server, also known as the search component, is the part of the image search engine that receives the query, performs the search and returns the results to the user.

In some simplified way, discarding all the additional processing we just described, the image search server is the image search engine.

The image search server contains the Image Search Module.

What the image search server does:

  1. Receive a query
  2. Processes search queries for images
  3. Finds the images in the index that contains the terms
  4. Returns an inverted index of the search results
  5. Presents the search results to the user in a webpage that contains: image thumbnails, information on the result

Here is the image information that may be display with the image search result webpage:

  • Thumbnails,
  • Title,
  • Description,
  • URL,
  • File size,
  • File type,
  • Image dimensions,
  • Domain hosting the image.

What is the Scoring and Ranking Module

The scoring and ranking module is the module from the image search engine that provide scores used at various stages of the pipeline to improve the ranking of images.

The scoring and ranking module contains two groups of algorithms:

  • The scoring algorithm provides scores for each term related to an image.
  • The ranking algorithm provides scores each image related to a search term.

The image search engine uses terms to index images. Ergo, the relevance of a term to a document impacts the quality of the search results. Consequently, Google provides rankings for terms associated with images.

Thus, the module provide scores for each of the terms associated with images.

How the Scores can be Used

Scores can be used for different purposes, at different stages, by different modules.

Those scores can be used to:

  • Identify the best term for an image
  • Identify good terms describing an image to be used as keywords for the image indexing module
  • Augment the transitional probability function to learn from image relationships
  • Provide the most relevant image(s) for a given term

How Ranks are Calculated?

The rank and scoring module also computes the ranking function to determine the scores of an image for a specific term.

The ranks are scored based on probability adjusted scores for other images of the image index. These score are also weighted based on the probability of navigating between images.

In a nutshell, the ranking of the image is based on not only its similarity with other images, but on the probability of users clicking on that image after seeing other images in the set.

The ranking algorithm essentially divides at the number of times a query is associated with an image with the number of times the query is appears in all the images of the index.

image 28

This simplified view helps to illustrate the process.

The algorithm however is more complex.

Once the values are initialized, they are multiplied with the transition probabilities and the resulting value is being used in the next iteration until convergence. Results can also be improved using TF-IDF to remove noisy terms.

Details of the functions are available in the patent and will not be discussed here.

What is the Image Repository / Index

The image repository, also known as the image index, is the database that stores the images and their information in a way that can be “searched” by the image search engine.

The image index receives images from the image crawler and then stores the images along with an index and terms associated with the image.

A copy of an image does not need to be stored to be in the index.

How Image Quality Score is Estimated?

The Image quality score can be estimated by the image quality control module of the image search engine by using one or more query-independent indicators:

  • Color depth of the image
  • How much the image is in focus
  • Level of saturation of the image
  • Uniqueness

The image quality is scored between 0 and 1.

More details of how the image quality control module works can be found by reading the “Automatic curation of digital images” patent.

How Duplicate Images Can be Identified

Showing duplicate images is rarely useful the the user. Thus, Google tries to identify duplicate, or near-duplicate, images in many ways:

  • Images with identical EXIF metadata
  • Images with with identical, or too similar, calculated image features

Patents Related to the Image Search Engine

The most complete patent regarding the image search engine is named “Ranking of images and image labels” and is the basis for most of the content you will read in this article.

Other patents include:

What Categories is the Patent About?

  • Indexing
  • Crawling
  • Image SEO

Definitions

Patent term Definition
Search System System that indexes content, receives query, ranks content and returns results for the query.
Image Search Query Search query for which the intent is to get a particular image content. It can include one or more terms.
Terms Part of the query that can include words, phrases, characters and so forth.
Image Features Features that can be used to identify similarities between images. Examples of features are intensity, color, edges, texture, etc.
Image term ranking function Formula that evaluates the relevance of a term to an image
Image quality score Metric defining the quality of images within a set of images
Structural-context similarity score Metric evaluating the similarity of images based on the level of dependance of the websites where the images were found.
Wavelet transform Evaluation of frequency of elements of an image that was split in geometrical shapes.
Transition probability Probability of a user clicking on an image after seeing another

Google Search Infrastructure Involved

The “Ranking of Images and Image Labels” patent mentions these elements from the Google Search Infrastructure:

  • Image Search System
    • Image Search Engine
      • Image Crawling Module
      • Image Terms Module
      • Image Features Module
      • Image Similarity Module
      • Probabilities Module
      • Scoring and Ranking Module
      • Image Indexing Module
      • Image Search Server
        • Image search module
    • Image Repository / Index

Conclusion

That was a lot.

Google Image search results are backed by multiple components and algorithm to make sure that images are relevant to a query and that images are high-quality and informative to the user.

We have learned that when Google crawls images they gather terms from the image context and store those terms in the indexing module to enable retrieval.

We also have learned how the features module and the similarity modules work together with the probabilities modules to identify how similar images are and how likely users are to navigate between images.

All these elements are used to score terms and rank images when the image search server is requested by the user to display images for a given query.

We now know how the image search engine works and how Google ranks images.

L’article How the Google Image Search Engine Works est apparu en premier sur JC Chouinard.

SEO