Method for decomposing signals into efficient time-frequency representations for data compression and recognition

• US 5,453,945 A
• Filed: 01/13/1994
• Issued: 09/26/1995
• Est. Priority Date: 01/13/1994
• Status: Expired due to Fees

• Current Assignee: Li Weiping, Michael R. Tucker
• Original Assignee: Li Weiping, Michael R. Tucker
• Inventors: Li, Weiping, Tucker, Michael R.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US08/182,692
• Time in Patent Office: 621 Days
• Field of Search: 364/725, 364/715.02, 382/56
• US Class Current: 708/400
• CPC Class Codes: G06F 2218/08 Feature extraction
• CPC Class Codes: G06T 9/007 Transform coding, e.g. discrete cosine transform

Abstract

A method for decomposing signals into efficient time-frequency representations for data compression and recognition which uses adaptable wavelet basis functions and concentrates a signal or image'"'"'s information to a higher degree than methods based on the discrete fourier transform, the discrete cosine transform, the standard wavelet transform and known adaptive transform techniques. The purpose of the present invention is to enable data signals and images to be stored and transmitted very efficiently. The time-frequency plane is broken up into subspaces. The method determines the optimum basis function for each of the subspace regions. Basis functions are chosen such that much of the information in the signal is contained in a small number of coefficients. The resulting coefficients form a set that represents the signal in the most concentrated manner.

Claims

1. A method of compressing a data signal comprising the steps of:

computing basis coefficients corresponding to basis functions of a data signal using wavelet mathematics wherein the basis functions are separated into a plurality of sets, Set 1 through Set M of basis functions having varying time-frequency characteristics, with said Set 1 being narrow in time and broad in frequency, Set M being long in time and narrow in frequency, and Set 2 through Set M-1 being progressively more narrow in frequency and longer in time; and

selecting a best group of basis coefficients to reconstruct the data signal by selecting a group of basis coefficients that concentrates most of the data signal'"'"'s energy into a smallest number of basis coefficients.

2. The method of claim 1, wherein said step of computing is accomplished by using no multipliers.

3. The method of claim 1, wherein said step of computing is accomplished for a set of basis coefficients by using only a previous set of basis coefficients.

4. The method of claim 3, wherein said step of computing is accomplished by using a filter chip that contains circuitry to load said previous set of basis coefficients in serial and in parallel.

5. The method of claim 1, wherein said step of computing is accomplished by using a filter chip that alternately computes wavelet low-frequency filter outputs and wavelet high-frequency filter outputs.

6. The method of claim 1, wherein said step of selecting is accomplished by using a bit measure that measures a number of bits used to optimally encode basis coefficients of each possible group of basis coefficients used to reconstruct the data signal and by selecting a group of basis coefficients having a lowest bit measure.

7. The method of claim 6, wherein said step of selecting is accomplished by using a shift encoder and summer to determine the bit measure for each possible group of basis coefficients.

8. The method of claim 1, wherein said step of selecting is accomplished by using a property of wavelet mathematics that results in basis coefficients that are orthogonal in time and frequency to determine which group of basis coefficients concentrates most of the data signal'"'"'s energy into a smallest number of basis coefficients.

9. The method of claim 1, further comprising the step of coding information related to the selected group of basis coefficients.

10. The method of claim 9, wherein said step of coding further comprises the steps of:

ordering basis coefficients in said selected group of basis coefficients in descending order of magnitude;

quantizing a magnitude of each of said basis coefficients in said selected group of basis coefficients;

subtracting said magnitude of each of said basis coefficients from a magnitude of a previous basis coefficient in said selected group of basis coefficients;

coding results of the step of subtracting using an entropy-based method;

assigning addresses to each of said basis coefficients according to a time and frequency region covered;

subtracting the address of each basis coefficient from the address of the previous basis coefficient and eliminating addresses of basis coefficients which cannot be used because they overlap in time or frequency with one or more previously used basis coefficients of said selected group of basis coefficients; and

coding results from said step of subtracting addresses using an entropy-based method.

11. An apparatus for compressing a data signal, comprising:

a plurality of low-pass and high-pass decomposition wavelet filters operable to operate on a data signal to computed basis coefficients corresponding to basis functions of the data signal, wherein the basis functions are separated into a plurality of sets, Set 1 through Set M of basis functions that have varying time-frequency characteristics, with Set 1 being narrow in time and broad in frequency, Set M being long in time and narrow in frequency, and Set 2 through Set M-1 being progressively more narrow in frequency and longer in time;

comparison circuitry coupled to the plurality of wavelet filters and operable to compare said basis coefficients and select a group of basis coefficients to reconstruct the data signal which can be coded with a smaller number of bits than any other group of basis coefficients which alternately could be used to reconstruct the data signal;

ordering circuitry coupled to the comparison circuitry and operable to order the selected group of basis coefficients in descending order of magnitude;

quantization circuitry coupled to the ordering circuitry and operable to quantize a magnitude of each basis coefficient in the selected group of basis coefficients;

magnitude subtracting circuitry coupled to the quantization circuitry and operable to subtract the magnitude of each basis coefficient from a magnitude of a previous basis coefficient in the selected group of basis coefficients;

coding circuitry coupled to the magnitude subtracting circuitry and operable to code the results of subtracting magnitudes using an entropy-based method;

addressing circuitry coupled to the coding circuitry and operable to assign addresses to each basis coefficient in the selected group of basis coefficients according to time and frequency regions covered;

address subtracting circuitry coupled to the addressing circuitry and operable to subtract the address of each basis coefficient in the selected group of basis coefficients from the address of the previous basis coefficient and to eliminate the addresses of basis coefficients which cannot be used because they overlap in time or frequency with one or more previously used basis coefficients in the selected group of basis coefficients;

coding circuitry coupled to the address subtracting circuitry and operable to code the results of subtracting addresses using an entropy-based method; and

decompression circuitry coupled to and operable to use the comparison circuitry, the ordering circuitry, the quantization circuitry, the magnitude subtracting circuitry, the coding circuitry, the addressing circuitry, the address subtracting circuitry, and the coding circuitry and operable to apply the result to a plurality of reconstruction wavelet filters to reconstruct the data signal.

12. The apparatus of claim 11, wherein said wavelet filters contain no multipliers.

13. The apparatus of claim 11, wherein said wavelet filters further comprise:

parallel loading circuitry operable to load a previous group of basis coefficients in parallel.

14. The apparatus of claim 11, wherein said comparison circuitry comprises:

shifter circuitry operable to shift bits of said basis coefficients to determine a number of bits required to encode each of said basis coefficients;

adder circuitry Coupled to the shifter circuitry and operable to add the number of bits required to represent each basis coefficient in a group of basis coefficients associated with a time region and a frequency region; and

storage circuitry coupled to the adder circuitry and operable to store a result of said adder circuitry, and further operable to select a group of said basis coefficients having a lowest added total of required bits associated with said frequency region.

15. The apparatus of claim 11, wherein said decomposition and reconstruction wavelet filters further comprise:

circuitry that implements a low-pass decomposition filter using a two-sum filter equation, comprising;

circuitry that operates to implement samples of the data signal in two'"'"'s complement form using a number of bits B;

a low-pass wavelet decomposition filter comprising L low-pass coefficients;

circuitry that operates to compute an inner sum over the L low-pass coefficients comprising each low-pass coefficient multiplied a bth bit of a shifted sample of the data signal; and

circuitry that operates to compute an outer sum over a bit counter b wherein each result of the inner sum is shifted by b bits and wherein b ranges from zero to the number of bits B;

circuitry that computes the inner sum of the two-sum filter equation using a ROM look-up table which is addressed by the bits of the samples of the data signal;

circuitry that computes the outer sum using an adder and shifter;

circuitry that computes a high-pass decomposition wavelet filter using the two-sum filter equation where high-pass decomposition filter coefficients are obtained by reordering the L low-pass decomposition coefficients;

circuitry that computes the low-pass reconstruction wavelet filter using the two-sum filter equation where the low-pass reconstruction filter coefficients are obtained by reordering the L low-pass decomposition coefficients; and

circuitry that computes the high-pass reconstruction wavelet filter using the two-sum filter equation where the high-pass reconstruction filter coefficients are obtained by reordering the L low-pass decomposition coefficients.

16. The apparatus of claim 11, wherein the plurality of wavelet filters compute basis coefficients for a set of basis coefficients by using only a previous set of basis coefficients.

17. A method for compressing and decompressing a data signal, comprising the steps of:

operating on a data signal using a plurality of low-pass and high-pass decompression wavelet filters to compute basis coefficients corresponding to basis functions of the data signal, wherein the basis functions are separated into a plurality of sets, Set 1 through Set M of basis functions that have varying time-frequency characteristics, with Set 1 being narrow in time and broad in frequency, Set M being long in time and narrow in frequency, and Set 2 through Set M-1 being progressively more narrow in frequency and longer in time;

comparing said basis coefficients and selecting a group of basis coefficients to reconstruct the data signal which can be coded with a smaller number of bits than any other group of basis coefficients which alternately could be used to reconstruct the data signal;

ordering the selected group of basis coefficients in descending order of magnitude;

quantizing a magnitude of each basis coefficient in the selected group of basis coefficients;

subtracting the magnitude of each basis coefficient from a magnitude of a previous basis coefficient in the selected group of basis coefficients;

coding the results of the step of subtracting magnitudes using an entropy-based method;

assigning addresses to each basis coefficient in the selected group of basis coefficients according to time and frequency regions covered;

subtracting the address of each basis coefficient in the selected group of basis coefficients from the address of the previous basis coefficient and eliminating the addresses of basis coefficients which cannot be used because they overlap in time or frequency with one or more previously used basis coefficients in the selected group of basis coefficients;

coding the results of the step of subtracting addresses using an entropy-based method; and

decompressing the data signal by performing the steps of comparing and selecting, of quantizing, of subtracting magnitudes, of coding results, of subtracting addresses, and of coding results in revere order, and operating on the result with reconstruction wavelet filters to reconstruct the data signal.

18. The method of claim 17, wherein said step of operating on the data signal to compute basis coefficients involves no multipliers.

19. The method of claim 17, wherein said step of operating on the data signal further comprises the steps of:

expressing a low-pass decomposition wavelet filter in a two-sum filter equation, the two-sum filter equation comprising;

samples of the data signal expressed in two'"'"'s complement form using a number of bits B;

a low-pass wavelet decomposition filter comprising L low-pass coefficients;

an inner sum over the L low-pass coefficients comprising each low-pass coefficient multiplied by the bth bit of a shifted sample of the data signal; and

an outer sum over a bit counter b wherein each result of the inner sum is shifted by b bits and wherein b ranges from zero to the number of bits B;

computing the inner sum of the two-sum filter equation using a ROM look-up table which is addressed by the bits of the samples of the data signal;

computing a high-pass decomposition wavelet filter using the two-sum filter equation where high-pass decomposition filter coefficients are obtained by reordering the L low-pass decomposition coefficients.

20. The method of claim 19, wherein the step of decompressing the data signal further comprises the steps of:

computing the low-pass reconstruction wavelet filter using the two-sum filter equation where the low-pass reconstruction filter coefficients are obtained by reordering the L low-pass decomposition coefficients; and

computing the high-pass reconstruction wavelet filter using the two-sum filter equation where the high-pass reconstruction filter coefficients are obtained by reordering the L low-pass decomposition coefficients.

21. The method of claim 20, wherein said step of decompressing the data signal further comprises:

using a wavelet filter chip employing the reordering of low-pass decomposition coefficients so that low-pass filter outputs and high-pass filter outputs are computed on alternating clock cycles.

22. The method of claim 19, wherein said step of operating on the data signal further comprises:

using a wavelet filter chip employing the reordering of low-pass decomposition coefficients so that low-pass filter outputs and high-pass filter outputs are computed on alternating clock cycles.

23. The method of claim 17, wherein said step of operating on the data signal is accomplished for a set of basis coefficients by using only a previous set of basis coefficients.

24. The method of claim 17, wherein said step of comparing comprises the steps of:

shifting bits of said basis coefficients to determine a number of bits required to encode each of said basis coefficients;

adding the number of bits required to encode each basis coefficient in a group of basis coefficients associated with a time region and a frequency region; and

storing a result of said adding, and selecting a group of said basis coefficients having a lowest added total of required bits associated with said frequency region.

25. A method of computing wavelet coefficients of a data signal and reconstructing the data signal from the wavelet coefficients, comprising the steps of:

expressing a low-pass decomposition wavelet filter in a two-sum filter equation, the two-sum filter equation comprising;

samples of the data signal expressed in two'"'"'s complement form using a number of bits B;

a low-pass wavelet decomposition filter comprising L low-pass coefficients;

an inner sum over the L low-pass coefficients comprising each low-pass coefficient multiplied by a bth bit of a shifted sample of the data signal; and

an outer sum over a bit counter b wherein each result of the inner sum is shifted by b bits and wherein b ranges from zero to the number of bits B;

computing the inner sum of the two-sum filter equation using a ROM look-up table which is addressed by the bits of the samples of the data signal;

computing the outer sum using an adder and shifter;

computing a high-pass decomposition wavelet filter using the two-sum filter equation where high-pass decomposition filter coefficients are obtained by reordering the L low-pass decomposition coefficients;

computing the low-pass reconstruction wavelet filter using the two-sum filter equation where the low-pass reconstruction filter coefficients are obtained by reordering the L low-pass decomposition coefficients; and

computing the high-pass reconstruction wavelet filter using the two-sum filter equation where the high-pass reconstruction filter coefficients are obtained by reordering the L low-pass decomposition coefficients.

26. The method of claim 25, wherein computing wavelet coefficients further comprises:

using a wavelet filter chip employing the reordering of low-pass decomposition coefficients so that low-pass filter outputs and high-pass filter outputs are computed on alternating clock cycles.

27. The method of claim 25, wherein reconstructing the data signal further comprises:

using a wavelet filter chip employing the reordering of low-pass decomposition coefficients so that low-pass filter outputs and high-pass filter outputs are computed on alternating clock cycles.