Method and apparatus for compressing and decompressing data prior to display

• US 5,991,515 A
• Filed: 07/15/1997
• Issued: 11/23/1999
• 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: Foskett, Nicholas J., Fall, Richard N., Wong, Davin C.
• Primary Examiner(s): Coles, Edward L.
• Assistant Examiner(s): HASKINS, TWYLER LAMB
• Application Number:
  US08/893,065
• Time in Patent Office: 861 Days
• Field of Search: 395/114, 395/115, 395/116, 395/110, 395/111, 395/112, 395/108, 395/117, 382/232, 382/233, 382/235, 358/450, 358/444, 358/540, 358/426, 358/261.3, 358/261.4, 358/432, 358/433
• US Class Current: 358/1.15
• 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: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• 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 method and apparatus for compressing and decompressing display data including methods for predicting compression results and correcting compression ratios prior to the compression of object data. The compressed objects are then decompressed using a related decompression mechanism and sent directly to a driver in the output display device for printing or display.

Claims

1. A compressor for use in a digital output processing system with selective object compression based on data object type, the compressor comprising:

an interpreter for transforming received data objects of a predefined type into an intermediate format of the object data;

a cascaded coder coupled to the interpreter for receiving the intermediate format of the data objects and outputting a compressed format of the data objects; and

a controller for receiving as an input the intermediate format of the data objects and a user defined compression ratio, the controller operable to predict if a data overflow condition will occur as a result of compression by the cascaded coder of the intermediate format of the data objects into a compressed format using a compression algorithm selected in accordance with the user defined compression factor, the controller operable to produce variance information and provide the variance information to the cascaded coder prior to the compression of the intermediate format of the data objects by the cascaded coder and wherein the cascaded coder is operable to modify prior to compression the intermediate format of the data objects using the variance data in the event the overflow condition is detected.

2. A compressor as recited in claim 1 wherein the compressor is implemented in an output device.

3. A compressor as recited in claim 2 wherein the output device is one of the group consisting of a printer device and a screen display.

4. A compressor as recited in claim 1 wherein the data objects are organized into at least one page.

5. A compressor as recited in claim 4 wherein the at least one page is organized into a plurality of bands, the bands having a display order on the page, wherein data objects on the page are displayed by the digital output processing system in display order.

6. A compressor as recited in claim 5 wherein the data objects are stored in display lists, wherein a display list is provided for each band of the page.

7. A compressor as recited in claim 1 wherein the types include text, graphics, and image types.

8. A compressor as recited in claim 1 further comprising a mechanism for dividing the bitmap objects into non-intersecting regions, wherein the compressor compresses the regions.

9. A compressor as recited in claim 8 wherein each of the regions has a type, and wherein a region type is equivalent to the type of a bitmap object from which the region was derived.

10. A compressor as recited in claim 1 wherein the interpreter applies a Fourier transform to the data objects and the coder is a JPEG coder.

11. A method of compressing object data by a digital output processing system comprising:

receiving data objects;

interpreting and transforming the data objects into an intermediate format of the data objects;

predicting if a data overflow condition will arise based at least in part on the intermediate format of the data objects;

varying the intermediate format of the data objects prior to compression if a data overflow condition is predicted resulting in a varied intermediate format of the data objects; and

compressing the varied intermediate format of the data objects.

14. The method of claim 11, further comprising:

receiving a user defined compression ratio; and

wherein the step of predicting if a data overflow condition will arise is based at least in part on the compression ratio.

12. A decompressor for use in a digital output processing system with selective object decompression, the decompressor comprising:

a selector for determining the type of decompression required for each object to be decompressed;

one or more decoders for decompressing object data based in part at least on the object type; and

a decompression table for storing state information associated with a partial decompression of an object by a decoder, the state information including an object identifier and continuation data the state information retrievable by a decoder for resuming decompression of a partially decompressed object, and wherein the decoder is operable to interrupt the decompression of an object to allow for streaming of uncompressed object data directly to a driver in the digital output processing system immediately after decompression by the decoder without requiring decompression and subsequent storage of all data associated with a given object.

13. A method of decompressing object data for display by a digital output processing system the method allowing for the streaming of a scan line of uncompressed data objects directly to a driver in the digital output processing system immediately after decompression and without requiring decompression and subsequent storage in memory of all data associated with a given object, the method comprising:

identifying an object to be decompressed;

determining the object type;

determining if the object has already been partially decompressed;

if not, decompressing a portion of the object intersecting the scan line;

if the object is partially decompressed then storing state information defining a state of the decoder at a time the decompressing step completed the partial decompression of the object, the state information including an object identifier and continuation data; and

if the object has already been partially decompressed, retrieving the state information for the object using the object identifier,

determining a next portion of the object to decompress based on the continuation data in the state information,

decompressing the next portion of the object intersecting the scan line, and

if the object includes more data to be decompressed, storing new state information defining the state of the decoder at the time of completion of the decompressing step, including new continuation data.