US5819288A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Statistically based image group descriptor particularly suited for use in an image classification and retrieval system
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1996-10-16
•
Granted: 1998-10-06
•
Expires: 2016-10-16
Abstract
Abstract Apparatus and an accompanying method for generating a semantically based, linguistically searchable, numeric descriptor of a pre-defined group of input images and which is particularly useful in a system for automatically classifying individual images, on a numerical basis, in, e.g., an image database, and, through a query-by-example paradigm, retrieving a desired image(s) therefrom. Specifically, a signature is computed for each image in a set using multi-level iterative convolution filtering, with pixel values supplied as input to each filtering level being separately convolved with each one of a set of predefined Gaussian kernels. Average and variance vectors, as collective numeric descriptors of all the images in the set, are separately computed across corresponding elements in all the image signatures for the set. A linguistic term, semantically descriptive of all the images in the set, is associated with the numeric descriptors of this set and, with this set, is stored in a database. For image retrieval, the descriptor for any set is accessed by a textual search through the database using the appropriate linguistic term. The descriptor is then compared against accessed signatures for other images in the database in order to retrieve a image, among those stored in the database, that is the most similar to those in the set associated with the descriptor.
Inventors
- 👤 Jeremy S. De Bonet
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 14:27
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/50; G06F16/58; G06F16/583; G06F16/5838; G06V; G06V10/00; G06V10/20; G06V10/36; G06V10/40; G06V10/56; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99941; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
221 words
Apparatus for generating a semantically based, linguistically searchable, numeric descriptor of a pre-defined group of input images, the apparatus comprising: a database having image information stored therein; a signature generator, responsive to each one of a set of input images, for producing a corresponding signature for each one of said images so as to form a plurality of signatures, each of the signatures having a plurality of elements and storing, in a corresponding one of the elements, a numeric value of each one of a plurality of different pre-defined visual characteristics of a corresponding one of the input images; a statistics generator, responsive to all of said signatures, for generating a value of a variance and a value of an average of each corresponding element taken across all the signatures and storing the variance and average values in a corresponding element in average and variance vectors, respectively, so as to define a statistical measure, wherein said statistical measure describes, with respect to the pre-defined characteristics, all the images taken collectively; and a database manager for associating a linguistic term, to identify said set of images, with said statistical measure, and for storing said measure and said term collectively in the database in such a manner that a textual search through the database and on the term will return said statistical measure.
Claim 2
Dependent Claim
221 words
Apparatus for generating a semantically based, linguistically searchable, numeric descriptor of a pre-defined group of input images, the apparatus comprising: a database having image information stored therein; a signature generator, responsive to each one of a set of input images, for producing a corresponding signature for each one of said images so as to form a plurality of signatures, each of the signatures having a plurality of elements and storing, in a corresponding one of the elements, a numeric value of each one of a plurality of different pre-defined visual characteristics of a corresponding one of the input images; a statistics generator, responsive to all of said signatures, for generating a value of a variance and a value of an average of each corresponding element taken across all the signatures and storing the variance and average values in a corresponding element in average and variance vectors, respectively, so as to define a statistical measure, wherein said statistical measure describes, with respect to the pre-defined characteristics, all the images taken collectively; and a database manager for associating a linguistic term, to identify said set of images, with said statistical measure, and for storing said measure and said term collectively in the database in such a manner that a textual search through the database and on the term will return said statistical measure.
Claim 3
Dependent Claim
200 words
The apparatus in claim 1 wherein said signature generator comprises: a plurality of three successive convolution filters, responsive to the input image, for producing through iterative convolution a final response image for each one of said pre-defined characteristics so as to yield a plurality of final response images, wherein each of said three convolution filters comprises: a convolver for separately convolving pixel values for each incoming image with each one of a plurality of predefined kernels to yield a corresponding one of a plurality of convolved images, said each incoming image for a first one of said filters being the input image, and for each subsequent filter being a different corresponding filter input image related to each separate convolved image produced by an immediately preceding one of said convolution filters; and a sum and normalizer for separately summing all pixel values in each one of the final response images produced by a last one of the convolution filters to yield a resultant sum and for normalizing the resultant sum by a total number of pixels in the final response image produced by the last filter so as to yield a value of a different corresponding one of the pre-defined characteristics.
Claim 4
Dependent Claim
76 words
The apparatus in claim 2 wherein the plurality of convolution filters further comprises connected, first, second and third convolution filters, arranged in succession, for iteratively convolving pixel values in the input image, wherein the first, second and third filters separately convolves the pixel values in the incoming image correspondingly applied to the first, second and third filters with each one of a plurality of individual kernels in first, second and third sets of predefined kernels, respectively.
Claim 5
Dependent Claim
16 words
The apparatus in claim 3 wherein the first, second and third sets of kernels are identical.
Claim 6
Dependent Claim
67 words
The apparatus in claim 4 wherein each of the convolvers further comprises serially connected horizontal and vertical down-sizing convolvers for convolving the incoming image applied thereto with first and second half-level kernels, respectively, to yield corresponding ones of the convolved images; each one of said individual kernels being a derivative of a Gaussian kernel and separable into a corresponding pair of said first and second half-level kernels.
Claim 7
Dependent Claim
84 words
The apparatus in claim 5 wherein each of the convolution filters further comprises a squarer, responsive to each of the convolved images produced in said each filter, for squaring a magnitude of each pixel value in said each image and produced by the convolver in said each filter so as to yield, as output of said each filter, a corresponding one of a plurality of filter response images, wherein the filter response images produced by the last convolution filter are the final response images.
Claim 8
Dependent Claim
25 words
The apparatus in claim 4 wherein the signature comprises a different corresponding sub-vector for image characteristic values for each color axis in the input image.
Claim 9
Dependent Claim
55 words
The apparatus in claim 1 further comprising pointers stored within the database and along with said measure, wherein each of the pointers specifies a corresponding location in the database at which each one of the images in the set is stored such that said textual search will return said pointers in addition to said measure.
Claim 10
Independent Claim
253 words
A system, responsive to a term chosen by a user, for retrieving, from a stored database, a desired image that is visually similar to images in a set associated with the term, wherein the system utilizes a semantically based, linguistically searchable, numeric descriptor of a pre-defined group of images, the system comprising: a database having image information stored therein; a signature generator, responsive to each one of a set of input images, for producing a corresponding signature for each one of said images so as to form a plurality of signatures, each of the signatures having a plurality of elements and storing, in a corresponding one of the elements, a numeric value of each one of a plurality of different pre-defined visual characteristics of a corresponding one of the input images; a statistics generator, responsive to all of said signatures, for generating a value of a variance and a value of an average of each corresponding element taken across all the signatures and storing the variance and average values in a corresponding element in average and variance vectors, respectively, so as to define a statistical measure, wherein said statistical measure describes, with respect to the pre-defined characteristics, all the images taken collectively; and a database manager for associating a linguistic term, to identify said set of images, with said statistical measure, and for storing said measure and said term collectively in the database in such a manner that a textual search through the database and on the term will return said statistical measure.
Claim 11
Independent Claim
253 words
A system, responsive to a term chosen by a user, for retrieving, from a stored database, a desired image that is visually similar to images in a set associated with the term, wherein the system utilizes a semantically based, linguistically searchable, numeric descriptor of a pre-defined group of images, the system comprising: a database having image information stored therein; a signature generator, responsive to each one of a set of input images, for producing a corresponding signature for each one of said images so as to form a plurality of signatures, each of the signatures having a plurality of elements and storing, in a corresponding one of the elements, a numeric value of each one of a plurality of different pre-defined visual characteristics of a corresponding one of the input images; a statistics generator, responsive to all of said signatures, for generating a value of a variance and a value of an average of each corresponding element taken across all the signatures and storing the variance and average values in a corresponding element in average and variance vectors, respectively, so as to define a statistical measure, wherein said statistical measure describes, with respect to the pre-defined characteristics, all the images taken collectively; and a database manager for associating a linguistic term, to identify said set of images, with said statistical measure, and for storing said measure and said term collectively in the database in such a manner that a textual search through the database and on the term will return said statistical measure.
Claim 12
Dependent Claim
201 words
The system in claim 9 wherein said signature generator comprises: a plurality of three successive convolution filters, responsive to the input image, for producing through iterative convolution a final response image for each one of said pre-defined characteristics so as to yield a plurality of final response images, wherein each of said three convolution filters comprises: a convolver for separately convolving pixel values for each incoming image with each one of a plurality of predefined kernels to yield a corresponding one of a plurality of convolved images, said each incoming image for a first one of said filters being said one input image, and for each subsequent filter being a different corresponding filter input image related to each separate convolved image produced by an immediately preceding one of said convolution filters; and a sum and normalizer for separately summing all pixel values in each one of the final response images produced by a last one of the convolution filters to yield a resultant sum and for normalizing the resultant sum by a total number of pixels in the final response image produced by the last filter so as to yield a value of a different corresponding one of the pre-defined characteristics.
Claim 13
Dependent Claim
76 words
The system in claim 10 wherein the plurality of convolution filters further comprises connected, first, second and third convolution filters, arranged in succession, for iteratively convolving pixel values in the input image, wherein the first, second and third filters separately convolves the pixel values in the incoming image correspondingly applied to the first, second and third filters with each one of a plurality of individual kernels in first, second and third sets of predefined kernels, respectively.
Claim 14
Dependent Claim
16 words
The system in claim 11 wherein the first, second and third sets of kernels are identical.
Claim 15
Dependent Claim
67 words
The system in claim 12 wherein each of the convolvers further comprises serially connected horizontal and vertical down-sizing convolvers for convolving the incoming image applied thereto with first and second half-level kernels, respectively, to yield corresponding ones of the convolved images; each one of said individual kernels being a derivative of a Gaussian kernel and separable into a corresponding pair of said first and second half-level kernels.
Claim 16
Dependent Claim
84 words
The system in claim 13 wherein each of the convolution filters further comprises a squarer, responsive to each of the convolved images produced in said each filter, for squaring a magnitude of each pixel value in said each image and produced by the convolver in said each filter so as to yield, as output of said each filter, a corresponding one of a plurality of filter response images, wherein the filter response images produced by the last convolution filter are the final response images.
Claim 17
Dependent Claim
25 words
The system in claim 12 wherein the signature comprises a different corresponding sub-vector for image characteristic values for each color axis in the input image.
Claim 18
Dependent Claim
55 words
The system in claim 9 further comprising pointers stored wherein the database and along with said measure, wherein each of the pointers specifies a corresponding location in the database at which each one of the images in the set is stored such that said textual search will return said pointers in addition to said measure.
Claim 19
Dependent Claim
167 words
The system in claim 9 further comprising: a manager, operative in conjunction with the database, for accessing, from the database and in response to a selected one of a plurality of pre-defined linguistic terms stored in said database, an associated statistical measure stored therein, and for accessing from the database individual ones of stored signatures for a plurality of other images in the database so as to define a plurality of test signatures; a comparator for comparing the statistical measure against each one of the test signatures so as to yield a similarity measure, the similarity measure for said one of the test images being reflective of a degree of visual similarity between the one test image and an image set defined by the associated statistical measure; and wherein the manager, in response to the similarity measure for each of the test images, selects at least one of test images having a highest relative similarity measure as a retrieved image and provides the retrieved image as output.
Claim 20
Dependent Claim
46 words
The system in claim 17 wherein the comparator comprises a comparison engine for determining the similarity measure, for the test image, as a function of a difference between corresponding elements in said average vector and said test signature, and a corresponding element in said variance vector.
Claim 21
Independent Claim
207 words
A method for generating a semantically based, linguistically searchable, numeric descriptor of a pre-defined group of input images, the method comprising the steps of: producing, in response to each one of a set of input images, a corresponding signature for each one of said images so as to form a plurality of signatures, each of the signatures having a plurality of elements and storing, in a corresponding one of the elements, a numeric value of each one of a plurality of different pre-defined visual characteristics of a corresponding one of the input images; generating, in response to all of said signatures, a value of a variance and a value of an average of each corresponding element taken across all the signatures and storing the variance and average values in a corresponding element in average and variance vectors, respectively, so as to define a statistical measure, wherein said statistical measure describes, with respect to the pre-defined characteristics, all the images taken collectively; and associating a linguistic term, to identify said set of images, with said statistical measure; and storing said measure and said term collectively in a database in such a manner that a textual search through the database and on the term will return said statistical measure.
Claim 22
Independent Claim
207 words
A method for generating a semantically based, linguistically searchable, numeric descriptor of a pre-defined group of input images, the method comprising the steps of: producing, in response to each one of a set of input images, a corresponding signature for each one of said images so as to form a plurality of signatures, each of the signatures having a plurality of elements and storing, in a corresponding one of the elements, a numeric value of each one of a plurality of different pre-defined visual characteristics of a corresponding one of the input images; generating, in response to all of said signatures, a value of a variance and a value of an average of each corresponding element taken across all the signatures and storing the variance and average values in a corresponding element in average and variance vectors, respectively, so as to define a statistical measure, wherein said statistical measure describes, with respect to the pre-defined characteristics, all the images taken collectively; and associating a linguistic term, to identify said set of images, with said statistical measure; and storing said measure and said term collectively in a database in such a manner that a textual search through the database and on the term will return said statistical measure.
Claim 23
Dependent Claim
196 words
The method in claim 19 wherein the signature producing step comprises the steps of: producing, in response to the input image and through iterative convolution using a plurality of three successive convolution filters, a final response image for each one of said pre-defined characteristics so as to yield a plurality of final response images, wherein in each of said three convolution filters: separately convolving pixel values for each incoming image with each one of a plurality of predefined kernels to yield a corresponding one of a plurality of convolved images, said each incoming image for a first one of said filters being the input image, and for each subsequent filter being a different corresponding filter input image related to each separate convolved image produced by an immediately preceding one of said convolution filters; separately summing all pixel values in each one of the final response images produced by a last one of the convolution filters to yield a resultant sum; and normalizing the resultant sum by a total number of pixels in the final response image produced by the last filter so as to yield a value of a different corresponding one of the pre-defined characteristics.
Claim 24
Dependent Claim
81 words
The method in claim 20 wherein the producing step comprises the step of iteratively convolving pixel values in the input image though successive first, second and third convolution filters, wherein the iterative convolving step comprises the step of separately convolving, through first, second and third filters, the pixel values in the incoming image correspondingly applied to the first, second and third filters with each one of a plurality of individual kernels in first, second and third sets of predefined kernels, respectively.
Claim 25
Dependent Claim
16 words
The method in claim 21 wherein the first, second and third sets of kernels are identical.
Claim 26
Dependent Claim
67 words
The method in claim 22 wherein the separately convolving step further comprises the step of convolving the incoming image, through successive horizontal and vertical down-sizing convolvers, with first and second half-level kernels, respectively, to yield corresponding ones of the convolved images; each one of said individual kernels being a derivative of a Gaussian kernel and separable into a corresponding pair of said first and second half-level kernels.
Claim 27
Dependent Claim
88 words
The method in claim 23 further comprising, in each of the convolution filters, the step of squaring, in response to each of the convolved images produced in said each filter, a magnitude of each pixel value in said each image and produced by the separately convolving step performed in said each filter so as to yield, as output of said each filter, a corresponding one of a plurality of filter response images, wherein the filter response images produced by the last convolution filter are the final response images.
Claim 28
Dependent Claim
58 words
The method in claim 19 further comprising the step of storing pointers within the database and along with said measure, wherein each of the pointers specifies a corresponding location in the database at which each one of the images in the set is stored such that said textual search will return said pointers in addition to said measure.
Claim 29
Dependent Claim
15 words
A computer-readable media having computer-executable instructions stored therein for performing the steps of claim 19.
Claim 30
Independent Claim
240 words
A method, responsive to a term chosen by a user, for retrieving, from a stored database, a desired image that is visually similar to images in a set associated with the term, wherein the method utilizes a semantically based, linguistically searchable, numeric descriptor of a pre-defined group of images, the method comprising the steps of: producing, in response to each one of a set of input images, for producing a corresponding signature for each one of said images so as to form a plurality of signatures, each of the signatures having a plurality of elements and storing, in a corresponding one of the elements, a numeric value of each one of a plurality of different pre-defined visual characteristics of a corresponding one of the input images; generating, in response to all of said signatures, a value of a variance and a value of an average of each corresponding element taken across all the signatures and storing the variance and average values in a corresponding element in average and variance vectors, respectively, so as to define a statistical measure, wherein said statistical measure describes, with respect to the pre-defined characteristics, all the images taken collectively; and associating a linguistic term, to identify said set of images, with said statistical measure; and storing said measure and said term collectively in a database in such a manner that a textual search through the database and on the term will return said statistical measure.
Claim 31
Independent Claim
240 words
A method, responsive to a term chosen by a user, for retrieving, from a stored database, a desired image that is visually similar to images in a set associated with the term, wherein the method utilizes a semantically based, linguistically searchable, numeric descriptor of a pre-defined group of images, the method comprising the steps of: producing, in response to each one of a set of input images, for producing a corresponding signature for each one of said images so as to form a plurality of signatures, each of the signatures having a plurality of elements and storing, in a corresponding one of the elements, a numeric value of each one of a plurality of different pre-defined visual characteristics of a corresponding one of the input images; generating, in response to all of said signatures, a value of a variance and a value of an average of each corresponding element taken across all the signatures and storing the variance and average values in a corresponding element in average and variance vectors, respectively, so as to define a statistical measure, wherein said statistical measure describes, with respect to the pre-defined characteristics, all the images taken collectively; and associating a linguistic term, to identify said set of images, with said statistical measure; and storing said measure and said term collectively in a database in such a manner that a textual search through the database and on the term will return said statistical measure.
Claim 32
Dependent Claim
196 words
The method in claim 27 wherein the signature producing step comprises the steps of: producing, in response to the input image and through iterative convolution using a plurality of three successive convolution filters, a final response image for each one of said pre-defined characteristics so as to yield a plurality of final response images, wherein in each of said three convolution filters: separately convolving pixel values for each incoming image with each one of a plurality of predefined kernels to yield a corresponding one of a plurality of convolved images, said each incoming image for a first one of said filters being the input image, and for each subsequent filter being a different corresponding filter input image related to each separate convolved image produced by an immediately preceding one of said convolution filters; separately summing all pixel values in each one of the final response images produced by a last one of the convolution filters to yield a resultant sum; and normalizing the resultant sum by a total number of pixels in the final response image produced by the last filter so as to yield a value of a different corresponding one of the pre-defined characteristics.
Claim 33
Dependent Claim
81 words
The method in claim 28 wherein the producing step comprises the step of iteratively convolving pixel values in the input image though successive first, second and third convolution filters, wherein the iterative convolving step comprises the step of separately convolving, through first, second and third filters, the pixel values in the incoming image correspondingly applied to the first, second and third filters with each one of a plurality of individual kernels in first, second and third sets of predefined kernels, respectively.
Claim 34
Dependent Claim
16 words
The method in claim 29 wherein the first, second and third sets of kernels are identical.
Claim 35
Dependent Claim
67 words
The method in claim 30 wherein the separately convolving step further comprises the step of convolving the incoming image, through successive horizontal and vertical down-sizing convolvers, with first and second half-level kernels, respectively, to yield corresponding ones of the convolved images; each one of said individual kernels being a derivative of a Gaussian kernel and separable into a corresponding pair of said first and second half-level kernels.
Claim 36
Dependent Claim
88 words
The method in claim 31 further comprising, in each of the convolution filters, the step of squaring, in response to each of the convolved images produced in said each filter, a magnitude of each pixel value in said each image and produced by the separately convolving step performed in said each filter so as to yield, as output of said each filter, a corresponding one of a plurality of filter response images, wherein the filter response images produced by the last convolution filter are the final response images.
Claim 37
Dependent Claim
58 words
The method in claim 27 further comprising the step of storing pointers within the database and along with said measure, wherein each of the pointers specifies a corresponding location in the database at which each one of the images in the set is stored such that said textual search will return said pointers in addition to said measure.
Claim 38
Dependent Claim
153 words
The method in claim 27 further comprising: accessing, from the database and in response to a selected one of a plurality of pre-defined linguistic terms stored in said database, an associated statistical measure stored therein; accessing from the database individual ones of stored signatures for a plurality of other images in the database so as to define a plurality of test signatures; a comparator for comparing the statistical measure against each one of the test signatures so as to yield a similarity measure, the similarity measure for said one of the test images being reflective of a degree of visual similarity between the one test image and an image set defined by the associated statistical measure; and selecting, in response to the similarity measure for each of the test images, at least one of test images having a highest relative similarity measure as a retrieved image; and providing the retrieved image as output.
Claim 39
Dependent Claim
46 words
The method in claim 34 wherein the comparing step comprises the step of determining the similarity measure, for the test image, as a function of a difference between corresponding elements in said average vector and said test signature, and a corresponding element in said variance vector.
Claim 40
Dependent Claim
15 words
A computer-readable media having computer-executable instructions stored thereon for performing the steps of claim 27.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-10-05 | 2002-04-06 | 2002-10-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-10-05 | 2006-04-06 | 2006-10-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-10-05 | 2010-04-06 | 2010-10-06 | $7700.00 | Window Closed / Lapsed |