Query image search

• US 9,053,115 B1
• Filed: 08/23/2012
• Issued: 06/09/2015
• Est. Priority Date: 04/20/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Rosenberg, Charles J., Wang, Jingbin, Moussa, Sarah, Murphy-Chutorian, Erik, Frome, Andrea, Singer, Yoram, Malpani, Radhika
• Primary Examiner(s): Hoang, Son T
• Application Number:
  US13/592,850
• Time in Patent Office: 1,020 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/14 Details of searching files based on file metadata
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/5866 using information manually generated, e.g. tags, keywords, comments, manually generated location and time information

Abstract

Methods, systems and apparatus for identifying result images for a query image. One or more labels that are associated with the query image are obtained. Candidate images matching the query labels are identified. Visual similarity scores are generated for the candidate images. Each visual similarity score represents the visual similarity of a respective candidate image to the query image. Relevance scores are generated for each of the candidate images based on the visual similarity scores. Each relevance score represents a measure of relevance of the respective candidate images to the query image. The candidate images are ranked based on the relevance scores, a highest ranking subset of the candidate images being identified as result images and referenced by image search results. The result images can be candidate images that satisfy a similarity condition relative to the query image and other result images.

Claims

1. A computer-implemented method, comprising:

accessing a plurality of images referenced by initial image search results responsive to a query image, each of the plurality of images having a visual similarity score that satisfies an initial similarity threshold, the visual similarity score being generated by an image similarity model that has been trained based on user similarity feedback from a plurality of users and feature distances between images referenced by the user similarity feedback, the user similarity feedback specifying a reference query image and a first of two training images that was identified, by the plurality of users, as more visually similar than a second of the two training images to the reference query image, each of the feature distances indicative of a visual distance between corresponding image feature scores for the reference query image and the first of the two training images;

selecting, in a data processing system and as a result image for the query image, a first image from the plurality of images, the first image having a visual similarity score that satisfies a first similarity threshold, the first similarity threshold being more selective than the initial similarity threshold;

determining that a second image from the plurality of images has a first degree of visual similarity relative to the query image;

determining that the second image from the plurality of images has a second degree of visual similarity relative to the first image from the plurality of images;

determining, based on the first degree of visual similarity and the second degree of visual similarity, that the second image satisfies a similarity condition specifying required degrees of visual similarity between the second image, the query image, and the first image; and

selecting, in the data processing system and as another result image for the query image, the second image from the plurality of images in response to determining that the second image satisfies the similarity condition, wherein a result image is an image for which a reference to the image is identified as a final image search result for the query image.

2. The method of claim 1, wherein the determining that the second image satisfies the similarity condition comprises identifying a second image having a visual similarity score that satisfies a second similarity threshold with reference to the query image and a third similarity threshold with reference to the first image.

3. The method of claim 2, further comprising:

iteratively identifying other second images based on the similarity condition until a threshold number of second images are identified.

4. The method of claim 1, wherein the selecting the first image comprises identifying as the first image, an image having at least a first threshold number of nearest neighbors that are also nearest neighbors of the query image, a nearest neighbor of an image being another image having a visual similarity score relative to the image that satisfies a nearest neighbor threshold.

5. The method of claim 4, further comprising identifying, as the second image, an image having at least a second threshold number of nearest neighbors that are also nearest neighbors of the first image and the query image.

6. The method of claim 5, wherein the first threshold number and the second threshold number of the nearest neighbors are equal.

7. The method of claim 1, further comprising selecting a dominant image characteristic for the plurality of images, the dominant image characteristic being an image characteristic that is included in a threshold number of the plurality of images;

filtering the plurality of images based on the dominant image characteristic; and

identifying the filtered plurality of images as result images for the query image.

8. The method of claim 7, wherein the filtering the plurality of images comprises:

for each of the plurality of images;

analyzing image feature scores of the image to identify whether the image contains the dominant image characteristic; and

removing the image from the plurality of images when the dominant image characteristic is not identified from the image feature scores.

9. A computer system, comprising:

a data store storing a plurality of images referenced by initial image search results responsive to a query image, each of the plurality of images having a visual similarity score that satisfies an initial similarity threshold, the visual similarity score being generated by an image similarity model that has been trained based on user similarity feedback from a plurality of users and feature distances between images referenced by the user similarity feedback, the user similarity feedback specifying a reference query image and a first of two training images that was identified, by the plurality of users, as more visually similar than a second of the two training images to the reference query image, each of the feature distances indicative of a visual distance between corresponding image feature scores for the reference query image and the first of the two training images; and

one or more computers that interact with the data store and identify final result images for the query image, the final result images including at least a first image and a second image, wherein the one or more computers determine a first degree of visual similarity between the first image and the query image, identify the first image as a final result image based on the first degree of visual similarity satisfying a first similarity threshold, determine a second degree of visual similarity between a second image and the first image, and identify the second image as another final result image based on the second degree of visual similarity meeting a required degree of similarity between the second image and the first image and based on the second image having a third degree of visual similarity, relative to the query image, that meets the first similarity threshold.

10. The system of claim 9, wherein the one or more computers are configured to identify the second image having a visual similarity score that satisfies a second similarity threshold to the query image and a third similarity threshold to the first image.

11. The system of claim 10, wherein the one or more computers are configured to iteratively identify an additional second image of the final result images until a threshold number of second images are identified.

12. The system of claim 9, wherein the one or more computers identify the final result images based on a similarity condition requiring:

at least a first threshold number of nearest neighbors of the first image being nearest neighbors of the query image, a nearest neighbor of an image being another image having a visual similarity score relative to the image that satisfies a nearest neighbor threshold; and

at least a second threshold number of nearest neighbors of the second image being nearest neighbors of the first image.

13. The system of claim 12, wherein the first threshold number and the second threshold number of the nearest neighbors are equal.

14. The system of claim 9, further comprising a user device, wherein the one or more computers are configured to interact with the user device.

15. The system of claim 9, wherein the one or more computers are configured to:

select a dominant image characteristic for highest ranking candidate images and select the final result images for the query image based on the dominant image characteristic, the dominant image characteristic being an image characteristic that is included in a threshold number of a highest ranking subset of the candidate images;

determine candidate images from the highest ranking subset of the candidate images that do not include the dominant characteristic; and

remove the candidate images that do not include the dominant characteristic from the highest ranking subset of candidate images.