Method and apparatus for reducing storage requirements for display data

• US 5,638,498 A
• Filed: 06/07/1995
• Issued: 06/10/1997
• 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: Tyler, William B., Kong, Soon Y., Foskett, Nicholas J., Gentile, Ronald S., Fall, Richard N.
• Primary Examiner(s): Evans, Arthur G.
• Application Number:
  US08/484,344
• Time in Patent Office: 734 Days
• Field of Search: 395/114, 395/112, 395/115, 395/116, 395/117, 395/509, 395/520, 395/521, 395/523, 382/232, 382/233, 382/235, 382/236, 358/450, 358/444, 358/540, 358/426, 358/261.3, 358/261.4, 358/432, 358/433
• US Class Current: 358/1.18
• 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 method and apparatus for reducing storage requirements for display data on a computer system. Data objects to be displayed are organized into display lists and each data object includes an object type, such as text, graphic, and image. The data objects are rasterized into an uncompressed band buffer and divided into non-intersecting bitmap regions each identified with one or more object types. Each non-empty region is assigned a compression algorithm dependent upon the type of the region and specified compression constraints. The regions are combined with each other into larger regions if appropriate, and each region is compressed using its assigned compression algorithm into a compressed band buffer, thus reducing the required storage space for the data objects. The compressed data is decompressed in scan line order with a selected decompression algorithm corresponding to the assigned compression algorithms to produce uncompressed output data. The uncompressed output data is supplied to an output display device for display.

Claims

1. A data processing system with selective object compression and decompression for processing data objects, comprising:

a rasterizer that converts data objects into bitmap objects;

means for dividing said bitmapped objects into non-intersecting regions, each of said regions having a type;

a compressor that compresses said regions with selected compression mechanisms chosen from a set of compression mechanisms to produce compressed bitmap object regions, where said type of said bitmap object region is used to select a compression mechanism for a particular bitmap object region, said compressor storing said compressed bitmap object regions in a memory; and

a decompressor that selectively decompresses said compressed bitmap object regions with selected decompression mechanisms chosen from a set of decompression mechanisms to produce uncompressed bitmap object regions, where the selection of a decompression mechanism for a particular compressed bitmap object region is dependent upon said selected compression mechanism for said particular compressed bitmap object region.

2. A data processing system as recited in claim 1 wherein said compressor and decompressor are implemented in an output device.

3. A data processing system as recited in claim 1 further including an output device for displaying uncompressed bitmapped objects received from said decompressor, said output device is one of the group consisting of a printer device and a screen display.

4. A data processing system as recited in claim 3 wherein said data objects are organized into at least one page where each said at least one page is organized into a plurality of bands, said bands having a display order on said page, wherein data objects on said page are displayed by said output device in said display order and where each of said non-overlapping regions associated with a data object spans only a single band.

5. A data processing system as recited in claim 4 wherein said data objects are stored in display lists, wherein a display list is provided for each band of said page.

6. A digital output processing system as recited in claim 1 wherein said types include text, graphics, and image types.

7. A data processing system as recited in claim 1 wherein each of said regions has a type, and wherein a region type is derived from all the types of the bitmap objects intersected by said region.

8. A data processing apparatus as recited in claim 1 wherein a region type for a particular region may be different from the type of bitmap object from which said region was derived.

9. A data processing system as recited in claim 4 wherein said decompressor further includes means for determining where an output scan line intersects compressed regions of a band, said decompressor decompressing said compressed regions where said scan line intersects said regions.

10. A data processing system as recited in claim 9 wherein said decompressor further includes means for outputting background data to said output device when where said scan line does not intersect a region including one or more bitmap objects.

11. A method for providing a digital output with selective object compression and decompression comprising:

receiving a page of output data including one or more objects, each object including type and location information respectively characterizing the type of the data from a predetermined plurality of data types and a location of said object on said page;

storing said type and location information for said objects in a display list indexed according to said location information;

compressing each of said objects with a selected compression algorithm chosen from a set of compression algorithms to produce compressed object data of said type, where said type information is used to select a compression algorithm for said compressed object data;

storing said compressed object data in a memory coupled to an output device;

when said page of data is to be displayed, identifying a first object to be displayed from said display list;

decompressing said compressed object data with a selected decompression algorithm chosen from a set of decompression algorithms to produce uncompressed output data, where said type information is used to select a decompression algorithm;

supplying output data associated with the object to be displayed to said output device;

identifying a next object to be displayed from said data stored in said display list; and

repeating the steps of decompressing the compressed object data, supplying output data and identifying a next object until all said objects in said page of output data have been supplied to said output device.

12. A method as recited in claim 11 further comprising the steps of:

dividing said page of output data into bands, and storing type and location information for each object within a band in an associated band display list; and

rasterizing one or more objects of said band display list as bitmap objects of an uncompressed band and storing the resultant uncompressed band objects in an uncompressed band buffer, wherein each bitmap object has a type corresponding to said type of said object from which was rasterized.

13. A method as recited in claim 12 wherein said step of compressing said object data includes compressing said uncompressed band objects into compressed band objects and said step of storing said compressed object data includes storing said compressed band objects in a compressed band buffer of a memory.

14. A method as recited in claim 13 wherein said step of compressing said output data includes selecting a set of compression algorithms which meet compression constraints.

15. A method as recited in claim 13 wherein said steps of decompressing said compressed object data and supplying said data to said output device includes decompressing said compressed band objects and supplying decompressed band objects to said output device.

16. A method as recited in claim 15 wherein said step of compressing said uncompressed band objects includes checking when said uncompressed band objects fit in said compressed band buffer when compressed, and, when said uncompressed band objects do not fit, decompressing and recompressing compressed band objects that were previously compressed.

17. A method as recited in claim 12 further comprising a step of combining said objects into a single object when a cost of combining said objects is under a predetermined threshold, said cost determined by the separation between the objects.

18. A method as recited in claim 17 wherein said cost of combining is determined by the amount of background data that is included in a combined resulting object compared to the amount of data included in said objects that were to be combined.

19. A method as recited in claim 17 further comprising a step of forcing combinations of objects to free memory storage in said compressed band buffer.

20. A method as recited in claim 12 wherein if during the step of compressing said uncompressed band objects a number of objects compressed for a given band exceeds a predetermined number, then multiple objects are combined into a single object prior to compression to reduce the number of objects actually compressed for a given band.

21. A method for compressing and decompressing a page of bitmapped data, organized into a plurality of bands to be displayed by an output display device, comprising;

(a) receiving one of the bands that includes one or more regions, each region having at least one type;

(b) using a type of each region to select a compression method for each of said regions from a plurality of available compression methods;

(c) compressing each of said regions of said band according to its selected compression methods to create a compressed band;

(d) storing said compressed band in a compressed band buffer; and

(e) decompressing said compressed band in said compressed band buffer and sending said decompressed band to said output display device for display.

22. A method as recited in claim 21 wherein said step of receiving a band of data includes storing said band of data in an uncompressed band buffer, said uncompressed band buffer being able to store at least one band of data.

23. A method as recited in claim 22 where said regions include one or more input objects having type and location information, and said receiving step further includes organizing and storing said input objects into a plurality of display lists, where each display list corresponds to one of said bands of said page and at least one display list includes said input objects, and rasterizing said objects of one of said display lists into said uncompressed band buffer.

24. A method as recited in claim 23 wherein said steps of rasterizing said objects of a display list and compressing said rasterized objects occurs before all of said input objects are included in said display lists, wherein said rasterizing and compressing step is accomplished to free display list storage when display list storage is not available.

25. A method as recited in claim 23 further comprising a step of dividing said regions into subregions consisting of non-intersecting rectangles each of which subregions includes one or more objects of the same type.

26. A method as recited in claim 21 further comprising the step of repeating the steps of receiving a band of data, selecting a compression method, compression said regions and storing said compressed band for each band in said page, and repeating the step of decompressing said compressed band in display order for each band in said page to be displayed.

27. A method as recited in claim 25 wherein said subregions are characterized as empty regions if they do not contain an object or non-empty if they contain one or more objects, and where adjacent non-empty subregions are combined into a single subregion before compressing said subregions if all the objects contained in the adjacent subregions are of the same type.

28. A method as recited in claim 22 wherein a compression method is selected only for said non-empty subregions and where only said non-empty subregions are compressed in said compressing step.

29. A method as recited in claim 21 wherein said step of selecting a compression method includes using pre-defined constraints to select said compression method, said pre-defined constraints including an estimated compression ratio achieved when compressing said region and the visual quality of said region when displayed after said region is compressed.

30. A method as recited in claim 21 wherein said step of storing said compressed band in said compressed band buffer includes checking when said compressed band fits in said compressed band buffer and recompressing previously compressed bands, when necessary, to fit said compressed band in said compressed band buffer.

31. A method as recited in claim 30 wherein said regions of said band are compressed at a compression level, and wherein said step of storing said compressed band in said compressed band buffer includes selecting a new compression level, and decompressing and recompressing all previously compressed bands at a new compression level before compressing said compressed band at said new compression level.

32. A method as recited in claim 21 wherein said step of sending said decompressed band to said output display includes outputting background display data for portions of said page not covered by said compressed regions.

33. A method as recited in claim 32 wherein said step of sending said decompressed bands to said output display includes determining where an output scan line intersects said regions of a band such that said compressed regions are decompressed when said scan line intersects said regions.

34. A system for compressing and decompressing data comprising:

a memory;

means for storing received data including a plurality of display lists, said received data including one or more objects each having a type, said objects organized into at least one page, said page organized into a plurality of bands, wherein a display list is provided for each band of said page;

means for identifying a band of data for processing including means for storing objects from a display list associated with said identified band in an uncompressed band buffer included in said memory;

means for partitioning said objects into non-overlapping regions and storing said regions in a region buffer included in said memory, each of said regions that include objects characterized by a type selected from one of the types of one of the objects that said region covers;

means for compressing said regions using said type of each of said regions to select a compression method from a plurality of compression method from a plurality of compression methods and storing said compressed regions in a compressed band buffer included in said memory;

means for decompressing said regions using said type of each of said regions to select a decompression method from a plurality of decompression methods and storing said decompressed regions in said compressed band buffer; and

an output display device for receiving decompressed data from said means for decompressing and displaying said decompressed data.

35. A system as recited in claim 34 further comprising means for rasterizing at least some of said objects from said display list into said uncompressed band buffer.

36. A system as recited in claim 34 wherein said means for partitioning said objects includes storing coordinates of objects in arrays in said memory and assigning regions to areas of said band between said coordinates.

37. A system as recited in claim 34 wherein said regions are characterized as either empty regions covering no objects, or as non-empty regions covering objects, said system further including means for combining adjacent non-empty regions into a single region.

38. A system as recited in claim 37 wherein said means for combining combines non-empty regions having the same selected compression algorithm into a single region.

39. A digital output processing system as recited in claim 37 wherein said means for combining combines non-empty regions having the same type and any empty regions disposed between said non-empty regions into a single region when there is insufficient space in said compressed band buffer to store an entire band of data.

40. A system as recited in claim 37 wherein said means for compressing only compresses non-empty regions.

41. A system as recited in claim 34 wherein said means for decompressing means further includes means for outputting background data to said output display device when compressed region data is not being displayed.

42. A system for processing data objects each representing display data for a display area and each having a data type and a location in the display area, comprising:

a divider for dividing the display area into a plurality of non-overlapping non-empty regions, where each region contains all or part of at least one data object and each region has a location and a region type derived from the data types of the object data in the region;

a plurality of compression mechanisms and decompression mechanisms, where each compression mechanism has an associated decompression mechanism;

a compressor that selects one of the compression mechanisms for each of the non-empty regions according to its region type and then uses the selected compression mechanism to compress those portions of the object data found in the region, thereby producing compressed object data;

a memory coupled to the compressor for storing compressed object data;

a decompressor coupled to the memory that decompresses compressed object data to produce uncompressed object data by applying to each compressed object data a decompression mechanism associated with the compression mechanism used to create the compressed object data; and

a monitor coupled to the compressor, decompressor, and memory for detecting when the memory is becoming full and triggering the decompression of previously compressed object data and the recompression thereof to free up space in the memory.

43. The system of claim 42 further comprising an object data combiner for combining one or more regions of uncompressed object data into a single region of uncompressed object data, where:

the object data combiner is invoked when the monitor has detected the memory is becoming full; and

the object combiner combines the uncompressed object data associated with each region according to predefined criteria, the uncompressed object data for the combined region to be recompressed by the compressor resulting in the freeing up of space in the memory.

44. The system of claim 43 wherein the object data combiner combines regions of uncompressed object data into a single combined region when a cost of combining the objects, determined by the separation between the regions, is under a predetermined threshold.

45. The system of claim 44 wherein the cost of combining is determined by the amount of background data that is included in a combined resulting region compared to the amount of object data included in the regions that were to be combined.

46. The system of claim 42 wherein the predefined criteria include combining adjacent regions that are of the same type and combining non-adjacent regions that are of the same type if the space separating the non-adjacent regions does not contain any object data.

47. The system of claim 42 further comprising a display engine coupled to receive uncompressed object data from the decompressor.

48. The system of claim 47 where the display engine is one of the group consisting of a laser printer engine, a plotter, and a CRT.

49. The system of claim 42 further comprising an embedded computer comprising:

a computer processor, and

a program memory coupled to the computer processor; and

a display engine coupled to receive uncompressed object data from the decompressor;

where

the display engine is coupled to the embedded computer; and

the compressor and decompressor are implemented as computer program instructions tangibly stored in the program memory.

50. The system of claim 42 further comprising:

means coupled to the decompressor for displaying the uncompressed object data; and

means for updating a pointer to indicate a next portion of a display area to display such that when the pointer intersects a non-empty region the decompressor decompresses and outputs the compressed data associated with the non-empty region and when the pointer does not intersect a non-empty region the decompressor outputs background data.

51. A system for processing data objects each representing display data for a page and each having a data type and a location on the page, where the page is divided into bands, the system comprising:

a memory;

a display list in the memory for each band of the page for storing those portions of the object data found in the band;

a divider coupled to the display list memory for dividing the object data in each band into a plurality of non-overlapping non-empty regions where each region contains all or part of at least one data object and each region has a location and a region type derived from the data types of the object data in the region;

a plurality of compression mechanisms and decompression mechanisms, where each compression mechanism has an associated decompression mechanism;

a compressor that selects one of the compression mechanisms for each of the non-empty regions according to the corresponding region type, uses the selected compression mechanism to compress the object data found in the region, thereby producing compressed object data, and stores compressed object data in the memory;

a decompressor coupled to the memory that decompresses compressed object data to produce uncompressed object data by applying to the compressed object data a decompression mechanism associated with the compression mechanism used to create the compressed object data; and

a monitor coupled to the compressor, decompressor, and memory for detecting when the memory is becoming full and triggering the decompression of previously compressed object data and the recompression thereof to free up space in the memory.

52. The system of claim 51 further comprising:

a rasterizer coupled to the display list memory to rasterize the data objects to produce bitmaps stored in the non-empty regions; and

a raster output device display engine coupled to receive uncompressed object data;

where the compression mechanisms operate on bitmaps to produce compressed bitmap object data; and

the decompression mechanisms operate on compressed bitmap object data to produce uncompressed bitmap object data for the raster output device display engine.

53. The system of claim 52 further comprising:

means for updating a pointer to indicate a next portion of a band to output to the raster output device such that when the pointer intersects a non-empty region the decompressor decompresses the compressed data associated with the non-empty region and outputs it, and when the pointer does not intersect a non-empty region the decompressor outputs background data.

54. A method for processing data objects each representing display data for a display area and having a data type and a location in the display area, the method comprising the steps of:

(a) receiving the data objects;

(b) storing the data objects in a display list associated with the display area;

(c) dividing the display area into a plurality of non-overlapping non-empty regions, each region including one or more data objects or portions of data objects and each region having a location and a region type derived from the data types of the data objects and portions of data objects in the region;

(d) providing a plurality of compression mechanisms and decompression mechanisms, where each compression mechanism has an associated decompression mechanism;

(e) compressing the object data in each non-empty region by selecting one of the compression mechanisms according to the corresponding region type and compressing the object data, thereby producing compressed object data;

(f) storing the compressed object data in a memory;

(g) decompressing the compressed object data by selecting a decompression mechanism associated with the compression mechanism used to create the compressed object data and decompressing the compressed object data to produce uncompressed object data; and

,

(h) monitoring to detect when the memory is becoming full and triggering the decompression of previously compressed object data and the recompression thereof to free up space in the memory.

55. The method of claim 54 further comprising the steps of:

combining a plurality of regions of uncompressed object data into a combined region of object data when the memory is becoming full; and

compressing the object data in the resulting combined region to free up space in the memory.

56. The method of claim 55 wherein regions are combined when a cost of combining the objects, determined by the separation between the regions, is under a predetermined threshold.

57. The method of claim 56 wherein the cost of combining is determined by the amount of background data that is included in a combined resulting region as compared to the amount of object data included in the regions that were to be combined.

58. A method for processing data objects each representing display data for a display area and having a data type and a location in the display area, the method comprising the steps of:

receiving the data objects;

establishing in the display area a plurality of non-overlapping bands;

dividing any data objects that span more than one band into multiple data objects that are each located in only one band;

establishing for each band a display list associated with the band;

storing the data objects located in a band in the display list associated with the band;

dividing each band into a plurality of non-overlapping non-empty regions each having a location and a region type derived from the data types of the data objects in the region;

providing a plurality of compression mechanisms and decompression mechanisms, where each compression mechanism has an associated decompression mechanism;

compressing a first band of data objects by selecting one of the compression mechanisms for each non-empty region in the first band according to the corresponding region type and using the selected compression mechanism to compress the data objects in the region, thereby producing compressed data objects;

storing the compressed data objects in a memory;

compressing and storing the remaining bands in the display area by applying to them the preceding two steps, respectively;

decompressing each band of compressed data objects by selecting for each compressed data object a decompression mechanism associated with the compression mechanism used to create the compressed data object and decompressing it to produce an uncompressed data object; and

monitoring to detect when the memory is becoming full and triggering the decompression of previously compressed data objects and the recompression thereof to free up space in the memory.

59. The method of claim 58 further comprising the steps of:

sending the uncompressed data objects to an output display; and

determining where an output scan line intersects the regions of a band such that the compressed regions are decompressed when the scan line intersects the regions.

60. The method of claim 58 further comprising the step of:

sending the uncompressed data objects to an output display; and

outputting background display data for portions of the page not covered by uncompressed data objects.