Apparatus and method for optimizing the rate control for multiscale entropy encoding

• US 6,351,491 B1
• Filed: 06/15/2000
• Issued: 02/26/2002
• Est. Priority Date: 06/23/1999
• Status: Expired due to Fees

• Current Assignee: Sarnoff Corporation (SRI International, Inc.)
• Original Assignee: Sarnoff Corporation (SRI International, Inc.)
• Inventors: Sodagar, Iraj, Lee, Hung-Ju, Zhang, Ya-Qin, Chiang, Tihao
• Primary Examiner(s): Kelley, Chris
• Assistant Examiner(s): An, Shawn S.
• Application Number:
  US09/594,401
• Time in Patent Office: 621 Days
• Field of Search: 375/240, 375/240.03, 348/397, 348/398, 348/399, 348/405, 348/419, 382/251, 382/252, 382/239, 382/240, 382/248, 382/232, 382/245, 382/246
• US Class Current: 375/240.03
• 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/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
• 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

A method and apparatus for recursively optimizing the rate control of a hierarchical subband coding system that offers spatial, quality and/or complexity scalabilities. The rate control method recursively adjusts the quantizer scale for each layer of a subband tree, i.e., a subband decomposed image.

Claims

1. Method for encoding an input image into a bitstream, said method comprising the steps of:

(a) generating a subband tree for the input image, where said subband tree has a plurality of subband layers of coefficients;

(b) quantizing said plurality of layers of coefficients with a plurality of quantizer scales, where each quantizer scale corresponds to a layer of said subband tree;

(c) recursively adjusting at least one of said plurality of quantizer scales in accordance with a quantization error that is computed from at least two of said plurality of subband layers; and

(d) encoding said quantized coefficients.

2. The method of claim 1, wherein said quantization error of adjusting step (c) is computed in accordance with a measure of mean square quantization error.

3. The method of claim 1, wherein said subband tree is a wavelet tree.

4. The method of claim 3, wherein said quantizing step b) comprises the steps of:

(b1) computing a target bitrate for each of said plurality of subband layers by using a polynomial model; and

(b2) quantizing coefficients from each of said plurality of subband layers in accordance with said computed target bitrate for each of said plurality of subband layers.

5. The method of claim 4, wherein said polynomial model is expressed as:

$\frac{R_i-H_i}{S_i}=\frac{A_1}{Q_i}+\frac{A_2}{{\left(Q_i\right)}^2}$

where R_i is a target bitrate for encoding a subband layer i, H_i is a number of bits for encoding header information, S_i is a measure of said quantization error in a subband layer i, Q_i is a quantization scale for a subband layer i, and A₁ and A₂ are first order and second order coefficients.

6. The method of claim 3, wherein said adjusting step c) comprises the step of:

(c1) computing said quantization error in accordance with a normalized mean square quantization error.

7. The method of claim 6, wherein said normalized mean square quantization error is expressed as:

$\mathrm{NMSE}<br><br>\left(i\right)=\left(\underset{j}{\sum <br><br>}<br><br>\mathrm{MSE}<br><br>\left(j\right)+\left(1<br><br>\left(k-i-1\right)\right)\right)<br><br>\left(k-i\right),$

where NMSE(i) is said normalized mean square quantization error for a subband layer i, k is a number of said subband layers, j denotes a spatial location in said subband layer i and symbols >

> and

<

<

are right and left bit shifting operations, respectively.

8. The method of claim 6, wherein said adjusting step c) further comprises the step of:

(c2) computing a new target bitrate for at least one of said plurality of subband layers in accordance with a weighting factor that accounts for quantization error changes in a next iteration of coding.

9. The method of claim 8, wherein said encoding step (d) encodes said quantized coefficients in accordance with said new target bitrate.

10. The method of claim 8, wherein said weighting factor is expressed as:

11. The method of claim 8, wherein said new target bitrate is expressed as:

12. The method of claim 4, wherein parameters of said polynomial model are updated using actual encoding results.

13. The method of claim 1, wherein said encoding step (d) encodes said quantized coefficients in accordance with multiscale zerotree entropy encoding (MZTE).

14. Apparatus for encoding an input image into a bitstream, said apparatus comprising:

a subband tree generator for generating a subband tree for the input image, where said subband tree has a plurality of subband layers of coefficients;

a quantizer, coupled to said subband tree generator, for quantizing said plurality of layers of coefficients with a plurality of quantizer scales, where each quantizer scale corresponds to a layer of said subband tree;

a rate controller, coupled to said quantizer, for recursively adjusting at least one of said plurality of quantizer scales in accordance with a quantization error that is computed from at least two of said plurality of subband layers; and

an encoder, coupled to said quantizer, for encoding said quantized coefficients.

15. The apparatus of claim 14, wherein said quantizer computes said quantization error in accordance with a measure of mean square quantization error.

16. The apparatus of claim 14, wherein said rate controller computes a target bitrate for each of said plurality of subband layers by using a polynomial model, and said quantizer quantizes coefficients from each of said plurality of subband layers in accordance with said computed target bitrate for each of said plurality of subband layers.

17. The apparatus of claim 16, wherein said rate controller further computes a new target bitrate for at least one of said plurality of subband layers in accordance with a weighting factor that accounts for quantization error changes in a next iteration of coding.

18. The apparatus of claim 14, further comprising a symbol assignor, coupled to said encoder, that assigns symbols to said quantized coefficients in accordance with multiscale zerotree entropy encoding (MZTE).

19. A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform the steps comprising of:

(a) generating a subband tree for the input image, where said subband tree has a plurality of subband layers of coefficients;

(b) quantizing said plurality of layers of coefficients with a plurality of quantizer scales, where each quantizer scale corresponds to a layer of said subband tree;

(c) recursively adjusting at least one of said plurality of quantizer scales in accordance with a quantization error that is computed from at least two of said plurality of subband layers; and

(d) encoding said quantized coefficients.

20. An encoding system comprising:

a motion compensator for generating a predicted image of a current input frame;

a subband coder, coupled to said motion compensator, for applying a subband decomposition to a difference signal between the input frame and said predicted image, where said decomposition produces a subband tree having a plurality of subband layers of coefficients, and for quantizing said plurality of layers of coefficients with a plurality of quantizer scales, where each quantizer scale corresponds to a layer of said subband tree; and

a rate controller, coupled to said subband coder, for recursively adjusting at least one of said plurality of quantizer scales in accordance with a quantization error that is computed from at least two of said plurality of subband layers.