Method and apparatus for compression and decompression of documents and the like using splines and spline-wavelets

• US 5,604,824 A
• Filed: 09/22/1994
• Issued: 02/18/1997
• Est. Priority Date: 09/22/1994
• Status: Expired due to Fees

• Current Assignee: Foto-Wear, Inc.
• Original Assignee: Houston Advanced Research Center
• Inventors: Chui, Charles K., Yuen, Pak-Kay
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Do, Anh Hong
• Application Number:
  US08/310,731
• Time in Patent Office: 880 Days
• Field of Search: 382/56, 382/248, 364/487, 364/481, 364/728.01, 364/421, 364/807, 367/50, 348/407, 73/602
• US Class Current: 382/248
• CPC Class Codes: H04N 19/10 using adaptive coding
• CPC Class Codes: H04N 19/102 characterised by the element, parameter or selection affected or controlled by the adaptive coding
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/635 characterised by filter definition or implementation details
• CPC Class Codes: H04N 19/90 using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals

Abstract

An apparatus and a corresponding method for performing compression and reconstruction of documents are disclosed. Compression of the document is performed by applying a scaling function and a wavelet function first in one direction (e.g., rows) and then in another direction (e.g., columns) to digital data representing the document. The scaling and wavelet functions correspond to spline and wavelet functions that are compactly supported over a convolution interval, and which can also be implemented by way of integer operations. Byte-packing may also be applied to the image data, without regard to pixel boundaries, allowing not only binary (two-color) documents to be compressed but also enabling the compression of more complex color documents. The spline-wavelet compression and reconstruction may be performed according to alternative methods, including dual-base wavelets, interpolatory wavelets, and wavelet packets.

Claims

1. A method of compressing digital data representative of a document, comprising the steps of:

formatting digital data corresponding to an image of the document into a two-dimensional array of digital values, each value corresponding to the appearance of the document at a corresponding location of the document;

performing a first decomposing of the array of digital values, in a first direction, into low-frequency and high-frequency portions by performing integer operations using a decomposition scaling function and a corresponding decomposition wavelet function, respectively, each of said decomposition scaling and wavelet functions described by a finite integer sequence of coefficients, the first decomposing step comprising the substeps of;

convolving the array, in the first direction, with a sequence of integer corresponding to the decomposition scaling function;

convolving the array, in the first direction, with a sequence of integers corresponding to the decomposition wavelet function; and

storing the results of the convolving substeps in memory as an array of first decomposed sequences;

performing a second decomposing of the results of the first decomposing step in a second direction, by performing integer operations using the decomposition scaling and wavelet functions, the second decomposing step comprising the substeps of;

convolving the array. of first decomposed sequences, in the second direction, with the sequence of integers corresponding to the decomposition scaling function;

convolving the array of first decomposed sequences, in the second direction, with the sequence of integers corresponding to the decomposition wavelet function; and

storing the results of the convolving substeps in memory as an array of second decomposed sequences; and

communicating the results of the decomposing steps to a receiving unit.

2. The method of claim 1, wherein said communicating step comprises:

storing the results of the decomposing steps in a memory.

3. The method of claim 1, wherein said communicating step comprises:

transmitting the results of the decomposing steps to a decompression system.

4. The method of claim 3, further comprising:

after the transmitting step, operating the decompression system-to perform a first reconstructing of the transmitted results in the second direction, by performing integer operations using a reconstruction scaling function and a reconstruction wavelet function, said scaling and wavelet functions described by finite integer sequences of coefficients, the first reconstructing step comprising the substeps of;

convolving, in the second direction, a low frequency portion of the transmitted results with a sequence of integers corresponding to the reconstruction scaling function;

convolving, in the second direction, a high frequency portion of the transmitted results with a sequence of integers corresponding to the reconstruction wavelet function; and

summing the results of the convolving substeps into an array of first reconstructed sequences having a low frequency portion and a high frequency portion;

operating the decompression system to perform a second reconstructing of the array of first reconstructed sequences in the first direction, by performing integer operations using the reconstruction scaling function and the reconstruction wavelet function, the second reconstructing step comprising the substeps of;

convolving, in the first direction, the low frequency portion of the array of first reconstructed sequences with a sequence of integers corresponding to the reconstruction scaling function;

convolving, in the first direction, the high frequency portion of the array of first reconstructed sequences with a sequence of integers corresponding to the reconstruction wavelet function; and

summing the results of the convolving substeps into an array of second reconstructed sequences; and

generating a visual output of the results of the reconstructing steps.

5. The method of claim 4, wherein the reconstruction scaling function is equal to the decomposition scaling function, and wherein the reconstruction wavelet function is equal to the decomposition wavelet function.

6. The method of claim 1, further comprising:

before the first decomposing step, projecting the two-dimensional array of digital values into a dual spline approximation coefficient array;

and wherein said first and second decomposing steps are performed using a dual decomposition scaling function and a dual decomposition wavelet function.

7. The method of claim 1, wherein the decomposition scaling function is a centralized B-spline scaling function;

and wherein the decomposition wavelet function is an interpolatory wavelet function corresponding to the centralized B-spline scaling function.

8. The method of claim 1, wherein the results of the second decomposing step comprise:

an LL component, corresponding to the low-frequency component, taken in the second direction, of the low-frequency decomposition in the first direction of the first decomposing step;

an LH component, corresponding to the high-frequency component, taken in the second direction, of the low-frequency decomposition in the first direction of the first decomposing step;

an HL component, corresponding to the low-frequency component, taken in the second direction, of the high-frequency decomposition in the first direction of the first decomposing step; and

an HH component, corresponding to the highfrequency component, taken in the second direction, of the high-frequency decomposition in the first direction of the first decomposing step;

and further comprising;

quantizing the LH, HL, and HH components prior to said communicating step.

9. The method of claim 8, further comprising:

after said quantizing step and prior to said communicating step, performing lossless compression on the LL, LH, HL, and HH components.

10. The method of claim 1, wherein said formatting step comprises:

substituting at least first and second digital values for display attributes corresponding to the image of the document, to generate a substituted array of the at least first and second digital values; and

after said substituting step, byte-packing the substituted array.

11. The method of claim 10, wherein said substituting step substitutes at least first, second and third digital values for display attributes corresponding to the image of the document.

12. The method of claim 1, wherein each of the decomposition scaling function and the decomposition wavelet function does not require support from outside of the array.

13. The method of claim 1, wherein each integer sequence of coefficients expressing the decomposition scaling function and the decomposition wavelet function is symmetric.

14. The method of claim 1, further comprising:

prior to the communicating step, repeating the steps of performing a first decomposing and a second decomposing upon the array of second decomposed sequences.

15. A method of compressing digital data representative of a document, comprising the steps of:

formatting digital data corresponding to an image of the document into a two-dimensional array of digital values, each value corresponding to the appearance of the document at a corresponding location of the document;

performing a first decomposing of the array of digital values, in a first direction, into low-frequency and high-frequency portions using a decomposition scaling function and a corresponding decomposition wavelet function, respectively, wherein the decomposition scaling function and decomposition wavelet functions are based upon non-orthogonal, symmetric, spline-based wavelet packets, the first decomposing step comprising the substeps of;

(a) decomposing the array of digital values, in the first direction, into a first low-frequency portion and a first high-frequency portion using the decomposition scaling function and the decomposition wavelet function, respectively;

(b) decomposing the first low-frequency portion, in the first direction, into a low-low frequency portion and a low-high-frequency portion using the decomposition scaling function and the decomposition wavelet function, respectively; and

(c) decomposing the high-frequency portion from substep (a), in the first direction, into a high-low-frequency portion and a high-high-frequency portion using the decomposition wavelet function and the decomposition scaling function, respectively;

performing a second decomposing of the results of the first decomposing step in a second direction, using the decomposition scaling and wavelet functions, the second decomposing step comprising the substeps of;

(d) decomposing the results of the first decomposing step, in the second direction, into a plurality of second-stage low-frequency portions and a plurality of second-stage high-frequency portion using the decomposition scaling function and the decomposition wavelet function, respectively;

(e) decomposing the plurality of second stage low-frequency portions from step (d), in the second direction, into a first plurality of third-stage low-frequency portions and a first plurality of third-stage high-frequency portions using the decomposition scaling function and the decomposition wavelet function, respectively; and

(f) decomposing the plurality of second stage high-frequency portion from the step (e), in the second direction, into a second plurality of third-stage low-frequency portions and a second plurality of third-stage high-frequency portions using the decomposition wavelet function and the decomposition scaling function, respectively; and

communicating the results of the decomposing steps to a receiving unit.

16. The method of claim 15, further comprising:

before the communicating steps, repeating the steps of performing a first decomposing and performing a second decomposing upon the second plurality of third-stage low-frequency portions and a second plurality of third-stage high-frequency portions.

17. A method of displaying compressed document image data, comprising:

receiving compressed image data corresponding to a document and storing the compressed image data in memory, said compressed image data arranged as blur and high-frequency coefficient sequences;

in a first image direction, applying a reconstruction scaling function and a reconstruction wavelet function, each of said reconstruction scaling function and reconstruction wavelet function described by a finite integer sequence of coefficients so that the applying is performed by using integer operations, to the compressed image data to reconstruct a low-frequency component and a high-frequency component, the applying step in the first direction comprising the substeps of;

convolving, in the first direction, the blur coefficient sequences of the transmitted results with a sequence of integers corresponding to the reconstruction scaling function;

convolving, in the first direction, the high frequency coefficient sequences of the transmitted results with a sequence of integers corresponding to the reconstruction wavelet function; and

summing the results of the convolving substeps into an array of first reconstructed sequences having a low frequency component and a high frequency component;

in a second image direction, applying the reconstruction scaling function and the reconstruction wavelet function to the reconstructed low-frequency component and high-frequency component, respectively, using integer operations, to reconstruct the document image, the applying step in the second image direction comprising the substeps of;

convolving, in the second direction, the low frequency component of the array of first reconstructed sequences with a sequence of integers corresponding to the reconstruction scaling function;

convolving, in the second direction, the high frequency component of the array of first reconstructed sequences with a sequence of integers corresponding to the reconstruction wavelet function; and

summing the results of the convolving substeps into an array of second reconstructed sequences; and

displaying the reconstructed document image.

18. The method of claim 17, further comprising:

before the displaying step, repeating said steps of applying the reconstruction scaling function and the reconstruction wavelet function in the first and second image directions.

19. The method of claim 17, further comprising:

performing lossless decompression on the compressed document image data, prior to said applying steps.

20. The method of claim 17, further comprising:

transforming the compressed image data into dual spline coefficient sequences;

and wherein said first and second decomposing steps are performed using the dual decomposition scaling function and the dual decomposition wavelet function.

21. The method of claim 17, wherein the reconstruction scaling function is a centralized B-spline scaling function;

and wherein the reconstruction wavelet function is an interpolatory wavelet function corresponding to the centralized B-spline scaling function.

22. The method of claim 17, wherein each of the reconstruction scaling function and the reconstruction wavelet function does not require support from outside of the array.

23. The method of claim 17, wherein each integer sequence of coefficients expressing the reconstruction scaling function and the reconstruction wavelet function is symmetric.

24. A method of displaying compressed image data contained within first and second groups of coefficient sequences, each of the first and second groups having at least one non-zero coefficient sequence therein, comprising the steps of:

receiving compressed image data corresponding to a document and storing the compressed image data in memory;

in a first image direction, applying a reconstruction scaling function and a reconstruction wavelet function to the compressed image data, wherein the reconstruction scaling and wavelet functions are based upon non-orthogonal, symmetric, spline-based wavelet packets, wherein the step of applying the reconstruction scaling and wavelet functions in a first image direction comprises the substeps of;

convolving the reconstruction scaling function with the first group of coefficient sequences, in the first image direction;

convolving the reconstruction wavelet function with the second group of coefficient sequences, in the first image direction;

after the convolving steps, summing each of the first group of coefficient sequences to an associated one of the second group of coefficient sequences, to produce third and fourth groups of coefficient sequences, each having at least one non-zero coefficient sequence;

after the summing step, convolving the reconstruction scaling function with the third group of coefficient sequences, in the first image direction;

convolving the reconstruction wavelet function with the fourth group of coefficient sequences, in the first image direction; and

then summing each of the third group of coefficient sequences to an associated one of the fourth group of coefficient sequences, to produce fifth and sixth groups of coefficient sequences, each having at least one non-zero coefficient sequence;

in a second image direction, applying the reconstruction scaling and wavelet functions in a second direction by the substeps of;

convolving the reconstruction scaling function with the fifth group of coefficient sequences, in the second image direction;

convolving the reconstruction wavelet function with the sixth group of coefficient sequences, in the second image direction;

after the convolving steps, summing each of the fifth group of coefficient sequences to an associated one of the sixth group of coefficient sequences, to produce a low-frequency component and a high-frequency component of the document image;

after the summing step, convolving the reconstruction scaling function with the low-frequency component of the document image, in the second image direction;

convolving the reconstruction wavelet function with the high-frequency component of the document image, in the second image direction; and

then summing the low-frequency and high-frequency components to produce an array corresponding to the document image; and

displaying the reconstructed document image.

25. The method of claim 24, further comprising:

before the step of applying a reconstruction scaling function and a reconstruction wavelet function in a first image direction, reading a tree map in the compressed image data to determine the ones of the first and second groups of coefficient sequences that are present in the compressed image data.

37. The method of claim 24, further comprising:

before the displaying step, repeating the steps of applying a reconstruction scaling function and a reconstruction wavelet function in a first image direction and of applying a reconstruction scaling function and a reconstruction wavelet function in a second image direction.

26. A system for communicating image information corresponding to documents, comprising:

an input source for providing digital image information corresponding to a document to be communicated; and

compressor circuitry having an input coupled to said input source, for decomposing each frame of digital image information in a first image direction, by performing finite integer matrix multiplications of the digital image information using a scaling function and a corresponding wavelet function that are described by finite integer sequences of coefficients, into a first low-frequency component and a first high-frequency component, by performing the operations of;

convolving a frame, in the first image direction, with a sequence of integers corresponding to the decomposition scaling function;

convolving the frame, in the first image direction, with a sequence of integers corresponding to the decomposition wavelet function; and

storing the results of the convolving operations in memory as an array containing the first low-frequency component and the first high-frequency component;

and for then further decomposing each of said low-frequency and high-frequency components of each frame of digital video image information in a second image direction, by performing finite integer matrix multiplications of the first low-frequency and high-frequency components using the scaling function and the corresponding wavelet function, into first and second pairs of low-frequency and second high-frequency components, said first pair being the decomposed representation of said first low-frequency component and said second pair corresponding to a decomposed representation of said first high-frequency component, by performing the operations of;

convolving each of the first low-frequency and high-frequency components, in the second image direction, with the sequence of integers corresponding to the decomposition scaling function;

convolving each of the first low-frequency and high-frequency components, in the second image direction, with the sequence of integers corresponding to the decomposition wavelet function; and

storing the results of the convolving operations in memory as an array of the first and second pairs of low-frequency and high-frequency components;

said compressor circuitry also having an output for presenting the first and second pairs of low-frequency and high-frequency components.

27. The system of claim 26, further comprising:

a format converter circuit coupled between said input source and said compressor, for converting the digital input video information into a portable gray-level format.

28. The system of claim 27, wherein the format converter circuit comprises circuitry for byte-packing data corresponding to image data received from the input source.

29. The system of claim 28, wherein said input source provides color document information;

and wherein said byte-packing circuitry performs byte-packing of data containing more than one bit per picture element of the document.

30. The system of claim 26, wherein said compressor circuitry comprises:

decomposing circuitry for performing the decomposing of each frame of digital image information into the first and second pairs of low-frequency and high-frequency components;

quantization circuitry for quantizing the high-frequency component of said first pair, and for quantizing both the low-frequency and the high-frequency components of the second pair; and

lossless compression circuitry, having an input coupled to said quantization circuitry, for performing lossless compression of the first and second low-frequency and high-frequency pairs, prior to presenting the decomposed flames of digital video image information at the output of the compressor circuitry.

31. The system of claim 30, further comprising:

main controller circuitry, for controlling the operation of the decomposing circuitry, so that the low-frequency component of said first pair may be repetitively provided to the decomposing circuitry for further decomposing.

32. The system of claim 26, wherein said compressor circuitry comprises:

an image buffer coupled to the input of the compressor circuitry for storing a frame of digital video image information; and

a digital processor for performing the decomposing of each frame of digital image information into the first and second pairs of low-frequency and high-frequency components by performing finite integer matrix multiplications of the digital image information using a scaling function and a corresponding wavelet function that do not require support outside of the digital image interval.

33. The system of claim 32, wherein said digital processor operates according to matrix operations using precalculated matrices corresponding to spline and wavelet function coefficient sequences stored in said compressor circuitry.

34. The system of claim 33, further comprising:

a communications network coupled to the output of the compressor circuitry;

decompressor circuitry, having an input coupled to said communications network, for reconstructing the decomposed digital image information in the second image direction by performing finite integer matrix multiplications of the digital image information using a reconstruction scaling function and a corresponding reconstruction wavelet function, by performing the operations of;

convolving, in the second image direction, a low frequency portion of the decomposed digital image information with a sequence of integers corresponding to the reconstruction scaling function;

convolving, in the second image direction, a high frequency portion of the transmitted results with a sequence of integers corresponding to the reconstruction wavelet function; and

summing the results of the convolving operations into an array of first reconstructed sequences having a low frequency portion and a high frequency portion;

and for then further reconstructing the array of first reconstructed sequences in the first image direction by performing finite integer matrix multiplications of the digital image information using the reconstruction scaling and wavelet functions by performing the operations of;

convolving, in the first image direction, the low frequency portion of the array of first reconstructed sequences with a sequence of integers corresponding to the reconstruction scaling function;

convolving, in the first image direction, the high frequency portion of the array of first reconstructed sequences with a sequence of integers corresponding to the reconstruction wavelet function; and

summing the results of the convolving operations into an array of second reconstructed sequences; and

means for displaying the reconstructed frames of digital image information.

35. The system of claim 26, wherein each of the scaling function and the corresponding wavelet function does not require support from outside of the array.

36. The system of claim 26, wherein each of the integer sequences of coefficients is symmetric.

38. A system for displaying compressed image data corresponding to a document, comprising:

a memory for storing the compressed image data;

decompressor circuitry for reconstructing the compressed image data in a first image direction by performing finite integer matrix multiplications of the digital image information using a reconstruction scaling function and a corresponding reconstruction wavelet function that are described by finite integer sequences of coefficients, by performing the operations of;

convolving, in the first image direction, a low frequency portion of the compressed image data with a sequence of integers corresponding to the reconstruction scaling function;

convolving, in the first image direction, a high frequency portion of the compressed image data with a sequence of integers corresponding to the reconstruction wavelet function; and

summing the results of the convolving operations into an array of first reconstructed sequences having a low frequency portion and a high frequency portion;

and for then further reconstructing the compressed image data in a second image direction by performing finite integer matrix multiplications of the array of first reconstructed sequences using the reconstruction scaling and wavelet functions by performing the operations of;

convolving, in the second image direction, the low frequency portion of the array of first reconstructed sequences with a sequence of integers corresponding to the reconstruction scaling function;

convolving, in the second image direction, the high frequency portion of the array of first reconstructed sequences with a sequence of integers corresponding to the reconstruction wavelet function; and

summing the results of the convolving operations into an array of second reconstructed sequences; and

means, coupled to said decompressor circuitry, for outputting the reconstructed compressed image data.

39. The system of claim 38, wherein said memory is coupled to a communications network.

40. The system of claim 38, wherein said decompressor circuitry comprises:

a digital processor coupled to said memory, for reconstructing the digital image information using precalculated matrices of integers.

41. The system of claim 38, wherein each of the reconstruction scaling function and the corresponding reconstruction wavelet function does not require support from outside of the array.

42. The system of claim 38, wherein each of the integer sequences of coefficients is symmetric.