Apparatus and method for hybrid compression and decompression of raster data

• US 6,330,363 B1
• Filed: 01/07/1999
• Issued: 12/11/2001
• 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:
  US09/227,167
• Time in Patent Office: 1,069 Days
• Field of Search: 382/232-235, 382/239-240, 382/162, 382/166, 382/245, 382/248, 358/426, 358/430, 358/261--26
• US Class Current: 382/232
• 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 decompression of encoded raster data to raster data, said raster data being an array of pixels with each pixel representing a color at a position in the array and said encoded raster data being separable into encoded data of first and second types, comprising:

a first decompressor coupled to receive said encoded data of the first type for decoding into reconstructed pixels of a first type and position tags associated with pixels of a second type; and

a second decompressor coupled to receive said encoded data of the second type for decoding 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.

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

said encoded data of the first type is obtained by a lossless encoding; and

said encoded data of the second type is obtained by a lossy encoding.

3. An apparatus for hybrid decompression of encoded raster data to raster data as in claim 1, wherein said encoded data of the first type is obtained by an encoding procedure that includes a run-length encoding.

4. An apparatus for hybrid decompression of encoded raster data to raster data as in claim 1, wherein said encoded data of the second type is obtained by an encoding procedure that includes a transform encoding.

5. An apparatus for hybrid decompression of encoded raster data to raster data as in claim 1, wherein:

said encoded data of the first type is obtained by an encoding procedure that includes a run-length encoding; and

said encoded data of the second type is obtained by an encoding procedure that 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.

6. An apparatus for hybrid compression of encoded raster data to raster data as in claim 5, 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.

7. A method for hybrid decompression of encoded raster data to raster data, said raster data being an array of pixels with each pixel representing a color at a position in the array and said encoded raster data being separable into encoded data of first and second types, comprising:

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

decoding 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.

8. A method for hybrid decompression of encoded raster data to raster data as in claim 7, wherein:

said decoding of encoded data of the first type is a decoding of a lossless encoding; and

said decoding of encoded data of the second type is a decoding of a lossy encoding.

9. A method for hybrid decompression of encoded raster data to raster data as in claim 7, wherein said decoding of encoded data of the first type includes decoding of a run-length encoding.

10. A method for hybrid decompression of encoded raster data to raster data as in claim 7, wherein said decoding of encoded data of the second type includes decoding a transform encoding.

11. A method for hybrid decompression of encoded raster data to raster data as in claim 7, wherein:

said decoding of encoded data of the first type includes decoding of a run-length encoding; and

said decoding of encoded data of the second type includes decoding of 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.

12. A method for hybrid decompression of encoded raster data to raster data as in claim 7, 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.