Apparatus and method for multiscale zerotree entropy encoding

• US 6,269,192 B1
• Filed: 06/30/1998
• Issued: 07/31/2001
• Est. Priority Date: 07/11/1997
• Status: Expired due to Term

• Current Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.), MediaTek, Inc.
• Original Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.), Sarnoff Corporation (SRI International, Inc.)
• Inventors: Hatrack, Paul, Sodagar, Iraj, Lee, Hung-Ju, Chai, Bing-Bing
• Primary Examiner(s): Johnson, Timothy M.
• Application Number:
  US09/107,544
• Time in Patent Office: 1,127 Days
• Field of Search: 382/232, 382/238, 382/240, 382/244, 382/247-248, 341/51, 341/107, 341/79, 358/261.2, 358/430, 375/240.11, 375/240.18, 375/240.19, 348/397.1, 348/398.1, 348/408.1, 348/416.1, 348/394.1, 348/409.1, 348/411.1, 348/437.1, 348/438.1
• US Class Current: 382/240
• CPC Class Codes: H04N 19/103 Selection of coding mode or of prediction mode
• CPC Class Codes: H04N 19/1883 the unit relating to sub-band structure, e.g. hierarchical level, directional tree, e.g. low-high [LH], high-low [HL], high-high [HH]
• CPC Class Codes: H04N 19/36 Scalability techniques involving formatting the layers as a function of picture distortion after decoding, e.g. signal-to-noise [SNR] scalability
• CPC Class Codes: H04N 19/64 characterised by ordering of coefficients or of bits for transmission
• CPC Class Codes: H04N 19/645 by grouping of coefficients into blocks after the transform
• 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

An apparatus and a concomitant method is disclosed for encoding wavelet trees to generate bitstreams with flexible degrees of spatial, quality and complexity scalabilities. The zerotree entropy (ZTE) encoding method is extended to achieve a fully scalable coding method by implementing a multiscale zerotree coding scheme.

Claims

1. A method for encoding an input image into a bitstream using a wavelet transform to produce a wavelet tree having a plurality of wavelet coefficients organized in a parent-child relationship into a plurality subbands, said method comprising the steps of:

(a) generating a wavelet tree having a plurality of original wavelet coefficients for the input image;

(b) quantizing said plurality of original wavelet coefficients with a first quantizer;

(c) applying zerotree scanning to at least one of said plurality of subbands in a depth-first manner to assign a symbol to at least one of said quantized wavelet coefficients of said wavelet tree;

(d) coding said plurality of quantized wavelet coefficients in accordance with said assigned symbol to generate a first scalability layer; and

(e) reconstructing said quantized wavelet coefficients to generate a next scalability layer.

2. The method of claim 1, wherein said coding step (d) generates a first signal-to-noise (SNR) scalability layer.

3. The method of claim 1, wherein said coding step (d) generates a first spatial scalability layer.

4. The method of claim 1, wherein said coding step (d) generates a first signal-to-noise (SNR) and spatial scalability layer.

5. The method of claim 1, wherein said applying zerotree scanning step (c) applies zerotree scanning, to said plurality of subbands that are above a LL subband.

6. The method of claim 5, further comprising the step of:

(d'"'"') coding said quantized wavelet coefficients in said LL subband by applying a backward prediction.

7. The method of claim 1, wherein said reconstructing said quantized wavelet coefficients step (e) comprises the steps of:

(e1) applying inverse quantization to said quantized wavelet coefficients;

(e2) subtracting said reconstructed wavelet coefficients from said original wavelet coefficients to generate residual wavelet coefficients; and

(e3) generating said next scalability layer from said residual wavelet coefficients.

8. The method of claim 7, wherein said generating said next scalability layer step (e3) comprises the steps of:

(e31) quantizing said plurality of residual wavelet coefficients with a second quantizer;

(e32) applying zerotree scanning to assign a symbol to at least one of said quantized residual wavelet coefficients; and

(e33) coding, said plurality of quantized residual wavelet coefficients in accordance with said assigned symbol to generate said next scalability layer.

9. The method of claim 8, wherein said coding step (e33) further comprises the step of coding said quantized residual wavelet coefficients by using refinement values.

10. The method of claim 8, wherein said applying zerotree scanning step (e32) comprises the step of using zero-tree states to assign a symbol to at least one of said quantized residual wavelet coefficients.

11. The method of claim 7, wherein said coding step (d) further comprises the step of coding said quantized wavelet coefficients by using residual handling.

12. The method of claim 11, wherein said residual handling comprises the step of:

coding a refinement index only for a nonzero residual value.

13. The method of claim 11, wherein said residual handling comprises the step of:

treating all residuals as having a zero value.

14. The method of claim 11, wherein said residual handling comprises the step of:

coding all refinement indices regardless of values of a plurality of residuals.

15. The method of claim 11, wherein said residual handling comprises the step of:

coding a symbol of a node of a residual value only if said node has a symbol type other than a zerotree symbol type.

16. The method of claim 8, wherein said coding step (d) comprises the step of using an adaptive arithmetic coder to code said plurality of quantized wavelet coefficients.

17. The method of claim 16, wherein said coding step (d) further comprises the step of maintaining separate tables of different models for said adaptive arithmetic coder.

18. The method of claim 17, wherein said step of maintaining separate tables comprises the steps of:

maintaining at least one table using a zeroth order model and

maintaining at least one table using a first order model.

19. The method of claim 17, wherein said step of maintaining separate tables comprises the steps of:

maintaining a first table for tracking a frequency of a zeroth order model;

maintaining a second table for tracking cumulative frequency counts of said zeroth order model;

maintaining a third table for tracking a frequency of a first order model; and

maintaining a fourth table for tracking cumulative frequency counts of said first order model.

20. The method of claim 16, further comprising the step of:

selectively adjusting a maximum frequency of a probability model of said adaptive arithmetic coder.

21. The method of claim 16, further comprising the step of:

initializing a probability model of said adaptive arithmetic coder for each of said scalability layer.

22. The method of claim 1, wherein said coding step (d) comprises the step of using an adaptive bitplane arithmetic coder to code said plurality of quantized wavelet coefficients.

23. An apparatus for encoding an input image into a bitstream using a wavelet transform to produce a wavelet tree having a plurality of wavelet coefficients organized in a parent-child relationship into a plurality subbands, said method comprising the steps of:

means for generating a wavelet tree having a plurality of original wavelet coefficients for the input image;

means for quantizing said plurality of original wavelet coefficients with a first quantizer;

means for applying zerotree scanning to at least one of said plurality of subbands in a depth-first manner to assign a symbol to at least one of said quantized wavelet coefficients of said wavelet tree;

means for coding said plurality of quantized wavelet coefficients in accordance with said assigned symbol to generate a first scalability layer; and

means for reconstructing said quantized wavelet coefficients to generate a next scalability layer.

24. 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 of:

(a) generating a wavelet tree having a plurality of original wavelet coefficients organized in a parent-child relationship into a plurality subbands for an input image;

(b) quantizing said plurality of original wavelet coefficients with a first quantizer;

(c) applying zerotree scanning to at least one of said plurality of subbands in a depth-first manner to assign a symbol to at least one of said quantized wavelet coefficients of said wavelet tree;

(d) coding said plurality of quantized wavelet coefficients in accordance with said assigned symbol to generate a first scalability layer; and

(e) reconstructing said quantized wavelet coefficients to generate a next scalability layer.