Association of terms with images using image similarity

• US 8,356,035 B1
• Filed: 04/10/2007
• Issued: 01/15/2013
• Est. Priority Date: 04/10/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Baluja, Shumeet, Jing, Yushi
• Primary Examiner(s): WILSON, KIMBERLY LOVEL
• Application Number:
  US11/733,734
• Time in Patent Office: 2,107 Days
• Field of Search: 707/3, 707/999.003, 707/741
• US Class Current: 707/741
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content

Abstract

Methods, systems, and apparatus, including computer program products, for associating terms with images. A plurality of images is received. One or more of the received images are associated with one or more terms. Degrees of similarity between a plurality of pairs of images in the plurality of images is determined. A respective weight with respect to a first image of the plurality of images is assign to one or more of the terms based at least on the degrees of similarity. One or more of the terms are selected based on the respective weights of the terms with respect to the first image, and the selected terms are associated with the respective image.

Claims

1. A method, comprising:

receiving, at a computer system, a plurality of images, wherein one or more of the images are associated with one or more terms;

for each of a plurality of pairs of images in the plurality of images, determining, by the computer system, a degree of similarity between the two images in the pair, including for a first image in the plurality of images determining degrees of similarity between the first image paired with one or more other images from the plurality of images;

for the first image, assigning to one or more of the terms a respective weight with respect to the first image based at least in part on the degrees of similarity between the first image and the one or more other images; and

selecting, by the computer system, one or more of the terms to associate with the first image based on the respective weights of the terms with respect to the first image and associating the selected terms with the first image.

2. The method of claim 1, wherein determining degrees of similarity between a plurality of pairs of images in the plurality of images comprises:

comparing the first image of the plurality of images to a second image of the plurality of images.

3. The method of claim 2, wherein comparing the first image to the second image comprises:

identifying one or more features of the first image;

identifying one or more features of the second image; and

comparing the features of the first image to the features of the second image.

4. The method of claim 3, wherein:

the features of the first image comprise one or more global features of the first image; and

the features of the second image comprise one or more global features of the second image.

5. The method of claim 3, wherein:

the features of the first image comprise one or more local features of the first image; and

the features of the second image comprise one or more local features of the second image.

6. The method of claim 3, wherein:

the features of the first image are associated with one or more points of interest in the first image; and

the features of the second image are associated with one or more points of interest in the second image.

7. The method of claim 3, wherein the features of the first image and the features of the second image comprise scale-invariant features.

8. The method of claim 1, wherein assigning to one or more of the terms a respective weight with respect to the first image based on the degrees of similarity comprises:

generating a weighted graph data structure, the weighted graph data structure comprising a plurality of nodes, each of the nodes corresponding to a respective image of the plurality of images, the plurality of nodes including a node corresponding to the first image, the nodes connected by weighted edges, wherein an edge connecting a first respective node to a second respective node is weighted based on a degree of similarity between an image corresponding to the first respective node and an image corresponding to the second respective node, wherein the terms are associated with one or more of the nodes;

propagating the terms to the first node, including assigning to a term a weight with respect to the first image based at least on the weights of the edges connected to the first node.

9. A system, comprising:

one or more processors; and

a computer-readable medium storing instructions for execution by the one or more processors, the instructions comprising instructions to;

receive a plurality of images, wherein one or more of the images are associated with one or more terms;

for each of a plurality of pairs of images in the plurality of images, determine a degree of similarity between the two images in the pair, including for a first image in the plurality of images determining degrees of similarity between the first image paired with one or more other images from the plurality of images;

for the first image, assign to one or more of the terms a respective weight with respect to the first image based at least in part on the degrees of similarity between the first image and the one or more other images; and

select one or more of the terms to associate with the first image based on the respective weights of the terms with respect to the first image and associate the selected terms with the first image.

10. The system of claim 9, wherein the degrees of similarity between the first image and the one or more other images are determined by comparing a first histogram for the first image with one or more other histograms for the one or more other images.

11. The system of claim 10, wherein the first histogram comprises a color histogram, an edge histogram, an intensity histogram, or a texture histogram for the first image;

and wherein the one or more other histograms comprise one or more color histograms, one or more edge histograms, one or more intensity histograms, or one or more texture histograms for the one or more other images.

12. A computer program product, encoded on a computer-readable storage medium, configured to cause a data processing apparatus to perform operations comprising:

receiving a plurality of images, wherein one or more of the images are associated with one or more terms;

for each of a plurality of pairs of images in the plurality of images, determining a degree of similarity between the two images in the pair, including for a first image in the plurality of images determining degrees of similarity between the first image paired with one or more other images from the plurality of images;

for the first image, assigning to one or more of the terms a respective weight with respect to the first image of the plurality of images based at least in part on the degrees of similarity between the first image and the one or more other images; and

selecting one or more of the terms to associate with the first image based on the respective weights of the terms with respect to the first image and associating the selected terms with the first image.

13. The computer program product of claim 12, wherein determining the degrees of similarity between the first image and the one or more other images comprises:

determining feature similarity scores for the first image and of the one or more other images, wherein each of the feature similarity scores are determined with regard to a feature from a plurality of features;

weighting the feature similarity scores based on weights associated with the plurality of features, wherein the weights correspond to a level of importance for each of the plurality of features in indicating similarity between the first image and the one or more other images; and

combining the weighted feature similarity scores to determine the degrees of similarity between the first image and the one or more other images.

14. The computer program product of claim 13, wherein features from the plurality of features are selected from the group consisting of:

color, intensity, edges, and texture.

15. A system, comprising:

one or more memories configured to receive a plurality of images, wherein one or more of the images are associated with one or more terms;

one or more data processing apparatus including;

means for determining, for each of a plurality of pairs of images in the plurality of images, a degree of similarity between the two images in the pair, including determining, for a first image in the plurality of images, degrees of similarity between the first image paired with one or more other images from the plurality of images;

means for assigning to one or more of the terms a respective weight with respect to the first image based at least on the degrees of similarity between the first image and the one or more other images; and

means for selecting one or more of the terms to associate with the first image based on the respective weights of the terms with respect to the first image and associating the selected terms with the first image.

16. A method, comprising:

receiving, at a computer system, a plurality of images, wherein one or more terms are associated with one or more of the images;

for each of a plurality of pairs of images in the plurality of images, determining, by the computer system, a degree of similarity between the two images in the pair;

generating a weighted graph data structure, the weighted graph data structure having nodes corresponding to the images, wherein an edge connecting a first node and a second node of the weighted graph data structure has a weight based on a degree of similarity between an image corresponding to the first node and an image corresponding to the second node;

propagating, by the computer system, the terms to the nodes of the weighted graph data structure based on the weighted edges, wherein for each node, the one or more terms propagated to the node are assigned a weight that is based at least in part on the weight of one or more edges connected to the node; and

selecting one or more terms for a respective image of the plurality of images based on the one or more respective weights assigned to the one or more terms at the node that corresponds to the respective image and associating the selected terms with the respective image.

17. The method of claim 16, wherein determining degrees of similarity between a plurality of pairs of images in the plurality of images comprises:

comparing a first image of the plurality of images to a second image of the plurality of images.

18. The method of claim 17, wherein comparing the first image to the second image comprises:

identifying one or more features of the first image;

identifying one or more features of the second image; and

comparing the features of the first image to the features of the second image.

19. The method of claim 18, wherein:

the features of the first image comprise one or more local scale-invariant features of the first image; and

the features of the second image comprise one or more local scale-invariant features of the second image.

20. A system, comprising:

one or more processors; and

a computer-readable medium storing instructions for execution by the one or more processors, the instructions comprising instructions to;

receive a plurality of images, wherein one or more terms are associated with one or more of the images;

for each of a plurality of pairs of images in the plurality of images, determine a degree of similarity between the two images in the pair;

generate a weighted graph data structure, the weighted graph data structure having nodes corresponding to the images, wherein an edge connecting a first node and a second node of the weighted graph data structure has a weight based on a degree of similarity between an image corresponding to the first node and an image corresponding to the second node;

propagate the terms to the nodes of the weighted graph data structure based on the weighted edges, wherein for each node, the one or more terms propagated to the node are assigned a weight that is based at least in part on the weight of one or more edges connected to the node; and

select one or more terms for a respective image of the plurality of images based on the one or more respective weights assigned to the one or more terms at the node that corresponds to the respective image and associating the selected terms with the respective image.

21. The system of claim 20, wherein the degree of similarity between a first image corresponding to the first node and a second image corresponding to the second node is determined based on a number of shared keypoints between the first image and the second image, wherein a keypoint comprises a point of interest in an image that, together with other keypoints, identifies an object in the image, wherein a shared keypoint comprises keypoints in the first image and the second image with one or more matching features.

22. The system of claim 21, wherein the one or more matching features are selected from the group consisting of:

color, intensity, edges, and texture.

23. A computer program product, encoded on a computer-readable storage medium, configured to cause a data processing apparatus to perform operations comprising:

receiving a plurality of images, wherein one or more terms are associated with one or more of the images;

for each of a plurality of pairs of images in the plurality of images, determining a degree of similarity between the two images in the pair;

generating a weighted graph data structure, the weighted graph data structure having nodes corresponding to the images, wherein an edge connecting a first node and a second node of the weighted graph data structure has a weight based on a degree of similarity between an image corresponding to the first node and an image corresponding to the second node;

propagating the terms to the nodes of the weighted graph data structure based on the weighted edges, wherein for each node, the one or more terms propagated to the node are assigned a weight that is based at least in part on the weight of one or more edges connected to the node; and

selecting one or more terms for a respective image of the plurality of images based on the one or more respective weights assigned to the one or more terms at the node that corresponds to the respective image and associating the selected terms with the respective image.

24. A system, comprising:

one or more memories configured to receive a plurality of images, wherein one or more terms are associated with one or more of the images;

one or more data apparatus including;

means for determining, for each of a plurality of pairs of images in the plurality of images, degrees of similarity between the two images in the pair;

means for generating a weighted graph data structure, the weighted graph data structure having nodes corresponding to the images, wherein an edge connecting a first node and a second node of the weighted graph data structure has a weight based on a degree of similarity between an image corresponding to the first node and an image corresponding to the second node;

means for propagating the terms to the nodes of the weighted graph data structure based on the weighted edges, wherein for each node, the one or more terms propagated to the node are assigned a weight that is based at least in part on the weight of one or more edges connected to the node; and

means for selecting one or more terms for a respective image of the plurality of images based on the one or more respective weights assigned to the one or more terms at the node that corresponds to the respective image and associating the selected terms with the respective image.

25. A method, comprising:

identifying, by a computer system, similarities between pairs of images in a set of images, wherein, for a particular image in the set of images, particular similarities between the particular image paired with one or more other images from the set of images are identified, wherein one or more images from the set of the images are associated with one or more terms;

representing, by the computer system, the similarities between the pairs of images as weights in a similarity graph, wherein the similarity graph includes i) nodes that represent the set of images and ii) weighted links between the nodes that represent the pairs of images and that include the weights that correspond to the similarities between the pairs of images, wherein a particular node that represents the particular image in the similarity graph is connected by one or more of the weighted links to one or more other nodes that represent the one or more other images, wherein the one or more of the weighted links includes one or more particular weights that correspond to the particular similarities between the particular image and the one or more other images; and

using, by the computer system and for at least the particular image, the similarity graph to identify a set of terms for an image search query, wherein the set of terms is identified based, at least in part, on the one or more particular weights that correspond to the particular similarities between the particular image and the one or more other images, wherein the image search query is specific to the particular image and will produce a search result that includes images that are similar to the particular image.

26. The method of claim 25, further comprising propagating one or more term weights for the one or more terms from one or more nodes that represent the one or more images to the particular node that represents the particular image, wherein the one or more term weights are propagated using the weighted links between the nodes in the similarity graph and, through one or more iterations, results in one or more particular terms weights for the one or more terms at the particular node;

wherein the set of terms is identified further based on a comparison of the one or more particular term weights to a minimum term weight.