Apparatus and method for hybrid compression of raster data

• US 5,982,937 A
• Filed: 12/24/1996
• Issued: 11/09/1999
• Est. Priority Date: 12/24/1996
• Status: Expired due to Term

• Current Assignee: Electronics For Imaging Incorporated
• Original Assignee: Electronics For Imaging Incorporated
• Inventors: Accad, Yigal
• Primary Examiner(s): Lee, Thomas D
• Assistant Examiner(s): BRINICH, STEPHEN M
• Application Number:
  US08/773,656
• Time in Patent Office: 1,050 Days
• Field of Search: 358/430, 358/539, 382/166, 382/239, 382/243
• 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

From a raster page, patches of connected pixels of the same color are identified. Patches of at least a predetermined sized, typically corresponding to text or line art objects, are subjected to a lossless compression. Patches below the predetermined size, typically corresponding to image or photo objects, are substantially subjected to a lossy compression. The patch predetermined size controls the mix of lossless and lossy compression procedures. Optimum compression is achieved by maximizing the lossless compression while attaining a targeted compression ratio. Various features include efficient recognition and encoding of patches, refined treatment of the boundaries between the lossless- and the lossy-compressed pixels, adaptive compression ratio control, and fail-safe compression provisions.

Claims

1. An apparatus for hybrid compression of raster data, said raster data being an array of pixels with each pixel representing a color at a position in the array, comprising:

a first storage for buffering subarrays of the array of pixels;

a patch recognizer operating on individual subarrays and recognizing patches of connected pixels of the same color therein, each patch having a determinable number of pixels;

a patch type discriminator separating individual patches into either a first type patch or a second type patch, depending respectively on whether or not the number of pixels in a patch is at least of a predetermined number;

a first compressor employing a first encoding procedure to encode pixels of the first type patches into encoded data of a first type; and

a second compressor employing a second encoding procedure to encode pixels of the second type patches into encoded data of a second type,

thereby allowing the encoded data of the first and second types to be stored in a storage in compressed form, and to be decodeable substantially by inverting the respective encoding procedures to obtain reconstructed pixels of said array.

2. An apparatus for hybrid compression of raster data as in claim 1, wherein:

said first encoding procedure is a lossless encoding; and

said second encoding procedure is a lossy encoding.

3. An apparatus for hybrid compression of raster data as in claim 1, wherein said first encoding procedure includes a run-length encoding.

4. An apparatus for hybrid compression of raster data as in claim 1, wherein said second encoding procedure includes a transform encoding.

5. An apparatus for hybrid compression of raster data as in claim 1, further comprising:

an adaptive controller that monitors a compression ratio attained by said apparatus at predetermined instants, said compression ratio being given by the number of bits required to store the portion of raster data that has been subject to encoding to date divided by the number of bits required to store the corresponding encoded raster data,

said adaptive controller, in a given instant responsive to a comparison between a compression ratio monitored and a targeted compression ratio, adaptively adjusting one or more compression parameters affecting the compression of said second compression procedure for meeting the targeted compression ratio.

6. An apparatus for hybrid compression of raster data as in claim 1, wherein said apparatus is responsive to a set of compression parameters for attaining a given compression ratio, said compression ratio being given by the number of bits required to store the raster data divided by the number of bits required to store the encoded raster data, said apparatus further comprising:

a recompression controller, responsive to an indication that a currently attained compression ratio not meeting a targeted compression ratio, for allowing the encoded raster data to be decoded to the raster data, and allowing said apparatus to recompress the raster data with another set of compression parameters that produces a higher compression ratio than said currently attained.

7. An apparatus for hybrid compression of raster data as in claim 6, wherein the set of compression parameters includes the predetermined number associated with the number of pixels in a patch.

8. An apparatus for hybrid compression of raster data as in claim 1, wherein:

said first encoding procedure includes a run-length encoding; and

said second encoding procedure includes a transform encoding that operates on a plurality of blocks to form transform encoded data, each block being a predefined matrix of pixels of the array.

9. An apparatus for hybrid compression of raster data as in claim 8, wherein the transform encoding is a JPEG encoding that operates on a plurality of blocks to form JPEG encoded data, each block being an 8×

8 pixel block of the array.

10. An apparatus for hybrid compression of raster data as in claim 8, wherein said patch type discriminator further includes an in-block counter that determines whether or not it is true that a block contains at least a predetermined threshold number of pixels of the second type patches, and if not true, reclassifies and separates these pixels as belonging to the first type patches.

11. An apparatus for hybrid compression of raster data as in claim 8, wherein for a block that is partially filled with pixels of the second type patches, said block'"'"'s complement pixels individually have a color value substantially given by averaging the color values of said pixels partially filling the block.

12. An apparatus for hybrid compression of raster data as in claim 8, wherein:

said patch type discriminator also generates position tags associated with pixels of the second type patches, said position tags being directed to said first compressor to be encoded by the first encoding procedure; and

such that when the encoded data of the first and second type are decoded into reconstructed pixels, the raster data is reconstructed from those reconstructed pixels of the first type patches and those reconstructed pixels of the second type patches having associated position tags.

13. An apparatus for hybrid compression of raster data as in claim 9, wherein:

said patch type discriminator also generates position tags associated with pixels of the second type patches, said position tags being directed to said first compressor to be encoded by the first encoding procedure; and

such that when the encoded data of the first and second type are decoded into reconstructed pixels, the raster data is reconstructed from those reconstructed pixels of the first type patches and those reconstructed pixels of the second type patches having associated position tags.

14. An apparatus for hybrid compression of raster data as in any one of claims 1 to 13, wherein said apparatus employs a first pass of said first compressor to serve also as said patch recognizer such that said first pass of said first compressor recognizes patches of connected pixels of the same color and also encodes first type patches during the recognition.

15. An apparatus for hybrid compression and decompression of raster data, said raster data being an array of pixels with each pixel representing a color at a position in the array, comprising:

a first storage for buffering subarrays of the array of pixels;

a patch recognizer operating on individual subarrays and recognizing patches of connected pixels of the same color therein, each patch having a determinable number of pixels;

a patch type discriminator separating individual patches into either a first type patch or a second type patch, depending respectively on whether or not the number of pixels in a patch is at least of a predetermined number;

a first compressor employing a first encoding procedure to encode pixels of the first type patches into encoded data of a first type; and

a second compressor employing a second encoding procedure to encode pixels of the second type patches into encoded data of a second type;

a second storage for storing the encoded data of the first and second types; and

first and second decompressors coupled to said second storage for respectively decoding the encoded data of the first and second types into corresponding pixels of said array to reconstruct the raster data.

16. An apparatus for hybrid compression and decompression of raster data as in claim 15, wherein:

said first decompressor decodes encoded data of the first type into reconstructed pixels of a first type and position tags associated with pixels of a second type; and

said second decompressor decodes encoded data of a second type into reconstructed pixels of the second type,

such that those reconstructed pixels of the first type and those reconstructed pixels of the second type having an associated position tag are decoded into their respective positions in the array to reconstruct the raster data.

17. An apparatus for hybrid compression and decompression of raster data as in claim 15, wherein:

said first encoding procedure is a lossless encoding; and

said second encoding procedure is a lossy encoding.

18. An apparatus for hybrid compression and decompression of raster data as in claim 15, wherein said first encoding procedure includes a run-length encoding.

19. An apparatus for hybrid compression and decompression of raster data as in claim 15, wherein said second encoding procedure includes a transform encoding.

20. An apparatus for hybrid compression and decompression of raster data as in claim 15, further comprising:

an adaptive controller that monitors a compression ratio attained by said apparatus at predetermined instants, said compression ratio being given by the number of bits required to store the portion of raster data that has been subject to encoding to date divided by the number of bits required to store the corresponding encoded raster data,

said adaptive controller, in a given instant responsive to a comparison between a compression ratio monitored and a targeted compression ratio, adaptively adjusting one or more compression parameters affecting the compression of said second compression procedure for meeting the targeted compression ratio.

21. An apparatus for hybrid compression and decompression of raster data as in claim 15, wherein said apparatus is responsive to a set of compression parameters for attaining a given compression ratio, said compression ratio being given by the number of bits required to store the raster data divided by the number of bits required to store the encoded raster data, said apparatus further comprising:

a recompression controller, responsive to an indication that a currently attained compression ratio not meeting a targeted compression ratio, for allowing the encoded raster data to be decoded to the raster data, and allowing said apparatus to recompress the raster data with another set of compression parameters that produces a higher compression ratio than said currently attained.

22. An apparatus for hybrid compression and decompression of raster data as in claim 21, wherein the set of compression parameters includes the predetermined number associated with the number of pixels in a patch.

23. An apparatus for hybrid compression and decompression of raster data as in claim 15, wherein:

said first encoding procedure includes a run-length encoding; and

said second encoding procedure includes a transform encoding that operates on a plurality of blocks to form transform encoded data, each block being a predefined matrix of pixels of the array.

24. An apparatus for hybrid compression and decompression of raster data as in claim 23, wherein the transform encoding is a JPEG encoding that operates on a plurality of blocks to form JPEG encoded data, each block being an 8×

8 pixel block of the array.

25. An apparatus for hybrid compression and decompression of raster data as in claim 23, wherein said patch type discriminator further includes an in-block counter that determines whether or not it is true that a block contains at least a predetermined threshold number of pixels of the second type patches, and if not true, reclassifies and separates these pixels as belonging to the first type patches.

26. An apparatus for hybrid compression and decompression of raster data as in claim 23, wherein for a block that is partially filled with pixels of the second type patches, said block'"'"'s complement pixels individually have a color value substantially given by averaging the color values of said pixels partially filling the block.

27. An apparatus for hybrid compression and decompression of raster data as in claim 23, wherein:

said patch type discriminator also generates position tags associated with pixels of the second type patches, said position tags being directed to said first compressor to be encoded by the first encoding procedure; and

such that when the encoded data of the first and second type are decoded into reconstructed pixels, the raster data is reconstructed from those reconstructed pixels of the first type patches and those reconstructed pixels of the second type patches having associated position tags.

28. An apparatus for hybrid compression and decompression of raster data as in claim 24, wherein:

said patch type discriminator also generates position tags associated with pixels of the second type patches, said position tags being directed to said first compressor to be encoded by the first encoding procedure; and

such that when the encoded data of the first and second type are decoded into reconstructed pixels, the raster data is reconstructed from those reconstructed pixels of the first type patches and those reconstructed pixels of the second type patches having associated position tags.

29. An apparatus for hybrid compression and decompression of raster data as in any one of claims 15 to 28, wherein said apparatus employs a first pass of said first compressor to serve also as said patch recognizer such that said first pass of said first compressor recognizes patches of connected pixels of the same color and also encodes first type patches during the recognition.

30. A method for hybrid compression of raster data, said raster data being an array of pixels with each pixel representing a color at a position in the array, comprising:

identifying patches of connected pixels of the same color;

discriminating whether each patch has a size that belongs to a first or second type, wherein a patch of said first type contains pixels of at least a predetermined number and a patch of said second type contains pixels less than said predetermined number;

encoding patches belonging to said first type by a first compression procedure; and

encoding patches belonging to said second type by a second compression procedure.

31. A method for hybrid compression of raster data as in claim 30, wherein:

said first encoding procedure is a lossless encoding; and

said second encoding procedure is a lossy encoding.

32. A method for hybrid compression of raster data as in claim 30, wherein said first encoding procedure includes a run-length encoding.

33. A method for hybrid compression of raster data as in claim 30, wherein second encoding procedure includes a transform encoding.

34. A method for hybrid compression of raster data as in claim 30, wherein said predetermined number is such that the raster page is compressed preferentially by said first compression procedure while attaining at least a targeted compression ratio.

35. A method for hybrid compression of raster data as in claim 30, further comprising:

monitoring a compression ratio attained by said method at predetermined instants, said compression ratio being given by the number of bits required to store the portion of raster data that has been subject to encoding to date divided by the number of bits required to store the corresponding encoded raster data,

responsive to a comparison between a compression ratio monitored and a targeted compression ratio in a given instant, adaptively adjusting one or more compression parameters affecting the compression of said second compression procedure for meeting the targeted compression ratio.

36. A method for hybrid compression of raster data as in claim 30, wherein said method is responsive to a set of compression parameters for attaining a given compression ratio, said compression ratio being given by the number of bits required to store the raster data divided by the number of bits required to store the encoded raster data, said method further comprising:

responsive to an indication that a currently attained compression ratio not meeting a targeted compression ratio, decoding the encoded raster data to the raster data, and recompressing the raster data with another set of compression parameters that produces a higher compression ratio than said currently attained.

37. A method for hybrid compression of raster data as in claim 36, wherein the set of compression parameters includes the predetermined number associated with the number of pixels in a patch.

38. A method for hybrid compression of raster data as in claim 30, wherein:

said first encoding procedure includes a run-length encoding; and

said second encoding procedure includes a transform encoding that operates on a plurality of blocks to form transform encoded data, each block being a predefined matrix of pixels of the array.

39. A method for hybrid compression of raster data as in claim 38, wherein the transform encoding is a JPEG encoding that operates on a plurality of blocks to form JPEG encoded data, each block being an 8×

8 pixel block of the array.

40. A method for hybrid compression of raster data as in claim 38, wherein said patch discriminating step further includes determining whether or not it is true that a block contains at least a predetermined threshold number of pixels of the second type patches, and if not true, reclassifying and separating these pixels as belonging to the first type patches.

41. A method for hybrid compression of raster data as in claim 38, wherein for a block that is partially filled with pixels of the second type patches, said block'"'"'s complement pixels individually have a color value substantially given by averaging the color values of said pixels partially filling the block.

42. A method for hybrid compression of raster data as in claim 38, wherein:

said patch discriminating step includes generating position tags associated with pixels of the second type patches, said position tags being directed to said first compressor to be encoded by the first encoding procedure; and

such that when the encoded data of the first and second type are decoded into reconstructed pixels, the raster data is reconstructed from those reconstructed pixels of the first type patches and those reconstructed pixels of the second type patches having associated position tags.

43. A method for hybrid compression of raster data as in claim 39, wherein:

said patch discriminating step includes generating position tags associated with pixels of the second type patches, said position tags being directed to said first compressor to be encoded by the first encoding procedure; and

such that when the encoded data of the first and second type are decoded into reconstructed pixels, the raster data is reconstructed from those reconstructed pixels of the first type patches and those reconstructed pixels of the second type patches having associated position tags.

44. A method for hybrid compression of raster data as in any one of claims 30 to 43, wherein said method employs a first pass of said first compressing procedure to identify patches of connected pixels of the same color and also to encode first type patches during the identifying of patches.

45. A method for hybrid compression of raster data as in claim 30, further comprising:

providing first and second layers of raster data that individually have a corresponding array of pixels as the raster data;

assigning to said first layer pixels from patches belonging to said first type and associated position tags corresponding to pixels from patches belonging to said second type;

assigning to said second layer pixels from patches belonging to said second type to said second layer; and

forming a representation of the raster data by superposition of first and second layers of raster data; and

applying said first compression procedure to said first layer and said second compression procedure to said second layer.

46. A method for hybrid compression and decompression of raster data, said raster data being an array of pixels with each pixel representing a color at a position in the array, comprising:

buffering subarrays of the array of pixels in a first storage;

identifying in individual subarrays patches of connected pixels of the same color, each patch having a determinable number of pixels;

discriminating and separating individual patches into either a first type patch or a second type patch, depending respectively on whether or not the number of pixels in a patch is at least of a predetermined number;

employing a first encoding procedure to encode pixels of the first type patches into encoded data of a first type; and

employing a second encoding procedure to encode pixels of the second type patches into encoded data of a second type;

storing the encoded data of the first and second types in a second storage; and

decoding the encoded data of the first and second types in the second storage into corresponding pixels of said array to reconstruct the raster data.

47. A method for hybrid compression and decompression of raster data as in claim 46, wherein:

the encoded data of the first type is decoded into reconstructed pixels of a first type and position tags associated with pixels of a second type; and

the encoded data of a second type is decoded into reconstructed pixels of the second type,

such that those reconstructed pixels of the first type and those reconstructed pixels of the second type having an associated position tag are decoded into their respective positions in the array to reconstruct the raster data.

48. A method for hybrid compression and decompression of raster data as in claim 46, wherein:

said first encoding procedure is a lossless encoding; and

said second encoding procedure is a lossy encoding.

49. A method for hybrid compression and decompression of raster data as in claim 46, wherein said first encoding procedure includes a run-length encoding.

50. A method for hybrid compression and decompression of raster data as in claim 46, wherein said second encoding procedure includes a transform encoding.

51. A method for hybrid compression and decompression of raster data as in claim 46, further comprising:

monitoring a compression ratio attained by said method at predetermined instants, said compression ratio being given by the number of bits required to store the portion of raster data that has been subject to encoding to date divided by the number of bits required to store the corresponding encoded raster data,

responsive to a comparison between a compression ratio monitored and a targeted compression ratio in a given instant, adaptively adjusting one or more compression parameters affecting the compression of said second compression procedure for meeting the targeted compression ratio.

52. A method for hybrid compression and decompression of raster data as in claim 46, wherein said method is responsive to a set of compression parameters for attaining a given compression ratio, said compression ratio being given by the number of bits required to store the raster data divided by the number of bits required to store the encoded raster data, said method further comprising:

responsive to an indication that a currently attained compression ratio not meeting a targeted compression ratio, decoding the encoded raster data to the raster data, and recompressing the raster data with another set of compression parameters that produces a higher compression ratio than said currently attained.

53. A method for hybrid compression and decompression of raster data as in claim 52, wherein the set of compression parameters includes the predetermined number associated with the number of pixels in a patch.

54. A method for hybrid compression and decompression of raster data as in claim 46, wherein:

said first encoding procedure includes a run-length encoding; and

said second encoding procedure includes a transform encoding that operates on a plurality of blocks to form transform encoded data, each block being a predefined matrix of pixels of the array.

55. A method for hybrid compression and decompression of raster data as in claim 54, wherein the transform encoding is a JPEG encoding that operates on a plurality of blocks to form JPEG encoded data, each block being an 8×

8 pixel block of the array.

56. A method for hybrid compression and decompression of raster data as in claim 54, wherein said patch discriminating step further includes determining whether or not it is true that a block contains at least a predetermined threshold number of pixels of the second type patches, and if not true, reclassifying and separating these pixels as belonging to the first type patches.

57. A method for hybrid compression and decompression of raster data as in claim 54, wherein for a block that is partially filled with pixels of the second type patches, said block'"'"'s complement pixels individually have a color value substantially given by averaging the color values of said pixels partially filling the block.

58. A method for hybrid compression and decompression of raster data as in claim 54, wherein:

said patch discriminating step includes generating position tags associated with pixels of the second type patches, said position tags being directed to said first compressor to be encoded by the first encoding procedure; and

such that when the encoded data of the first and second type are decoded into reconstructed pixels, the raster data is reconstructed from those reconstructed pixels of the first type patches and those reconstructed pixels of the second type patches having associated position tags.

59. A method for hybrid compression and decompression of raster data as in claim 55, wherein:

said patch discriminating step includes generating position tags associated with pixels of the second type patches, said position tags being directed to said first compressor to be encoded by the first encoding procedure; and

such that when the encoded data of the first and second type are decoded into reconstructed pixels, the raster data is reconstructed from those reconstructed pixels of the first type patches and those reconstructed pixels of the second type patches having associated position tags.

60. A method for hybrid compression and decompression of raster data as in any one of claims 46 to 59, wherein said method employs a first pass of said first compressing procedure to identify patches of connected pixels of the same color and also to encode first type patches during the identifying of patches.