Page printer having adaptive data compression for memory minimization

• US 5,479,587 A
• Filed: 09/03/1992
• Issued: 12/26/1995
• Est. Priority Date: 09/03/1992
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Zimmerman, Gary, Nelson, Terry M., Berge, Thomas G., Campbell, Russ
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): LEGREE, TRACY MICHELLE
• Application Number:
  US07/940,111
• Time in Patent Office: 1,209 Days
• Field of Search: 395/100, 395/101, 395/110, 395/112, 395/114, 395/115, 395/116, 341/51, 341/65, 341/67, 341/55
• US Class Current: 358/1.17
• CPC Class Codes: G06K 15/00 Arrangements for producing a permanent visual presentation of the output data , e.g. computer output printersprinting or plotting combined with another operation, e.g. with conveying, G06K17/00
• CPC Class Codes: G06K 2215/0031 Compressed bit maps
• CPC Class Codes: G06K 2215/0071 Post-treatment of the composed image, e.g. compression, rotation
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/48 alternating with other codes during the code conversion process, e.g. run-length coding being performed only as long as sufficientlylong runs of digits of the same kind are present

Abstract

A peripheral unit converts an input data flow to page-arranged outputs and includes a random access memory capacity that is insufficient in size to accommodate an entire page of raster data. The peripheral unit also includes a processor and a control memory that holds a plurality of data compression procedures, each procedure exhibiting a different performance characteristic. The peripheral unit performs a method for compressing portions of the input data flow that includes the steps of: allocating the random access memory to portions of the input data flow; determining when an insufficient amount of random access memory is available for such allocation; employing a first data compression procedure on the input data flow portions to produce a compressed data portion; testing the compressed data portion to determine if a level of compression has been achieved that exceeds a threshold and, if not, employing succeeding data compression procedures and repeating the test for each procedure against a threshold, whereby the compression procedure that first enables a threshold level of compression to be achieved is the compression procedure employed to compress the data flow portion. Improved compression methods and techniques for handling input data flows with both integral and independent image descriptors are also described.

Claims

1. In a peripheral unit that converts an input data flow to a page-arranged output, said peripheral unit including random access memory with allocated memory space for storing only a portion of said page-arranged output, a processor and control memory containing a plurality of data compression procedures, each said procedure exhibiting a speed of compression performance characteristic, a method for compressing portions of said input data flow for storage in said random access memory, said method comprising the steps of:

allocating portions of said input data flow for storage in said random access memory;

determining when an insufficient amount of said random access memory is available for allocation to said input data flow portions;

employing a first data compression procedure upon a said input data flow portion to produce a compressed data portion, said first data compression procedure generally accomplishing data compression in less time than other data compression procedures available in said peripheral unit;

testing a compression level of said compressed data portion against a compression threshold to determine if said compression level exceeds said threshold, and if not, employing another data compression procedure and repeating said testing in relation to a threshold, whereby a compression procedure is found that enables the compression level of said input data flow portion to exceed a said threshold and is employed to compress said data flow portion.

2. The method as recited in claim 1 wherein said data compression procedures comprise ones which compress data in a lossless manner and at least another which compresses data in a lossy manner, data compressed in a lossless manner being decompressible with no loss of data and data compressed in a lossy manner being decompressible only with loss of data, a said lossless compression procedure being employed first before said lossy compression procedure.

3. The method as recited in claim 2 wherein one said lossless compression procedure is a Lempel/Ziv/Welch (LZW) compression procedure, said procedure building a table of received data strings and assigning a code to each said string, the method further comprising:

limiting the number of string entries in said table to less than a maximum required to obtain optimum data compression, so as to limit a code length required to identify a said string, thereby enabling compression and decompression actions to occur at a faster rate.

4. The method as recited in claim 1 wherein subsequent to said allocating step but prior to said determining step, the method comprises an additional step of:

determining if any said data portion exceeds a predetermined data size, and if so, further determining if allocatable memory remaining within said random access memory is less than a predetermined level, and if both determinations are affirmative, subjecting said data portion to data compression.

5. The method as recited in claim 4 wherein said data compression is accomplished by use of a lossless compression procedure.

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

storing said data portion in random access memory after it has been data compressed; and

adjusting said predetermined level by subtracting therefrom memory space taken by said stored data portion.

7. The method as recited in claim 1 wherein said peripheral unit includes a print engine that, when operative, runs at a constant speed, said method comprising the additional steps of:

calculating a complexity factor for data portions within a page and determining if said complexity factor indicates that too great a time will be required to convert said data portions to a raster video format in relation to said print engine speed; and

upon such a determination, subjecting at least one data portion to immediate conversion to a raster video format and performing data compression thereon.

8. The method as recited in claim 7, wherein if at any time subsequent to said conversion and compression of said one data portion, it is determined that remaining data portions can be acted upon without causing a memory out indication, said remaining data portions are converted to raster video without compression.

9. The method of claim 1 wherein a said image data includes font data, the method comprising the further step of:

automatically applying a lossless compression technique to said font data if a font represented by said font is at least equal in size to a predetermined level.

10. The method of claim 9 wherein, if said font size is not equal to said predetermined level, applying said lossless compression technique only in the event random access memory for storing said image data is insufficient in capacity.

11. A method for data compressing a raster pixel image, comprising the steps of:

a. performing run-length encoding for data segments in an initial raster row of said image and outputting, for each run of a data segment in said row, a run length command indicating a run count and an identification of the run data segment; and

b. for data segments in a subsequent row of said image, comparing whether said data segments are the same as or different from data segments in an immediately previous raster row; and

c. issuing commands which identify for said subsequent raster row, which of said data segments exhibit said "same" condition and further indicate said different said data segments.

12. The method as recited in claim 11 wherein step(b) further identifies a presence of a run of data segments in a said subsequent raster row and outputs a run command comprising a count and an identity of the data segment that is repeated in said run.

13. The method as recited in claim 12 wherein said further identification of a run of a data segment only occurs after a different data segment is determined and before a same data segment is next detected.

14. The method as recited in claim 13 wherein run length encoding may span from raster row to raster row until a said run ends.

15. The method as recited in claim 11 wherein said command issued in step c includes a count of the number of same data segments, followed by a count of and an identity of different data segments that follow said same data segments.

16. The method as recited in claim 11 further comprising the step of:

eliminating any commands issued for a raster row if said row is found to be identical to an immediately adjacent row; and

issuing a repeat row command that causes said immediately adjacent row to be repeated.

17. The method as recited in claim 11, further comprising the steps of:

inserting an end of row command when a run of zeros is sensed at an end of a row; and

upon decompression, padding with zeros any row that ends prior to a predetermined row length.

18. A method for data compressing a raster-arranged pixel image, comprising the steps of:

a. providing a first table of data segment patterns indicative of an image comprised of clustered bit patterns and of an image comprised of dispersed bit patterns;

b. comparing data segments of an image to said data segment patterns in said first table to determine a classification of said image, said classification comprising clustered or dispersed;

c. compressing said image by reducing each n×

n bit block of said pixel image to an n-bit data segment and accompanying said compressed image by a classification indicator; and

d. decompressing said image by employing said n-bit data segment to access a stored n×

n pixel matrix from a pair of matrix tables in accordance with said classification indicator, one said tables including n×

n-bit images classified as clustered and another said table including n×

n-bit images classified as dispersed, each said table addresses in accordance with said n-bit data segment.

19. The method as recited in claim 18 wherein said image is classified as either clustered or dispersed by assigning a first value to any data segment of said image that matches a clustered data segment pattern in said first table and assigning a second value to any data segment that matches a dispersed data segment pattern in said first table, said classification determined by combining said first and second values and comparing said combined values to a threshold.

20. The method as recited in claim 19 wherein said first values are positive numbers and said second values are negative numbers, said threshold being a neutral value therebetween.

21. In a peripheral unit for converting an input data flow to a page--arranged output, said peripheral unit having insufficient random access memory allocated to store an entire video raster image of said page arranged output, a method for converting said input data flow to a page intermediate form that includes a plurality of image strips that make up said page arranged output, each image strip including image processing commands that enable subsequent conversion of each said image strip to a raster video form, said method comprising:

a. establishing a threshold value of data segments in an image strip;

b. determining (1) if a number of data segments in an image strip exceeds said threshold value, and (2) if remaining memory in said random access memory is less than a predetermined level and if said determinations 1 and 2 are affirmative;

c. converting said image strip immediately to raster video and attempting a compression thereof;

d. storing in said random access memory, compressed raster video that results from step c;

e. adjusting said threshold value to a smaller value to account for remaining random access memory in said random access memory; and

f. repeating steps a-e for remaining image strip of said page.

22. The method as recited in claim 21 wherein step (c) employs a compression action that examines blocks of raster data and performs compression actions that take into account both vertical and horizontal data redundancies in each said block of raster data.

23. The method as recited in claim 22 wherein said compression action comprises the steps of:

providing output commands which indicate vertical redundancies existing between succeeding rows of a block of raster data and further providing commands indicative of horizontal data redundancy occurring in a said row.

24. A method as in claim 21 where the strip complexity can be empirically determined by measurement with a system timer, and this result used to ascertain whether to pre-rasterized the strip when the complexity prediction is within the uncertain complexity window.

25. In a peripheral unit that converts an input data flow to a page-arranged output, said data flow including data describing an image, a said image comprised of a set of subimages, each subimage further comprised of a video raster bit map and a descriptor having a field that identifies where said video raster bit map is stored, a method for compressing data representing a said image and subimages, comprising:

selecting a group of descriptors that represent a subset of said set of subimages;

attempting to compress, through the use of a first compression technique, the video raster bit map associated with each said selected descriptor;

comparing against a threshold, a level of compression of said subset of subimages achieved through said compression attempt and if said threshold is at least equalled, employing said first compression technique to data compress all subimages comprising said image.

26. The method as recited in claim 25 wherein each said descriptor has fields reserved for indicating facts regarding an associated video raster bit map, said method further comprising:

employing a second compression technique upon said subset of subimages in the event said level of compression is not equalled and again comparing an achieved level of compression against a threshold and employing said second compression technique for all subimages of said image in the event said threshold is at least equaled.

27. The method as recited in claim 26 wherein said facts in each said descriptor are employed during decompression of said image, said facts indicating the method of compression employed to compress said video raster bit maps.

28. The method as recited in claim 27 wherein at least said first compression method is lossless.

29. The method as recited in claim 28 wherein said peripheral unit includes random access-memory (RAM) whose capacity is insufficient to store an entire page of said page-arranged output, said method comprising the further steps of:

determining, subsequent to application of a said compression technique, whether sufficient space is available in said RAM to store a compressed image and, if not;

applying a lossy compression technique to said subimages.

30. The method as recited in claim 29 wherein, as part of said lossy compression technique, said image is classified as either dispersed or clustered by comparison of video raster bit maps of at least some said subset of subimages to a table of entries that define bit patterns comprising clustered and dispersed bit arrangements, said classification employed during decompression of said lossy compressed image.

31. The method as recited in claim 29, wherein said lossy compression technique is employed for said image only if a prior applied lossless compression technique did not exceed a level of compression of said image that is available from said lossy technique.