Query-dependent image similarity

• US 8,832,096 B1
• Filed: 11/16/2011
• Issued: 09/09/2014
• Est. Priority Date: 09/01/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Cai, Wei, Jing, Yushi
• Primary Examiner(s): Yen, Syling
• Application Number:
  US13/297,521
• Time in Patent Office: 1,028 Days
• Field of Search: 707/706, 707722-728, 707/731, 707/732, 707/736, 707/758, 707/781
• US Class Current: 707/727
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for evaluating image similarity. In one aspect, a method includes receiving, by a data processing apparatus, image search data for different search sessions, a search session being a pre-specified period, the image search data for a search session including: search query data specifying search queries that were received during the search session; responsive image data specifying images that were identified in response to the search queries; and interaction data specifying images referenced by search results with which a user interacted. Sets of learning images are identified based on the image search data. The sets of learning images include co-selected images for the search sessions. A query-dependent image profile for a particular image is determined based in part on the co-selected images that were identified in response to the particular query.

Claims

1. A method performed by data processing apparatus, the method comprising:

receiving, by a data processing apparatus, image search data for different search sessions, a search session being a pre-specified period, the image search data for a search session including;

search query data specifying text search queries that were received during the search session;

responsive image data specifying images that were identified in response to the text search queries; and

interaction data specifying images referenced by search results with which a user interacted;

identifying, based on the image search data, two or more images that were selected by a user during a search session as co-selected images for the search session;

determining that a pair of images from the two or more images are co-selected images for a particular text query based on a co-selection rate for the pair of images meeting a co-selection threshold, wherein the co-selection rate is based on a number of times that different users interacted with the pair of images during a search session;

determining, based in part on the co-selected images for the particular text query, a query-dependent image profile for the particular text query, the query-dependent image profile specifying an importance of one or more visual characteristics of images for identifying images responsive to the particular text query;

receiving, from a user device, the particular text search query;

identifying one or more images responsive to the particular text query based on visual characteristics of the one or more images and the query-dependent image profile for the particular text query; and

providing, to the user device, data specifying the one or more images that were identified as responsive to the particular text query based on the query-dependent image profile.

2. The method of claim 1, further comprising:

receiving data specifying a set of feature values for each of one or more images;

for each of the images;

determining a distance vector for the image and a reference image, the distance vector being determined based on a visual distance between one or more image feature values from each of the image and the reference image, the reference image being an image that has been identified as responsive to the particular text query; and

computing a query-dependent image similarity score for the image and the reference image based on the visual distance and the query-dependent image profile; and

providing data specifying the query-dependent image similarity scores.

3. The method of claim 2, further comprising:

receiving data indicating that the particular text query was received from a user device;

selecting a set of images that are responsive to the particular text query, the set of images being selected, at least in part, on the query-dependent image similarity scores; and

providing data specifying the set of images.

4. The method of claim 1, wherein identifying two or more images comprises identifying two images that were both interacted with when referenced by a search results page for the particular text query.

5. The method of claim 1, further comprising:

obtaining a co-selection vector for each of the images that, according to the responsive image data, were identified in response to the particular text query;

determining a co-selection score for pairs of the images, the co-selection score for each pair of images indicating a distance between the co-selection vectors for the images in the pair; and

selecting, based on the co-selection scores and a search rank for each of the images, a plurality of sets of learning images for the query-dependent image profile, the search rank being a value indicative of a presentation location for the image on a search results page.

6. The method of claim 5, wherein selecting a plurality of sets of learning images comprises, for each set of learning images, selecting a pair of images for which the co-selection score is greater than a first distance threshold, wherein a first image in the pair has a search rank that is higher than the search rank for a second image in the pair.

7. The method of claim 6, wherein selecting a plurality of sets of learning images further comprises, selecting a third image for each set of learning images, wherein:

the co-selection score between the first image and the third image is below a second distance threshold;

the search rank of the third image is greater than the search rank of the second image, but lower than the first image; and

the first distance threshold is greater than the second distance threshold.

8. The method of claim 1, wherein determining a query-dependent image profile comprises determining an image feature weight vector for which a norm of the image feature weight vector is less than a threshold value.

9. The method of claim 1, wherein selecting a plurality of sets of learning images further comprises, selecting a third image for each set of learning images, wherein the co-selection score between the first image and the third image meets a second distance threshold.

10. The method of claim 9, wherein the search rank of the third image is greater than the search rank of the second image, but lower than the first image.

11. The method of claim 9, wherein the first distance threshold is greater than the second distance threshold.

12. The method of claim 1, further comprising:

determining, based in part on the co-selected images that were identified in response to a particular text query, a query-dependent image profile for the particular text query, the query-dependent image profile specifying, for one or more image feature values, an importance of the image feature value for determining a measure of image similarity for images, an image feature value being indicative of a visual characteristic of the image; and

providing data specifying the query-dependent image profile.

13. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving, by a data processing apparatus, image search data for different search sessions, a search session being a pre-specified period, the image search data for a search session including;

search query data specifying text search queries that were received during the search session;

responsive image data specifying images that were identified in response to the text search queries; and

interaction data specifying images referenced by search results with which a user interacted;

identifying, based on the image search data, two or more images that were selected by a user during a search session as co-selected images for the search session;

determining that a pair of images from the two or more images are co-selected images for a particular text query based on a co-selection rate for the pair of images meeting a co-selection threshold, wherein the co-selection rate is based on a number of times that different users interacted with the pair of images during a search session;

determining, based in part on the co-selected images for the particular text query, a query-dependent image profile for the particular text query, the query-dependent image profile specifying an importance of one or more visual characteristics of images for identifying images responsive to the particular text query; and

receiving, from a user device, the particular text search query;

identifying one or more images responsive to the particular text query based on visual characteristics of the one or more images and the query-dependent image profile for the particular text query; and

providing, to the user device, data specifying the one or more images that were identified as responsive to the particular text query based on the query-dependent image profile.

14. The computer storage medium of claim 13, wherein the program further comprises instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving data specifying a set of feature values for each of one or more images;

for each of the images;

determining a distance vector for the image and a reference image, the distance vector being determined based on a visual distance between one or more image feature values from each of the image and the reference image, the reference image being an image that has been identified as responsive to the particular text query; and

computing a query-dependent image similarity score for the image and the reference image based on the visual distance and the query-dependent image profile; and

providing data specifying the query-dependent image similarity scores.

15. The computer storage medium of claim 14, wherein the program further comprises instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving data indicating that the particular text query was received from a user device;

selecting a set of images that are responsive to the particular text query, the set of images being selected, at least in part, on the query-dependent image similarity scores; and

providing data specifying the set of images.

16. The computer storage medium of claim 13, wherein identifying two or more images comprises identifying two images that were both interacted with when referenced by a search results page for the particular text query.

17. The computer storage medium of claim 13, wherein the program further comprises instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

obtaining a co-selection vector for each of the images that, according to the responsive image data, were identified in response to the particular text query;

determining a co-selection score for pairs of the images, the co-selection score for each pair of images indicating a distance between the co-selection vectors for the images in the pair; and

selecting, based on the co-selection scores and a search rank for each of the images, a plurality of sets of learning images for the query-dependent image profile, the search rank being a value indicative of a presentation location for the image on a search results page.

18. The computer storage medium of claim 17, wherein selecting a plurality of sets of learning images comprises, for each set of learning images, selecting a pair of images for which the co-selection score is greater than a first distance threshold, wherein a first image in the pair has a search rank that is higher than the search rank for a second image in the pair.

19. The computer storage medium of claim 18, wherein selecting a plurality of sets of learning images further comprises, selecting a third image for each set of learning images, wherein:

the co-selection score between the first image and the third image is below a second distance threshold;

the search rank of the third image is greater than the search rank of the second image, but lower than the first image; and

the first distance threshold is greater than the second distance threshold.

20. The computer storage medium of claim 13, wherein determining a query-dependent image profile comprises determining an image feature weight vector for which a norm of the image feature weight vector is less than a threshold value.

21. The computer storage medium of claim 13, wherein selecting a plurality of sets of learning images further comprises, selecting a third image for each set of learning images, wherein the co-selection score between the first image and the third image meets a second distance threshold.

22. The computer storage medium of claim 21, wherein the search rank of the third image is greater than the search rank of the second image, but lower than the first image.

23. The computer storage medium of claim 21, wherein the first distance threshold is greater than the second distance threshold.

24. The computer storage medium of claim 23, wherein the program further comprises instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

determining, based in part on the sets of learning images that include co-selected images that were identified in response to a particular text query, a query-dependent image profile for the particular text query, the query-dependent image profile specifying, for one or more image feature values, an importance of the image feature value for determining a measure of image similarity for images, an image feature value being indicative of a visual characteristic of the image; and

providing data specifying the query-dependent image profile.

25. A system comprising:

a data store storing image search data for different search sessions, a search session being a pre-specified period, the image search data for a search session including;

search query data specifying text search queries that were received during the search session;

responsive image data specifying images that were identified in response to the text search queries; and

interaction data specifying images referenced by search results with which a user interacted; and

one or more computers that are configured to interact with the data store, the one or more computers being further configured to perform operations comprising;

receiving, from the data store, the image search data;

identifying, based on the image search data, two or more images that were selected by a user during a search session as co-selected images for the search session;

determining that a pair of images from the two or more images are co-selected images for a particular text query based on a co-selection rate for the pair of images meeting a co-selection threshold, wherein the co-selection rate is based on a number of times that different users interacted with the pair of images during a search session;

determining, based in part on the co-selected images for the particular text query, a query-dependent image profile for the particular text query, the query-dependent image profile specifying an importance of one or more visual characteristics of images for identifying images responsive to the particular text query; and

receiving, from a user device, the particular text search query;

identifying one or more images responsive to the particular text query based on visual characteristics of the one or more images and the query-dependent image profile for the particular text query; and

providing, to the user device, data specifying the one or more images that were identified as responsive to the particular text query based on the query-dependent image profile.

26. The system of claim 25, wherein the one or more computers are further configured to perform operations comprising:

receiving data specifying a set of feature values for each of one or more images;

for each of the images;

determining a distance vector for the image and a reference image, the distance vector being determined based on a visual distance between one or more image feature values from each of the image and the reference image, the reference image being an image that has been identified as responsive to the particular text query; and

computing a query-dependent image similarity score for the image and the reference image based on the visual distance and the query-dependent image profile; and

providing data specifying the query-dependent image similarity scores.

27. The system of claim 26, wherein the one or more computers are further configured to perform operations comprising:

receiving data indicating that the particular text query was received from a user device;

selecting a set of images that are responsive to the particular text query, the set of images being selected, at least in part, on the query-dependent image similarity scores; and

providing data specifying the set of images.

28. The system of claim 25, wherein identifying two or more images comprises identifying two images that were both interacted with when referenced by a search results page for the particular text query.

29. The system of claim 25, wherein the one or more computers are further configured to perform operations comprising:

obtaining a co-selection vector for each of the images that, according to the responsive image data, were identified in response to the particular text query;

determining a co-selection score for pairs of the images, the co-selection score for each pair of images indicating a distance between the co-selection vectors for the images in the pair; and

selecting, based on the co-selection scores and a search rank for each of the images, a plurality of sets of learning images for the query-dependent image profile, the search rank being a value indicative of a presentation location for the image on a search results page.

30. The system of claim 29, wherein selecting a plurality of sets of learning images comprises, for each set of learning images, selecting a pair of images for which the co-selection score is greater than a first distance threshold, wherein a first image in the pair has a search rank that is higher than the search rank for a second image in the pair.

31. The system of claim 30, wherein selecting a plurality of sets of learning images further comprises, selecting a third image for each set of learning images, and wherein:

the co-selection score between the first image and the third image is below a second distance threshold;

the search rank of the third image is greater than the search rank of the second image, but lower than the first image; and

the first distance threshold is greater than the second distance threshold.

32. The system of claim 25, wherein determining a query-dependent image profile comprises determining an image feature weight vector for which a norm of the image feature weight vector is less than a threshold value.

33. A system comprising:

a data store storing image search data for different search sessions, a search session being a pre-specified period, the image search data for a search session including;

search query data specifying text search queries that were received during the search session;

responsive image data specifying images that were identified in response to the text search queries; and

interaction data specifying images referenced by search results with which a user interacted; and

one or more computers that are configured to interact with the data store, the one or more computers being further configured to perform operations comprising;

receiving, from the data store, the image search data;

determining a co-selection score for pairs of the images that were selected by a user during a search session as co-selected images for the search session, the co-selection score for a pair of images indicating a distance between co-selection vectors for the images in the pair, and wherein the co-selection score is based on a number of times that users interacted with the pair of images during a search session;

selecting, based on the co-selection scores and a search rank for each of the images, a plurality of sets of learning images, the search rank being a value indicative of a presentation location for the image on a search results page; and

receiving, from a user device, the particular text search query;

identifying one or more images responsive to the particular text query based on visual characteristics of the one or more images and the query-dependent image profile for the particular text query; and

providing, to the user device, data specifying the one or more images that were identified as responsive to the particular text query based on the query-dependent image profile.

34. The system of claim 33, wherein selecting a plurality of sets of learning images comprises, for each set of learning images, selecting a pair of images for which the co-selection score meets a first distance threshold, wherein a first image in the pair has a search rank that is higher than the search rank for a second image in the pair.

35. The system of claim 34, wherein selecting a plurality of sets of learning images further comprises, selecting a third image for each set of learning images, wherein the co-selection score between the first image and the third image meets a second distance threshold.

36. The system of claim 35, wherein the search rank of the third image is greater than the search rank of the second image, but lower than the first image.

37. The system of claim 35, wherein the first distance threshold is greater than the second distance threshold.

38. The system of claim 37, wherein the one or more computers are further configured to perform operations comprising:

determining, based in part on the sets of learning images that include co-selected images that were identified in response to a particular text query, a query-dependent image profile for the particular text query, the query-dependent image profile specifying, for one or more image feature values, an importance of the image feature value for determining a measure of image similarity for images, an image feature value being indicative of a visual characteristic of the image; and

providing data specifying the query-dependent image profile.

39. The system of claim 33, wherein determining a query-dependent image profile comprises determining an image feature weight vector for which a norm of the image feature weight vector is less than a threshold value.