Iterative convolution filter particularly suited for use in an image classification and retrieval system

• US 5,899,999 A
• Filed: 10/16/1996
• Issued: 05/04/1999
• 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): Lintz, Paul R.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/732,614
• Time in Patent Office: 930 Days
• Field of Search: 707/104, 382/133, 382/167, 382/203, 382/232, 382/233, 382/240, 382/254, 382/443, 360/78.09, 356/139.01, 356/376, 378/15, 378/62, 364/724.1, 600/443
• US Class Current: 1/1
• 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/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

Apparatus and an accompanying method for an iterative convolution filter for determining an image signature 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 an image using multi-level (e.g. L levels) iterative convolution filtering, with pixel values for each color axis supplied as input to each filtering level being separately convolved with each one of a set of, e.g., K predefined kernels, each being, e.g., a derivative of a Guassian kernel, to yield an output image. Each of the output images, of which K^L occur for each color axis, is either applied as input to the next filtering level or applied to a summer to yield a resultant sum over all pixel values in that particular output image. This sum becomes the value of a corresponding one of K^L elements, for each color axis, in the signature.

Claims

1. Apparatus, responsive to an input image, for generating a signature therefor and having a numeric value for each of a plurality of pre-defined characteristics present in the input image, the apparatus comprising:

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

2. The system in claim 1 further comprising an image comparator for comparing corresponding ones of the values of said pre-defined characteristics of the signature for each of first and second input images so as to yield an output value whereby said output value numerically represents a degree of similarity between said first and second input images.

3. The system in claim 1 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 system in claim 3 wherein the first, second and third sets of kernels are identical.

5. The system in claim 4 wherein each of said convolvers comprises a down-sizing convolver.

6. The system in claim 5 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.

7. The system in claim 6 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.

8. The system in claim 5 wherein each of said first, second and third set of kernels is an identical set of 25 two-dimensional derivatives of Gaussian kernels, each being 3×

3 in size.

9. The system in claim 5 wherein the signature comprises a different corresponding sub-vector for image characteristic values for each color axis in the input image.

10. Apparatus, responsive to an input image having pixel values for a plurality (C) of different color axes, for generating a signature therefor and having a numeric value for each of a plurality of pre-defined characteristics present in the input image, the apparatus comprising:

a plurality of convolution filters, responsive to the pixel values of the input image for each one of said color axes, for producing a final response image for each one of said pre-defined characteristics so as to yield a plurality of final response images, comprising;

first, second and third filters, arranged in succession, for iteratively and separately convolving the pixel values in an incoming image correspondingly applied to the first, second and third filters with each one of K individual kernels in first, second and third sets of predefined kernels, respectively, to yield a corresponding one of a plurality of convolved images, wherein said incoming image for a first one of said filters is the pixel values of the input image and for said color axis, and the incoming image for each subsequent one of the filters is a different corresponding filter input image related to each separate convolved image for said color axis and produced by an immediately preceding one of said 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;

whereby the signature has values for C×

K³ different ones of said characteristics.

11. The apparatus in claim 10 further comprising an image comparator for comparing corresponding ones of the values of said pre-defined characteristics of the signature for each of first and second input images so as to yield an output value whereby said output value numerically represents a degree of similarity between said first and second images.

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

13. The system in claim 12 wherein each of said convolvers comprises a down-sizing convolver.

14. The system in claim 13 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.

15. The system in claim 14 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.

16. The system in claim 13 wherein each of said first, second and third set of kernels is an identical set of 25 two-dimensional derivatives of Gaussian kernels, each being 3×

3 in size.

17. A method for generating a signature for an input image and which has a numeric value for each of a plurality of pre-defined characteristics present in the input image, the method comprising the steps of:

producing, in response to the input image and through iterative convolution using 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 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.

18. The method in claim 17 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.

19. The method in claim 17 further comprising the step of comparing corresponding ones of the values of said pre-defined characteristics of the signature for each of first and second input images so as to yield an output value whereby said output value numerically represents a degree of similarity between said first and second input images.

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

21. The method in claim 20 wherein said separately convolving step comprises the step of performing a down-sizing convolution.

22. The method in claim 21 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.

23. The method in claim 22 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.

24. The method in claim 21 wherein each of said first, second and third set of kernels is an identical set of 25 two-dimensional derivatives of Gaussian kernels, each being 3×

3 in size.

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

26. A method for generating a signature for an input image having pixel values for a plurality (C) of different color axes, for generating a signature therefor and having a numeric value for each of a plurality of pre-defined characteristics present in the input image, the method comprising the steps of:

producing, in response to the pixel values of the input image for each one of said color axes, a final response image for each one of said pre-defined characteristics so as to yield a plurality of final response images, comprising;

iteratively and separately convolving, through successively arranged first, second and third filters, the pixel values in an incoming image correspondingly applied to the first, second and third filters with each one of K individual kernels in first, second and third sets of predefined kernels, respectively, to yield a corresponding one of a plurality of convolved images, wherein said incoming image for a first one of said filters is the pixel values of the input image and for said color axis, and the incoming image for each subsequent one of the filters is a different corresponding filter input image related to each separate convolved image for said color axis and produced by an immediately preceding one of said filters; and

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;

whereby the signature has values for C×

K³ different ones of said characteristics.

27. The method in claim 26 further comprising the step of comparing corresponding ones of the values of said pre-defined characteristics of the signature for each of first and second input images so as to yield an output value whereby said output value numerically represents a degree of similarity between said first and second input images.

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

29. The method in claim 28 wherein said separately convolving step comprises the step of performing a down-sizing convolution.

30. The method in claim 29 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.

31. The method in claim 30 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.

32. The method in claim 29 wherein each of said first, second and third set of kernels is an identical set of 25 two-dimensional derivatives of Gaussian kernels, each being 3×

3 in size.

33. A computer-readable media having computer-executable instructions stored thereon for producing the steps of claim 26.