Dual stage compression of bit mapped image data using refined run length and LZ compression

• US 5,627,534 A
• Filed: 03/23/1995
• Issued: 05/06/1997
• Est. Priority Date: 03/23/1995
• Status: Expired due to Term

• Current Assignee: Pendragon Networks LLC (Pendrell Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Craft, David J.
• Primary Examiner(s): Gaffin, Jeffrey A.
• Assistant Examiner(s): VICK, JASON
• Application Number:
  US08/409,766
• Time in Patent Office: 775 Days
• Field of Search: 341/51, 341/55, 341/63, 341/67, 341/82, 341/87, 341/107
• US Class Current: 341/87
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: G06V 10/421 by analysing segments intersecting the pattern
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

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.

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.

2. The apparatus recited in claim 1, further comprising:

memory means for receiving and storing the tokens.

3. The apparatus recited in claim 2, wherein the binary format serial input data is a bit mapped video image in raster scan line format.

4. The apparatus recited in claim 3, wherein the first data units are of byte size with the byte code indicating changes in the binary value.

5. The apparatus recited in claim 4, wherein the second compression means uses a content addressable memory (CAM) and generates raw and compressed tokens.

6. The apparatus recited in claim 1, wherein the means for transmitting is an audio-visual communication media.

7. The apparatus recited in claim 6, wherein the binary format serial input data is a bit mapped video image in raster scan line format.

8. The apparatus recited in claim 7, wherein the first data units are of byte size with the byte code indicating changes in the binary value.

9. The apparatus recited in claim 8, wherein the second compression means uses a content addressable memory (CAM) and generates raw and compressed tokens.

10. The apparatus recited in claim 1, wherein the binary format serial input data is a bit mapped video image in raster scan line format.

11. The apparatus recited in claim 10, wherein the first data units are of byte size with the byte code indicating changes in the binary value.

12. The apparatus recited in claim 11, wherein the second compression means uses a content addressable memory (CAM) and generates raw and compressed tokens.

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.

14. The method recited in claim 13, further comprising the step of:

storing received tokens in a memory.

15. The method recited in claim 14, wherein the binary format serial input data is a bit mapped video image in raster scan line format.

16. The method recited in claim 15, wherein the first data units are of byte size with the byte code indicating changes in the binary value.

17. The method recited in claim 16, wherein the Lempel-Ziv sliding window compressing is performed with a content addressable memory (CAM) and generates raw and compressed tokens.

18. The method recited in claim 13, wherein the step of transmitting is performed over an audio-visual communication media.

19. The method recited in claim 18, wherein the binary format serial input data is a bit mapped video image in raster scan line format.

20. The method recited in claim 19, wherein the first data units are of byte size with the byte code indicating changes in the binary value.

21. The method recited in claim 20, wherein the Lempel-Ziv sliding window compressing is performed with a content addressable memory (CAM) and generates raw and compressed tokens.

22. The method recited in claim 13, wherein the binary format serial input data is a bit mapped video image in raster scan line format.

23. The method recited in claim 22, wherein the first data units are of byte size with the byte code indicating changes in the binary value.

24. The method recited in claim 23, wherein the Lempel-Ziv sliding window compressing is performed with a content addressable memory (CAM) and generates raw and compressed tokens.