Method and apparatus for compressing mixed text and image data

• US 5,832,126 A
• Filed: 07/03/1996
• Issued: 11/03/1998
• Est. Priority Date: 07/07/1995
• Status: Expired due to Term

• Current Assignee: Oki Data Corporation (OKI Electric Industry Company Limited)
• Original Assignee: Oki Data Corporation (OKI Electric Industry Company Limited)
• Inventors: Tanaka, Kimiyuki
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Tadayon, Bijan
• Application Number:
  US08/675,047
• Time in Patent Office: 853 Days
• Field of Search: 382/168, 382/169, 382/170, 382/171, 382/172, 382/173, 382/174, 382/175, 382/176, 382/177, 382/178, 382/179, 382/180, 382/181, 382/232, 382/233, 382/234, 382/235, 382/237, 382/239, 382/240, 382/244, 382/245, 382/246, 382/248, 382/249, 382/250, 382/251, 382/252, 382/253, 382/238, 358/426, 358/261.1, 358/261.2, 358/261.3, 358/262.1, 358/430, 358/433, 358/464, 358/450, 358/453
• US Class Current: 382/239
• 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: 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

To convert a mixture of text data and dot-mapped image data to compressed dot-mapped data not exceeding a given size, the text data are converted to dot-mapped data, then losslessly compressed, after which the dot-mapped image data are down-sampled as necessary. To compress dot-mapped data to within a given size, lossless compression, lossy compression, and down-sampling followed by compression are attempted until the necessary size reduction is achieved. To convert a page of object data to compressed dot-mapped data, the objects are classified and prioritized, then rasterized and compressed by different methods according to their priorities. The compression ratios are predicted and monitored, and the compression parameters are modified according to the prediction error.

Claims

1. A method of compressing data of mixed types having different priority levels to within a given size, comprising the steps of:

separating said data of mixed types into data of a first type and data of a second type, the data of said first type having a higher priority than the data of said second type;

compressing the data of said first type using a first compression method, producing compressed data of said first type;

storing the compressed data of said first type in a memory area having said given size;

calculating a remaining size of said memory area by subtracting a size of the compressed data of said first type from said given size;

selecting a second compression method having a compression ratio not less than a ratio of a size of the data of said second type to said remaining size;

compressing the data of said second type using said second compression method, producing compressed data of said second type; and

storing the compressed data of said second type in said memory area.

2. The method of claim 1, wherein said compression ratio is unity if the size of the data of said second type does not exceed said remaining size.

3. The method of claim 1, comprising the further step of transmitting the compressed data of said first type and the compressed data of said second type from said memory area to a printer having a page buffer of said given size.

4. The method of claim 1, wherein said method is carried out on successive strips of the data of mixed types, comprising the further step of:

updating said given size by subtracting a size of said compressed data of said second type from said remaining size.

5. The method of claim 1, wherein said step of compressing the data of said second type further comprises the steps of:

compressing the data of said second type using a lossless compression method, thereby producing first compressed data of said second type; and

compressing the data of said second type using a lossy compression method, thereby producing second compressed data of said second type, if said first compressed data of said second type have a size exceeding said remaining size.

32. The method of claim 1, wherein said data of said first type are dot-mapped text data, and said data of said second type are dot-mapped image data.

33. The method of claim 32, wherein said first compression method is a lossless compression method.

34. The method of claim 32, wherein said second compression method reduces a resolution of said dot-mapped image data according to said compression ratio.

6. An apparatus for compressing data of mixed types having different priority levels to within a given size, comprising:

a data separator for separating said data of mixed types into data of a first type and data of a second type, the data of said first type having a higher priority than the data of said second type;

a first data compressor for compressing the data of said first type using a first compression method, producing compressed data of said first type;

a control unit coupled to said first data compressor, for calculating a remaining size by subtracting a size of the compressed data of said first type from said given size, then calculating a compression ratio by comparing a size of the data of said second type with said remaining size; and

a second data compressor for compressing the data of said second type according to said compression ratio, producing compressed data of said second type.

7. The apparatus of claim 6, wherein said compression ratio is unity if a size of the data of said second type does not exceed said remaining size.

8. The apparatus of claim 6, further comprising:

a first buffer coupled to said first data compressor, for storing said compressed data of said first type; and

a second buffer coupled to said data separator, for storing said data of said second type prior to compression by said second data compressor.

9. The apparatus of claim 8, wherein said control unit also subtracts a size of said compressed data of said second type from said remaining size, and uses a resulting difference as an updated given size for use in compressing further data of said first type and further data of said second type.

35. The apparatus of claim 6, wherein said data of said first type are dot mapped text data, and said data of said second type are dot-mapped image data.

36. The apparatus of claim 35, wherein said first data compressor is a lossless data compressor.

37. The apparatus of claim 35, wherein said second data compressor reduces a resolution of said dot-mapped image data according to said compression ratio.

10. A method of compressing dot-mapped data to within a given size, comprising the steps of:

compressing said dot-mapped data using a first compression method, thereby producing first compressed data according to a first compression ratio;

comparing a size of said first compressed data with said given size;

compressing said dot-mapped data using a second compression method having a second compression ratio which is greater than said first compression ratio, thereby producing second compressed data, if the size of said first compressed data exceeds said given size;

comparing a size of said second compressed data with said given size; and

compressing said dot-mapped data using a third compression method having a third compression ratio which is greater than said second compression ratio, said third compression method including at least a reduction of resolution, thereby producing third compressed data, if the size of said second compressed data exceeds said given size.

11. The method of claim 10, wherein said third compression method also includes compression using a method selected from between said first compression method and said second compression method, following said reduction of resolution.

12. The method of claim 10, wherein said dot-mapped data constitute one page of data to be transmitted to a printer.

13. The method of claim 12, comprising the further steps of:

notifying a human user if the size of said first compressed data exceeds said given size;

proceeding to said step of compressing said dot-mapped data using a second compression method, responsive to a first command from said human user;

proceeding directly to said step of compressing said dot-mapped data using a third compression method, bypassing said step of compressing said dot-mapped data by a second compression method, responsive to a second command from said human user; and

skipping transmission of said one page of data, responsive to a third command from said human user.

14. An apparatus for compressing dot-mapped data to within a given size, for transmission of the compressed data from a computing device to a peripheral device, comprising:

first compression means, disposed in said computing device, for compressing said dot-mapped data to produce first compressed data according to a first compression ratio;

second compression means, disposed in said computing device, for compressing said dot-mapped data to produce second compressed data according to a second compression ratio which is greater than the first compression ratio;

resolution-reducing means, disposed in said computing device, for reducing a resolution of said dot-mapped data by a specifiable ratio; and

a control unit coupled to said first compression means and said second compression means,

for selecting said first compressed data if said first compressed data have a size not exceeding said given size,

for selecting said second compressed data if said first compressed data have a size exceeding said given size and said second compressed data have a size not exceeding said given size, and

for directing said resolution-reducing means to reduce said dot-mapped data, then selecting one compression means from between said first compression means and said second compression means and directing the selected compression means to compress the dot-mapped data as reduced by said resolution-reducing means, if both said first compressed data and said second compressed data have sizes exceeding said given size.

15. The apparatus of claim 14, wherein said first compression means is a lossless compression means, and said second compression means is a lossy compression means.

16. The apparatus of claim 14, wherein said control unit notifies a human user when a selected one of said first compression means and said second compression means fails to compress said dot-mapped data to within said given size.

17. The apparatus of claim 16, wherein said control unit selects different compression means from between said first compression means and said second compression means and decides whether to use said resolution-reducing means, responsive to commands from said human user.

18. A method of compressing data describing a group of objects forming a page of a documents to within a given size for transmission from a computing device to a peripheral device, comprising the steps of:

dividing said data into object data describing individual objects of different types on said page;

classifying said objects according to object type;

assigning priorities to said objects, according to object type;

selecting compression parameters for each of said objects, to said priorities; and

compressing the object data according to corresponding compression parameters, thereby producing compressed data.

19. The method of claim 18, further comprising the steps of:

calculating a predicted size of said compressed data from said compression parameters;

comparing an actual size of said compressed data with said predicted size to determine a prediction error; and

adjusting said compression parameters according to said prediction error.

20. The method of claim 19, wherein said step of adjusting comprises altering said compression parameters to obtain a higher compression ratio, when said actual size exceeds said predicted size by a certain amount.

21. The method of claim 19, comprising the further steps of:

storing said compressed data in an output buffer;

comparing a total size of the compressed data stored in said output buffer with said given size;

deleting at least part of the compressed data stored in said output buffer, if said total size exceeds said given size; and

again compressing the data from which the compressed data thus deleted was produced, using stronger compression parameters.

22. The method of claim 18, comprising the further steps of:

selecting resolution reduction ratios for said objects, according to said priorities; and

reducing a resolution of said object data according to said resolution reduction ratios.

23. The method of claim 19, wherein said object data comprise successive dot lines, and said steps of compressing, calculating, comparing, and adjusting are performed one dot line at a time.

24. The method of claim 19, wherein said steps of compressing, calculating, comparing, and adjusting are performed one object at a time.

25. The method of claim 18, comprising the further steps of:

calculating a total size of said object data; and

storing said object data directly in an output buffer, without performing said step of compressing, if said total size is within said given size.

38. The method of claim 20, wherein said step of adjusting also comprises altering said compression parameters to obtain a lower compression ratio, when said predicted size exceeds said actual size by another certain amount.

26. An apparatus for compressing object data describing a group of objects forming a page of a document to within a given size for transmission from a computing device to a peripheral device, comprising:

an object classifier, for reading header information about said objects, including information about object type, and classifying said objects according to object type;

a prioritizer coupled to said object classifier, for assigning priorities to said objects, responsive to object type;

a compression parameter selector coupled to said prioritizer, for selecting compression parameters for each of said objects, according to said priorities; and

a data compressor coupled to said compression parameter selector, for compressing said object data using different methods having different compression ratios, according to the compression parameters selected by said compression parameter selector, thereby producing compressed data.

27. The apparatus of claim 26, further comprising a data buffer for storing said object data prior to compression by said data compressor.

28. The apparatus of claim 26, further comprising a buffer space calculator coupled to said data compressor, for calculating a predicted size of said compressed data from said compression parameters, comparing an actual size of said compressed data with said predicted size to provide comparison results, and reporting the comparison results to said compression parameter selector so that said compression parameter selector adjusts said compression parameters according to the comparison results.

29. The apparatus of claim 28, further comprising an object data buffer coupled to said object classifier, for storing the object data;

and

a rasterizer coupled to said object classifier, for converting the object data stored in said object data buffer to dot-mapped data and reducing a resolution of said dot-mapped data, according to resolution ratios specified by said compression parameter selector, said priorities, and the comparison results reported by said buffer space calculator.

30. The apparatus of claim 29, wherein said data compressor compresses said data by compressing the dot-mapped data in said object data buffer, one object at a time.

31. The apparatus of claim 30, wherein said compression parameter selector specifies said resolution ratios responsive to said priorities, so that a higher-priority object among said group of objects never has a higher resolution ratio than a lower-priority object among said group of objects.

39. The apparatus of claim 27, wherein said object data comprise successive dot lines, and said data compressor compresses said object data one dot line at a time.