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

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.

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.

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.

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.

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.