Representation and retrieval of images using context vectors derived from image information elements

• US 6,173,275 B1
• Filed: 09/17/1997
• Issued: 01/09/2001
• Est. Priority Date: 09/20/1993
• Status: Expired due to Term

• Current Assignee: Fair Isaac Corporation
• Original Assignee: HNC Software Inc. (Fair Isaac Corporation)
• Inventors: Caid, William R., Hecht-Neilsen, Robert
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Rhodes, Jason W.
• Application Number:
  US08/931,927
• Time in Patent Office: 1,210 Days
• Field of Search: 706/14, 706/12, 706/18, 706/934, 382/253, 382/190, 382/195, 382/205, 382/224, 382/225, 382/251
• US Class Current: 706/14
• 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
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: Y10S 706/934 Information retrieval or Information management

Abstract

Image features are generated by performing wavelet transformations at sample points on images stored in electronic form. Multiple wavelet transformations at a point are combined to form an image feature vector. A prototypical set of feature vectors, or atoms, is derived from the set of feature vectors to form an “atomic vocabulary.” The prototypical feature vectors are derived using a vector quantization method (e.g., using neural network self-organization techniques) in which a vector quantization network is also generated. The atomic vocabulary is used to define new images. Meaning is established between atoms in the atomic vocabulary. High-dimensional context vectors are assigned to each atom. The context vectors are then trained as a function of the proximity and co-occurrence of each atom to other atoms in the image. After training, the context vectors associated with the atoms that comprise an image are combined to form a summary vector for the image. Images are retrieved using a number of query methods (e.g., images, image portions, vocabulary atoms, index terms). The user'"'"'s query is converted into a query context vector. A dot product is calculated between the query vector and the summary vectors to locate images having the closest meaning. The invention is also applicable to video or temporally related images, and can also be used in conjunction with other context vector data domains such as text or audio, thereby linking images to such data domains.

Claims

1. In a computer having a processor and a storage, said storage storing a plurality of images in computer-readable form, a computer-implemented process for generating a set of prototypical feature vectors for representing the images, the process comprising:

generating for each of a plurality of images, a plurality of continuous feature vectors from pixel data of the image;

deriving from the continuous feature vectors a plurality of prototypical feature vectors, the prototypical feature vectors providing a vocabulary of image features for representing the images;

associating each image with a plurality of prototypical feature vectors;

associating each prototypical feature vector with an initial context vector;

for each image, and for each prototypical feature vector associated with the image, modifying the context vector associated with the prototypical feature vector to be more similar to the context vectors associated with other prototypical feature vectors associated with the image; and

storing the modified context vectors, wherein the modified context vectors enable retrieval of selected images with feature vectors similar to feature vectors of a query image by comparison of a context vector associated with the feature vectors derived from the query image to the context vectors associated with the plurality of images.

2. The computer-implemented process of claim 1 wherein associating each image with a plurality of prototypical feature vectors comprises:

for each image, mapping each continuous feature vector of the image to a closest prototypical feature vector, to represent the image with a plurality of the prototypical feature vectors.

3. The computer-implemented process of claim 1 further comprising:

receiving a new image in computer-readable form;

generating a new feature vector at each of a plurality of sample points in the new image;

mapping each new feature vector of the new image to the closest prototypical feature vector; and

representing the new image using the prototypical feature vectors corresponding to the mapped new feature vectors.

4. The method of claim 1, wherein generating for each of a plurality of images, a plurality of continuous feature vectors, comprises:

for each image, generating a wavelet at each of a plurality of sample points in the image.

5. The method of claim 4, wherein the wavelets are Gabor wavelets.

6. The method of claim 4, wherein each feature vector comprises between 60 and 1000 wavelets for each sample point.

7. The method of claim 4, wherein the sample points are form a grid of points on an image.

8. The method of claim 4, wherein the sample points are non-uniformly distributed on the image.

9. The method of claim 1, wherein deriving from the continuous feature vectors a plurality of prototypical feature vectors includes deriving scaled or rotated versions of selected prototypical feature vectors.

10. In a computer having a processor and storage, said storage comprising a plurality of images in computer-readable form and a set of information elements used to represent the images, a computer-implemented process for generating a set of context vectors that represent relationships among the information elements, the process comprising the steps of:

associating each image with quantized information elements derived from wavelet transformations on the pixel data of the image, the quantized information elements providing a vocabulary of image features for representing the images;

for each image, associating a context vector with each information element associated with the image;

for each information element associated with each image, modifying the context vector associated with the information element to be more similar to the context vectors associated other information elements occurring in the image; and

storing the modified context vectors, wherein the modified context vectors enable retrieval of selected images with information elements similar to information elements of a query image by comparison of a context vector derived from the information elements of the query image to the context vectors associated with the plurality of images.

11. The computer-implemented process of claim 10, wherein the information elements are feature vectors that represent the image features produced by the wavelet transformations of the images in the storage.

12. The computer-implemented process of claim 10, wherein the context vector associated with each information element is modified as a function of the temporal relationship of the information element in the image to other information elements in other images.

13. The computer-implemented process of claim 10, further comprising:

generating a summary vector associated with each image by superposition of context vectors associated with the information elements that represent the image.

14. The computer-implemented process of claim 13 further comprising:

associating one or more index terms with selected images.

15. The computer-implemented process of claim 14, further comprising for additionally automatically indexing new images, the steps of:

receiving a new image in computer-readable form having an associated summary vector;

determining a similarity between the new image and at least one existing image as a function of the summary vector associated with the new image and the summary vectors associated with the existing images; and

associating one or more index terms with the new image as a function of the similarity of the new image to the existing images, and the index terms of the existing images.

16. The computer implemented process of claim 14, for additionally automatically indexing new images, further comprising:

receiving a new image having an associated summary vector;

selecting from the plurality of existing images, at least one existing image similar to the new image according to a similarity of the summary vector of the new image to the summary vector of the existing image; and

associating the new image with one or more index terms of the selected at least one existing image.

17. The computer-implemented process of claim 10, further comprising:

for each image;

retrieving the information elements, and associated context vectors, that represent the image;

weighting each modified context vector as a function of the frequency of occurrence of the associated information element in the plurality of images;

generating a summary vector associated with each image as a function of the weighted context vectors associated with the information elements that represent the image;

normalizing the summary context vector; and

storing the summary context vector in the computer storage.

18. The computer-implemented process of claim 17 further comprising, after retrieving the information elements:

eliminating selected information elements, and associated modified context vectors for the image that corresponds to information elements on a stop-list of information elements.

19. The computer implemented process of claim 10, wherein associating a context vector with each information element comprises:

associating the information element with a context vector comprising a majority of randomly generated components.

20. In a computer having a processor and storage, said storage comprising a plurality of images, a computer-implemented process of selecting images, the process comprising:

storing a plurality of feature vectors derived from the pixel data of the images, each feature vector representing local image features about a selected portion of an image and associated with a context vector;

storing each image in association with a summary vector, the summary vector generated as a function of a plurality of context vectors, each context vector associated with one of the feature vectors assigned to the image;

receiving a query image;

generating query feature vectors from the pixel data of the query image;

generating a query context vector from context vectors associated with the query feature vectors;

comparing the query context vector with the summary vectors associated with a plurality of images in the storage;

an

selecting images having a summary vector similar to the query context vector.

21. The computer-implemented process of claim 20, wherein generating query feature vectors comprises:

generating a query feature vector at each of a plurality of sample points on the query image;

mapping each query feature vector to one of a plurality of prototypical feature vectors which form a vocabulary of image features for representing the images; and

wherein generating a query context vector further comprises;

forming a query context vector from context vectors associated with the prototypical feature vectors corresponding to each mapped query feature vector.

22. The computer-implemented process of claim 21, wherein generating a query feature vector comprises:

computing a wavelet transformation at each of the plurality of sample points in the query image; and

generating a query feature vector at each of the plurality of sample points as a function of the wavelet transformation at the sample point.

23. The computer-implemented process of claim 20 wherein the query is an image information element.

24. The computer-implemented process of claim 20 further comprising:

receiving a text query;

generating a query context vector derived from a context vector for at least one word included in the query; and

retrieving at least one image having a summary vector similar to the query context vector.

25. The computer-implemented process of claim 20, wherein:

comparing the query context vector comprises;

computing a dot product between the query context vector and the summary vector of each of a plurality of images in the storage, and

selecting images comprises;

selecting images having a high dot product with the query context vector.

26. The computer-implemented process of claim 20 further comprising:

partitioning a selected image into a plurality of blocks;

generating a block context vector associated with each block;

comparing the query context vector with each block context vector; and

displaying the blocks in the selected image as a function of the block comparing step.

27. The method of claim 20, further comprising:

generating the feature vectors by applying a wavelet transformation to each image at each of a plurality of sample points in the image.

28. In a computer-implemented system comprising a plurality of images, each image comprising pixel data, a system for generating a set of context vectors that represent relationships between image features, the system comprising:

a computer processor for executing programmed instructions and for storing and retrieving data;

a program memory, coupled to the processor, for storing program instructions for execution by the processor;

an image database, coupled to the processor, for receiving, storing, and sending a plurality of images, each image comprising a plurality of feature vectors, and each feature vector associated with a context vector and derived from the pixel data of the image and representing image features about a selected pixel of the image;

an iterative training component, executable by the processor in accordance with program instructions in the program memory, for modifying the context vector associated with each feature vector to be more similar to the context vectors associated with other feature vectors that comprise the image; and

storage means, coupled to the processor, for storing the modified context vectors in the image database.

29. The system of claim 28 further comprising:

a summary vector generation component, executable by the processor in accordance with program instructions in the program memory, for generating a summary vector associated with each image as a function of the modified context vectors associated with the feature vectors that comprise each image.

30. The system of claim 28, further comprising:

a feature vector generator component, executable by the processor in accordance with program instructions in the program memory, for generating the feature vectors by applying a wavelet transformation to each image at each of a plurality of sample points in the image.

31. A computer-implemented system for selecting images from an image database comprising a plurality of images stored in electronic form, each image comprising pixel data and having an associated summary vector, the system comprising:

a computer processor for executing programmed instructions and for storing and retrieving data;

an input device, coupled to the processor, for receiving a query;

a program memory, coupled the processor, for storing program instructions for execution by the processor;

a summary vector generator, executable by the processor in accordance with program instructions in the program memory, for generating for each image a summary vector as a function of a plurality of context vectors, each context vector associated with image features derived from the pixel data of a selected portion of the image, and for storing the image in association with its summary vector in the image database;

a query context vector generator executable by the processor in accordance with program instructions in the program memory for generating a query context vector as a function of a received query;

a retrieval component, execuable by the processor in accordance with program instructions in the program memory, for retrieving images from the image database as a function of a similarity between the generated query context vector and each summary vector associated with each image in the plurality of images; and

a display unit, coupled to the processor, for displaying retrieved images.

32. The system of claim 31, further comprising:

a feature vector generator component, executable by the processor in accordance with program instructions in the program memory, for generating the feature vectors by applying a wavelet transformation to the pixel data of each image at each of a plurality of sample points in the image, each feature vector representing an image feature.

33. In a computer having a processor and a storage, said storage storing a plurality of images in computer-readable form, a computer-implemented process for generating a set of prototypical feature vectors for representing the images, and for organizing the feature vectors for representing similarity between images, the method comprising:

generating from pixel data of the images a plurality of continuous feature vectors representing local image features;

deriving from the continuous feature vectors a plurality of prototypical feature vectors, the prototypical feature vectors providing a vocabulary of image features;

associating each prototypical feature vector with a context vector;

for each image having a plurality of continuous feature vectors, associating each continuous feature vector of the image with a closest prototypical feature vector, so that each image is represented by a plurality of prototypical feature vectors;

for each prototypical feature vector being a target feature vector in an image, modifying the context vector associated with the target feature vector to be similar to the context vectors associated with non-target feature vectors co-occurring in the image with the target feature vector; and

storing the prototypical feature vectors in association with their modified context vectors, to enable retrieval of an image in response to feature vectors or context vectors.

34. The computer implemented process of claim 33, further comprising:

modifying the context vector of the target feature vector as a function of a spatial relationship of the target feature vectors to the non-target feature vectors in the image.

35. The computer implemented process of claim 33, further comprising:

modifying the context vector of the target feature vector as a function of a spatio-temporal relationship of the target feature vectors to the non-target feature vectors occurring in other, temporally related images.

36. The computer implemented process of claim 33, further comprising:

modifying the context vector of the target feature vector as a function of a frequency of occurrence of target feature vector in the plurality of images.

37. The computer implemented process of claim 33, further comprising:

generating for each image a summary vector associated with the image by superimposition of the modified context vectors associated with the prototypical feature vectors that represent the image.

38. The computer implemented process of claim 33, wherein associating each prototypical feature vector with a context vector comprises:

associating each prototypical feature vector with a context vector comprising a majority of randomly generated components.

39. The computer implemented process of claim 33, wherein a context vector is modified according to the formula:

${\mathrm{CV}}_{\mathrm{target}}^{\mathrm{new}}={\mathrm{CV}}_{\mathrm{target}}^{\mathrm{old}}+\underset{i\ne <br><br>\mathrm{target}}{\sum <br><br>}<br><br>\frac{1}{f_i}<br><br>G<br><br>\left(<br><br>{\mathrm{CV}}_{\mathrm{target}}^{\mathrm{old}}-{\mathrm{CV}}_i<br><br>\right)·<br><br>{\mathrm{CV}}_i$

where;

${\mathrm{CV}}_{t<br><br>\text{\hspace{1em}<br><br>}<br><br>\arg <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{et}}^{\mathrm{old}}$

 

is the context vector of the target feature vector before modification;

${\mathrm{CV}}_{\mathrm{target}}^{\mathrm{new}}$

 

is the context vector of the target feature vector following modification;

CV_i is a context vector of a non-target feature vector i;

ƒ

_i is a frequency of occurrence of non-target feature vector i in at least one image; and

G( ) is a weighting function.

40. The computer implemented process of claim 39, wherein:

G( ) is a Gaussian weighting function equal in the unit co-variance case to;

41. The method of claim 33, wherein generating from the pixel data of the image a plurality of continuous feature vector further comprises:

generating the continuous feature vectors by applying a wavelet transformation to each image at each of a plurality of sample points in the image.

42. The method of claim 41, wherein the wavelet transformation uses Gabor wavelets.

43. The method of claim 33, wherein deriving from the continuous feature vectors a plurality of prototypical feature vectors includes deriving scaled or rotated versions of selected prototypical feature vectors.

49. The computer program product of claim 41, wherein the feature vector generator generates the feature vectors by applying a wavelet transformation to each image at each of a plurality of sample points in the image.

44. A computer program product, for use with a processor and an image database including a plurality of images in computer readable form, the computer program product executable by the processor for configuring and controlling the processor to generate and organize a set of prototypical feature vectors associated for representing similarity between two or more images, by performing the steps of:

generating for each of the images a plurality of continuous feature vectors from pixel data of the images;

deriving from the continuous feature vectors a plurality of prototypical feature vectors, the prototypical feature vectors providing a vocabulary of image features for representing the images;

associating each prototypical feature vector with a context vector;

for each image, associating each continuous feature vector of the image with a closest prototypical feature vector, each image represented by a plurality of prototypical feature vectors;

for each prototypical feature vector being a target feature vector in an image, modifying the context vector associated with the target feature vector as a function of the context vectors associated with non-target feature vectors co-occurring in the image with the target feature vector; and

storing the prototypical feature vectors in association with their modified context vectors to enable retrieval of an image from the image database in response to feature vectors or context vectors.

45. The computer program product of claim 44, wherein the product controls the processor to further perform the step of deriving scaled or rotated versions of selected prototypical feature vectors.

46. The computer program product of claim 44, wherein each feature vector is derived from a selected portion of an image and centered on a pixel in the selected image portion.

47. A computer program product, for use in a computer system comprising a processor and an image database storing a plurality of images in computer readable form, each image comprising a plurality of information elements and having pixel data, and for organizing a set of context vectors that represent relationships between the information elements, the computer program product comprising:

a feature vector generator executable by the processor for generating from the pixel data of each image a plurality of feature vectors for each image, each feature vector comprising a plurality of wavelets;

a context vector generator, executable by the processor, for associating a context vector with each feature vector;

an iterative training component, executable by the processor, for modifying the context vector associated with each feature vector in an image as a function of the context vectors associated with feature vectors co-occuring in the image, and

storage means, coupled to the processor, for storing the modified context vectors in the image database in association with the images.

48. The computer program product of claim 47 further comprising:

a summary vector generation component, executable by the processor, for generating a summary vector associated with each image by superposition of the modified context vectors associated with the feature vectors that comprise each image.

50. The computer program product of claim 47, wherein the feature vector generator generates scaled or rotated versions of selected prototypical feature vectors.

51. The computer program product of claim 47, wherein the feature vector generator generates each feature vector by applying a wavelet transformation to a selected portion of an image centered on a pixel in the selected image portion.

52. A computer program product, for use in a computer system comprising a processor and an image database storing a plurality of images in computer readable form, each image comprising a plurality of information elements and having pixel data, and for selecting images from the image database, the computer program product storing:

a summary vector generator, executable by the processor, for generating for each image a summary vector as a function of a plurality of context vectors, each context vector associated with images features derived from the pixel data of a selected portion of the image, and for storing the image in association with its summary vector in the image database;

a query context vector generator, executable by the processor, for generating a query context vector as a function of image features derived from pixel data of selected portions of a received query image; and

a retrieval component, executable by the processor, for determining a similarity between the query context vector and the summary vectors associated with images in the image database.

53. A computer implemented method of creating a set of feature vectors and context vectors for representing stored images, each image comprising pixel data, the method comprising:

generating for each image, a plurality of feature vectors, each feature vector derived from the the pixel data of a selected portion of the image, each feature vector comprising a plurality of wavelet correlation values;

deriving from the feature vectors a set of prototypical feature vectors, the prototypical feature vectors providing a vocabulary of image features;

for each image, associating each feature vector of the image with a prototypical feature vector;

for each image, associating each prototypical feature vector with a context vector;

for each image, modifying each context vector associated with a prototypical feature vector of the image to be more similar to the context vectors associated with prototypical feature vectors co-occurring in the image; and

storing the modified context vectors in association with the stored images.

54. The method of claim 53, further comprising:

receiving a new image;

generating for the new image a plurality of feature vectors, each feature vector associated with a selected pixel in the image;

assigning to each feature vector of the new image the modified context vector of the prototypical feature vector most similar to the feature vector of the new image.

55. The method of claim 53, further comprising:

receiving a query image;

generating for the query image a plurality of feature vectors, each feature vector associated with a selected pixel in the image;

assigning to each feature vector of the query image the modified context vector of the prototypical feature vector most similar to the feature vector of the new image; and

retrieving from the plurality of images those images having context vectors similar to the context vectors assigned to the query image.

56. The method of claim 53, wherein each feature vector is centered on a pixel in a selected image portion.

57. The method of claim 53, wherein deriving from the continuous feature vectors a plurality of prototypical feature vectors includes deriving scaled or rotated versions of selected prototypical feature vectors.

58. A computer implemented method of creating a set of feature vectors and context vectors for representing images, each image comprising pixel data, the method comprising:

for each image, generating a plurality of feature vectors, each feature vector derived from a selected portion of the pixel data of the image, each feature vector comprising a plurality of wavelet correlation a values;

deriving from the feature vectors a plurality of prototypical feature vectors, the prototypical feature vectors providing a vocabulary of image features;

associating each prototypical feature vector with a high dimensional context vector;

for each image, mapping each feature vector of the image to a prototypical feature vector;

for each image, modifying the context vectors associated with the prototypical feature vectors co-occurring in the image to be more similar to each other; and

storing the modified context vectors in association with the prototypical feature vectors.

59. The method of claim 58, wherein deriving from the feature vectors a plurality of prototypical feature vectors comprises deriving scaled or rotated versions of selected prototypical feature vectors.

60. A method of generating context vectors and feature vectors for representing images, the method comprising:

providing a dictionary comprising a plurality of feature vectors, each feature vector comprising a plurality of wavelet correlation values derived from wavelet transformations on the pixel data of at least one image;

associating a context vector to each feature vector;

selecting a context vector to be modified;

modifying the selected context vector to be more similar to the context vectors assigned to feature vectors which co-occur in at least one image with the feature vector associated with the selected context vector; and

storing the modified context vector in association with at least one image.

61. A computer implemented method of representing an image, the method comprising:

storing a dictionary comprising a plurality of prototypical feature vectors, each prototypical feature vector including a plurality of wavelet correlation values, and associated with a context vector or and providing a localized image feature;

receiving an image;

generating for each of a plurality of selected points in the image a continuous feature vector by applying a wavelet transformation to each selected point;

mapping each of the continuous feature vectors of the image to one of the prototypical feature vectors in the dictionary; and

storing the prototypical feature vectors and their respective context vectors in association with the image, to enable retrieval of the image in response to at least one context vector or at least one feature vector.

62. The method of claim 61, further comprising:

associating the image with a summary vector derived from the context vectors associated with the mapped prototypical feature vectors.

63. The method of claim 61, further comprising:

receiving a query context vector; and

retrieving at least one image having a summary vector similar to the query context vector.

64. A computer implemented method of retrieving from an image database having a plurality of images, an image similar to a query image, the method comprising:

storing a dictionary including a plurality of prototypical feature vectors, each feature vector including a plurality of wavelet correlation values, and associated with a context vector;

receiving a query image;

for each of a plurality of sample points in the query image, generating a continuous feature vector by applying a wavelet transformation at the sample point;

mapping each of the continuous feature vectors of the query image to one of the prototypical features vectors in the dictionary;

obtaining the context vectors associated with the mapped prototypical feature vectors; and

retrieving from the image database at least one image having a context vector similar to the context vectors associated with the query image.