Image coding apparatus and method utilizing separable transformations

• US 5,148,498 A
• Filed: 08/01/1990
• Issued: 09/15/1992
• Est. Priority Date: 08/01/1990
• Status: Expired due to Term

• Current Assignee: Aware Incorporated (Crowley Holdings Preferred LLC)
• Original Assignee: Aware Incorporated (Crowley Holdings Preferred LLC)
• Inventors: Resnikoff, Howard L., Lawton, Wayne M., Pollen, David, Linden, David C. P.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Fox, David
• Application Number:
  US07/561,449
• Time in Patent Office: 776 Days
• Field of Search: 382/27, 382/44, 382/54, 382/56, 358/429, 358/432, 358/433, 358/467, 358/141, 364/724.05, 364/724.16
• US Class Current: 382/248
• CPC Class Codes: H03H 17/0202 Two or more dimensional filters; Filters for complex signals multidimensional convolutions G06F17/153
• CPC Class Codes: H04N 19/635 characterised by filter definition or implementation details

Abstract

An image coding apparatus and method are disclosed. The method and apparatus are applicable to coding any array of arbitrary dimension. The apparatus utilizes FIR filters which generate three or more sets of coefficients from linear arrays generated from the array being coded. Each set of coefficients represents spatial frequency information of different frequencies. The filters utilize coefficient sets which are preferrably orthogonal.

Claims

1. An apparatus for compressing an image comprising a two-dimensional array of pixel intensity values, said apparatus comprising:

image storage means comprising means for storing said array of pixel intensity values as a plurality of rows and columns;

linear filtering means for filtering a one-dimensional sequence of digital values to generate a low-frequency array representing the low-frequency components of said one-dimensional sequence and two or more high-frequency arrays representing high-frequency components of said one-dimensional sequence, said linear filtering means comprising means for convolving said one-dimensional signal with three or more sequences of filter coefficients ⁱ a_p wherein ##EQU1## M is an integer greater than 2, i runs from 0 to the total number of high-frequency arrays so generated, and said low-frequency array is generated by convolving said one-dimensional sequence with the filter coefficient ⁰ a_p ;

row processing means for causing said linear filtering means to process each said row in said image storage means to generate a low-frequency row array comprising a two-dimensional array of digital values organized as a plutality of rows and columns and a plurality of high-frequency rows arrays, each said high-frequency row array comprising a two-dimensional array of digital values organized as a plurality of rows and columns; and

column processing means for causing said linear filtering means to process each said column in said low-frequency row array to generate a low-frequency column array representing the low spatial frequency information in said image.

2. The apparatus of claim 1 wherein said column processing means further comprises means for causing said linear filtering means to process each said column in said high-frequency row arrays to generate a high-frequency column array representing the high spatial frequency information in said image.

3. The apparatus of claim 1 wherein said filter coefficients further satisfy the condition ##EQU2## wherein q is any positive integer and (*) denotes complex conjugation.

4. The apparatus of claim 1 wherein said filter coefficients further satisfy the condition ##EQU3## wherein said condition is satisfied for all i >

0 and any positive integer value q less than some predetermined value.

5. The apparatus for synthesizing an image comprising a two-dimensional array of pixel intensity values organized as a plurality of rows and columns from M two-dimensional sets of image coefficients, each said set of image coefficients being organized as a plurality of rows and columns, wherein M is greater than two, said apparatus comprising:

coefficient storage means comprising means for storing said two-dimensional sets of image coefficients;

linear synthesizing means for combining M one-dimensional input sequences of digital values to generates an output numerical sequence, wherein each of said one-dimensional sequences may be obtained by filtering said output numerical sequence through a finite impulse response filter having a set of filter coefficients _i a_p corresponding to each said input sequence, wherein ##EQU4## for i from 0 to M-1;

column processing means for causing said linear synthesizing means to combine corresponding columns of said sets of image coefficients to generate M column arrays, each said column array comprising a two-dimensional array of numerical values organized as a plurality of rows and columns; and

row processing means for causing said linear synthesizing means to combine corresponding rows of said column arrays to generate a row of said reconstructed image.

6. The apparatus of claim 5, wherein said filter coefficients further satisfy the condition ##EQU5## wherein q is any positive integer and (*) denotes complex conjugation.

7. The apparatus of claim 5 wherein said filter coefficients further satisfy the condition ##EQU6## wherein said condition is satisfied for all i>

0 and any positive integer value q less than some predetermined value.

8. In an apparatus including a linear filter for filtering a one-dimensional sequence of digital values to generate a low frequency array representing the low-frequency components of said one-dimensional sequence and two or more high-frequency arrays representing high-frequency components of said one-dimensional sequence, said linear filter comprising means for convolving said one-dimensional signal with three or more sequences of filter coefficients ⁱ a_p wherein ##EQU7## M is an integer greater than 2, i runs from 0 to the total number of high-frequency arrays so generated, and said low-frequency array is generated by convolving said one-dimensional sequence with the sequence ⁰ a_p, a method for compressing an image comprising a two-dimensional array of pixel intensity values, said method comprising the step of:

storing said array of pixel intensity values as a plurality of rows and columns;

filtering a one-dimensional sequence of digital values to generate a low-frequency array representing the low-frequency components of said one-dimensional sequence and two or more high-frequency arrays representing high-frequency components of said one-dimensional sequence, said filtering step comprising convolving said one-dimensional signal with three or more sequences of filter coefficients ⁱ a_p wherein ##EQU8## M is an integer greater than 2, i runs from 0 to the total number of high-frequency arrays so generated, and said low-frequency array is generated by convolving said one-dimensional sequence with the sequence ⁰ a_p ;

causing said linear filter to process each said row in said image storage means to generate a low-frequency row array comprising a two-dimensional array of digital values comprising a two-dimensional array of digital values organized as a plurality of rows and columns and a plurality of high-frequency row arrays, each said high-frequency row array comprising a two-dimensional array of digital values organized as a plurality of rows and columns; and

causing said linear filter to process each said column in said low-frequency row array to generate a low-frequency column array representing the low spatial frequency information in said image.

9. The method of claim 8 further comprising the step of causing said linear filter to process each said column in said high-frequency row arrays to generate a high-frequency column of arrays representing the high spatial frequency information in said image.

10. The method of claim 8 wherein said filter coefficients further satisfy the condition ##EQU9## wherein q is any positive integer and (*) denotes complex conjugation.

11. The method of claim 8 wherein said filter coefficients further satisfy the condition ##EQU10## wherein said condition is satisfied for all i>

0 and any positive integer value q less than some predetermined value.

12. In an apparatus including a linear synthesizing means for combining M one-dimensional input sequences of digital values to generate an output numerical sequence, wherein each of said one-dimensional sequences may be obtained by filtering said output numerical sequence through a finite impulse response filter having a set of filter coefficients ⁱ a_p corresponding to each said input sequence, wherein ##EQU11## for i from 0 to M-1, a method for synthesizing an image comprising a two-dimensional array of pixel intensity values organized as a plurality of rows and columns from M two-dimensional sets of image coefficients, each said set of image coefficients being organized as a plurality of rows and columns, wherein M is greater than two, said method comprising:

storing said two-dimensional sets of image coefficients;

causing said linear synthesizing means to combine corresponding columns of said sets of image coefficients to generate M column arrays, each said column array comprising a two-dimensional array of numerical values organized as a plurality of rows and columns; and

causing said linear synthesizing means to combine corresponding rows of said column arrays to generate a row of said reconstructed image.

13. The method of claim 12 wherein said filter coefficients further satisfy the condition ##EQU12## wherein q is any positive integer and (*) denotes complex conjugation.

14. The method of claim 12 wherein said filter coefficients further satisfy the condition ##EQU13## wherein said condition is satisfied for all i>

0 and any positive integer value q less than some predetermined value.