Dual stage compression of bit mapped image data using refined run length and LZ compression
First Claim
1. A digital data lossless compression apparatus, comprising:
- a source of binary format serial input data;
first compression means for receiving the serial input data and run length compressing the binary format serial input data into first data units of a fixed first size;
means for coding the first data units of fixed first size to individually represent run lengths of consistent binary value as appears within the serial input data;
second compression means for receiving succession of first data units of fixed first size and Lempel-Ziv sliding window compressing the first data units of fixed first size into tokens of both fixed size types and variable size types; and
means for transmitting the tokens.
3 Assignments
0 Petitions
Accused Products
Abstract
A dual stage data lossless compressor for optimally compressing bit mapped imaged data. The first stage run length compresses data bits representing pixel positions along a scan line of a video image to data units of fixed length. The units alternate to represent runs of alternate video image data values. The run length compressed data units are subject to second stage compression using a sliding window Lempel-Ziv compressor. The output from the Lempel-Ziv compressor includes raw tokens of fixed length and compressed tokens of varying lengths. The combination of a run length precompressor and a sliding window Lempel-Ziv post compressor, in which the run length compressor output is a succession of data units of fixed length, provides an optimum match between the capabilities and idiosyncracies of the two compressors, and related decompressors, when processing business form data images. Furthermore, the asymmetric simplicity of Lempel-Ziv sliding window decompression and run length decompression simplicity leads to a decompression speed compatible with contemporary applications.
-
Citations
24 Claims
-
1. A digital data lossless compression apparatus, comprising:
-
a source of binary format serial input data; first compression means for receiving the serial input data and run length compressing the binary format serial input data into first data units of a fixed first size; means for coding the first data units of fixed first size to individually represent run lengths of consistent binary value as appears within the serial input data; second compression means for receiving succession of first data units of fixed first size and Lempel-Ziv sliding window compressing the first data units of fixed first size into tokens of both fixed size types and variable size types; and means for transmitting the tokens. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A method of losslessly compressing digital data, comprising the steps of:
-
receiving binary format serial input data; run length compressing received binary format serial input data into first data units of a fixed first size; coding the first data units of fixed first size to individually represent run lengths of consistent binary value as appears within the serial input data; Lempel-Ziv sliding window compressing a succession of first data units of fixed first size into tokens of both fixed size types and variable size types; and transmitting the tokens. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
Specification