Method and apparatus for processing data for a visual-output device with reduced buffer memory requirements

• US 5,504,842 A
• Filed: 06/06/1995
• Issued: 04/02/1996
• Est. Priority Date: 11/10/1992
• Status: Expired due to Term

• Current Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Gentile, Ronald S.
• Primary Examiner(s): Bayerl, Raymond J.
• Assistant Examiner(s): SAX, STEVEN PAUL
• Application Number:
  US08/467,792
• Time in Patent Office: 301 Days
• Field of Search: 395/115, 395/114, 395/110, 395/101, 395/116, 358/296, 358/298, 400/121
• US Class Current: 358/1.15
• 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 15/181 Receiving print data characterized by its formatting, e.g. particular page description languages
• CPC Class Codes: G06K 15/1851 parted in a plurality of segments per page
• CPC Class Codes: G06K 15/1865 by compressing the rasterized print data
• CPC Class Codes: G06K 2215/0065 Page or partial page composition
• CPC Class Codes: G06K 2215/0071 Post-treatment of the composed image, e.g. compression, rotation
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: G06T 9/007 Transform coding, e.g. discrete cosine transform
• 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: 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

Abstract

A two-dimensional page representation to be printed has a combination of text, graphic and image representation types. A data memory stores data representative of the page representation. A program memory stores program instructions including a plurality of different algorithms for compressing data associated with corresponding different representation types and their combinations. A processor is coupled to the data and program memories for (a) identifying separate data for each of a plurality of regions containing collectively the page representation, with the data for each region corresponding to the portion of the page representation contained in that region; (b) determining the types of representations and boundaries of each type of representation and the combinations of types contained in each region; (c) rasterizing and compressing the data associated with the determined types of representations for each region with algorithms based on selected compression factors; (d) storing sequentially the compressed data for each region; and (e) when needed for printing, sequentially for each region, reading the corresponding stored data, decompressing the read data, and transmitting the decompressed data to the print device for printing.

Claims

1. A method of producing a page representation including at least two representation types on a page by a raster output device, the method comprising the steps of:

receiving data defining the page representation;

dividing the page into a plurality of contiguous regions containing collectively at least a portion of the page representation;

identifying separate data for each region corresponding to the portion of the page representation contained in that region;

determining at least one type of representation or combination of types of representations for the portion of the page representation defined by the data associated with each of the regions containing data;

rasterizing the identified data for each of the regions containing data;

providing a plurality of different algorithms for compressing the data associated with corresponding different representation types and combinations of representation types;

selecting algorithms corresponding to each of the determined representation types and combinations of representation types for each region;

compressing the rasterized data for each region with an algorithm corresponding to each of the determined types of representations for that region;

storing the compressed data for each region; and

serially for each region, reading the stored data associated with the region, decompressing the read data, and transmitting the decompressed data to the raster output device.

2. A method according to claim 1 where the data identified for at least one determined representation type for at least one region has one of at least two identifiable characteristics, the method further comprising the steps of determining the characteristic of the data identified for the at least one representation type determined for the at least one region, and wherein the step of selecting includes selecting an algorithm corresponding to the determined characteristic when the determined representation type is the at least one representation type, and the step of compressing includes compressing the data identified for the determined at least one representation type with the algorithm selected corresponding to the determined characteristic of the data of the determined at least one representation type.

3. A method according to claim 1 wherein the step of determining includes determining at least two types of representation for at least one region;

the method further comprising the step of dividing the at least one region into a plurality of subregions with at least a first one of the subregions containing at least a first one of the representation types and at least a second one of the subregions containing at least a second one of the representation types; and

wherein the step of selecting includes selecting compression algorithms for compressing the identified data corresponding to the at least first and second subregions; and

the step of compressing includes compressing the defining data for the at least first and second subregions according to the corresponding selected algorithms.

4. A method according to claim 3 wherein the step of selecting includes selecting at least a first algorithm for compressing the identified data corresponding to the at least a first representation type and selecting at least a second algorithm different than the at least first algorithm for compressing the identified data corresponding to the at least a second representation type.

5. A method according to claim 3 where at least the first and second subregions overlap in a common portion;

and wherein the step of dividing the at least one region into subregions further includes identifying the common portion;

the step of selecting includes selecting at least one of the algorithms for compressing the identified data corresponding to the common portion; and

the step of compressing includes compressing at least the identified data corresponding to the common portion according to the selected at least one of the algorithms.

6. A method according to claim 3 wherein the portion of the page representation contained within the one region occupies less area than the area of the one region, and the step of dividing includes dividing the one region into the plurality of subregions containing the portion of the page representation contained in the one region, with the subregions collectively occupying an area that is less than the area of the one region.

7. A method according to claim 1 wherein the at least a portion of the page that is divided into regions has a maximum area and the at least a portion of the page representation contained in the regions occupies less area than the maximum area and the step of dividing includes dividing the at least a portion of the page into the plurality of regions so that the regions collectively occupy an area that is less than the maximum area.

8. A method according to claim 1 further comprising the steps of providing data defining a base set of primitive elements;

and assigning for each region an assigned set of primitive elements selected from the base set and representing collectively the portion of the page representation in that region; and

wherein the step of compressing comprises rasterizing and compressing the data corresponding to the assigned set of primitive elements for each region.

9. A method according to claim 8 further comprising the step of dividing each region into at least one subregion for each type of representation and for each combination of types of representations contained within that region.

10. A method according to claim 9 wherein representations of different types overlap in at least one of the regions and the step of dividing further includes dividing the at least one region into at least one combination subregion that contains different representation types.

11. A method according to claim 10 wherein the step of selecting includes selecting at least one algorithm corresponding to overlapping representations of different types;

and the step of compressing includes compressing the data associated with the combination subregion according to the selected at least one algorithm.

12. A method according to claim 1 wherein the step of providing includes providing at least one compression factor having a determinable value;

the method further comprising, prior to the step of selecting, the step of determining the value of the at least one compression factor, and wherein the step of selecting includes selecting at least a first compression algorithm if the at least one compression factor has a value that has a predetermined relationship to a first value.

13. A method according to claim 12 wherein at least one of the compression factors is a target compression ratio.

14. A method according to claim 12 wherein at least one of the compression factors is a target visual quality of the page representation.

15. A method according to claim 12 wherein at least one of the compression factors is a target computational complexity.

16. A method according to claim 12 wherein the page representation includes at least two representation types, and the method further comprises the step of determining at least one type of representation for the portion of the page representation defined by the data associated with the at least one region, and wherein at least one of the compression factors is the type of representation, and the step of selecting includes selecting at least the first compression algorithm if the determined representation type is a first type.

17. A method according to claim 12 wherein the portion of the page representation for at least one region has one of two identifiable characteristics and at least one of the compression factors is the characteristic of the portion of the page representation in a region, and the method further comprises the step of determining the characteristic of the portion of the page representation for at least the one region, and the step of selecting includes selecting at least the first compression algorithm if the determined characteristic is the one characteristic.

18. A method according to claim 12 wherein the page representation includes a plurality of object representations and at least one of the compression factors is the proportion that an object representation occupies relative to the page representation, and the method further comprises the step of determining the proportion that an object representation occupies relative to the page representation, and the step of selecting includes selecting at least the first compression algorithm if the proportion that an object representation that forms at least a portion of the page representation in the one region, has a value that has a predetermined relationship to a first value.

19. A method according to claim 12 wherein the step of providing the at least one compression factor includes providing a plurality of compression factors;

and the step of selecting includes selecting at least the first compression algorithm if the at least one of the compression factors has a value that has a predetermined relationship to a first value.

20. A method according to claim 19 further comprising the step of prioritizing at least two of the compression factors, and wherein the step of selecting includes selecting a compression algorithm based upon the relative priority of the at least two of the compression factors.

21. A method according to claim 12 wherein the at least one compression factor has a target value and the actual value is determinable based on the step of compressing, the method including, after the step of compressing identified data for at least one region, determining the actual value of the at least one compression factor, and if the actual value has a predetermined relationship to the target value, decompressing the compressed data for the at least one region, selecting at least one compression algorithm based on the relationship of the actual value to the target value, and recompressing the previously compressed data using the selected at least one compression algorithm.

22. A method according to claim 12 wherein the at least one compression factor has a target value and the actual value is determinable based on the step of compressing, the method including, after the step of compressing identified data for at least one region, determining the actual value of the at least one compression factor, and if the actual value has a predetermined relationship to the target value, selecting at least a second compression algorithm different than the at least a first compression algorithm, based on the relationship of the actual value to the target value, and compressing at least a portion of the data identified for at least a second region with the at least a second compression algorithm.

23. A system for producing a page representation comprising:

a raster output device;

input means for receiving data defining the page representation;

at least one data memory means for storing raster data representative of the page representation; and

at least one computer means including program memory means for storing computer program instructions including a plurality of different algorithms for compressing data and at least one compression factor having a determinable value, and processing means coupled to the input means, the raster output device, the data memory means and the program memory means for executing the stored program instructions, the processing means being responsive to input data for (a) identifying separate data for each of a plurality of regions containing collectively the page representation, the data for each region corresponding to the portion of the page representation contained in that region;

(b) determining the value of the at least one compression factor for the data identified for at least one of the regions;

(c) rasterizing the identified data for each region containing data;

(d) selecting at least one compression algorithm for compressing the data identified for each region, including selecting at least one algorithm for the at least one of the regions corresponding to the value of the at least one compression factor;

(e) compressing the data for each region containing data with the selected at least one algorithm;

(f) storing the compressed data for each region containing data; and

(g) after compressing the data, serially, for each region, reading the stored data associated with the region, decompressing the read data, and transmitting the decompressed data to the raster output device;

the raster output device being responsive to the decompressed data for producing the page representation.