Efficient convolutions using polynomial covers

• US 6,144,767 A
• Filed: 11/10/1998
• Issued: 11/07/2000
• Est. Priority Date: 04/02/1998
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Simard, Patrice Yvon, Bottou, Leon
• Primary Examiner(s): Tadayon, Bijan
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/189,202
• Time in Patent Office: 728 Days
• Field of Search: 382/209, 382/210, 382/211, 382/212, 382/213, 382/257, 382/279, 382/278, 382/280, 382/276
• US Class Current: 382/209
• CPC Class Codes: G06V 10/431 Frequency domain transformation; Autocorrelation

Abstract

Signal processing and pattern recognition is efficiently accomplished by using a plurality of low degree polynomials to approximate the images. The polynomials are then differentiated to obtain impulse functions. The impulse functions may be easily and efficiently convolved and the convolution subsequently integrated to extract the desired signal information.

Claims

1. An image processing arrangement for comparing a first image (ƒ

(x)) to a second image (g(x)), the arrangement comprising

a first quantizer for receiving as an input the first image and generating an approximation thereof defined as a polynomial first image cover having a predetermined degree d.sub.ƒ

, said first cover defined by a plurality of non-overlapping cover regions c_i ;

a second quantizer for receiving as an input the second image and generating an approximation thereof defined as a polynomial second image cover having a predetermined degree d_g, said second cover defined by a plurality of non-overlapping cover regions c_i ;

a first differentiator receiving as an input the first polynomial of degree d.sub.ƒ

and differentiating said first polynomial d.sub.ƒ

+1 times to generate an impulse response representation of said first image;

a second differentiator receiving as an input the second polynomial of degree d_g and differentiating said second polynomial d_g +1 times to generate an impulse response representation of said second image;

a convolver responsive to the first and second impulse response representations for summing said impulse functions to generate a convolution representation of said first and second images; and

an integrator responsive to the convolution output from the convolver for integrating said convolution ((d.sub.ƒ

+1+dg+1)=d.sub.ƒ

+d_g +2) times to generate as an output the pattern information related to the first and second images.

2. An image processing arrangement as defined in claim 1 wherein the first quantizer generates a polynomial cover F(x) which minimizes a predetermined error relation e_ci (ƒ

(x),p(x)).

3. An image processing arrangement as defined in claim 2 wherein the predetermined error relation is defined by ##EQU3## for each cover region c_i.

4. An image processing arrangement as defined in claim 2 wherein the first polynomial cover comprises a set of non-overlapping rectangular areas.

5. An image processing arrangement as defined in claim 4 wherein the arrangement further comprises a compactor for evaluating the plurality of impulse functions associated with the non-overlapping rectangular areas and summing the values of co-located impulse functions to reduce the number of separate impulse functions.

6. An image processing arrangement as defined in claim 1 wherein the second quantizer generates a polynomial cover G(x) which minimizes a predetermined error measure e_ci (g(x),p(x)).

7. An image processing arrangement as defined in claim 6 wherein the predetermined error measure is ##EQU4## for a predetermined value of e_i.

8. An image processing arrangement as defined in claim 6 wherein the second polynomial cover comprises a set of non-overlapping rectangular areas.

9. An image processing arrangement as defined in claim 6 wherein the arrangement further comprises a compactor for evaluating the plurality of impulse functions associated with the non-overlapping rectangular areas and summing the values of co-located impulse functions to reduce the number of separate impulse functions.

10. A method of extracting signal information from a pair of images, the pair of images defined by a first image ƒ

(x) and a second image g(x), the method comprising the steps of;

a) quantizing each image by defining a cover for each image comprising a series of low degree polynomials of degree d.sub.ƒ

and d_g, respectively, said quantized representations defined as F(x) and G(x), respectively;

b) differentiating each quantized representation, the first quantized representation F(x) differentiated d.sub.ƒ

+1 times and the second quantized representation G(x) differentiated d_g +1 times, each differentiating generating an impulse response representation of each image, to form F'"'"'(x) and G'"'"'(x), respectively;

c) convolving the impulse response representations of F'"'"'(x) and G'"'"'(x) to generated F'"'"'(x)*G'"'"'(x); and

d) integrating the convolution F'"'"'(x)*G'"'"'(x) (d.sub.ƒ

+1+dg+1) times to generate as an output the pattern information related to the first and second images.

11. A signal information extraction method as defined in claim 10 wherein in performing step a), a predetermined error measure eci(ƒ

(x),p(x)) is used to assess the quantization process.

12. A signal extraction method as defined in claim 11 wherein in performing step a), the following predetermined error measure is used ##EQU5## to define the quantized representation F(x) for a predetermined error e_i.

13. A signal information extraction method as defined in claim 10 wherein in performing step a), a plurality of non-overlapping rectangular cover polynomials are defined for F(x).

14. A signal information extraction method as defined in claim 13 wherein the method further comprises the step of summing the impulse response representations of the plurality of non-overlapping rectangular cover polynomials generated in step b) prior to convolving the differentials F'"'"'(x) and G'"'"'(x).

15. A signal information extraction method as defined in claim 13 wherein each non-overlapping rectangular area is defined using a recursive process, beginning with a rectangular area equal to the image size and recursively dividing each rectangular error in half until an error threshold is obtained.

16. A signal information extraction method as defined in claim 10 wherein in performing step a), a predetermined error measure e_ci (g(x),p(x)) is used to assess the quantization process.

17. A signal information extraction method as defined in claim 16 wherein the predetermined error measure is defined as ##EQU6## and used define the quantized representation G(x) for a predetermined error e_i.

18. A signal information extraction method as defined in claim 10 wherein in performing step a), a plurality of non-overlapping rectangular cover polynomials are defined for G(x).

19. A signal information extraction method as defined in claim 18 wherein the method further comprises the step of summing the impulse response representations of the plurality of non-overlapping rectangular cover polynomials generated in step b) prior to convolving the differentials F'"'"'(x) and G'"'"'(x).

20. A signal information extraction method as defined in claim 18 wherein each non-overlapping rectangular area is defined using a recursive process, beginning with a rectangular area equal to the image size and recursively dividing each rectangular error in half until an error threshold is obtained.

21. An image processing arrangement for comparing a first image (ƒ

(x)) to a second image (g(x)), the first image being larger than the second image and the second image defined a plurality of separate impulse functions for each pixel within said second image, the arrangement comprising

a quantizer for receiving as an input the first image and generating an approximation thereof defined as a polynomial image cover having a predetermined degree d.sub.ƒ

, said first cover defined by a plurality of non-overlapping cover regions c_i ;

a differentiator receiving as an input the polynomial of degree d.sub.ƒ

and differentiating said polynomial d.sub.ƒ

+1 times to generate an impulse response representation of said first image;

a convolver responsive to the impulse response representation of said first image generated by said differentiator and the plurality of separate impulse functions of said second image for summing said impulse functions to generate a convolution representation of said first and second images; and

an integrator responsive to the convolution output from the convolver for integrating said convolution (d.sub.ƒ

+1) times to generate as an output the pattern information related to the first and second images.

22. An image processing arrangement as defined in claim 21 wherein the quantizer generates a polynomial cover F(x) which minimizes a predetermined error measure e_ci (ƒ

(x),p(x)).

23. An image processing arrangement as defined in claim 22 wherein the predetermined error measure is defined as follows:

##EQU7## for each cover region c_i.

24. An image processing arrangement as defined in claim 21 wherein the polynomial cover comprises a set of non-overlapping rectangular areas.

25. An image processing arrangement as defined in claim 21 wherein the arrangement further comprises a compactor for evaluating the plurality of impulse functions associated with the non-overlapping rectangular areas with the plurality of impulse functions of the second image and summing the values of co-located impulse functions to reduce the number of separate impulse functions.

26. A method of extracting signal information from a pair of images, the pair of images defined by a first image ƒ

(x) and a second image g(x), the second image being smaller than the first image and represented by a plurality of impulse functions for each pixel within said second image, the method comprising the steps of;

a) quantizing the first image by defining a cover for said first image comprising a series of low degree polynomials of degree d.sub.ƒ

, said quantized representation defined as F(x), respectively;

b) differentiating said quantized representation d.sub.ƒ

+1 times to generate an impulse response representation of said first image, defined as F'"'"'(x);

c) convolving the impulse response representation F'"'"'(x) with the plurality of impulse functions of the second image to generate F'"'"'(x)*g(x); and

d) integrating the convolution F'"'"'(x)*g(x) (d.sub.ƒ

+1) times to generate as an output the pattern information related to the first and second images.

27. A signal information extraction method as defined in claim 26 wherein in performing step a), a predetermined error measure e_ci (ƒ

(x),p(x)) is used to defined the quantized representation F(x).

28. A signal information extraction method as defined in claim 27 wherein in performing step a), the predetermined error measure is defined as ##EQU8##

29. A signal information extraction method as defined in claim 26 wherein in performing step a), a plurality of non-overlapping rectangular cover polynomials are defined for F(x).

30. A signal information extraction method as defined in claim 29 wherein the method further comprises the step of summing the impulse response representations of the plurality of non-overlapping rectangular cover polynomial generated in step b) with the impulse response representation of said second image prior to performing the convolving step.

31. A signal information extraction method as defined in claim 29 wherein each non-overlapping rectangular area is defined using a recursive process, beginning with a rectangular area equal to the image size and recursively dividing each rectangular error in quarters until an error threshold is obtained.