Data compression of bit map images

• US 5,611,024 A
• Filed: 08/28/1992
• Issued: 03/11/1997
• Est. Priority Date: 08/28/1992
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Adams, Greg, Braaten, Jeffrey M., Campbell, Scott O.
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): Popovici, Dov
• Application Number:
  US07/937,504
• Time in Patent Office: 1,656 Days
• Field of Search: 395/114-116, 395/112, 395/101, 358/426, 358/261.1, 358/261.2, 358/261.3, 358/261.4, 358/444, 358/427, 358/430, 358/432, 358/433, 341/107, 341/87, 341/51, 341/67, 382/232
• US Class Current: 358/1.15
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

A method and apparatus for storing compressed bit map images in a laser printer. Bit map images representing a page of data are divided into bands and compressed into the printer memory. Then, when needed by the interpreter/rasterizer, they are decompressed into another portion of that memory, or when desired to print those bands they are directly transmitted to a decompression engine. The bands of bit map image are compressed using a Lempel-Ziv algorithm that contains improvements allowing compression towards the end of the band and improves the compression speed at the beginning of the band by initializing a hash table. Further, the interpreter/rasterizer switches between compression routines depending on the available memory and the desired speed of compression. The compression routine requests supplemental destination buffers when it needs additional memory in which to compress data. Finally, the compression continues to add margin white space during the compression of the uncompressed bit images so that margin what space need not be stored in the uncompressed bit image.

Claims

1. A method of storing a bit image in a memory of a laser printer that contains the memory, an interpreter/rasterizer, and a print engine, the method comprising:

receiving a stream of page description language codes into the printer;

converting said page description language codes into a bit image by interpreting the page description language codes in the interpreter/rasterizer;

compressing said bit image into a compressed bit image whereby storage of said compressed bit image requires less memory space than storage of the bit image, yet said compressed bit image retains all of the information contained in the bit image whereby an identical copy of said bit image is extractable from said compressed bit image, the step of compressing the bit image further comprising the steps of;

initially compressing portions of the bit image using a first compression algorithm;

after said compressing using said first compression algorithm, determining if said compressed bit image that said

first compression algorithm yields has a compression ratio above a predetermined limit; and

if determined that said compressed bit image that said first compression algorithm yielded does not have a compression ratio greater than said predetermined limit, compressing said portions of the bit image using a second compression algorithm, wherein said second compression algorithm is computationally more complex than said first compression algorithm but said compressed portions of the bit image yielded by said second compression algorithm is smaller than said compressed bit image yielded by said first compression algorithm;

storing said compressed bit image into a specified portion of the memory;

decompressing said compressed bit image whereby said decompressed bit image is identical to the bit image that was initially compressed; and

sending said decompressed bit image to the print engine.

2. A method of storing a bit image in a memory of a laser printer that contains the memory, an interpreter/rasterizer, and a print engine, the method comprising:

receiving a stream of page description language codes into the printer;

converting said page description language codes into a bit image by interpreting the page description language codes in the interpreter/rasterizer;

compressing said bit image into a compressed bit image whereby storage of said compressed bit image requires less memory

compressing said bit image into a compressed bit image whereby storage of said compressed bit image requires less memory space than storage of the bit image, yet said compressed bit image retains all of the information contained in the bit image whereby an identical copy of said bit image is extractable from said compressed bit image, the step of compressing the bit image further comprising the steps of;

initially compressing portions of said bit image using a first compression algorithm;

after said compressing using said first compression algorithm, determining if said compressed bit image that said first compression algorithm yields has a compression ratio above a predetermined limit; and

if determined that said compressed bit image that said first compression algorithm yielded does not have a compression ratio greater than said predetermined limit, compressing subsequent portions of the bit image using a second compression algorithm, wherein said second compression algorithm is computationally more complex then said first compression algorithm but said compressed subsequent portions of the bit image yielded by said second compression algorithm are smaller then would be compressed subsequent portions of said bit image if said subsequent portions of said bit image were compressed by said first compression algorithm;

storing said compressed bit image into a specified portion of the memory;

decompressing said compressed bit image whereby said decompressed bit image is identical to the bit image that was initially compressed; and

sending said decompressed bit image to the print engine.

3. A method of storing a bit image in a memory of a laser printer that contains the memory, an interpreter/rasterizer, and a print engine, the method comprising:

receiving a stream of page description language codes into the printer;

converting said page description language codes into a bit image by interpreting the page description language codes in the interpreter/rasterizer;

compressing said bit image into a compressed bit image whereby storage of said compressed bit image requires less memory space than storage of the bit image, yet said compressed bit image retains all of the information contained in the bit image whereby an identical copy of said bit image is extractable from said compressed bit image;

storing said compressed bit image into a specified portion of the memory;

decompressing said compressed bit image whereby said decompressed bit image is identical to the bit image that was initially compressed; and

sending said decompressed bit image to the print engine,

wherein the step of compressing said bit image comprises the step of using a Lempel-Ziv algorithm to compress said bit image,

wherein said Lempel-Ziv algorithm maintains a maximum copy count variable, wherein said Lempel-Ziv algorithm initializes said maximum copy count variable to a first predetermined value, and when said Lempel-Ziv algorithm attempts to compress data within a predetermined number of bytes from the end of the bit image, said Lempel-Ziv algorithm reduces the value of said maximum copy count variable.

4. A method of storing a bit image in a memory of a laser printer that contains the memory, an interpreter/rasterizer, and a print engine, the method comprising:

compressing a portion of a bit image stored in a source block of memory into a compressed bit image and storing said compressed bit image into a first destination block of memory, stopping said compressing when either all of said bit image has been compressed or said first destination block of memory is full, whereby storage of said compressed bit image requires less memory space than storage of the bit image, yet said compressed bit image retains all of the information contained in the bit image whereby an identical copy of the bit image is extractable from said compressed bit image; and

if said first destination block of memory is full, requesting a second destination block of memory, and then performing said compressing step to compress to said second destination block of memory instead of said first destination block of memory; and

repeating until the bit image in said source block is fully compressed,

wherein said requesting said second destination block of memory comprises the steps of;

determining the desired size of said second destination block of memory by use of the equation

space="preserve" listing-type="equation">m=(s2÷

(s1+d1))

where

m is the desired size of said second destination block of memory

s1 is the size of that portion of said source block of memory that was compressed to said first destination block of memory

d1 is the size of said first destination block of memory

s2 is the size of that portion of said source block of memory that was not compressed to said first destination block of memory; and

requesting said second destination block of memory of size m.

5. A laser printer comprising:

memory;

means for converting page description language codes into a bit image by interpreting the page description language codes;

a print engine;

means for receiving a stream of page description language codes into the printer and providing them to said means for converting;

means for compressing the bit image developed by said means for converting into a compressed bit image whereby storage of said compressed bit image requires less memory space than storage of the bit image, yet said compressed bit image retains all of the information contained in the bit image whereby an identical copy of the bit image is extractable from said compressed bit image, said means for compressing further comprising;

means for initially compressing portions of the bit image using a first compression algorithm;

means for determining if said compressed bit image that said first compression algorithm yields has a compression ratio above a predetermined limit; and

means for compressing said portions of the bit image using a second compression algorithm if said compressed bit image that said first compression algorithm yields does not have a compression ratio above a predetermined limit, wherein said second compression algorithm is computationally more complex than said first compression algorithm but said compressed portions of the bit image yielded by said second compression algorithm is smaller than said compressed bit image yielded by said first compression algorithm;

means for storing said compressed bit image into a specified portion of the memory;

means for decompressing said compressed bit image whereby the decompressed bit image is identical to the bit image that was initially compressed; and

means for sending said decompressed bit image to said print engine.

6. A laser printer comprising:

memory;

means for converting page description language codes into a bit image by interpreting the page description language codes;

a print engine;

means for receiving a stream of page description language codes into the printer and providing them to said means for converting;

means for compressing the bit image developed by said means for converting into a compressed bit image whereby storage of said compressed bit image requires less memory space than storage of the bit image, yet said compressed bit image retains all of the information contained in the bit image whereby an identical copy of the bit image is extractable from said compressed bit image, said means for compressing further comprising;

means for initially compressing portions of said bit image using a first compression algorithm;

means for determining if said compressed bit image that said first compression algorithm yields has a compression ratio above a predetermined limit; and

means for compressing subsequent portions of the bit image using a second compression algorithm if said compressed bit image that said first compression algorithm yielded does not have a compression ratio greater than said predetermined limit, wherein said second compression algorithm is computationally more complex then said first compression algorithm but said compressed subsequent portions of the bit image yielded by said second compression algorithm are smaller then would be compressed subsequent portions of said bit image if said subsequent portions of said bit image were compressed by said first compression algorithm;

means for storing said compressed bit image into a specified portion of the memory;

means for decompressing said compressed bit image whereby the decompressed bit image is identical to the bit image that was initially compressed; and

means for sending said decompressed bit image to said print engine.

7. A laser printer comprising:

memory;

means for converting page description language codes into a bit image by interpreting the page description language codes;

a print engine;

means for receiving a stream of page description language codes into the printer and providing them to said means for converting;

means for compressing the bit image developed by said means for converting into a compressed bit image whereby storage of said compressed bit image requires less memory space than storage of the bit image, yet said compressed bit image retains all of the information contained in the bit image whereby an identical copy of the bit image is extractable from said compressed bit image, said means for compressing further comprising;

means for using a Lempel-Ziv algorithm to compress said bit image in which said Lempel-Ziv algorithm maintains a maximum copy count variable, wherein said Lempel-Ziv algorithm comprises;

means for initializing said maximum copy count variable to a first predetermined value and for reducing the value of said maximum copy count variable when said Lempel-Ziv algorithm attempts to compress data within a predetermined number of bytes from the end of the bit image;

means for storing said compressed bit image into a specified portion of the memory;

means for decompressing said compressed bit image whereby the decompressed bit image is identical to the bit image that was initially compressed; and

means for sending said decompressed bit image to said print engine.