US6859802B1 — Image retrieval based on relevance feedback

Claim 1

Independent Claim 375 words

One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors, causes the one or more processors to perform acts including: receiving an initial image selection; generating a plurality of query vectors by extracting, for each query vector, one of a plurality of low-level features from the initial image selection; selecting a set of potentially relevant images based at least in part on distances between the plurality of query vectors and a plurality of feature vectors corresponding to low-level features of a plurality of images; receiving feedback regarding the relevance of one or more images of the set of potentially relevant images; generating a new plurality of query vectors based at least in part on the feedback; generating a weighting of feature elements based at least in part on the feedback; and selecting a new set of potentially relevant images based at least in part on both the weighting of feature elements and distances between the new plurality of query vectors and the plurality of feature vectors, wherein the selecting a new set of potentially relevant images comprises using a matrix in determining the distance between one of the new plurality of query vectors and one of the plurality of feature vectors, and further comprising dynamically selecting the matrix based on both a number of images in the set of potentially relevant images for which relevance feedback was input and a number of feature elements in the one feature vector, wherein the dynamically selecting further comprises: if the number of images in the set of potentially relevant images for which relevance feedback was input is not less than the number of feature elements in the one feature vector, then using one matrix that transforms the query vector and the one feature vector to a higher-level feature space and then using another matrix that assigns a weight to each element of the transformed query vector and the transformed feature vector, and if the number of images in the set of potentially relevant images is less than the number of feature elements in the one feature vector, then using a matrix that assigns a weight to each element of the query vector and the one feature vector.

Claim 2

Dependent Claim 375 words

One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors, causes the one or more processors to perform acts including: receiving an initial image selection; generating a plurality of query vectors by extracting, for each query vector, one of a plurality of low-level features from the initial image selection; selecting a set of potentially relevant images based at least in part on distances between the plurality of query vectors and a plurality of feature vectors corresponding to low-level features of a plurality of images; receiving feedback regarding the relevance of one or more images of the set of potentially relevant images; generating a new plurality of query vectors based at least in part on the feedback; generating a weighting of feature elements based at least in part on the feedback; and selecting a new set of potentially relevant images based at least in part on both the weighting of feature elements and distances between the new plurality of query vectors and the plurality of feature vectors, wherein the selecting a new set of potentially relevant images comprises using a matrix in determining the distance between one of the new plurality of query vectors and one of the plurality of feature vectors, and further comprising dynamically selecting the matrix based on both a number of images in the set of potentially relevant images for which relevance feedback was input and a number of feature elements in the one feature vector, wherein the dynamically selecting further comprises: if the number of images in the set of potentially relevant images for which relevance feedback was input is not less than the number of feature elements in the one feature vector, then using one matrix that transforms the query vector and the one feature vector to a higher-level feature space and then using another matrix that assigns a weight to each element of the transformed query vector and the transformed feature vector, and if the number of images in the set of potentially relevant images is less than the number of feature elements in the one feature vector, then using a matrix that assigns a weight to each element of the query vector and the one feature vector.

Claim 3

Dependent Claim 58 words

One or more computer readable media as recited in claim 1 , wherein the dynamically selecting comprises using a diagonal matrix if the number of images in the set of potentially relevant images for which relevance feedback was input is less than the number of feature elements in the one feature vector, and otherwise using a full matrix.

Claim 4

Dependent Claim 97 words

One or more computer readable media as recited in claim 1 , wherein X represents an image matrix that is generated by stacking N feature vectors, each of length K, corresponding to the set of potentially relevant images for which relevance feedback was received and resulting in an (N×K) matrix, C represents a weighted covariance matrix of X, det(C) represents the matrix determinant of C, and the matrix comprises a full matrix (W*) that is generated as follows: W * = ( det ⁢ ⁢ ( C ) ) 1 K ⁢ ⁢ C - 1 .

Claim 5

Dependent Claim 69 words

One or more computer readable media as recited in claim 1 , wherein w kk represents the kk th element of matrix W, x k represents the k th feature element, σ k , represents the standard deviation of the sequence of x k 's, the matrix comprises a diagonal matrix with each diagonal element (w kk ) being generated as follows: w kk = 1 σ k .

Claim 6

Dependent Claim 294 words

One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or mire processors, causes the one or more processors to perform acts including: receiving an initial image selection; generating a plurality of query vectors by extracting, for each query vector, one of a plurality of low-level features from the initial image selection; selecting a set of potentially relevant images based at least in part on distances between the plurality of query vectors and a plurality of feature vectors corresponding to low-level features of a plurality of images; receiving feedback regarding the relevance of one or more images of the set of potentially relevant images; generating a new plurality of query vectors based at least in part on the feedback wherein N represents the number of images in the set of potentially relevant images for which relevance feedback has been received, or, represents the relevance of image n in the set of images, {right arrow over (π)} T represents a transposition of a vector generated by concatenating the individual π n values, and X represents an image matrix that is generated by stacking N training vectors corresponding to the set of potentially relevant images into a matrix, and wherein each new query vector ({right arrow over (q)}) of the new plurality of query vectors is generated as follows: q → = π → T ⁢ ⁢ X ∑ n = 1 N ⁢ ⁢ π n ; generating a weighting of feature elements based at least in part on the feedback; and selecting a new set of potentially relevant images based at least in part on both the weighting of feature elements and distances between the new plurality of query vectors and the plurality of feature vectors.

Claim 7

Dependent Claim 294 words

One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or mire processors, causes the one or more processors to perform acts including: receiving an initial image selection; generating a plurality of query vectors by extracting, for each query vector, one of a plurality of low-level features from the initial image selection; selecting a set of potentially relevant images based at least in part on distances between the plurality of query vectors and a plurality of feature vectors corresponding to low-level features of a plurality of images; receiving feedback regarding the relevance of one or more images of the set of potentially relevant images; generating a new plurality of query vectors based at least in part on the feedback wherein N represents the number of images in the set of potentially relevant images for which relevance feedback has been received, or, represents the relevance of image n in the set of images, {right arrow over (π)} T represents a transposition of a vector generated by concatenating the individual π n values, and X represents an image matrix that is generated by stacking N training vectors corresponding to the set of potentially relevant images into a matrix, and wherein each new query vector ({right arrow over (q)}) of the new plurality of query vectors is generated as follows: q → = π → T ⁢ ⁢ X ∑ n = 1 N ⁢ ⁢ π n ; generating a weighting of feature elements based at least in part on the feedback; and selecting a new set of potentially relevant images based at least in part on both the weighting of feature elements and distances between the new plurality of query vectors and the plurality of feature vectors.

Claim 8

Dependent Claim 286 words

One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors, causes the one or more processors to perform acts including: receiving an initial image selection; generating a plurality of query vectors by extracting, for each query vector, one of a plurality of low-level features from the initial image selection; selecting a set of potentially relevant images based at least in part on distances between the plurality of query vectors and a plurality of feature vectors corresponding to low-level features of a plurality of images; receiving feedback regarding the relevance of one or more images of the set of potentially relevant images; generating a new plurality of query vectors based at least in part on the feedback; generating a weighting of feature elements based at least in part on the feedback; and selecting a new set of potentially relevant images based at least in part on both the weighting of feature elements and distances between the new plurality of query vectors and the plurality of feature vectors, wherein f i represents a summation, over the images in the set of potentially relevant images, of a product of a relevance of the image and a distance between the query vector and the feature vector, and wherein the selecting a new set of potentially relevant images comprises combining, for each image, a weighted distance between the plurality of query vectors and the plurality of feature vectors, and wherein the weight (u i ) for each of a plurality (I) of distances between a query vector and a corresponding feature vector is calculated as: u i = ∑ j = 1 l ⁢ ⁢ f j f i .

Claim 9

Dependent Claim 286 words

One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors, causes the one or more processors to perform acts including: receiving an initial image selection; generating a plurality of query vectors by extracting, for each query vector, one of a plurality of low-level features from the initial image selection; selecting a set of potentially relevant images based at least in part on distances between the plurality of query vectors and a plurality of feature vectors corresponding to low-level features of a plurality of images; receiving feedback regarding the relevance of one or more images of the set of potentially relevant images; generating a new plurality of query vectors based at least in part on the feedback; generating a weighting of feature elements based at least in part on the feedback; and selecting a new set of potentially relevant images based at least in part on both the weighting of feature elements and distances between the new plurality of query vectors and the plurality of feature vectors, wherein f i represents a summation, over the images in the set of potentially relevant images, of a product of a relevance of the image and a distance between the query vector and the feature vector, and wherein the selecting a new set of potentially relevant images comprises combining, for each image, a weighted distance between the plurality of query vectors and the plurality of feature vectors, and wherein the weight (u i ) for each of a plurality (I) of distances between a query vector and a corresponding feature vector is calculated as: u i = ∑ j = 1 l ⁢ ⁢ f j f i .

Claim 10

Independent Claim 135 words

A method comprising: generating a query vector corresponding to a feature of one image; identifying a feature vector corresponding to the feature of another image; identifying a number of training samples for which relevance feedback has been received; if the number of training samples either equals or exceeds a threshold amount, then determining a distance between the query vector and the feature vector including transforming the query vector and the feature vector to a higher-level feature space and then assigning a weight to each element of the transformed query vector and the transformed feature vector; and if the number of training samples does not exceed the threshold amount, then determining the distance between the query vector and the feature vector including assigning a weight to each element of the query vector and the feature vector.

Claim 11

Independent Claim 135 words

A method comprising: generating a query vector corresponding to a feature of one image; identifying a feature vector corresponding to the feature of another image; identifying a number of training samples for which relevance feedback has been received; if the number of training samples either equals or exceeds a threshold amount, then determining a distance between the query vector and the feature vector including transforming the query vector and the feature vector to a higher-level feature space and then assigning a weight to each element of the transformed query vector and the transformed feature vector; and if the number of training samples does not exceed the threshold amount, then determining the distance between the query vector and the feature vector including assigning a weight to each element of the query vector and the feature vector.

Claim 12

Dependent Claim 33 words

A method as recited in claim 7 , wherein the feature vector includes a plurality of feature elements and wherein the threshold amount comprises the number of feature elements in the feature vector.

Claim 13

Dependent Claim 79 words

A method as recited in claim 7 , wherein if the number of training samples either equals or exceeds the threshold amount, then determining the distance (g), where P is a mapping matrix, {right arrow over (q)} is the query vector, {right arrow over (x)} is the feature vector, and Λ is a weighting matrix, as: g= ( P ( {right arrow over (q)}−{right arrow over (x)})) T Λ( P ( {right arrow over (q)}−{right arrow over (x)} )).

Claim 14

Dependent Claim 69 words

A method as recited in claim 7 , wherein if the number of training samples does not exceed the threshold amount, then determining the distance (g), where {right arrow over (q)} is the query vector, {right arrow over (x)} is the feature vector, and Λ is a weighting matrix, as: g =( {right arrow over (q)}−{right arrow over (x)} ) T Λ( {right arrow over (q)}−{right arrow over (x)}).

Claim 15

Dependent Claim 65 words

A method as recited in claim 7 , further comprising: repeating the generating, identifying of the feature vector, identifying of the number of training samples, and the determining for each of a plurality of features; and identifying how closely the image and the another image match each other by combining the distances between the query vectors and the feature vectors for the plurality of features.

Claim 16

Dependent Claim 40 words

A method as recited in claim 11 , wherein the identifying how closely the image and the another image match each other comprises calculating a weighted summation of each of the individual distances for each of the plurality of features.

Claim 17

Dependent Claim 25 words

One or more computer readable media including a computer program that is executable by a processor to perform the method recited in claim 7 .

Claim 18

Independent Claim 151 words

A system comprising: a query vector generator to generate a query vector corresponding to a feature of one image; a comparator, coupled to the query vector generator, to, identify a feature vector corresponding to the feature of another image, identify a number of training samples for which relevance feedback has been received, if the number of training samples either equals or exceeds a threshold amount, then to determine a distance between the query vector and the feature vector including transforming the query vector and the feature vector to a higher-level feature space and then assigning a weight to each element of the transformed query vector and the transformed feature vector, and if the number of training samples does not exceed the threshold amount, then to determine the distance between the query vector and the feature vector including assigning a weight to each element of the query vector and the feature vector.

Claim 19

Independent Claim 151 words

A system comprising: a query vector generator to generate a query vector corresponding to a feature of one image; a comparator, coupled to the query vector generator, to, identify a feature vector corresponding to the feature of another image, identify a number of training samples for which relevance feedback has been received, if the number of training samples either equals or exceeds a threshold amount, then to determine a distance between the query vector and the feature vector including transforming the query vector and the feature vector to a higher-level feature space and then assigning a weight to each element of the transformed query vector and the transformed feature vector, and if the number of training samples does not exceed the threshold amount, then to determine the distance between the query vector and the feature vector including assigning a weight to each element of the query vector and the feature vector.

Claim 20

Independent Claim 136 words

A method comprising: for one of a plurality of images and each of a plurality of features, generating, based on a set of search criteria, a query vector for the feature, identifying a feature vector, corresponding to the image, for the feature, wherein identifying the feature vector includes: identifying a low-level feature vector corresponding to the feature; and mapping the low-level feature vector to a higher level feature space; determining how closely the feature vector matches the query vector: and determining how closely the image matches the set of search criteria based on how closely, for the plurality of features, the feature vectors match the query vectors, wherein generating the query vector comprises generating the query vector based at least in part on user relevance feedback regarding how relevant images previously displayed to a user were.

Claim 21

Independent Claim 136 words

A method comprising: for one of a plurality of images and each of a plurality of features, generating, based on a set of search criteria, a query vector for the feature, identifying a feature vector, corresponding to the image, for the feature, wherein identifying the feature vector includes: identifying a low-level feature vector corresponding to the feature; and mapping the low-level feature vector to a higher level feature space; determining how closely the feature vector matches the query vector: and determining how closely the image matches the set of search criteria based on how closely, for the plurality of features, the feature vectors match the query vectors, wherein generating the query vector comprises generating the query vector based at least in part on user relevance feedback regarding how relevant images previously displayed to a user were.

Claim 22

Dependent Claim 22 words

A method as recited in claim 15 , wherein the identifying the feature vector further comprises incorporating, into the mapping, relevance feedback.

Claim 23

Independent Claim 145 words

A method of generating a query vector to compare to a feature vector of another image, the method comprising: receiving feedback regarding the relevance of each image of a set of images; wherein N represents the number of images in the set of images for which user relevance feedback has been received, ζ n represents the relevance of image n in the set of images, {right arrow over (π)} T represents a transposition of a vector generated by concatenating the individual π n values, and X represents an image matrix that is generated by stacking N training vectors corresponding to the set of images into a matrix; and generating a query vector ({right arrow over (q)}) corresponding to one of a plurality of features as follows: q → = π → T ⁢ ⁢ X ∑ n = 1 N ⁢ ⁢ π n .

Claim 24

Independent Claim 145 words

A method of generating a query vector to compare to a feature vector of another image, the method comprising: receiving feedback regarding the relevance of each image of a set of images; wherein N represents the number of images in the set of images for which user relevance feedback has been received, ζ n represents the relevance of image n in the set of images, {right arrow over (π)} T represents a transposition of a vector generated by concatenating the individual π n values, and X represents an image matrix that is generated by stacking N training vectors corresponding to the set of images into a matrix; and generating a query vector ({right arrow over (q)}) corresponding to one of a plurality of features as follows: q → = π → T ⁢ ⁢ X ∑ n = 1 N ⁢ ⁢ π n .

Claim 25

Dependent Claim 25 words

One or more computer readable media including a computer program that is executable by a processor to perform the method recited in claim 17 .

Claim 26

Independent Claim 128 words

A method of generating a weight to apply to distances between query vectors and feature vectors when combining the distances, the method comprising: receiving feedback regarding the relevance of each image of a set of images; wherein f i represents a summation, over the images in the set of images, of a product of a relevance of the image and a distance between the query vector and the feature vector; and generating a weight (u i ) for each of a plurality (I) of distances between a query vector corresponding to one of a plurality (I) of features and a feature vector corresponding to the one of the plurality (I) of features as: u i = ∑ j = 1 l ⁢ ⁢ f j f i .

Claim 27

Independent Claim 128 words

A method of generating a weight to apply to distances between query vectors and feature vectors when combining the distances, the method comprising: receiving feedback regarding the relevance of each image of a set of images; wherein f i represents a summation, over the images in the set of images, of a product of a relevance of the image and a distance between the query vector and the feature vector; and generating a weight (u i ) for each of a plurality (I) of distances between a query vector corresponding to one of a plurality (I) of features and a feature vector corresponding to the one of the plurality (I) of features as: u i = ∑ j = 1 l ⁢ ⁢ f j f i .

Claim 28

Dependent Claim 25 words

One or more computer readable media including a computer program that is executable by a processor to perform the method recited in claim 19 .

Claim 29

Dependent Claim 168 words

One or more computer readable media including a computer program that is executable by a processor to cause the processor to perform acts of: receiving user feedback regarding the relevance of each image of a set of images, the user feedback forming a range including at least Highly Relevant, Relevant, No Opinion, Irrelevant, and Highly Irrelevant; wherein N represents the number of images in the set of images for which user feedback has been received, π n represents the relevance of image n in the set of images, {right arrow over (π)} T represents a transposition of a vector generated by concatenating the individual π n values, and X represents an image matrix that is generated by stacking N training vectors corresponding to the set of images into a matrix; and generating a query vector ({right arrow over (q)}) corresponding to one of a plurality of features as follows: q → = π → T ⁢ ⁢ X ∑ n = 1 N ⁢ ⁢ π n .

Claim 30

Dependent Claim 168 words

One or more computer readable media including a computer program that is executable by a processor to cause the processor to perform acts of: receiving user feedback regarding the relevance of each image of a set of images, the user feedback forming a range including at least Highly Relevant, Relevant, No Opinion, Irrelevant, and Highly Irrelevant; wherein N represents the number of images in the set of images for which user feedback has been received, π n represents the relevance of image n in the set of images, {right arrow over (π)} T represents a transposition of a vector generated by concatenating the individual π n values, and X represents an image matrix that is generated by stacking N training vectors corresponding to the set of images into a matrix; and generating a query vector ({right arrow over (q)}) corresponding to one of a plurality of features as follows: q → = π → T ⁢ ⁢ X ∑ n = 1 N ⁢ ⁢ π n .

Claim 31

Dependent Claim 24 words

One or more computer readable media as recited in claim 21 , wherein the receiving user feedback comprises receiving user feedback via speech recognition.

Claim 32

Dependent Claim 259 words

One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors, causes the one or more processors to: select a set of potentially relevant images based at least in part on distances between a plurality of query vectors extracted from an initial image selection and a plurality of feature vectors corresponding to low-level features of a plurality of images; receive feedback regarding the relevance of one or more images of the set of potentially relevant images; generate a new plurality of query vectors based at least in part on the feedback; generate a weighting of feature elements based at least in part on the feedback; and select a new set of potentially relevant images based at least in part on both the weighting of feature elements and distances between the new plurality of query vectors and the plurality of feature vectors, wherein fi represents a summation, over the images in the set of potentially relevant images, of a product of a relevance of the image and a distance between the query vector and the feature vector, and wherein the selecting a new set of potentially relevant images comprises combining, for each image, a weighted distance between the plurality of query vectors and the plurality of feature vectors, and wherein the weight (u i ) for each of a plurality (I) of distances between a query vector and a corresponding feature vector is calculated as: u i = ∑ j = 1 l ⁢ ⁢ f j f i .

Claim 33

Dependent Claim 259 words

One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors, causes the one or more processors to: select a set of potentially relevant images based at least in part on distances between a plurality of query vectors extracted from an initial image selection and a plurality of feature vectors corresponding to low-level features of a plurality of images; receive feedback regarding the relevance of one or more images of the set of potentially relevant images; generate a new plurality of query vectors based at least in part on the feedback; generate a weighting of feature elements based at least in part on the feedback; and select a new set of potentially relevant images based at least in part on both the weighting of feature elements and distances between the new plurality of query vectors and the plurality of feature vectors, wherein fi represents a summation, over the images in the set of potentially relevant images, of a product of a relevance of the image and a distance between the query vector and the feature vector, and wherein the selecting a new set of potentially relevant images comprises combining, for each image, a weighted distance between the plurality of query vectors and the plurality of feature vectors, and wherein the weight (u i ) for each of a plurality (I) of distances between a query vector and a corresponding feature vector is calculated as: u i = ∑ j = 1 l ⁢ ⁢ f j f i .

Claim 34

Dependent Claim 164 words

One or more computer readable media as recited in claim 23 , wherein the plurality of instructions to cause the one or more processors to select comprises instructions to cause the one or more processors to use a matrix in determining the distance between one of the new plurality of query vectors and one of the plurality of feature vectors, and further comprises instructions to cause the one or more processors to dynamically select the matrix based on both a number of images in the set of potentially relevant images for which relevance feedback was input and a number of feature elements in the one feature vector, wherein the instructions to dynamically select comprise instructions to cause the one or more processors to use a diagonal matrix when the number of images in the set of potentially relevant images for which relevance feedback was input is less than a number of feature elements in the one feature vector, and otherwise using a fill matrix.

Claim 35

Dependent Claim 153 words

One or more computer readable media as recited in claim 23 , wherein the plurality of instructions to cause the one or more processors to select comprises instructions to cause the one or more processors to: use one matrix that transforms the query vector and the one feature vector to a higher-level feature space and then using another matrix that assigns a weight to each element of the transformed query vector and the transformed feature vector when the number of images in the set of potentially relevant images for which relevance feedback was input is not less than the number of feature elements in the one feature vector; and use a matrix that assigns a weight to each element of the query vector and the one feature vector when the number of images in the set of potentially relevant images is less than the number of feature elements in the one feature vector.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2008-02-22	2008-08-23	2009-02-22	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2012-02-22	2012-08-23	2013-02-22	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2016-02-22	2016-08-23	2017-02-22	$7700.00	Window Closed / Lapsed

Image retrieval based on relevance feedback

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag