Digital image compression utilizing shrinkage of subband coefficients

• US 6,853,318 B1
• Filed: 12/30/2003
• Issued: 02/08/2005
• Est. Priority Date: 12/30/2003
• Status: Active Grant

• Current Assignee: Monument Peak Ventures, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Eastman Kodak Company
• Inventors: Deever, Aaron T., Rabbani, Majid
• Primary Examiner(s): Jeanglaude, Jean Bruner
• Application Number:
  US10/748,609
• Time in Patent Office: 406 Days
• Field of Search: 341/50, 341/51, 382/209, 382/166, 375/240.1, 714/746
• US Class Current: 341/50
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/647 using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]

Abstract

In compressions of digital images having a plurality of initial pixels, an image type and a quantization step-size set preassigned to the image type, are associated with a respective coordinate of each of the initial pixels. The digital image is decomposed to produce a plurality of subbands. Coefficients of the subbands define a plurality of resultant pixels, each having a respective one of the coordinates. The subband coefficients also define, for each subband coefficient, a group of resultant pixels to which the subband coefficient contributes. After the decomposition, each of the subband coefficients are shrunk by a respective adjustment that is a function of the respective quantization step-size sets associated with the coordinates of the resultant pixels to which the subband coefficient contributes.

Claims

1. A method for encoding digital image data representing a plurality of initial pixels, each said initial pixel having a coordinate, said method having a plurality of predefined image types, each said image type having a preassigned one of a plurality of quantization step-size sets, said method comprising the steps of:

associating a respective one of a plurality of different image types and a respective said quantization step-size set with each of the coordinates;

transforming the digital image data using a subband decomposition to produce a plurality of subbands, each said subband having a plurality of subband coefficients, said subband coefficients defining a plurality of resultant pixels and ones of said resultant pixels contributed to by respective said subband coefficients, said resultant pixels each having a respective one of said coordinates;

shrinking each of said subband coefficients by an adjustment that is a function of respective said quantization step-size sets of said coordinates of respective said ones of said resultant pixels to provide corresponding adjusted coefficients.

2. The method of claim 1 wherein said transforming defines a mapping of said coordinates of said resultant pixels into a plurality of influence regions;

and said method further comprises selecting an image type, in each said influence region, having the corresponding said quantization step-size set of smallest magnitude.

3. The method of claim 1 further comprising quantizing each said adjusted coefficient to provide a respective quantized coefficient.

4. The method of claim 3 wherein said quantizing and said adjustment together provide an effective quantization step-size set for each said subband coefficient that is larger than or equal to the smallest of said quantization step-size sets of the digital image data.

5. The method of claim 3 further comprising the steps of:

following said transforming, partitioning each said subband into a plurality of codeblocks;

forming a plurality of partial-bitplanes from respective said quantized coefficients of each said codeblock of each said subband;

following said quantizing, entropy encoding each said codeblock of quantized coefficients independently of the other said codeblocks to provide encodement values; and

discarding at least one of said partial-bitplanes;

wherein said shrinking, said quantizing, and said discarding steps together provide an effective quantization step-size set for each said subband coefficient that is larger than or equal to the smallest of said quantization step-size sets of the digital image data.

6. The method of claim 5 further comprising, prior to said entropy encoding:

forming a plurality of partial-bitplanes from said quantized coefficients of each said codeblock of each said subband; and

discarding any of said partial-bitplanes having a discard parameter in a predetermined range, said discard parameter being a function of a respective said assigned step-size set.

7. The method of claim 3 further comprising the steps of:

following said transforming, partitioning each said subband into a plurality of codeblocks;

following said shrinking, entropy encoding each said codeblock independently of the other said codeblocks to provide encodement values; and

combining said encodement values into a continuous bitstream.

8. The method of claim 7 further comprising, prior to said entropy coding:

forming at least one partial-bitplane from said quantized coefficients of each said codeblock of each said subband; and

discarding any of said partial-bitplanes having a discard parameter in a predetermined range, said discard parameter being a function of a respective said assigned step-size set.

9. The method of claim 8 wherein said discard parameter is a function of both said respective assigned step-size set and a predetermined quantization step-size set.

10. The method of claim 3 wherein said quantizing of each said adjusted coefficient utilizes a predetermined base quantization step-size set to provide said respective encodement values.

11. The method of claim 10 wherein said predetermined base quantization step-size set has the smallest magnitude of said plurality of quantization step-size sets.

12. The method of claim 10 wherein said transforming defines a mapping of said coordinates of said resultant pixels into a plurality of influence regions;

and said method further comprises selecting an image type, in each said influence region, having the corresponding said quantization step-size set of smallest magnitude.

13. The method of claim 1 wherein said transforming further comprises applying a discrete wavelet transform.

14. A computer program product for encoding digital image data representing a plurality of pixels, said product comprising:

a computer readable storage medium having a computer program stored thereon, said computer program defining a coordinate of each said pixel, said computer program defining a plurality of image types, each said image type having a preassigned one of a plurality of quantization step-size sets, said computer program performing the steps of;

associating a respective one of a plurality of different image types and a respective said quantization step-size set with each of the coordinates;

transforming the digital image data using a subband decomposition to produce a plurality of subbands, each said subband having a plurality of subband coefficients, said subband coefficients defining a plurality of resultant pixels and ones of said resultant pixels contributed to by respective said subband coefficients, said resultant pixels each having a respective one of said coordinates;

shrinking each of said subband coefficients by an adjustment that is a function of respective said quantization step-size sets of said coordinates of respective said ones of said resultant pixels to provide corresponding adjusted coefficients.

15. An image encoder for encoding digital image data representing a plurality of pixels, said encoder comprising:

a classification unit, which determines the image type associated with each pixel and outputs a first map defining coordinates and image type of each said pixel, each said image type having a preassigned one of a plurality of quantization step-size sets;

a transform unit applying a subband decomposition to said digital image data, said transform unit outputting a plurality of subbands, each said subband having a plurality of subband coefficients, said subband coefficients defining a second map of resultant pixels having the same coordinates as said first map, said second map defining ones of said resultant pixels contributed to by respective said subband coefficients;

a coefficient type identifier receiving said maps, said coefficient type identifier determining corresponding ones of said subband coefficients and said quantization step-size sets at each of said coordinates; and

responsively outputting coefficient types, each said coefficient type defining an adjustment that is a function of one or more of respective said quantization step-size sets corresponding to respective said subband coefficients;

a subband coefficient modifier receiving said coefficient types and responsively shrinking each said coefficient by a respective said adjustment.

16. The image encoder of claim 15 wherein said second map maps said coordinates of said resultant pixels into a plurality of influence regions;

and said classification unit selects an image type, in each said influence region, having the corresponding said quantization step-size set of smallest magnitude.

17. The image encoder of claim 15 further comprising a uniform quantizer having a deadzone, said quantizer quantizing said adjusted coefficients.

18. The image encoder of claim 17 wherein said shrinking and said quantizing together provide an effective quantization step-size set for each said subband coefficient that is larger than or equal to the smallest of said quantization step-size sets of the digital image data.

19. The image encoder of claim 17 further comprising:

an image type bitplane discard table having predetermined number of partial-bitplane discards associated with possible combinations of said image types and said subbands;

a codeblock bitplane discard unit receiving said adjusted coefficients and respective said partial-bitplane discards and responsively generating an identification of ones of said partial-bitplanes discardable from each said codeblock;

an arithmetic binary coding unit receiving said adjusted coefficients and said identification of said discardable partial-bitplanes, said coding unit encoding said adjusted coefficients for each said codeblock and discarding the respective said discardable partial-bitplanes.

20. The image encoder of claim 19 wherein said shrinking, said quantizing, and said discarding together provide an effective quantization step-size set for each said subband coefficient that is larger than or equal to the smallest of said quantization step-size sets of the digital image data.