Statistically based image group descriptor particularly suited for use in an image classification and retrieval system

• US 5,819,288 A
• Filed: 10/16/1996
• Issued: 10/06/1998
• Est. Priority Date: 10/16/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: De Bonet, Jeremy S.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/732,616
• Time in Patent Office: 720 Days
• Field of Search: 360/8, 382/305, 382/128, 382/232, 345/429, 707/530, 707/200
• US Class Current: 1/1
• 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/5838 using colour
• CPC Class Codes: G06V 10/36 Applying a local operator, i.e. means to operate on image points situated in the vicinity of a given point; Non-linear local filtering operations, e.g. median filtering
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

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.

Claims

1. 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.

2. 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.

3. 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.

4. The apparatus in claim 3 wherein the first, second and third sets of kernels are identical.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. The system in claim 11 wherein the first, second and third sets of kernels are identical.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. The method in claim 21 wherein the first, second and third sets of kernels are identical.

23. 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.

24. 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.

25. 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.

26. A computer-readable media having computer-executable instructions stored therein for performing the steps of claim 19.

27. 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.

28. 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.

29. 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.

30. The method in claim 29 wherein the first, second and third sets of kernels are identical.

31. 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.

32. 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.

33. 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.

34. 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.

35. 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.

36. A computer-readable media having computer-executable instructions stored thereon for performing the steps of claim 27.