Single-pass guaranteed-fit data compression using rate feedback

• US 7,003,167 B2
• Filed: 11/01/2001
• Issued: 02/21/2006
• Est. Priority Date: 11/01/2001
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Mukherjee, Debargha
• Primary Examiner(s): Chen, Wenpeng
• Application Number:
  US10/036,663
• Publication Number:
  US 20030081845A1
• Time in Patent Office: 1,573 Days
• Field of Search: 382/232, 382239-168, 382/250, 382251-270, 375/240.03, 375/240.02, 375/240.14, 375/240.15, 375/240.05, 375/240.12, 375/240, 358/466, 341/61
• US Class Current: 382/239
• CPC Class Codes: H04N 1/333 Mode signalling or mode changing; Handshaking therefor
• 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

An image-compression system provides for high-quality guaranteed-fit image block-by-block compression in a single pass. A baseline block-target allocator determines a baseline target size for the compressed blocks resulting from the source-image blocks. A block target-size accumulator determines a target block size by adding any excess compression from the preceding block to the baseline, as indicated by a compressed-block size reader. A mode selector performs a content analysis of the current block. It then selects among the compression modes guaranteed to meet the target block size one that achieves optimal image quality. A compression encoder compresses the current block according to the selected compression mode.

Claims

1. A single pass compression method for regulating compression of serialized input data as a function of an in-progress measure of said compression:

a) converting source data into a series of blocks each containing one or more colors, said series including a first block, intermediate blocks, and a last block;

b) determining a baseline target block size based upon a target compression ratio for said source data;

c) for each block in turn, determining a current target block size, the current target block size for said first block being said baseline target block size, the current target block size for said intermediate block and said last block being equal to the said current baseline target block size plus an accumulating savings associated with the preceding block in said series;

d) for each block in turn, selecting a compression mode based on the number of colors in said block, said compression mode to compress that block so that the resulting compressed block fits its corresponding target block size as determined in step c; and

e) for each block in turn, compressing the block using the compression mode selected in step d to yield a corresponding compressed block.

2. The method as recited in claim 1, further comprising:

f) for each of said first and intermediate blocks in turn, determining said accumulated savings as a function of the size of the compressed block resulting from step e.

3. A method as recited in claim 2 wherein step f comprises determining the size of the compressed block resulting from step e and determining said savings in part as a function of said size.

4. A method as recited in claim 1 wherein said mode is selected from mode families, said mode families including an n-color mode family including lossless or lossy n-color compression modes, and a BTC-VQ mode family including lossy BTC-VQ compression modes.

5. A method as recited in claim 4, wherein said colors are clustered to form one or more color clusters, and said selected mode family is selected from said n-color mode family if said source image comprises less then a predetermined number of distinct color clusters and is selected from said BTC-VQ mode family if said source image comprises more than a predetermined number of distinct color clusters.

6. A method as recited in claim 4 wherein said families further include a raw mode family including at least a degenerate raw compression mode in which the current block is transmitted uncompressed.

7. A method as recited in claim 4 wherein said families further include an interpolated mode family including plural interpolation modes.

8. A method as recited in claim 5 wherein said predetermined number is four.

9. A method as recited in claim 1 wherein said source data comprises a compound document.

10. A method as recited in claim 1 wherein said function is greedy with respect to a target block size.

11. A single pass image compression system comprising:

an encoder for sequentially compressing a series of source blocks each containing one or more colors, said encoder implementing plural compression modes with respective predetermined maximum compressed block sizes;

a mode selector coupled to said encoder for selecting one of said compression modes for compressing a given source block based on the number of colors in said given source block, said mode selector selecting a compression mode at least in part as a function of a target block size for a current source block;

an evaluator for determining the target block size for each of said source blocks; and

an allocator for determining a baseline target block size based upon a target compression ratio for said source image.

12. A system as recited in claim 11 wherein said evaluator includes a block-size reader for determining the block size of a compressed block resulting from compressing of a respective source block, said evaluator determining said target block size in part as a function of the size of said compressed block.

13. A system as recited in claim 11 wherein said mode selector assigns some of said source blocks to an n-color mode family of n-color compression modes and other source blocks to a BTC-VQ mode family of BTC-VQ compression modes.

14. A system as recited in claim 13 wherein said mode selector assigns some of said source blocks to a raw mode family of modes including an uncompressed raw mode.

15. A system as recited in claim 14 wherein said raw mode family also includes truncated raw modes.

16. A system as recited in claim 15 wherein said mode selector assigns some of said source blocks to a family of interpolated compression modes.