Grouping of image search results

• US 8,352,465 B1
• Filed: 09/03/2010
• Issued: 01/08/2013
• Est. Priority Date: 09/03/2009
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Jing, Yushi, Rowley, Henry A., Chennapragada, Aparna
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US12/876,077
• Time in Patent Office: 858 Days
• Field of Search: 707/723, 707/737, 707/748, 707/778, 707/829, 707/915, 707/956
• US Class Current: 707/723
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/50 of still image data
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/54 Browsing; Visualisation therefor
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/587 using geographical or spatial information, e.g. location
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06V 10/7625 Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms
• CPC Class Codes: G06V 10/7788 the supervisor being a human, e.g. interactive learning with a human teacher
• CPC Class Codes: G06V 10/945 User interactive design; Environments; Toolboxes

Abstract

This specification relates to presenting image search results. In general, one aspect of the subject matter described in this specification can be embodied in methods that include the actions of receiving an image query, the image query being a query for image search results; receiving ranked image search results responsive to the image query, the image search results each including an identification of a corresponding image resource; generating a similarity matrix for images identified by the image search results; generating a hierarchical grouping of the images using the similarity matrix; identifying a canonical image for each group in the hierarchical grouping using a ranking measure; and presenting a visual representation of the image search results based on the hierarchical grouping and the identified canonical images.

Claims

1. A computer-implemented method comprising:

obtaining an image query, the image query being a query for image search results;

obtaining ranked image search results responsive to the image query, the image search results each including an identification of a corresponding image resource;

generating a similarity matrix for images identified by the image search results;

generating a hierarchical grouping of the images using the similarity matrix;

identifying a canonical image for each of a plurality of groups in the hierarchical grouping using a ranking measure; and

providing a visual representation of the image search results based on the hierarchical grouping and the identified canonical images using a representation of one or more of the identified canonical images to represent one or more corresponding groups of images in the visual representation, and wherein the visual representation includes one or more first canonical images having a first size representing higher level image clusters and one or more second canonical images having a second smaller size and each second canonical image being associated with a respective first canonical image.

2. The method of claim 1, wherein identifying a canonical image for each group includes:

identifying an image of the group having a highest image search rank; and

selecting the image having the highest image search rank as the canonical image for the group.

3. The method of claim 1, wherein identifying a canonical image for each group includes:

identifying an image of the group having a highest ranking according to the ranking measure; and

selecting the image having the highest ranking as the canonical image for the group.

4. The method of claim 3, wherein selecting the image having the highest ranking includes:

calculating an image ranking score for each image in the group including calculating a similarity between each image using one or more similarity metrics.

5. The method of claim 1, where generating the hierarchical grouping of images includes using hierarchical agglomerative clustering to group the image search results in a dendrogram structure and where the canonical image for each group corresponds to a respective cluster in the dendrogram.

6. The method of claim 1, where generating the hierarchical grouping further comprises:

generating a first number of clusters using the images in the similarity matrix, identifying a respective canonical images for each cluster of the first number of clusters, and generating a second number of clusters using the identified canonical images for the first number of clusters.

7. A tangible computer storage medium storing instructions that, when executed by data processing apparatus, cause the data processing apparatus to perform operations comprising:

obtaining an image query, the image query being a query for image search results;

obtaining ranked image search results responsive to the image query, the image search results each including an identification of a corresponding image resource;

generating a similarity matrix for images identified by the image search results;

generating a hierarchical grouping of the images using the similarity matrix;

identifying a canonical image for each of a plurality of groups in the hierarchical grouping using a ranking measure; and

providing a visual representation of the image search results based on the hierarchical grouping and the identified canonical images using a representation of one or more of the identified canonical images to represent one or more corresponding groups of images in the visual representation, and wherein the visual representation includes one or more first canonical images having a first size representing higher level image clusters and one or more second canonical images having a second smaller size and each second canonical image being associated with a respective first canonical image.

8. The computer storage medium of claim 7, wherein identifying a canonical image for each group includes:

identifying an image of the group having a highest image search rank; and

selecting the image having the highest image search rank as the canonical image for the group.

9. The computer storage medium of claim 7, wherein identifying a canonical image for each group includes:

identifying an image of the group having a highest ranking according to the ranking measure; and

selecting the image having the highest ranking as the canonical image for the group.

10. The computer storage medium of claim 9, wherein selecting the image having the highest ranking includes:

calculating an image ranking score for each image in the group including calculating a similarity between each image using one or more similarity metrics.

11. The computer storage medium of claim 7, where generating the hierarchical grouping of images includes using hierarchical agglomerative clustering to group the image search results in a dendrogram structure and where the canonical image for each group corresponds to a respective cluster in the dendrogram.

12. The computer storage medium of claim 7, where generating the hierarchical grouping further comprises:

generating a first number of clusters using the images in the similarity matrix, identifying a respective canonical images for each cluster of the first number of clusters, and generating a second number of clusters using the identified canonical images for the first number of clusters.

13. A system comprising:

one or more processors configured to perform operations comprising;

obtaining an image query, the image query being a query for image search results;

obtaining ranked image search results responsive to the image query, the image search results each including an identification of a corresponding image resource;

generating a similarity matrix for images identified by the image search results;

generating a hierarchical grouping of the images using the similarity matrix;

identifying a canonical image for each of a plurality of groups in the hierarchical grouping using a ranking measure; and

providing a visual representation of the image search results based on the hierarchical grouping and the identified canonical images using a representation of one or more of the identified canonical images to represent one or more corresponding groups of images in the visual representation, and wherein the visual representation includes one or more first canonical images having a first size representing higher level image clusters and one or more second canonical images having a second smaller size and each second canonical image being associated with a respective first canonical image.

14. The system of claim 13, wherein identifying a canonical image for each group includes:

identifying an image of the group having a highest image search rank; and

selecting the image having the highest image search rank as the canonical image for the group.

15. The system of claim 13, wherein identifying a canonical image for each group includes:

identifying an image of the group having a highest ranking according to the ranking measure; and

selecting the image having the highest ranking as the canonical image for the group.

16. The system of claim 15, wherein selecting the image having the highest ranking includes:

calculating an image ranking score for each image in the group including calculating a similarity between each image using one or more similarity metrics.

17. The system of claim 13, where generating the hierarchical grouping of images includes using hierarchical agglomerative clustering to group the image search results in a dendrogram structure and where the canonical image for each group corresponds to a respective cluster in the dendrogram.

18. The system of claim 13, where generating the hierarchical grouping further comprises:

generating a first number of clusters using the images in the similarity matrix, identifying a respective canonical images for each cluster of the first number of clusters, and generating a second number of clusters using the identified canonical images for the first number of clusters.