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

I claim:

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.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

1.Field of the Invention

This invention relates to a method and apparatus for processing data representative of a visual representation, typically including a combination of text, graphics, and images, that is to be output to a visual-output device, such as a screen display or print device. More particularly it relates to such a method and apparatus in which a data memory, referred to herein functionally as a "buffer memory", has reduced capacity requirements resulting from the selective compression of data.

2. Related Art

The preferred embodiment of, and preferred method of practicing the present invention is directed to printers that form a raster image typically connected indirectly over a network, or directly to a computer for printing documents created on the computer. The invention is realizable for other forms of output devices as well, such as a video display generated on a CRT monitor or an LCD. Thus, the device creating the actual visual representation is referred to as a "visual-output device". The visual area within which the visual representation exists is referred to as a "page", regardless of its actual form. The complete visual representation is referred to as a "page representation". A separately defined part of a page representation is referred to as an "object".

One of the significant cost elements in a conventional printer is a buffer memory, also referred to as a frame buffer, for storing raster data defining the page representation. Conventional printer configurations employ buffer memories that are capable of storing all of the raster data required to define each pixel on a page. An extensive amount of memory capacity is therefore typically required. A black-and-white representation for a 8.5 inch.times.11 inch sheet of paper at a pixel density of 300 dpi (dots or pixels per inch) requires in excess of 1 MByte (1 million 8-bit bytes)of memory. Higher spatial and tonal resolutions, color priming and larger paper sizes require even more memory. A continuous tone, four-color representation at a pixel density of 600 dpi for the same sized page requires about 135 MBytes of memory. Since the printer costs rise with memory size, it is desirable to provide printers with reduced memory requirements.

A memory device known by the proprietary name of "Memory Miser" produced by Advanced Micro Devices of Santa Clara, Calif., stores data in a resident memory by applying a compression algorithm to all of the data input. When required for output it is decompressed based on the reverse of the compression algorithm and output. If used in a printer, such a device would reduce the amount of memory required. However, the memory would need to be at least large enough to store the most complex page representation in order to be able to process any page that is input. This printer would have little flexibility in processing the variety of page representations possible with present day printers.

SUMMARY OF THE INVENTION

The present invention provides a method for using, and an apparatus permitting a reduced-size memory. Further, it provides a method and apparatus that can accommodate a variety of page representation characteristics and data processing objectives.

The invention is directed generally to an apparatus and a method for processing data representative of a page representation for output to a visual-output device, such as the electro-mechanical printing apparatus (also referred to as the print device), of a printer. The method begins with the step of receiving data that defines a page representation. A plurality of regions of the page are selected, which regions contain at least a portion of the page representation. In one aspect of the invention, separate data for each such region is identified corresponding to the portion of the page representation contained in that region. Data identified for at least one of the regions is then compressed, using at least one compression algorithm and stored. For producing the page representation after storing the compressed data, the compressed data is decompressed and transmitted to the visual-output device.

In another aspect of the invention, at least one compression factor and a plurality of compression algorithms are provided. The compression factor has a determinable value that is related to a reference value. A compression algorithm is then chosen based on the relationship of the determined value of the compression factor to the reference value.

More specifically, the preferred embodiment of the invention is an apparatus for printing a two-dimensional page representation composed potentially of text, graphic and image objects (object representations) individually, and in combination. A print device is responsive to raster data for printing a page containing the page representation. An input device, such as a personal computer or workstation, is used for inputting data defining the page representation. A program memory stores program instructions including a plurality of different algorithms for compressing the data associated with corresponding different representation types and their combinations. The selection of compression algorithms is based in part on balancing the compression factors of compression ratio, computational complexity, and visual quality. A processor is coupled to the input device, print device, program memory and a data memory for executing the stored program instructions.

The processor is responsive to the data input in the form of descriptive commands for identifying data for each of a plurality of ordered regions or bands containing collectively at least a portion, and preferably, all of the page representation. The data for each region corresponds to the portion of the page representation contained in that region. Some regions may not contain data. The descriptive commands, which are not necessarily band limited, are converted into lists of primitive elements selected from a set of primitive elements. Each primitive element represents at least a portion of an object representation. These lists are referred to as display lists. There is preferably a display list for each region, although the display list could be for the entire page, or for other defined regions.

The types (and combinations of types) of representations and boundaries (referred to as bounding boxes) of each type contained in each region are determined. The display list data associated with the determined types of representations for each region is rasterized into an uncompressed band and then compressed using algorithms corresponding to the analysis of certain compression factors. Rasterizing refers generally to the conversion of high-level descriptive commands into rasters. Data associated with primitive elements is often already in raster form. However, for purposes of this discussion, rasterizing refers to the conversion of display list data for a region into raster form without regard for whether or not the data associated with the corresponding primitive elements is already in raster form.

The compression factors may, and preferably do include compression goals specifying target visual quality, compression ratio, and computational complexity. Compression ratio refers generally to the bytes of memory required to hold the compressed data relative to the bytes of memory required to hold the same data uncompressed. Additionally considered are such factors as the type of representation, content of individual bounding boxes, overall content of the page representation, estimated versus actual compression being achieved, and the number of passes or attempts made at compressing the data. Other factors may also be used, and some of these factors may not be used in all situations. For example, the factors could be prioritized so that some are given more weight than others. As an extension of this, in certain situations some factors could be given no weight at all relative to other factors.

Some of these factors inherently have values that are readily determined. Others relate to characteristics or features the state of which is determined and a value assigned accordingly. For instance, the three representation types of text, graphics and images could be assigned arbitrary respective identifier values 1, 2, and 3.

An algorithm, generally speaking, refers to a particular algorithm or combination of algorithms with particular parameter values. Thus, a change in parameter values results in a change in the algorithm.

The compressed data is stored sequentially by region. In the preferred embodiment, when required for printing, data for a region is read and decompressed. Depending on the system configuration, the compressed data may be transmitted to an external printer or stored pending requirement of the data by the print device. The data is then transmitted to the print device for printing. Producing data (display lists)for each region and defining the regions to conform to the sequential output of raster data to an output device minimizes the number of times the data is decompressed, data added, and then recompressed. During this overall process "data" defining the page representation takes the form of descriptive commands, display lists and associated information, and raster data.

Data representative of the page representation is thus compressed and held in memory until such time as it is required by the print device for printing, or until the content of a region is changed. The data for the regions are swapped in and out of the compressed-data memory using the selected compression and corresponding decompression algorithms, thereby reducing substantially the buffer memory requirements. This and other features and advantages of the present invention will be apparent from the following detailed description of the preferred embodiment of the invention and as illustrated in the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of an apparatus made according to and for practicing the method of the invention.

FIG. 2 is an illustration of a page having different types of two-dimensional representations.

FIG. 3 is a flow diagram summarizing a method of practicing the invention.

FIG. 4 is a flow diagram of step 58 of the diagram of FIG. 3.

FIG. 5 illustrates visually the development of non-intersecting bounding boxes from bounding boxes of different representation types that overlap according to the method of the diagram of FIG. 4.

FIG. 6 is a simplified graphic example of overlapping bounding boxes with identifying coordinates used in the method of the diagram of FIG. 4.

FIG. 7 is a flow diagram illustrating the development of non-intersecting bounding boxes corresponding to step 122 in FIG. 4.

FIG. 8 is a flow diagram of step 78 of the diagram of FIG. 3.

FIG. 9 is a flow diagram of step 80 of the diagram of FIG. 3.

FIG. 10 is a functional block diagram corresponding to the apparatus of FIG. 1.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT AND METHOD

Referring initially to FIG. 1, a generalized visual-representation-generating system made according to the present invention is shown generally at 10. It includes a visual information source 12 connected via a communication link 14 to an output-data generator 16. Generator 16 is connected to a visual-output device 18 via a communication link 20. As will be seen, various embodiments are realizable from this general structure. Output data generator 16 can be resident within a host unit including source 12, can be resident within an output unit including visual-output device 18, or can be functionally split between a host unit and an output unit.

In the typical instance when data generator 16 and output device 18 comprise a laser or other raster printer, information source 12 is a conventional work station or other computer-based system, such as an Apple Macintosh or IBM PC. The term print device is also used herein as an example of a visual-output device. In the preferred embodiment, this term applies to the electro-mechanical apparatus responsive to raster data for producing a printed page. Generator 16 could also be incorporated in a computer or workstation, such as a computer-based system as has just been mentioned, programmed to function as described herein, for controlling a raster display or printing device, as has also been mentioned. Further, as is discussed with reference to FIG. 10, a host unit could generate and output the compressed data and an output unit could receive the compressed data, decompress it and transmit it to a resident visual-output device.

The preferred embodiment of the invention is thus directed to the printing of two-dimensional pixel representations. The general concepts are equally applicable to three (or more) dimensional representations to the extent they are realizable in the system of FIG. 1.

Generator 16 includes an input/output controller 22 coupled to communication links 14 and 20. A conventional CPU (central processing unit) or processor 24 is coupled to controller 22, as well as to a read/write or random access memory (RAM) 26, used partially as a buffer memory, for storing data, and a read only memory (ROM) 28 for storing program instructions and fixed information, such as nonvariable data and compression and decompression algorithms, as is discussed in further detail with reference to FIGS. 3, 5, and 7-10. Any of a variety of conventional CPU's may be used, depending on the actual application. Further, other forms of hardware that accomplish the same functions can be used.

FIG. 2 illustrates a page 30 having a page representation 34 that could be defined by data input by the input device using a conventional page-description language, such as the language available from Adobe Systems Incorporated known by the name PostScript. In the printer environment, as a PostScript file is created on source 12 (FIG. 1), objects can be created in any arbitrary order or fashion on a page. The objects are defined by one or more descriptive commands. As used herein, then, an "object-defining command" is the command or collection of commands that define an object.

Different compression schemes have been found to be preferable for the different representation types of text, graphics, and images. For instance, the human eye is often less sensitive to changes in images than to degradations in something as well defined as text. Thus, technically lossy compression schemes such as JPEG, when used at reduced levels of compression for images, can be visually lossless. Further, by the nature of graphics objects, some otherwise lossy schemes may be usable without compromising spatial resolution. The LZW technique has been found to work well on text, runlength coding is effective for graphics and text/graphics combinations, and the JPEG technique is useful for images. It is therefore advantageous to identify the different types of objects in a page representation.

Continuing to refer to FIG. 2, page 30 has defined boundaries represented by border line 32. The boundaries thus represent the maximum area within which page representation 34 is to be produced. Page representation 34 includes the following objects on a background of a single color. A title or main heading 36 is formed of text in different colors (represented by the different tones). A subheading 38 identifies a text representation 40; a subheading 42 identifies a graphics representation 44; and a subheading 46 identifies an image representation 48. These subheadings are text representations in relatively large fonts and, along with text representation 40, are all a single color different than the background color. Text representation 40 is in a reduced font. Graphics representation 44 has grid identifiers 50 in the form of alphanumeric characters (text), and a bar chart section 52 composed of bars of different colors. Image representation 48 is simply an array of pixels of varying colors.

Page representation 34 incorporates separate examples of large and small text, graphics, and image representations or objects. In a more complex page representation various of the different objects could overlap. That is, they could be printed at least partially on a common area. The preferred method of the present invention is designed to take such overlapping areas into consideration, as is discussed in greater detail below.

A generalized flow diagram chart of a process or method 54 according to the invention is provided in FIG. 3. Processor 24 of FIG. 1 executes instructions to function as an interpreter that recognizes the PostScript descriptive commands input as page data from source 12, as is provided by step 56 in the flow diagram of FIG. 3. In the general method of the invention, the page description data is divided into at least one, and preferably R different data regions at step 58. The regions can be determined in advance, as is the case with the preferred embodiment and therefore be determined arbitrarily with reference to a particular page representation. They could also be determined dynamically for each page representation. Referring to FIG. 2, an example of a dynamic determination would be to divide the page into separate regions corresponding to title heading 36, text subheading 38, text section 40, graphics subheading 42, each of grid identifiers 50, bar chart section 52, image subheading 46 and image section 48. In the preferred embodiment of the invention, however, in which raster data is produced for printing a page, the page area is divided into a plurality of fixed regions in the form of parallel bands. The bands are chosen and ordered to correspond to the generation of raster data for output to a print device, and is therefore related to the resolution and scan order of the output device.

Referring again to FIG. 2, page 30 is shown for purposes of illustration divided into sixteen bands 60-75. When it is time to print, data for band 60 is read out and decompressed first and the data progresses sequentially through the bands until data for the last band 75 is output. These bands each correspond to multiple raster "scans" of the page and provide for ordering the data in a way that will make the data readily available for printing. An actual letter-size page having a resolution of 300 dpi may be divided into about 20 to 40 bands.

As has been mentioned, the present invention provides for a reduction in the amount of memory required through the use of compression techniques, as is represented by step 78 in FIG. 3. By compressing a rasterized version of the descriptive data of the page representation, according to the preferred embodiment, and decompressing it as needed by the printer or display, the amount of RAM needed may be drastically reduced.

This memory reduction is achieved by storing in the working RAM a compressed representation of what is conventionally stored uncomp