Method and apparatus for compressing and decompressing print data in the background operations of a printer

• US 6,038,033 A
• Filed: 08/20/1997
• Issued: 03/14/2000
• Est. Priority Date: 08/20/1997
• Status: Expired due to Term

• Current Assignee: Lexmark International Incorporated (Ninestar Corporation)
• Original Assignee: Lexmark International Incorporated (Ninestar Corporation)
• Inventors: Bender, Michael Donald, Songer, Christopher Mark
• Primary Examiner(s): Coles, Edward L.
• Assistant Examiner(s): HASKINS, TWYLER LAMB
• Application Number:
  US08/915,183
• Time in Patent Office: 937 Days
• Field of Search: 395/115, 395/116, 395/114, 395/101, 395/112, 395/110, 395/102, 358/444, 358/448, 358/404, 358/401, 358/296, 358/400, 358/1.16, 358/1.17, 358/1.15, 358/1.1, 358/1.13, 358/1.11, 358/1.2, 364/900
• US Class Current: 358/1.16
• CPC Class Codes: G06K 15/02 using printers
• CPC Class Codes: G06K 2215/0071 Post-treatment of the composed image, e.g. compression, rotation
• CPC Class Codes: H04N 1/32448 Controlling data flow to or from the memory in relation to the available memory capacity
• CPC Class Codes: H04N 1/41 Bandwidth or redundancy reduction by scanning H04N1/17 ; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: H04N 2201/329 Storage of less than a complete document page or image frame

Abstract

An improved printer is provided which includes a separate hardware compression module and hardware decompression module contained within the ASIC of the print engine. A "Request Counter" register is decremented each time memory is requested to store a block of bitmap image data. When the Request Counter decreases to a predetermined value, the current size of the remaining "free memory" space is evaluated. If this free memory is less than another predetermined value (a "low water mark"), then blocks of data that have already been stored in the printer'"'"'s memory are sent to the compression module to be compressed before the printer literally runs out of free memory, and the printer can continue storing and processing more incoming print job data. By thus preserving some of the free memory, the printer can continue to process or rasterize more print data while the compression hardware simultaneously operates independently to compress one or more blocks of data. Since the compressor hardware operate independently of the printer'"'"'s microprocessor, the printer can continue to process further data during the actual compression operations, thereby preventing the printer'"'"'s microprocessor from becoming idle, which otherwise would become a very inefficient utilization of the printer'"'"'s processing power. The present invention is especially useful in processing color data, especially in printers containing relatively small quantities of RAM, since color data typically requires four (4) planes of bitmap image data per page to be printed.

Claims

1. In an image processing system having a memory circuit for storing information, a data compression circuit, an image output device, and a processing circuit that controls the routing of data between said memory circuit, data compression circuit, and image output device;

a method for selectively compressing image data, said method comprising the steps of;

(a) selecting a predetermined threshold value of memory size;

(b) dividing a page of image data into a plurality of blocks;

(c) initiating processing of each of said plurality of blocks of image data;

(d) comparing the actual size of free memory space within said memory circuit with respect to said predetermined threshold value, and;

(i) if said actual size of free memory space is greater than said predetermined threshold value, temporarily storing at least one of said plurality of blocks of image data in said memory circuit; and

(ii) if said actual size of free memory space is not greater than said predetermined threshold value, compressing at least one of said plurality of blocks of image data via said data compression circuit, and temporarily storing said at least one of said plurality of blocks of compressed image data in said memory circuit, while virtually simultaneously continuing processing of said plurality of blocks of image data using available free memory space of said memory circuit.

2. The method as recited in claim 1, further comprising the step of selecting said blocks for compression according to a priority, wherein the blocks selected first are the "oldest" blocks currently contained in said memory circuit.

3. The method as recited in claim 1, further comprising the steps of excluding certain of said blocks from being compressed, including those of said blocks that:

(a) fail to compress to a desired compression ratio;

(b) cause the number of uncompressed blocks to fall below a predetermined minimum number;

(c) fall within an active region of a page currently being processed.

4. In an image processing system having a memory circuit for storing information, a data compression circuit, an image output device, and a processing circuit that controls the routing of data between said memory circuit, data compression circuit, and image output device;

a method for selectively compressing image data, said method comprising the steps of;

(a) setting a Request Counter to a predetermined value, and selecting a first predetermined threshold value and a second predetermined threshold value;

(b) dividing a page of image data into a plurality of blocks;

(c) initiating processing of each of said plurality of blocks of image data;

(d) said Request Counter'"'"'s value is not greater than said first threshold value, comparing the actual size of free memory space within said memory circuit with respect to said second threshold value, and;

(i) said actual size of free memory space is greater than said second threshold value, temporarily storing at least one of said plurality of blocks of image data in said memory circuit;

(ii) if said actual size of free memory space is not greater than said second threshold value, compressing at least one of said plurality of blocks of image data via said data compression circuit, and temporarily storing said at least one of said plurality of blocks of compressed image data in said memory circuit,

virtually simultaneously continuing processing of said plurality of blocks of image data using available free memory space of said memory circuit; and

(e) if said Request Counter'"'"'s value is greater than said first threshold value, decreasing said Request Counter'"'"'s value upon each occurrence of storing one of said plurality of blocks.

5. The method as recited in claim 4, further comprising the steps of:

(a) successively retrieving each of said plurality of blocks of uncompressed image data in said memory circuit and communicating said blocks to said image output device, and increasing said Request Counter'"'"'s value upon each occurrence of retrieving one of said plurality of blocks; and

(b) retrieving and decompressing each of said plurality of blocks of compressed image data in said memory circuit, via a data decompression circuit, and communicating said blocks to said image output device,

virtually simultaneously continuing processing of said plurality of blocks of image data using available free memory space of said memory circuit.

6. The method as recited in claim 4, further comprising the step of selecting said blocks for compression according to a priority, wherein the blocks selected first are the "oldest" blocks currently contained in said memory circuit.

7. The method as recited in claim 4, wherein the step of setting said Request Counter to a predetermined value is determined by the manufacturer of said image processing system for a particular print resolution, and said predetermined value is related to the number or uncompressed image data blocks that can be stored in the image processing system'"'"'s memory circuit before requiring the initiation of compressing said image data blocks.

8. The method as recited in claim 5, further comprising the step of selecting said blocks for decompression according to a priority, wherein the blocks selected first are blocks that are to be displayed next, and blocks selected second are blocks needed by an interpreter for further image processing.

9. The method as recited in claim 4, further comprising the steps of excluding certain of said blocks from being compressed, including those of said blocks that:

(a) fail to compress to a desired compression ratio;

(b) cause the number of uncompressed blocks to fall below a predetermined minimum number;

(c) fall within an active region of a page currently being processed.

10. In a printing system having a memory circuit for storing information, a data compression circuit, a print engine, and a processing circuit that controls the routing of data between said memory circuit, data compression circuit, and print engine;

a method for selectively compressing image data, said method comprising the steps of;

(a) selecting a predetermined threshold value of memory size;

(b) dividing a page of image data into a plurality of blocks;

(c) initiating processing of each of said plurality of blocks of image data;

(d) comparing the actual size of free memory space within said memory circuit with respect to said predetermined threshold value, and;

(i) if said actual size of free memory space is greater than said predetermined threshold value, temporarily storing at least one of said plurality of blocks of image data in said memory circuit; and

(ii) if said actual size of free memory space is not greater than said predetermined threshold value, compressing at least one of said plurality of blocks of image data via said data compression circuit, and temporarily storing said at least one of said plurality of blocks of compressed image data in said memory circuit, while virtually simultaneously continuing processing of said plurality of blocks of image data using available free memory space of said memory circuit.

11. The method as recited in claim 10, further comprising the step of selecting said blocks for compression according to a priority, wherein the blocks selected first are the "oldest" blocks currently contained in said memory circuit.

12. The method as recited in claim 10, further comprising the steps of excluding certain of said blocks from being compressed, including those of said blocks that:

(a) fail to compress to a desired compression ratio;

(b) cause the number of uncompressed blocks to fall below a predetermined minimum number;

(c) fall within an active region of a page currently being processed.

13. In a printing system having a memory circuit for storing information, a data compression circuit, a print engine, and a processing circuit that controls the routing of data between said memory circuit, data compression circuit, and print engine;

a method for selectively compressing image data, said method comprising the steps of;

(a) setting a Request Counter to a predetermined value, and selecting a first predetermined threshold value and a second predetermined threshold value;

(b) dividing a page of image data into a plurality of blocks;

(c) initiating processing of each of said plurality of blocks of image data;

(d) said Request Counter'"'"'s value is not greater than said first threshold value, comparing the actual size of free memory space within said memory circuit with respect to said second threshold value, and;

(i) said actual size of free memory space is greater than said second threshold value, temporarily storing at least one of said plurality of blocks of image data in said memory circuit;

(ii) if said actual size of free memory space is not greater than said second threshold value, compressing at least one of said plurality of blocks of image data via said data compression circuit, and temporarily storing said at least one of said plurality of blocks of compressed image data in said memory circuit,

virtually simultaneously continuing processing of said plurality of blocks of image data using available free memory space of said memory circuit; and

(e) if said Request Counter'"'"'s value is greater than said first threshold value, decreasing said Request Counter'"'"'s value upon each occurrence of storing one of said plurality of blocks.

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

(a) successively retrieving each of said plurality of blocks of uncompressed image data in said memory circuit and communicating said blocks to said print engine, and increasing said Request Counter'"'"'s value upon each occurrence of retrieving one of said plurality of blocks; and

(b) retrieving and decompressing each of said plurality of blocks of compressed image data in said memory circuit, via a data decompression circuit, and communicating said blocks to said print engine,

virtually simultaneously continuing processing of said plurality of blocks of image data using available free memory space of said memory circuit.

15. The method as recited in claim 13, further comprising the step of selecting said blocks for compression according to a priority, wherein the blocks selected first are the "oldest" blocks currently contained in said memory circuit.

16. The method as recited in claim 13, wherein the step of setting said Request Counter to a predetermined value is determined by the manufacturer of said printing system for a particular print resolution, and said predetermined value is related to the number or uncompressed image data blocks that can be stored in the printing system'"'"'s memory circuit before requiring the initiation of compressing said image data blocks.

17. The method as recited in claim 14, further comprising the step of selecting said blocks for decompression according to a priority, wherein the blocks selected first are blocks that are to be displayed next, and blocks selected second are blocks needed by an interpreter for further image processing.

18. The method as recited in claim 13, further comprising the steps of excluding certain of said blocks from being compressed, including those of said blocks that:

(a) fail to compress to a desired compression ratio;

(b) cause the number of uncompressed blocks to fall below a predetermined minimum number;

(c) fall within an active region of a page currently being processed.

19. The method as recited in claim 13, wherein the current value of said Request Counter is related to the amount of actual free memory available in said memory circuit.

20. The method as recited in claim 13, further comprising the step of avoiding thrashing of said blocks that are part of a currently active page.

21. The method as recited in claim 13, further comprising the step of using a straightforward method of compressing said blocks of image data only after the actual size of said free memory falls to near-zero.

22. A printing apparatus, comprising:

(a) a memory circuit used for storing image data;

(b) a data compression circuit used for compressing image data;

(c) a processing circuit that is configured to control the flow of data between said memory circuit and said data compression circuit, said processing circuit being configured to divide a page of image data into a plurality of blocks; and

to set a predetermined threshold value of memory size;

(d) said processing circuit also being configured to initiate processing of each of said plurality of blocks of image data, and to compare the actual size of free memory space within said memory circuit to said threshold value;

wherein if said actual size of free memory space is greater than said threshold value, at least one of said plurality of blocks of image data is stored in said memory circuit, and if said actual size of free memory space is not greater than said threshold value, said processing circuit being further configured to command said data compression circuit to compress at least one of said plurality of blocks of image data while said processing circuit continues to process others of said plurality of blocks of image data using available free memory space of said memory circuit; and

(e) said data compression circuit being configured to perform its compression operation independently of said processing circuit;

the effect of which is to have a compression function and an image processing function occurring simultaneously within said printing apparatus.

23. The printing apparatus as recited in claim 22, wherein, after said data compression circuit has completed its compression cycle for one of said blocks of image data, said processing circuit is further configured to store at least one of said plurality of blocks of compressed image data in said memory circuit.

24. The printing apparatus as recited in claim 22, further comprising a DMA controller that interfaces said compression circuit with said memory circuit.

25. The printing apparatus as recited in claim 22, further comprising a decompression circuit that is configured to receive at least one block of compressed image data that is retrieved from said memory circuit, perform a decompression operation on that block, then transfer the resultant decompressed block of image data back to said memory circuit.

26. A printing apparatus, comprising:

(a) a memory circuit used for storing image data;

(b) a data compression circuit used for compressing image data;

(c) a processing circuit that is configured to control the flow of data between said memory circuit and said data compression circuit, said processing circuit being configured to divide a page of image data into a plurality of blocks; and

to set a Request Counter to a predetermined value, to set a first predetermined threshold value, and to set a second predetermined threshold value;

(d) said processing circuit also being configured to initiate processing of each of said plurality of blocks of image data, and if said Request Counter'"'"'s value is not greater than said first threshold value, to compare the actual size of free memory space within said memory circuit to said second threshold value;

wherein if said actual size of free memory space is greater than said second threshold value, at least one of said plurality of blocks of image data is stored in said memory circuit, and if said actual size of free memory space is not greater than said second threshold value, said processing circuit being further configured to command said data compression circuit to compress at least one of said plurality of blocks of image data while said processing circuit continues to process others of said plurality of blocks of image data using available free memory space of said memory circuit; and

(e) said data compression circuit being configured to perform its compression operation independently of said processing circuit;

the effect of which is to have a compression function and an image processing function occurring simultaneously within said printing apparatus.

27. The printing apparatus as recited in claim 26, wherein, if said Request Counter'"'"'s value is greater than said first threshold value, then said processing circuit is further configured to decrease said Request Counter'"'"'s value, upon each occurrence of storing one of said plurality of blocks in said memory circuit.

28. The printing apparatus as recited in claim 26, wherein, after said data compression circuit has completed its compression cycle for one of said blocks of image data, said processing circuit is further configured to store at least one of said plurality of blocks of compressed image data in said memory circuit.

29. The printing apparatus as recited in claim 26, further comprising a DMA controller that interfaces said compression circuit with said memory circuit.

30. The printing apparatus as recited in claim 26, further comprising a decompression circuit that is configured to receive at least one block of compressed image data that is retrieved from said memory circuit, perform a decompression operation on that block, then transfer the resultant decompressed block of image data back to said memory circuit.