Image searching techniques

• US 20020078043A1
• Filed: 12/28/2000
• Published: 06/20/2002
• Est. Priority Date: 12/15/2000
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: America Online Inc. (Warner Bros. Discovery, Inc.)
• Inventors: Pass, Gregory S., Wood, Frank
• Granted Patent: US 6,556,710 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/5838 using colour

Abstract

A search for an image includes receiving a set of features corresponding to image characteristics that then are compared to features indexed for multiple stored images. A search result is produced based on the comparison. The received set of features may correspond to posterized image characteristics that then are compared to features that have been indexed and that correspond to posterized image characteristics for multiple stored images. The received set of features may be compared to features that have been indexed for multiple stored images in an inverted index. The inverted index may include a relationship between features and images including those features. Additionally or alternatively, the received set of features may be compared to a list of features, where the list of features includes a relationship between features and images including those features.

Claims

1. A method for performing an image search, the method comprising:

receiving a set of features corresponding to image characteristics;

comparing the received set of features to features that have been indexed for multiple stored images; and

producing a search result based on the comparison.

2. The method as in claim 1 wherein receiving the set of features includes:

receiving at least a portion of an image;

identifying features corresponding to image characteristics within the portion of the image received; and

computing a joint histogram for the portion of the image based on the features identified as corresponding to the image characteristics within the portion of the image.

3. The method as in claim 2 wherein receiving the set of features further includes:

receiving text that corresponds to image characteristics; and

identifying features from the text corresponding to image characteristics.

4. The method as in claim 1 wherein receiving the set of features includes:

receiving text that corresponds to image characteristics; and

identifying features from the text corresponding to image characteristics.

5. The method as in claim 1 wherein comparing the received set of features includes comparing the received set of features to features that have been indexed for multiple stored images in an inverted index.

6. The method as in claim 5 wherein the inverted index includes a relationship between features and corresponding images including the features.

7. The method as in claim 1 wherein comparing the received set of features includes comparing the received set of features to a list of features, the list of features including a relationship between features and corresponding images including the features.

8. The method as in claim 1 wherein producing the search result includes retrieving a set of images for display in a ranked manner.

9. The method as in claim 8 wherein retrieving the set of images includes ranking the set of images in order from an image that is most relevant to the received set of features to an image that is least relevant to the received set of features, wherein the order of the images is determined based on similarity metrics.

10. The method as in claim 1 wherein:

receiving the set of features includes receiving a set of features corresponding to posterized image characteristics; and

comparing the retrieved set of features includes comparing the received set of features to features that have been indexed and that correspond to posterized image characteristics for multiple stored images.

11. The method as in claim 10 wherein receiving the set of features corresponding to posterized image characteristics includes:

receiving a set of features corresponding to image characteristics; and

posterizing at least one of the received set of features to create posterized image characteristics.

12. The method as in claim 11 wherein the posterizing the received set of features includes:

computing a first histogram vector based on the received set of features that correspond to image characteristics, the first histogram vector including one or more vector elements, each representing information for a different received feature;

identifying multiple subsets within at least one of the vector elements included in the first histogram vector; and

creating a second histogram vector that includes a vector element for each of the subsets identified within the vector elements included in the first histogram vector, data within the vector elements of the second histogram vector representing the posterized image characteristics.

13. The method as in claim 10 wherein receiving the set of features corresponding to posterized image characteristics includes:

receiving at least a portion of an image;

identifying features corresponding to image characteristics within the portion of the received image; and

computing a posterized joint histogram for the portion of the image based on the features identified as corresponding to the image characteristics within the portion of the image.

14. The method as in claim 13 wherein receiving the set of features corresponding to posterized image characteristics further includes:

receiving text that corresponds to posterized image characteristics; and

identifying features from the text corresponding to posterized image characteristics.

15. The method as in claim 10 wherein receiving the set of features corresponding to posterized image characteristics includes:

receiving text that corresponds to posterized image characteristics; and

identifying features from the text corresponding to posterized image characteristics.

16. The method as in claim 10 wherein comparing the received set of features includes comparing the received set of features to features that have been indexed for multiple stored posterized images in an inverted index.

17. The method as in claim 16 wherein the inverted index includes a relationship between features and corresponding posterized images including the features.

18. The method as in claim 10 wherein comparing the received set of features includes comparing the set of features to a list of features, the list of features including a relationship between features and corresponding posterized images including the features.

19. The method as in claim 10 wherein producing the search result includes retrieving a set of images for display in a ranked manner.

20. The method as in claim 19 wherein retrieving the set of images includes ranking the set of images in order from an image that is most relevant to the received set of features to an image that is least relevant to the received set of features, the order of the images being determined based on similarity metrics.

21. A method for retrieving images and producing a ranked result, the method comprising:

receiving at least one feature corresponding to an image characteristic;

searching an index of features corresponding to indexed images to identify selected indexed images including at least the received feature;

determining whether to retrieve the selected indexed images based on whether the selected indexed images satisfy at least one similarity metric; and

retrieving the selected indexed images that satisfy the at least one similarity metric to produce a ranked list of images.

22. The method as in claim 21 wherein receiving the feature includes receiving multiple features corresponding to image characteristics, and searching the index of features includes searching to determine if the indexed images include at least one of the multiple features received.

23. The method as in claim 22 wherein the index includes joint histogram features.

24. The method as in claim 23 further comprising computing a joint histogram from the multiple features received, wherein searching includes searching the index of joint histogram features to determine if the indexed images include at least one of the computed joint histogram features.

25. The method as in claim 21 wherein receiving the feature includes receiving a feature corresponding to a posterized image characteristic.

26. The method as in claim 21 wherein receiving the feature includes receiving multiple features corresponding to posterized image characteristics, and searching the index of features includes searching to determine if the indexed images include at least one of the multiple features received.

27. The method as in claim 26 wherein the index includes posterized joint histogram features.

28. The method as in claim 27 further comprising computing a posterized joint histogram from the multiple features received, wherein searching includes searching the index of posterized joint histogram features to determine if the indexed images include at least one of the computed posterized joint histogram features.

30. The computer program of claim 29 wherein the receiving code segment includes a code segment that causes the computer to receive text that corresponds to image characteristics.

31. The computer program of claim 29 wherein the receiving code segment includes:

a receiving code segment that causes the computer to receive at least a portion of an image;

an identifying code segment that causes the computer to identify features corresponding to image characteristics within the received portion of the image; and

a computing code segment that causes the computer to compute a joint histogram for the portion of the image based on the features identified as corresponding to the image characteristics within the portion of the image.

32. The computer program of claim 31 wherein the receiving code segment further includes:

a receiving code segment that causes the computer to receive text that corresponds to image characteristics; and

an identifying code segment that causes the computer to identify features from the text corresponding to image characteristics.

33. The computer program of claim 29 wherein the comparing code segment includes a code segment that causes the computer to compare the received set of features to features that have been indexed for multiple stored images in an inverted index.

34. The computer program of claim 33 wherein the inverted index includes a relationship between features and corresponding images including the features.

35. The computer program of claim 29 wherein the comparing code segment includes a code segment that causes the computer to compare the received set of features to a list of features, the list of features including a relationship between features and corresponding images including the features.

36. The computer program of claim 29 wherein the producing code segment includes a code segment that causes the computer to retrieve a set of images for display in a ranked manner.

37. The computer program of claim 36 wherein the retrieving code segment that causes the computer to receive a set of images includes ranking the set of images in order from an image that is most relevant to the received set of features to an image that is least relevant to the received set of features, the order of the images being determined based on similarity metrics.

38. The computer program of claim 29 wherein:

the receiving code segment that causes the computer to receive includes receiving a set of features corresponding to posterized image characteristics; and

the comparing code segment that causes the computer to compare includes comparing the received set of features to features that have been indexed and that correspond to posterized image characteristics for multiple stored images.

39. The computer program of claim 38 further comprising:

a receiving code segment that causes the computer to receive a set of features corresponding to image characteristics; and

a posterizing code segment that causes the computer to posterize at least one of the received set of features to create posterized image characteristics.

40. The computer program of claim 39 wherein the posterizing includes:

a computing code segment that causes the computer to compute a first histogram vector based on the received set of features that correspond to image characteristics, the first histogram vector including one or more vector elements, each representing information for a different received feature;

an identifying code segment that causes the computer to identify multiple subsets within at least one of the vector elements included in the first histogram vector; and

a creating code segment that causes the computer to create a second histogram vector that includes a vector element for each of the subsets identified within the vector elements included in the first histogram vector, data within the vector elements of the second histogram vector representing the posterized image characteristics.

41. The computer program of claim 38 wherein the receiving code segment includes:

a receiving code segment that causes the computer to receive at least a portion of an image;

an identifying code segment that causes the computer to identify features corresponding to image characteristics within the portion of the image received; and

a computing code segment that causes the computer to compute a posterized joint histogram for the portion of the image based on the features identified as corresponding to the image characteristics within the portion of the image.

42. The computer program of claim 38 wherein the receiving code segment includes:

a receiving code segment that causes the computer to receive text that corresponds to posterized image characteristics; and

an identifying code segment that causes the computer to identify features from the text corresponding to posterized image characteristics.

43. The computer program of claim 41 wherein the receiving code segment further includes:

a receiving code segment that causes the computer to receive text that corresponds to posterized image characteristics; and

an identifying code segment that causes the computer to identify features from the text corresponding to posterized image characteristics.

44. The computer program of claim 38 wherein the comparing code segment includes a comparing code segment that causes the computer to compare the received set of features to features that have been indexed for multiple stored posterized images in an inverted index.

45. The computer program of claim 44 wherein the inverted index includes a relationship between features and corresponding posterized images including the features.

46. The computer program of claim 38 wherein the comparing code segment includes a comparing code segment that causes the computer to compare the received set of features to a list of features, wherein the list of features includes a relationship between features and corresponding posterized images including the features.

47. The computer program of claim 38 wherein the producing code segment includes a retrieving code segment that causes the computer to retrieve a set of images for display in a ranked manner.

48. The computer program of claim 47 wherein the retrieving code segment includes a ranking code segment that causes the computer to rank the set of images in order from an image that is most relevant to the received set of features to an image that is least relevant to the received set of features, with the order of the images being determined based on similarity metrics.

50. The computer program of claim 49 wherein the receiving code segment includes a receiving code segment that causes the computer to receive multiple features corresponding to image characteristics, and the searching code segment includes a searching code segment that causes the computer to search the index of features to determine if the indexed images include at least one of the multiple features received.

51. The computer program of claim 50 wherein the index includes joint histogram features.

52. The computer program of claim 51 further comprising:

a computing code segment that causes the computer to compute a joint histogram from the multiple features received,

wherein the searching code segment includes a searching code segment that causes the computer to search the index of joint histogram features to determine if the indexed images include at least one of the computed joint histogram features.

53. The computer program of claim 49 wherein the receiving code segment includes a receiving code segment that causes the computer to receive a feature corresponding to a posterized image characteristic.

54. The computer program of claim 49 wherein:

the receiving code segment causes the computer to receive multiple features corresponding to posterized image characteristics, and

the searching code segment causes the computer to search the index of features to determine if the indexed images include at least one of the multiple features received.

55. The computer program of claim 54 wherein the index includes posterized joint histogram features.

56. The computer program of claim 55 further comprising a computing code segment that causes the computer to compute a posterized joint histogram from the multiple features received, wherein the searching code segment causes the computer to search the index of posterized joint histogram features to determine if the indexed images include at least one of the computed posterized joint histogram features.

29. A computer program stored on a computer readable medium or a propagated signal for performing an image search, the computer program comprising:

a receiving code segment that causes the computer to receive a set of features corresponding to image characteristics;

a comparing code segment that causes the computer to compare the received set of features to features that have been indexed for multiple stored images; and

a producing code segment that causes the computer to produce a search result based on the comparison.

49. A computer program stored on a computer readable medium or a propagated signal for retrieving images and producing a ranked result, the computer program comprising:

a receiving code segment that causes the computer to receive at least one feature corresponding to an image characteristic;

a searching code segment that causes the computer to search an index of features corresponding to indexed images to identify selected indexed images including at least the received feature;

a determining code segment that causes the computer to determine whether to retrieve the selected indexed images based on whether the selected indexed images satisfy at least one similarity metric; and

a retrieving code segment that causes the computer to retrieve the selected indexed images that satisfy the at least one similarity metric to produce a ranked list of images.