Apparatus and method for encoding wavelet trees generated by a wavelet-based coding method

Claim 2

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, said method comprising the steps of: (a) generating a first wavelet tree for the input image, said first wavelet tree is an unbalanced wavelet tree having a plurality of coefficients, where each of said plurality of coefficients corresponds to a node of said first wavelet tree; (b) mapping said first wavelet tree onto a second wavelet tree, where said second wavelet tree is a balanced wavelet tree having a coefficient frame that is different from a coefficient frame of said first wavelet tree; and (c) coding said plurality of coefficients of said second wavelet tree.

Claim 3

The method of claim 1, where a node of said second wavelet tree is treated as an empty node if no corresponding node exists in said first wavelet tree.

Claim 4

The method of claim 2, further comprising the step of: (b1) quantizing said plurality of coefficients of said second wavelet tree prior to the coding step (c).

Claim 5

The method of claim 1, further comprising the step of: (b1) quantizing said plurality of coefficients of said second wavelet tree; and (b2) assigning a symbol to each of said plurality of quantized coefficients prior to the coding step (c); and wherein said coding step (c) codes said plurality of quantized coefficients of said second wavelet tree in accordance with said assigned symbols.

Claim 6

The method of claim 4, wherein said quantizing step is performed in a depth first pattern.

Claim 7

The method of claim 5, wherein said depth first pattern comprises a top-down scanning pattern starting from a parent node down through to a child node and any of said child's descendant nodes before traversing to a neighboring parent node.

Claim 8

The method of claim 4, wherein said symbol assigning step (b2) assigns each quantized coefficient either a zerotree root symbol, a valued zerotree root symbol, a value symbol or a skip symbol, where said zerotree root symbol denotes a coefficient of a node that is a root of a zerotree, where said valued zerotree root symbol denotes a coefficient of a node having a non-zero value and having children that are all zerotree roots, where said valued symbol denotes a coefficient of a node having a value and having at least one descendant that has a non-zero value, and where said skip symbol denotes a node that should be skipped.

Claim 9

The method of claim 1, wherein said wavelet trees represent vector wavelet trees.

Claim 10

The method of claim 1, wherein said wavelet trees represent object wavelet trees.

Claim 11

Method for decoding a signal carrying an image that was encoded using a wavelet transform to produce a wavelet tree having a plurality of nodes organized in a parent-child relationship, said method comprising the steps of: (a) generating a first wavelet tree from the signal, where said first wavelet tree is a balanced wavelet tree having a plurality of coefficients, where each of said plurality of coefficients corresponds to a node of said first wavelet tree; (b) mapping said first wavelet tree onto a second wavelet tree, where said second wavelet tree is an unbalanced wavelet tree having a coefficient frame that is different from a coefficient frame of said first wavelet tree; and (c) using said second wavelet tree to generate the image.

Claim 12

Method for decoding a signal carrying an image that was encoded using a wavelet transform to produce a wavelet tree having a plurality of nodes organized in a parent-child relationship, said method comprising the steps of: (a) generating a first wavelet tree from the signal, where said first wavelet tree is a balanced wavelet tree having a plurality of coefficients, where each of said plurality of coefficients corresponds to a node of said first wavelet tree; (b) mapping said first wavelet tree onto a second wavelet tree, where said second wavelet tree is an unbalanced wavelet tree having a coefficient frame that is different from a coefficient frame of said first wavelet tree; and (c) using said second wavelet tree to generate the image.

Claim 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, said method comprising the steps of: a wavelet tree generator for generating a first wavelet tree for the input image, said first wavelet tree is an unbalanced wavelet tree having a plurality of coefficients, where each of said plurality of coefficients corresponds to a node of said first wavelet tree; a wavelet tree mapper, coupled to said wavelet tree generator, for mapping said first wavelet tree onto a second wavelet tree, where said second wavelet tree is a balanced wavelet tree having a coefficient frame that is different from a coefficient frame of said first wavelet tree; and a coder, coupled to said wavelet tree mapper, for coding said plurality of coefficients of said second wavelet tree.

Claim 14

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, said method comprising the steps of: a wavelet tree generator for generating a first wavelet tree for the input image, said first wavelet tree is an unbalanced wavelet tree having a plurality of coefficients, where each of said plurality of coefficients corresponds to a node of said first wavelet tree; a wavelet tree mapper, coupled to said wavelet tree generator, for mapping said first wavelet tree onto a second wavelet tree, where said second wavelet tree is a balanced wavelet tree having a coefficient frame that is different from a coefficient frame of said first wavelet tree; and a coder, coupled to said wavelet tree mapper, for coding said plurality of coefficients of said second wavelet tree.

Claim 15

The apparatus of claim 11, further comprising: a quantizer, coupled to said wavelet tree mapper, for quantizing said plurality of coefficients of said second wavelet tree; and a symbol assignor, coupled to said quantizer and said coder, for assigning a symbol to each of said plurality of quantized coefficients, where said plurality of quantized coefficients of said second wavelet tree are coded in accordance with said assigned symbols.

Claim 16

Signal processing system for encoding and decoding an input image using a wavelet transform to produce a wavelet tree having a plurality of nodes organized in a parent-child relationship, said system comprising: an encoder comprising: a wavelet tree generator for generating a first wavelet tree for the input image, said first wavelet tree is an unbalanced wavelet tree having a plurality of coefficients, where each of said plurality of coefficients corresponds to a node of said first wavelet tree; a wavelet tree mapper, coupled to said wavelet tree generator, for mapping said first wavelet tree onto a second wavelet tree, where said second wavelet tree is a balanced wavelet tree having a coefficient frame that is different from a coefficient frame of said first wavelet tree; and a coder, coupled to said wavelet tree mapper, for coding said plurality of coefficients of said second wavelet tree; and a decoder, coupled to said encoder, said decoder comprising; a decoder for decoding a plurality of coefficients from the signal, where each of said plurality of coefficients corresponds to a node of a third balanced wavelet tree; a wavelet tree mapper, coupled to said decoder, for mapping said third wavelet tree onto a fourth wavelet tree, where said fourth wavelet tree is an unbalanced wavelet tree and has a coefficient frame that is different from a coefficient frame of said third wavelet tree; and an inverse transform section, coupled to said wavelet tree mapper, for transforming said second wavelet tree into the image.

Claim 17

Signal processing system for encoding and decoding an input image using a wavelet transform to produce a wavelet tree having a plurality of nodes organized in a parent-child relationship, said system comprising: an encoder comprising: a wavelet tree generator for generating a first wavelet tree for the input image, said first wavelet tree is an unbalanced wavelet tree having a plurality of coefficients, where each of said plurality of coefficients corresponds to a node of said first wavelet tree; a wavelet tree mapper, coupled to said wavelet tree generator, for mapping said first wavelet tree onto a second wavelet tree, where said second wavelet tree is a balanced wavelet tree having a coefficient frame that is different from a coefficient frame of said first wavelet tree; and a coder, coupled to said wavelet tree mapper, for coding said plurality of coefficients of said second wavelet tree; and a decoder, coupled to said encoder, said decoder comprising; a decoder for decoding a plurality of coefficients from the signal, where each of said plurality of coefficients corresponds to a node of a third balanced wavelet tree; a wavelet tree mapper, coupled to said decoder, for mapping said third wavelet tree onto a fourth wavelet tree, where said fourth wavelet tree is an unbalanced wavelet tree and has a coefficient frame that is different from a coefficient frame of said third wavelet tree; and an inverse transform section, coupled to said wavelet tree mapper, for transforming said second wavelet tree into the image.

Claim 18

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 first wavelet tree for the input image, said first wavelet tree is an unbalanced wavelet tree having a plurality of coefficients, where each of said plurality of coefficients corresponds to a node of said first wavelet tree; (b) mapping said first wavelet tree onto a second wavelet tree, where said second wavelet tree is a balanced wavelet tree having a coefficient frame that is different from a coefficient frame of said first wavelet tree; and (c) coding said plurality of coefficients of said second wavelet tree.

Claim 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 first wavelet tree for the input image, said first wavelet tree is an unbalanced wavelet tree having a plurality of coefficients, where each of said plurality of coefficients corresponds to a node of said first wavelet tree; (b) mapping said first wavelet tree onto a second wavelet tree, where said second wavelet tree is a balanced wavelet tree having a coefficient frame that is different from a coefficient frame of said first wavelet tree; and (c) coding said plurality of coefficients of said second wavelet tree.

Claim 20

The computer-readable medium of claim 14, where a node of said second wavelet tree is treated as an empty node if no corresponding node exists in said first wavelet tree.

Claim 21

The computer-readable medium of claim 15, further comprising the step of: (b1) quantizing said plurality of coefficients of said second wavelet tree prior to the coding step (c).

Claim 22

The computer-readable medium of claim 14, further comprising the step of: (b1) quantizing said plurality of coefficients of said second wavelet tree; and (b2) assigning a symbol to each of said plurality of quantized coefficients prior to the coding step (c); and wherein said coding step (c) codes said plurality of quantized coefficients of said second wavelet tree in accordance with said assigned symbols.

Claim 23

The computer-readable medium of claim 17, wherein said quantizing step is performed in a depth first pattern.

Claim 24

The computer-readable medium of claim 18, wherein said depth first pattern comprises a top-down scanning pattern starting from a parent node down through to a child node and any of said child's descendant nodes before traversing to a neighboring parent node.

Claim 25

The computer-readable medium of claim 17, wherein said symbol assigning step (b2) assigns each quantized coefficient either a zerotree root symbol, a valued zerotree root symbol, a value symbol or a skip symbol, where said zerotree root symbol denotes a coefficient of a node that is a root of a zerotree, where said valued zerotree root symbol denotes a coefficient of a node having a non-zero value and having children that are all zerotree roots, where said valued symbol denotes a coefficient of a node having a value and having at least one descendant that has a non-zero value, and where said skip symbol denotes a node that should be skipped.

Claim 26

The computer-readable medium of claim 14, wherein said wavelet trees represent vector wavelet trees.

Claim 27

The computer-readable medium of claim 14, wherein said wavelet trees represent object wavelet trees.

Claim 28

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 first wavelet tree from the signal, where said first wavelet tree is a balanced wavelet tree having a plurality of coefficients, where each of said plurality of coefficients corresponds to a node of said first wavelet tree; (b) mapping said first wavelet tree onto a second wavelet tree, where said a second wavelet tree is an unbalanced wavelet tree having a coefficient frame that is different from a coefficient frame of said first wavelet tree; and (c) using said second wavelet tree to generate the image.

Claim 29

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 first wavelet tree from the signal, where said first wavelet tree is a balanced wavelet tree having a plurality of coefficients, where each of said plurality of coefficients corresponds to a node of said first wavelet tree; (b) mapping said first wavelet tree onto a second wavelet tree, where said a second wavelet tree is an unbalanced wavelet tree having a coefficient frame that is different from a coefficient frame of said first wavelet tree; and (c) using said second wavelet tree to generate the image.