Apparatus and method for encoding wavelet trees by backward predictive coding of wavelet transformed coefficients

• US 6,236,758 B1
• Filed: 10/22/1999
• Issued: 05/22/2001
• Est. Priority Date: 02/12/1997
• Status: Expired due to Term

• Current Assignee: MediaTek, Inc.
• Original Assignee: Sharp Corporation (Hon Hai Precision Industry Co., Ltd.), Sarnoff Corporation (SRI International, Inc.)
• Inventors: Sodagar, Iraj, Lee, Hung-Ju
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): Johnson, Timothy M.
• Application Number:
  US09/425,363
• Time in Patent Office: 578 Days
• Field of Search: 382/232, 382/238, 382/239, 382/240, 382/248, 375/240.02, 375/240.12, 375/240.18, 375/240.19, 341/51, 341/79, 341/107, 358/261.2, 358/430, 348/394.1, 348/395.1, 348/397.1, 348/398.1, 348/400.1, 348/403.1, 348/404.1, 348/408.1, 348/409.1, 348/437.1, 348/438.1
• US Class Current: 382/240
• 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/63 using sub-band based transform, e.g. wavelets
• 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 in a wavelet-based coding technique using backward predictive coding of wavelet transformed coefficients, which addresses both balanced and unbalanced wavelet trees and increases the overall coding efficiency.

Claims

1. Method for encoding an input image using a wavelet transform to produce a wavelet tree having a plurality of nodes organized in a parent-child relationship, where said nodes are organized into a plurality of bands, said method comprising the steps of:

(a) generating a wavelet tree for the input image, said wavelet tree having a plurality of coefficients, where each of said plurality of coefficients corresponds to a node of said wavelet tree; and

(b) coding said plurality of coefficients of said wavelet tree using a difference value, where said difference value is a difference between adjacent coefficient values.

2. The method of claim 1, wherein said difference value is derived from a horizontal coefficient.

3. The method of claim 1, wherein said difference value is derived from a vertical coefficient.

4. The method of claim 1, wherein said difference value is derived in accordance with:

5. The method of claim 4, wherein said wavelet coefficient a is diagonal relative to said current wavelet coefficient x, wherein said wavelet coefficient b is vertical relative to said current wavelet coefficient x, and wherein said wavelet coefficient c is horizontal relative to said current wavelet coefficient x.

6. The method of claim 1, wherein said coefficients of said wavelet tree are within a LL band of said plurality of bands.

7. 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 wavelet tree for the input image, said wavelet tree having a plurality of coefficients, where each of said plurality of coefficients corresponds to a node of said wavelet tree; and

(b) coding said plurality of coefficients of said wavelet tree using a difference value, where said difference value is a difference between adjacent coefficient values.

8. The computer-readable medium of claim 7, wherein said difference value is derived from a horizontal coefficient.

9. The computer-readable medium of claim 7, wherein said difference value is derived from a vertical coefficient.

10. The computer-readable medium of claim 7, wherein said difference value is derived in accordance with:

11. The computer-readable medium of claim 10, wherein said wavelet coefficient a is diagonal relative to said current wavelet coefficient x, wherein said wavelet coefficient b is vertical relative to said current wavelet coefficient x, and wherein said wavelet coefficient c is horizontal relative to said current wavelet coefficient x.

12. The computer-readable medium of claim 7, wherein said coefficients of said wavelet tree are within a LL band of said plurality of bands.

13. Apparatus for encoding an input image using a wavelet transform to produce a wavelet tree having a plurality of nodes organized in a parent-child relationship, where said nodes are organized into a plurality of bands, said apparatus comprising:

a wavelet tree generator for generating a wavelet tree for the input image, said wavelet tree having a plurality of coefficients, where each of said plurality of coefficients corresponds to a node of said wavelet tree; and

a coder for coding said plurality of coefficients of said wavelet tree using a difference value, where said difference value is a difference between adjacent coefficient values.

14. The apparatus of claim 13, wherein said difference value is derived from a horizontal coefficient.

15. The apparatus of claim 13, wherein said difference value is derived from a vertical coefficient.

16. The apparatus of claim 13, wherein said difference value is derived in accordance with:

17. The apparatus of claim 16, wherein said wavelet coefficient a is diagonal relative to said current wavelet coefficient x, wherein said wavelet coefficient b is vertical relative to said current wavelet coefficient x, and wherein said wavelet coefficient c is horizontal relative to said current wavelet coefficient x.

18. The apparatus of claim 13, wherein said coefficients of said wavelet tree are within a LL band of said plurality of bands.