Single-pass guaranteed-fit data compression using rate feedback

• US 20030081845A1
• Filed: 11/01/2001
• Published: 05/01/2003
• Est. Priority Date: 11/01/2001
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Said, Amir, Chrysalis, Christos, Mukherjee, Debargha
• Granted Patent: US 7,003,167 B2
• Time in Patent Office: Days
• 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 compression method comprising regulating compression of serialized input data as a function of an in-progress measure of said compression.

2. A method as recited in claim 1 further comprising a step of:

a) converting a source image into a series of blocks, said series including a first block, intermediate blocks, and a last block;

wherein, said regulating includes

b) determining a baseline target block size;

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 blocks and said last blocks being equal to 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 guaranteed to compress that block so that the resulting compressed block fits its corresponding target block size as determined in step c,

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

f) for each of said first and intermediate blocks in turn, determine said accumulated savings in part 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 involves 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 2 wherein step d involves analyzing the content of the block and selecting said compression mode in part as a function of results of that analysis.

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

6. A method as recited in claim 5 wherein each block with fewer than a predetermined number of distinct colors is assigned to said n-color family.

7. A method as recited in claim 5 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.

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

9. A method as recited in claim 2 wherein said source image is a compound document.

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

11. An image compression system comprising:

an encoder for sequentially compressing a series of source-image blocks, 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 one of said source-image blocks, said mode selector selecting one of said compression modes at least in part as a function of a target block size for a current source-image block; and

an evaluator for determining the target block size for each of said source-image blocks.

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-image 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 12 wherein said mode selector selects a compression mode for a current image block in part as a function of its content.

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

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

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

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

18. An image decompression method comprising:

receiving compressed block image data in which some but not all image blocks have been encoded block-truncation coding;

for each block, determining from the block data whether or not it has been encoded using block-truncation coding;

in the event that a block has been encoded using block-truncation coding, decoding said block using a block-truncation decoding algorithm; and

in the event that a block has not been encoded using block-truncation coding, not decoding said block using a block-truncation decoding algorithm.