Content-based image ranking

• US 8,781,231 B1
• Filed: 08/25/2009
• Issued: 07/15/2014
• Est. Priority Date: 08/25/2009
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kumar, Sanjiv, Rowley, Henry A., Makadia, Ameesh
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): VANCHY JR, MICHAEL J
• Application Number:
  US12/547,303
• Time in Patent Office: 1,785 Days
• Field of Search: 382/190, 382155-161, 382/168, 382/170, 382/171, 705/14.52, 705/14.54, 707/999.006, 707/999.007
• US Class Current: 382/190
• CPC Class Codes: G06F 16/54 Browsing; Visualisation therefor
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures
• CPC Class Codes: G06V 2201/10 Recognition assisted with metadata

Abstract

Methods, systems, and apparatus, including computer program products, for ranking search results for queries. The method includes calculating a visual similarity score for one or more pairs of images in a plurality of images based on visual features of images in each of the one or more pairs; building a graph of images by linking each of one or more images in the plurality of images to one or more nearest neighbor images based on the visual similarity scores; associating a respective score with each of one or more images in the graph based on data indicative of user behavior relative to the image as a search result for a query; and determining a new score for each of one or more images in the graph based on the respective score of the image, and the respective scores of one or more nearest neighbors to the image.

Claims

1. A computer-implemented method comprising:

calculating, using one or more processors, a visual similarity score for one or more pairs of images in a plurality of images based on visual features of images in each of the one or more pairs;

building a graph of images by linking each of one or more images in the plurality of images to one or more nearest neighbor images based on the visual similarity scores of the image pairs that include the image;

identifying respective historical click data for each of the images in the graph wherein the historical click data comprises a count of user selections of the image when the image was presented as a search result responsive to a query, and wherein a viewing time of the image after being selected exceeded a pre-determined threshold;

associating a respective score with each of the images in the graph based on respective historical click data for the image; and

determining a new score for each of one or more images in the graph based on the respective score of the image, and the respective scores of one or more nearest neighbors to the image as weighted by their visual similarity to the image.

2. The method of claim 1, further comprising:

ranking each of one or more images in the plurality of images according to the image'"'"'s new score.

3. The method of claim 1, where calculating a visual similarity score for one or more pairs of images includes extracting one or more features from visual content of a first image, and the method further comprises identifying one or more k nearest neighbor images based on a distance measure between the first image and each of the one or more k nearest neighbor images.

4. The method of claim 3, where the distance measure is a combination of basic distances from multiple visual features.

5. The method of claim 4, where the distance measure is based on a joint equal contribution (JEC).

6. The method of claim 1, where a first image is connected by an edge to each of one or more k nearest neighbor images, and the edge is associated with a weight that represents the distance measure between the first image and a first nearest neighbor image.

7. The method of claim 6, where the weight is calculated by passing the distance measure through a linear or non-linear function.

8. The method of claim 6, where determining the new score includes:

calculating the new score using a function that has a closed-form solution.

9. The method of claim 8, where calculating the new score includes:

normalizing the weights; and

calculating C=(1−

α

)*(I−

(α

*W))<sup>−

1</sup>*c, where c is a vector representing the respective scores, C is a vector representing the new scores, W is a matrix representing the normalized weights, I is an identity matrix, and α

is a determined parameter.

10. The method of claim 7, where determining the new score includes:

iteratively calculating the new score until convergence.

11. The method of claim 10, where iteratively calculating the new score includes:

normalizing the weights; and

calculating

12. A non-transitory computer readable medium encoded with a computer program operable to cause one or more processors to perform operations comprising:

calculating a visual similarity score for one or more pairs of images in a plurality of images based on visual features of images in each of the one or more pairs;

building a graph of images by linking each of one or more images in the plurality of images to one or more nearest neighbor images based on the visual similarity scores of the image pairs that include the image;

identifying respective historical click data for each of the images in the graph wherein the historical click data comprises a count of user selections of the image when the image was presented as a search result responsive to a query, and wherein a viewing time of the image after being selected exceeded a pre-determined threshold;

associating a respective score with each of the images in the graph based on respective historical click data for the image; and

determining a new score for each of one or more images in the graph based on the respective score of the image, and the respective scores of one or more nearest neighbors to the image as weighted by their visual similarity to the image.

13. The program product of claim 12, further operable to cause one or more processors to perform operations including:

ranking each of one or more images in the plurality of images according to the image'"'"'s new score.

14. The program product of claim 12, where calculating a visual similarity score for one or more pairs of images includes extracting one or more features from visual content of a first image, and where the program product is further operable to cause one or more processors to perform operations including identifying one or more k nearest neighbor images based on a distance measure between the first image and each of the one or more k nearest neighbor images.

15. The program product of claim 14, where the distance measure is a combination of basic distances from multiple visual features.

16. The program product of claim 15, where the distance measure is based on a joint equal contribution (JEC).

17. The program product of claim 12, where a first image is connected by an edge to each of one or more k nearest neighbor images, and the edge is associated with a weight that represents the distance measure between the first image and a first nearest neighbor image.

18. The program product of claim 17, where the weight is calculated by passing the distance measure through a linear or non-linear function.

19. The program product of claim 17, where determining the new score includes:

calculating the new score using a function that has a closed-form solution.

20. The program product of claim 19, where calculating the new score includes:

normalizing the weights; and

calculating C=(1−

α

)*(I−

(α

*W))<sup>−

1</sup>*c, where c is a vector representing the respective scores, C is a vector representing the new scores, W is a matrix representing the normalized weights, I is an identity matrix, and α

is a determined parameter.

21. The program product of claim 17, where determining the new score includes:

iteratively calculating the new score until convergence.

22. The program product of claim 21, where iteratively calculating the new score includes:

normalizing the weights; and

calculating

23. A system comprising:

a machine-readable storage device including a program product; and

one or more computers operable to execute the program product, interact with a display device, and perform operations comprising;

calculating a visual similarity score for one or more pairs of images in a plurality of images based on visual features of images in each of the one or more pairs;

building a graph of images by linking each of one or more images in the plurality of images to one or more nearest neighbor images based on the visual similarity scores of the image pairs that include the image;

identifying respective historical click data for each of the images in the graph wherein the historical click data comprises a count of user selections of the image when the image was presented as a search result responsive to a query, and wherein a viewing time of the image after being selected exceeded a pre-determined threshold;

associating a respective score with each of the images in the graph based on respective historical click data for the image; and

determining a new score for each of one or more images in the graph based on the respective score of the image, and the respective scores of one or more nearest neighbors to the image as weighted by their visual similarity to the image.