Ranking of images and image labels

• US 7,961,986 B1
• Filed: 06/30/2008
• Issued: 06/14/2011
• Est. Priority Date: 06/30/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Jing, Yushi, Baluja, Shumeet
• Primary Examiner(s): Desire; Gregory M
• Application Number:
  US12/164,808
• Time in Patent Office: 1,079 Days
• Field of Search: 382/145, 382/305, 382/306, 382/311, 704/10, 707/3.5, 707/104.1, 707/3, 707/5, 707/7, 707/752
• US Class Current: 382/305
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• 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 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

The subject matter of this specification can be embodied in, among other things, a method that includes determining a score for an image of a plurality of images with respect to each of one or more terms, identifying one or more of the terms for each of which the score for the image with respect to the respective identified term satisfies a criterion, and associating the identified terms with the image. Determining the score for the image with respect to a respective term includes determining probabilities of navigating between images in the plurality of images and determining the score for the image with respect to the respective term based on the probabilities.

Claims

1. A method comprising:

determining, using a computer system, a score for an image of a plurality of images with respect to each of one or more terms;

identifying, using the computer system, one or more of the terms for each of which the score for the image with respect to the respective identified term satisfies a criterion; and

associating the identified terms with the image;

wherein determining the score for the image with respect to a respective term comprises;

determining probabilities of navigating between images in the plurality of images; and

determining the score for the image with respect to the respective term based on the probabilities.

2. The method of claim 1, wherein determining probabilities of navigating between images in the plurality of images comprises:

determining degrees of similarity between pairs of images in the plurality of images; and

determining probabilities of navigating between images in the plurality of images using the degrees of similarity.

3. The method of claim 2, wherein determining degrees of similarity between pairs of images in the plurality of images comprises, for a respective pairing of images, identifying and comparing one or more features of each image in the pairing.

4. The method of claim 2, wherein determining probabilities of navigating between images in the plurality of images based on the degrees of similarity comprises:

determining probabilities of navigating based at least on the degrees of similarity and quality metrics of the images in the plurality of images.

5. The method of claim 4, wherein the quality metrics comprise one or more of a degree of focus of a respective image, a number of colors in a respective image, or a degree of saturation of a respective image.

6. The method of claim 2, wherein determining probabilities of navigating between images in the plurality of images based on the degrees of similarity comprises:

determining probabilities of navigating based at least on the degrees of similarity and one or more relationship metrics between pages hosting the images in the plurality of images.

7. The method of claim 2, wherein determining probabilities of navigating between images in the plurality of images based on the degrees of similarity comprises:

determining probabilities of navigating based on the degrees of similarity, relationship metrics between pages hosting the images in the plurality of images, and quality metrics of the images in the plurality of images.

8. The method of claim 1, wherein navigating between images in the plurality of images comprises providing a first image to a user, and receiving a user selection of a second image from the plurality of images, wherein the second image is different than the first image.

9. The method of claim 1, wherein the criterion comprises a threshold score, and wherein a score associated with a term and the image satisfies the criterion when the score is equal to or greater than the threshold score.

10. The method of claim 1, wherein the criterion comprises a top number of scores for the terms associated with the image, and wherein a score associated with a term and the image satisfies the criterion when the score is one of the top number of scores for the terms associated with the image.

11. The method of claim 1, wherein determining the score for the image with respect to the respective term based on the probabilities comprises combining probability adjusted scores for others of the plurality of images with respect to the respective term, wherein each of the probability adjusted scores comprises a score associated with one of the other images multiplied by a probability of navigating from the one of the other images to the image.

19. The system of claim 8, wherein navigating between images in the plurality of images comprises providing a first image to a user, and receiving a user selection of a second image from the plurality of images, wherein the second image is different than the first image.

20. The system of claim 8, wherein the criterion comprises a threshold score, and wherein a score associated with a term and the image satisfies the criterion when the score is equal to or greater than the threshold score.

21. The system of claim 8, wherein the criterion comprises a top number of scores for the terms associated with the image, and wherein a score associated with a term and the image satisfies the criterion when the score is one of the top number of scores for the terms associated with the image.

22. The system of claim 8, wherein determining the score for the image with respect to the respective term based on the probabilities comprises combining probability adjusted scores for others of the plurality of images with respect to the respective term, wherein each of the probability adjusted scores comprises a score associated with one of the other images multiplied by a probability of navigating from the one of the other images to the image.

12. A system comprising:

a computer-readable medium;

one or more processors; and

instructions stored in the computer-readable medium and configured for execution by the one or more processors, the instructions comprising instructions to;

determine a score for an image of a plurality of images with respect to each of one or more terms;

identify one or more of the terms for each of which the score for the image with respect to the respective identified term satisfies a criterion; and

associate the identified terms with the image;

wherein the instructions to determine the score for the image with respect to a respective term comprises instructions to;

determine probabilities of navigating between images in the plurality of images; and

determine the score for the image with respect to the respective term based on the probabilities.

13. The system of claim 12, comprising instructions to:

determine degrees of similarity between pairs of images in the plurality of images; and

determine probabilities of navigating between images in the plurality of images using the degrees of similarity.

14. The system of claim 13, wherein determining degrees of similarity between pairs of images in the plurality of images comprises, for a respective pairing of images, identifying and comparing one or more features of each image in the pairing.

15. The system of claim 12, comprising instructions to:

determine probabilities of navigating based at least on the degrees of similarity and quality metrics of the images in the plurality of images.

16. The system of claim 15, wherein the quality metrics comprise one or more of a degree of focus of a respective image, a number of colors in a respective image, or a degree of saturation of a respective image.

17. The system of claim 12, comprising instructions to:

determine probabilities of navigating based at least on the degrees of similarity and one or more relationship metrics between pages hosting the images in the plurality of images.

18. The system of claim 12, comprising instructions to determine probabilities of navigating based on the degrees of similarity, relationship metrics between pages hosting the images in the plurality of images, and quality metrics of the images in the plurality of images.

24. The computer program product of claim 12, wherein determining probabilities of navigating between images in the plurality of images comprises:

determining degrees of similarity between pairs of images in the plurality of images; and

determining probabilities of navigating between images in the plurality of images using the degrees of similarity.

25. The computer program product of claim 24, wherein determining degrees of similarity between pairs of images in the plurality of images comprises, for a respective pairing of images, identifying and comparing one or more features of each image in the pairing.

26. The computer program product of claim 24, wherein determining probabilities of navigating between images in the plurality of images based on the degrees of similarity comprises:

determining probabilities of navigating based at least on the degrees of similarity and quality metrics of the images in the plurality of images.

27. The computer program product of claim 26 wherein the quality metrics comprise one or more of a degree of focus of a respective image, a number of colors in a respective image, or a degree of saturation of a respective image.

28. The computer program product of claim 24, wherein determining probabilities of navigating between images in the plurality of images based on the degrees of similarity comprises:

determining probabilities of navigating based at least on the degrees of similarity and one or more relationship metrics between pages hosting the images in the plurality of images.

29. The computer program product of claim 24, wherein determining probabilities of navigating between images in the plurality of images based on the degrees of similarity comprises:

determining probabilities of navigating based on the degrees of similarity, relationship metrics between pages hosting the images in the plurality of images, and quality metrics of the images in the plurality of images.

23. A computer program product, encoded on a non-transitory and tangible computer-readable medium, operable to cause a data processing apparatus to perform operations comprising:

determining a score for an image of a plurality of images with respect to each of one or more terms;

identifying one or more of the terms for each of which the score for the image with respect to the respective identified term satisfies a criterion; and

associating the identified terms with the image;

wherein determining the score for the image with respect to a respective term comprises;

determining probabilities of navigating between images in the plurality of images; and

determining the score for the image with respect to the respective term based on the probabilities.

30. The computer program product of claim 23, wherein navigating between images in the plurality of images comprises providing a first image to a user, and receiving a user selection of a second image from the plurality of images, wherein the second image is different than the first image.

31. The computer program product of claim 23, wherein the criterion comprises a threshold score, and wherein a score associated with a term and the image satisfies the criterion when the score is equal to or greater than the threshold score.

32. The computer program product of claim 23, wherein the criterion comprises a top number of scores for the terms associated with the image, and wherein a score associated with a term and the image satisfies the criterion when the score is one of the top number of scores for the terms associated with the image.

33. The computer program product of claim 23, wherein determining the score for the image with respect to the respective term based on the probabilities comprises combining probability adjusted scores for others of the plurality of images with respect to the respective term, wherein each of the probability adjusted scores comprises a score associated with one of the other images multiplied by a probability of navigating from the one of the other images to the image.

34. A system, comprising:

means for determining a score for an image of a plurality of images with respect to each of one or more terms;

means for identifying one or more of the terms for each of which the score for the image with respect to the respective identified term satisfies a criterion; and

means for associating the identified terms with the image;

wherein the means for determining the score for the image with respect to a respective term comprises;

means for determining probabilities of navigating between images in the plurality of images; and

means for determining the score for the image with respect to the respective term based on the probabilities.