IMAGE SIMILARITY FROM DISPARATE SOURCES

• US 20110029561A1
• Filed: 07/31/2009
• Published: 02/03/2011
• Est. Priority Date: 07/31/2009
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Excalibur IP, LLC (Acacia Research Corporation)
• Inventors: Weinberger, Kilian Quirin, Kurapati, Kaushal, Sathish, Sriram J., Ng, Polly, Slaney, Malcolm
• Granted Patent: US 9,384,214 B2
• Time in Patent Office: Days
• US Class Current: 707/772
• CPC Class Codes: G06F 16/56 having vectorial format
• 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 16/583 using metadata automatically derived from the content

Abstract

A search engine determines a set of other images that are similar to a user-selected image, and presents those other images to the user. In determining whether two images are sufficiently similar to each other to merit presentation of one, the search engine determines a Euclidean distance between separate feature vectors that are associated with each of the images. Each such vector indicates diverse types of information that is known about the associated image. The types of information included within such a vector may include attributes that reflect visual characteristics that are visible in an image, verbal tags that have been associated with the image users in a community of users, concepts derived from those tags, coordinates that reflect a geographic location at which a camera that produced the image was when the camera produced the image, and concepts related to groups with which the image is associated.

Claims

1. A computer-implemented method comprising steps of:

determining, for each image in a plurality of images, a set of metadata for the image;

generating, for each particular image in the plurality of images, a data structure that contains information regarding the set of metadata for the particular image;

in response to a particular user'"'"'s request to find other images that are similar to a selected image, comparing values in the data structure that was generated for the particular image to values in the data structure that was generated for a candidate search result image in the plurality of images; and

in response to determining that a result of the comparing exceeds a specified threshold, presenting at least the candidate search result image to the user as an image that is similar to the selected image;

wherein the steps are performed by a computer system.

2. The method of claim 1, wherein:

determining the set of metadata for the image comprises determining;

(a) a set of attributes that reflect visual characteristics that are visible in the image, (b) a set of tags that have been associated with the image by one or more users in a community of users, (c) a set of concepts to which tags in the set of tags are related, and (d) for each concept in the set of concepts, a probability that the set of tags reflects the concept, thereby producing a set of concept probabilities for the image; and

generating the data structure that contains information regarding the set of metadata for the particular image comprises generating a particular data structure that contains information regarding the (a) the set of attributes determined for the particular image, and (b) the set of concept probabilities determined for the particular image.

3. The method of claim 2, wherein the particular data structure that was generated for the particular image is a first feature vector, wherein the data structure that was generated for the candidate search result image is second feature vector, and wherein comparing values in the first feature vector to values in the second feature vector comprises determining a Euclidean distance of the first and second feature vectors.

4. The method of claim 2, further comprising:

for each particular tag in the set of tags determined for the particular image, (a) determining a quantity of different images, in the plurality of images, with which the particular tag is associated, and (b) weighting a value for a particular concept probability, in the data structure that was generated for the particular image, based at least part on said quantity.

5. The method of claim 2, further comprising:

for each particular tag in the set of tags determined for the particular image, (a) determining a quantity of different images, in the plurality of images, with which the particular tag is associated, and (b) weighting a value for a particular concept probability, in the data structure that was generated for the particular image, based at least part on said quantity;

wherein weighting the value for the particular concept probability comprises determining a location, within a distribution of different tags'"'"' quantities, at which the particular tag'"'"'s quantity lies, and weighting the value for the particular concept probability based at least in part on a distance of the particular tag'"'"'s location from a median of the distribution.

6. The method of claim 2, further comprising:

for each particular tag in the set of tags determined for the particular image, (a) determining a quantity of different images, in the plurality of images, with which the particular tag is associated, and (b) weighting a value for a particular concept probability, in the data structure that was generated for the particular image, based at least part on said quantity;

wherein weighting the value for the particular concept probability comprises decreasing an extent of influence that the value for the particular concept probability will have on said comparing as a distance of the particular tag'"'"'s quantity becomes farther away from a median of a distribution of different tags'"'"'quantities.

7. The method of claim 2, wherein generating the data structure for the particular image comprises inserting, into the data structure for the particular image, one or more values that are indicative of geographic coordinates at which a device that captured the particular image was present at a time that the device captured the particular image.

8. The method of claim 2, wherein generating the particular data structure for the particular image comprises inserting, into the particular data structure for the particular image, one or more values that are indicative of groups to which the particular image belongs.

12. A volatile or non-volatile computer-readable storage medium storing one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the method recited in claim 1.

13. A volatile or non-volatile computer-readable storage medium storing one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the method recited in claim 2.

14. A volatile or non-volatile computer-readable storage medium storing one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the method recited in claim 3.

15. A volatile or non-volatile computer-readable storage medium storing one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the method recited in claim 4.

16. A volatile or non-volatile computer-readable storage medium storing one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the method recited in claim 5.

17. A volatile or non-volatile computer-readable storage medium storing one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the method recited in claim 6.

18. A volatile or non-volatile computer-readable storage medium storing one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the method recited in claim 7.

19. A volatile or non-volatile computer-readable storage medium storing one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the method recited in claim 8.

9. A computer-implemented method comprising steps of:

receiving a user'"'"'s request to view other images that are deemed to be similar to a first image;

determining a first group with which the first image is associated;

determining a first set of concepts based at least in part on textual data that are associated with multiple images in the first group;

determining a first set of concept probabilities for concepts in the first set of concepts;

populating at least a subsection of a first feature vector with concepts in the first set of concept probabilities;

determining a second group with which a second image is associated;

determining a second set of concepts based at least in part on textual data that are associated with multiple images in the second group;

determining a second set of concept probabilities for concepts in the second set of concepts;

populating at least a subsection of a second feature vector with concepts in the second set of concept probabilities;

determining a Euclidean distance based at least in part on the first feature vector and the second feature vector; and

based at least in part on the Euclidean distance, selecting the second image from an image corpus for inclusion within a set of other images that are deemed to be similar to the first image; and

presenting the set of other images to a user from which the request was received;

wherein the steps are performed by a computer system.

10. The method of claim 9, further comprising weighting one or more concept probabilities in the first feature vector based at least in part on how far from a median of a concept probability distribution the one or more concept probabilities in the first feature vector occur in the concept probability distribution.

20. A volatile or non-volatile computer-readable storage medium storing one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the method recited in claim 9.

21. A volatile or non-volatile computer-readable storage medium storing one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the method recited in claim 10.

11. A computer-implemented method comprising steps of:

receiving a user'"'"'s request to view other images that are deemed to be similar to a first image;

in response to the request, determining a first user group to which a first owner of the first image belongs;

determining a second user group to which a second owner of a second image belongs;

determining a distance of the first user group to the second user group within a graph of connected user groups; and

based at least in part on the distance of the first user group to the second user group, selecting the second image from an image corpus for inclusion within a set of other images that are deemed to be similar to the first image; and

presenting the set of other images to a user from which the request was received;

wherein the steps are performed by a computer system.

22. A volatile or non-volatile computer-readable storage medium storing one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the method recited in claim 11.