Clustering queries for image search

• US 9,424,338 B2
• Filed: 04/29/2014
• Issued: 08/23/2016
• Est. Priority Date: 05/11/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Jing, Yushi, Covell, Michele, Holiday, Stephen C.
• Primary Examiner(s): GOFMAN, ALEX N
• Application Number:
  US14/264,411
• Publication Number:
  US 20150169725A1
• Time in Patent Office: 847 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/5838 using colour

Abstract

Aspects of the subject matter described herein relate to functions used for retrieving image results based on search queries. More specifically, image search queries can be pre-grouped or classified based on visual and semantic similarity. For example, a pairwise image similarity value for a pair of queries can be computed based on one or more of the sum of all of the overlapping the image results, the sum of the image distances between all of the pairs of images in the image results, and the rank of each of the images in the image results. The pairwise image similarity values can then be used to generate image query clusters. Each image query clusters can include a set of queries with high pairwise image similarity values. In some examples, a distance function can be determined for each image query cluster. This data can be used to provide image results.

Claims

1. A computer-implemented method comprising:

obtaining a pair of search queries including (i) a first search query and (ii) a second search query;

obtaining (i) a first set of multiple images that are identified as responsive to the first search query, and (ii) a second set of multiple images that are identified as responsive to the second search query;

determining, for each pair of images that includes (i) a first image from the first set of multiple images that are identified as responsive to the first search query and (ii) a second image from the second set of multiple images that are identified as responsive to the second search query, an image distance between the first image of the pair and the second image of the pair based on information associated with one or more pixels of the first image of the pair and information associated with one or more corresponding pixels of the second image of the pair;

determining a measure of similarity between (i) the first set of multiple images that are identified as responsive to the first search query and (ii)the second set of multiple images that are identified as responsive to the second search query, based at least on the respective image distances for each pair of images that includes (i) a first image from the first set of multiple images that are identified as responsive to the first search query and (ii) a second image from the second set of multiple images that are identified as responsive to the second search query;

determining that the measure of similarity between (i) the first set of multiple images that are identified as responsive to the first search query and (ii) the second set of multiple images that are identified as responsive to the second search query satisfies a similarity threshold; and

in response to determining that the measure of similarity between (i) the first set of multiple images that are identified as responsive to the first search query and (ii) the second set of multiple images that are identified as responsive to the second search query satisfies the similarity threshold, assigning the pair of search queries to a cluster of search queries.

2. The method of claim 1, wherein determining an image distance between the first image of the pair and the second image of the pair, comprises:

determining the image distance based on comparing the first image of the pair and the second image of the pair at a pixel level.

3. The method of claim 1, comprising:

generating a distance function associated with the cluster of search queries based on images that are identified as responsive to the search queries in the cluster of search queries.

4. The method of claim 3, wherein generating a distance function associated with the cluster of search queries based on images that are identified as responsive to the search queries in the cluster of search queries comprises:

determining a reference image for the cluster of search queries from the images that are identified as responsive to the search queries in the cluster of search queries;

determining a set of secondary images from the cluster of search queries from the images that are identified as responsive to the search queries in the cluster of search queries;

determining a respective image distance between the reference image and each image of the set of secondary images; and

determining the distance function associated with the cluster of search queries based on the determined image distances between the reference image and each image of the set of secondary images.

5. The method of claim 3, comprising:

receiving a third search query;

identifying the cluster of search queries as responsive to the third search query based on one or more search terms of the third search query; and

identifying a set of search results based on the generated distance function associated with the cluster of search queries.

6. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

obtaining a pair of search queries including (i) a first search query and (ii) a second search query;

obtaining (i) a first set of multiple images that are identified as responsive to the first search query, and (ii) a second set of multiple images that are identified as responsive to the second search query;

determining, for each pair of images that includes (i) a first image from the first set of multiple images that are identified as responsive to the first search query and (ii) a second image from the second set of multiple images that are identified as responsive to the second search query, an image distance between the first image of the pair and the second image of the pair based on information associated with one or more pixels of the first image of the pair and information associated with one or more corresponding pixels of the second image of the pair;

determining a measure of similarity between (i) the first set of multiple images that are identified as responsive to the first search query and (ii) the second set of multiple images that are identified as responsive to the second search query, based at least on the respective image distances for each pair of images that includes (i) a first image from the first set of multiple images that are identified as responsive to the first search query and (ii) a second image from the second set of multiple images that are identified as responsive to the second search query;

determining that the measure of similarity between (i) the first set of multiple images that are identified as responsive to the first search query and (ii) the second set of multiple images that are identified as responsive to the second search query satisfies a similarity threshold; and

in response to determining that the measure of similarity between (i) the first set of multiple images that are identified as responsive to the first search query and (ii) the second set of multiple images that are identified as responsive to the second search query satisfies the similarity threshold, assigning the pair of search queries to a cluster of search queries.

7. The system of claim 6, wherein determining an image distance between the first image of the pair and the second image of the pair, comprises:

determining the image distance based on comparing the first image of the pair and the second image of the pair at a pixel level.

8. The system of claim 6, wherein the operations comprise:

generating a distance function associated with the cluster of search queries based on images that are identified as responsive to the search queries in the cluster of search queries.

9. The system of claim 8, wherein generating a distance function associated with the cluster of search queries based on images that are identified as responsive to the search queries in the cluster of search queries comprises:

determining a reference image for the cluster of search queries from the images that are identified as responsive to the search queries in the cluster of search queries;

determining a set of secondary images from the cluster of search queries from the images that are identified as responsive to the search queries in the cluster of search queries;

determining a respective image distance between the reference image and each image of the set of secondary images; and

determining the distance function associated with the cluster of search queries based on the determined image distances between the reference image and each image of the set of secondary images.

10. The system of claim 8, wherein the operations comprise:

receiving a third search query;

identifying the cluster of search queries as responsive to the third search query based on one or more search terms of the third search query; and

identifying a set of search results based on the generated distance function associated with the cluster of search queries.

11. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising

obtaining a pair of search queries including (i) a first search query and (ii) a second search query;

obtaining (i) a first set of multiple images that are identified as responsive to the first search query, and (ii) a second set of multiple images that are identified as responsive to the second search query;

determining, for each pair of images that includes (i) a first image from the first set of multiple images that are identified as responsive to the first search query and (ii) a second image from the second set of multiple images that are identified as responsive to the second search query, an image distance between the first image of the pair and the second image of the pair based on information associated with one or more pixels of the first image of the pair and information associated with one or more corresponding pixels of the second image of the pair;

determining a measure of similarity between (i) the first set of multiple images that are identified as responsive to the first search query and (ii) the second set of multiple images that are identified as responsive to the second search query, based at least on the respective image distances for each pair of images that includes (i) a first image from the first set of multiple images that are identified as responsive to the first search query and (ii) a second image from the second set of multiple images that are identified as responsive to the second search query;

determining that the measure of similarity between (i) the first set of multiple images that are identified as responsive to the first search query and (ii) the second set of multiple images that are identified as responsive to the second search query satisfies a similarity threshold; and

in response to determining that the measure of similarity between (i) the first set of multiple images that are identified as responsive to the first search query and (ii) the second set of multiple images that are identified as responsive to the second search query satisfies the similarity threshold, assigning the pair of search queries to a cluster of search queries.

12. The computer-readable medium of claim 11, wherein determining an image distance between the first image of the pair and the second image of the pair, comprises:

determining the image distance based on comparing the first image of the pair and the second image of the pair at a pixel level.

13. The computer-readable medium of claim 11, wherein the operations comprise:

generating a distance function associated with the cluster of search queries based on images that are identified as responsive to the search queries in the cluster of search queries.

14. The computer-readable medium of claim 13, wherein generating a distance function associated with the cluster of search queries based on images that are identified as responsive to the search queries in the cluster of search queries comprises:

determining a reference image for the cluster of search queries from the images that are identified as responsive to the search queries in the cluster of search queries;

determining a set of secondary images from the cluster of search queries from the images that are identified as responsive to the search queries in the cluster of search queries;

determining a respective image distance between the reference image and each image of the set of secondary images; and

determining the distance function associated with the cluster of search queries based on the determined image distances between the reference image and each image of the set of secondary images.