Embedded image coder with rate-distortion optimization

• US 6,625,321 B1
• Filed: 01/30/1998
• Issued: 09/23/2003
• Est. Priority Date: 02/03/1997
• Status: Expired due to Fees

• Current Assignee: Sharp Laboratories of America Incorporated (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Sharp Laboratories of America Incorporated (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Li, Jin, Lei, Shaw-Min
• Primary Examiner(s): Johnson, Timothy M.
• Application Number:
  US09/016,571
• Time in Patent Office: 2,062 Days
• Field of Search: 382/239, 382/232, 382/240, 382/247, 382/250, 382/251, 348/384-440, 341/106, 341/107, 341/51, 358/261.2, 358/430, 358/467
• US Class Current: 382/239
• CPC Class Codes: H04N 19/10 using adaptive coding
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• 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/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• 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

Abstract

A rate-distortion optimized embedding (RDE) coder optimizes rate-distortion performance by coding information bits in the order of their R-D slope. RDE allocates the available coding bits first to the information bit with the steepest R-D slope, which indicates the largest distortion decrease per coding bit. The resultant RDE bitstream can be truncated at any point and still maintain an optimal R-D performance. To avoid the overhead of coding order transmission, an expected R-D slope is calculated by both the encoder and the decoder from previous RDE coded bits. A probability estimation table from a QM arithmetic coder allows the R-D slope to be derived using a lookup table operation. The rate-distortion optimised embedding (RDE) coder significantly improves the coding efficiency over a wide range of bit rates.

Claims

1. A rate-distortion optimization method for embedded coding of a digital image, comprising the steps of:

transforming the image to form a set of coefficients;

quantizing the coefficients to form a set of symbols;

calculating, for each symbol, a predicted rate-distortion slope based on an expected distortion decrease and an expected coding rate increase for that symbol;

selecting an encoding order for the symbols by ordering each symbol according to that symbol'"'"'s calculated predicted rate-distortion slope, such that symbols with a steeper predicted rate distortion slope, and therefore larger predicted distortion decrease, are encoded before symbols with a less steep predicted rate distortion slope.

2. A rate-distortion optimization method for embedded coding of a digital image, comprising the steps of:

transforming the image to form a set of coefficients each comprising multiple bits;

analyzing a current layer, comprising the most significant unencoded bit from each coefficient, by calculating, for each bit in the current layer, a predicted rate-distortion slope based on an expected distortion decrease and an expected coding rate increase for that bit; and

encoding a selected bit in the current layer with an entropy coder, the bit selected according to its calculated predicted rate distortion slope, such that bits from the current layer with a steeper predicted rate distortion slope, and therefore larger predicted distortion decrease, are encoded before bits with a less steep predicted rate distortion slope.

3. A method according to claim 2 wherein encoding a selected bit comprises encoding one bit in the current layer having a maximum predicted rate-distortion slope.

4. A method according to claim 2 including the following:

setting a threshold value;

encoding the bits in the current layer having a predicted rate-distortion slope greater than the threshold value;

reducing the threshold value; and

reconfiguring the current layer of bits to include the most significant unencoded bits in each coefficient.

5. A method according to claim 2 wherein the predicted rate-distortion slope for a given bit is generated according to the coding layer of that bit, a significance status of that bit'"'"'s coefficient indicating whether all previous bits in the coefficient are zeros, and the significance statuses of surrounding coefficients.

6. A method according to claim 2 wherein the predicted rate-distortion slope is derived for each bit according to a significance identification mode or a refinement mode.

7. A method according to claim 6 wherein the significance identification mode encodes all significant bits in the coefficients defined as all bits up to a first binary 1 value and the refinement mode encodes all refinement bits defined as all bits after the first binary 1 value.

8. A method according to claim 7 wherein the rate distortion slope is derived for the significant bits as follows:

${\mathrm{\lambda <br><br>}}_{i,\mathrm{sig}}=\frac{E<br><br>\left[\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>D_i\right]}{E<br><br>\left[\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>R_i\right]}=\frac{2.25<br><br>T_{n_i}^2}{1+H<br><br>\left(p_i\right)/p_i}=f_s<br><br>\left(p_i\right)<br><br>T_{n_i}^2,$

where the function f_s(p) is the significance R-D slope modification factor defined as;

$f_s<br><br>\left(p\right)=\frac{2.25}{1+\frac{H<br><br>\left(p\right)}{p}},$

T_ni is a quantization step size determined by the coding layer n_i, p_i is probability of significance that a candidate bit b_ni=1, and H(p) is entropy of a binary symbol.

9. A method according to claim 7 wherein the rate distortion slope derived for the refinement bits is the following:

${\mathrm{\lambda <br><br>}}_{i,\mathrm{ref}}=\frac{E<br><br>\left[\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>D_i\right]}{E<br><br>\left[\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>R_i\right]}=0.25<br><br>T_{n_i}^2,$

where T_ni is a quantization step size determined by the coding layer n_i.

10. A method according to claim 7 wherein the rate distortion slope for the significance bits and the refinement bits are derived according to a Laplacian probability distribution.

11. A method according to claim 6 wherein the significance identification mode uses a QM-coder that estimates a probability that the bit is significant according to a significant status of the same and adjacent coefficients.

12. A method according to claim 6 including precomputing and storing a table containing the rate-distortion slope values for significance bit coding and refinement bit coding and indexing the rate-distortion slope values according to the coding layer and a coder state corresponding the probability of significance or insignificance that the most probable bit during the significant identification mode is a 1 or a 0.

13. An embedded encoder for optimizing rate-distortion coding of a digitized image, comprising:

a transformer for encoding the digitized image, thereby forming a set of coefficients each comprising multiple bits;

a rate-distortion slope calculator for analyzing a set of candidate bits comprising a most significant unencoded bit from each coefficient, and determining, for each candidate bit, a predicted rate-distortion slope based on an expected distortion decrease and an expected coding rate increase for that bit; and

a symbol selector for selecting an order for encoding the bits based on the predicted rate-distortion slope for each bit, such that bits with a steeper predicted rate distortion slope, and therefore larger predicted distortion decrease, are encoded before bits with a less steep predicted rate distortion slope.

14. A system according to claim 13 wherein the rate-distortion slope calculator operates in a significance identification mode when all previously coded bits in the coefficient are zero and a refinement mode after a first nonzero bit is identified in the coefficient during the significance identification mode.

15. A system according to claim 14 wherein the rate-distortion slope calculator comprises a lookup table including one refinement mode rate-distortion entry for each layer of coefficient bits and two significance identification mode rate-distortion entries, a first entry for a symbol 1 to be the most probable symbol, and

a second entry for a symbol 0 to be the most probable symbol for each one of multiple QM-coder states each associated with a probability of significance.

16. A method for embedded coding a data array, comprising the steps of:

calculating a predicted rate distortion slope for each symbol in a group of symbols taken from the data array, the predicted rate distortion slope for a symbol based on an expected distortion decrease and an expected coding rate increase for that symbol; and

selecting an encoding order for the symbols in the group by ordering each symbol according to that symbol'"'"'s calculated predicted rate-distortion slope, such that symbols with a steeper predicted rate distortion slope, and therefore larger predicted distortion decrease, are encoded before symbols with a less steep predicted rate distortion slope.

17. The method of claim 16, wherein selecting an encoding order for the symbols in the group comprises the steps of:

setting a threshold value; and

encoding the symbols in the group having predicted rate distortion slopes greater than the threshold value.

18. The method of claim 16, wherein selecting an encoding order for the symbols in the group comprises the steps of:

selecting the symbol from the group having the largest predicted rate distortion slope; and

encoding that symbol.

19. An embedded digital image decoder comprising:

an entropy decoder for decoding an entropy-coded bitstream comprising embedded transform coefficient data;

a rate-distortion slope calculator for calculating a predicted rate-distortion slope for a transform coefficient location in a coefficient array, based on an expected distortion decrease and an expected coding rate increase for transmission of a bit corresponding to that coefficient location; and

a bit encoding order decoder for determining the bit encoding order present in the decoded entropy-coded bitstream based on predicted rate-distortion slope calculated by the rate-distortion slope calculator.

20. The embedded digital image coder of claim 19, wherein for a bit present in the decoded entropy-coded bitstream, the bit encoding order decoder identifies the transform coefficient location having the largest predicted rate-distortion slope as the location in the coefficient array corresponding to that bit.

21. The embedded digital image decoder of claim 19, wherein the bit encoding order decoder examines the predicted rate-distortion slope for locations in the coefficient array in a predefined coefficient scan order, and determines a bit encoding order representing coefficient locations in that scan order having a predicted rate-distortion slope that exceed a slope threshold.

22. A method for decoding an embedded-coded image, the method comprising the steps of:

initializing a transform coefficient array;

decoding an encoded bitstream comprising embedded transform coefficient data; and

determining the bit encoding order present in the decoded entropy-coded bitstream, by calculating a predicted rate-distortion slope for the most significant undecoded bit from each transform coefficient, and assigning data from the decoded entropy-coded bitstream to those coefficients in a descending order of predicted rate-distortion slope.

23. The method of claim 22, wherein the step of assigning data in a descending order of predicted rate-distortion slope comprises examining transform coefficients in a predefined coefficient scan order, and assigned data from the decoded entropy-coded bitstream to coefficients in that order that have a predicted rate-distortion slope exceeding a preset threshold.

24. The method of claim 22, wherein the step of assigning data in a descending order of predicted rate-distortion slope comprises identifying the transform coefficient location having the largest predicted rate-distortion slope as the next coefficient having a bit present in the bit encoding order.

25. The method of claim 22, wherein the step of calculating a predicted rate distortion slope comprises the steps of determining the coding layer of the bit, determining the significance status of the transform coefficient, and determining the significance statuses of surrounding coefficients.

26. The method of claim 25, wherein the step of calculating a predicted rate distortion slope uses a QM-coder that estimates the probability that the bit is significant according to the significance status of the coefficient and adjacent coefficients.

27. The method of claim 26, wherein the step of calculating a predicted rate distortion slope comprises precomputing and storing a table containing rate distortion slope values, and indexing into this table using the coding layer of the bit, the significance status of the transform coefficient, and the significance statuses of surrounding coefficients.