US5867602A — Reversible wavelet transform and embedded codestr…

Claim 1

Independent Claim 106 words

An encoder for encoding input data into a compressed data stream, said coder comprising: a reversible wavelet filter for transforming the input data into a plurality of coefficients using a pyramidal decomposition; an ordering and modeling mechanism coupled to the reversible wavelet filter, said ordering and modeling mechanism generating an embedded codestream in response to the plurality of coefficients, wherein the ordering and modeling order the plurality of coefficients and order binary values within each of the plurality of coefficients; and a binary entropy coder, coupled to the ordering and modeling mechanism, operable to binary entropy code the embedded codestream to produce the compressed data stream.

Claim 2

Dependent Claim 106 words

An encoder for encoding input data into a compressed data stream, said coder comprising: a reversible wavelet filter for transforming the input data into a plurality of coefficients using a pyramidal decomposition; an ordering and modeling mechanism coupled to the reversible wavelet filter, said ordering and modeling mechanism generating an embedded codestream in response to the plurality of coefficients, wherein the ordering and modeling order the plurality of coefficients and order binary values within each of the plurality of coefficients; and a binary entropy coder, coupled to the ordering and modeling mechanism, operable to binary entropy code the embedded codestream to produce the compressed data stream.

Claim 3

Dependent Claim 27 words

The encoder defined in claim 1 wherein the reversible wavelet filter performs the pyramidal decomposition of the input data using a series of TS and S transforms.

Claim 4

Dependent Claim 50 words

The encoder defined in claim 1 wherein the reversible wavelet filter produces a series of coding units which undergo embedded coding and binary entropy coding using a set of statistics and probabilities, and further wherein the statistics and probabilities are reset at the start of coding of each coding unit.

Claim 5

Dependent Claim 24 words

The encoder defined in claim 1 wherein the encoding of the second bit is conditioned on its bit position from an initial one bit.

Claim 6

Dependent Claim 41 words

The encoder defined in claim 1 wherein the ordering and modeling mechanism uses a series of coefficients surrounding a particular coefficient as a context, and further wherein each of the series of coefficients contributes at least one bit for the context.

Claim 7

Dependent Claim 17 words

The encoder defined in claim 5 wherein a predetermined number of the coefficients provide an extra bit.

Claim 8

Dependent Claim 37 words

The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a context model using contexts based on neighboring and parent coefficient values, and further wherein the parent coefficient values are only of S-transform parents.

Claim 9

Dependent Claim 37 words

The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a context model using contexts based on neighboring and parent coefficient values, and further wherein the parent coefficient values are only of TS-transform parents.

Claim 10

Dependent Claim 16 words

The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a context model.

Claim 11

Dependent Claim 26 words

The encoder defined in claim 1 wherein the ordering and modeling mechanism encodes a sign bit based in part on a sign of another known coefficient.

Claim 12

Dependent Claim 21 words

The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a context model that uses adaptively changing contexts.

Claim 13

Dependent Claim 50 words

The encoder defined in claim 1 wherein the reversible wavelet filter transforms the input data into a plurality of coefficients using Monte Carlo division, wherein a pseudo random generator provides an output determinate of a rounding operation to be performed on the output of the wavelet of the filtering operation.

Claim 14

Dependent Claim 17 words

The encoder defined in claim 1 wherein the binary entropy coder comprises a finite state machine coder.

Claim 15

Dependent Claim 17 words

The encoder defined in claim 1 wherein the binary entropy coder comprises a high speed parallel coder.

Claim 16

Dependent Claim 14 words

The encoder defined in claim 1 wherein the binary entropy coder comprises a Q-coder.

Claim 17

Dependent Claim 15 words

The encoder defined in claim 1 wherein the reversible wavelet filter performs a two-dimensional decomposition.

Claim 18

Dependent Claim 25 words

The encoder defined in claim 16 wherein reversible wavelet filter comprises a two-dimensional filter having two one-dimensional filters cascaded followed by a two-dimensional rounding mechanism.

Claim 19

Dependent Claim 44 words

The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a context model that codes a single decision if a plurality of head bits are to coded and their north, south, east, and west neighbors and parents all have tail-information 0.

Claim 20

Dependent Claim 16 words

The encoder defined in claim 18 wherein the plurality of head bits comprises 16 head bits.

Claim 21

Dependent Claim 21 words

The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a context model that encodes with M-ary centers.

Claim 22

Dependent Claim 22 words

The encoder defined in claim 1 wherein coding of coefficients on the lowest level of decomposition is coded using a DPCM scheme.

Claim 23

Dependent Claim 55 words

The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a context model that uses contexts based on whether a non-zero magnitude bit has been observed in a coefficient and the number of bit-planes since said first non-zero magnitude bit, and wherein bits after the first non-zero magnitude bit are not conditioned.

Claim 24

Dependent Claim 22 words

The encoder defined in claim 1 wherein the reversible wavelet filter, ordering and modeling mechanism and binary entropy coder perform non-bitplane coding.

Claim 25

Dependent Claim 19 words

The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a look-up table to provide conditioning.

Claim 26

Dependent Claim 30 words

The encoder defined in claim 24 wherein the look-up table provides a context based on a parent of a current coefficient, and the coefficients above and below the current coefficient.

Claim 27

Dependent Claim 18 words

The encoder defined in claim 25 wherein the parent of the current coefficient comprises only an S-transform parent.

Claim 28

Dependent Claim 18 words

The encoder defined in claim 25 wherein the parent of the current coefficient comprises only a TS-transform parent.

Claim 29

Dependent Claim 28 words

The encoder defined in claim 25 wherein conditioning on the parent is obtained by ORing with the output of the look-up table handling the handles the other conditioning.

Claim 30

Dependent Claim 37 words

The encoder defined in claim 24 wherein the look-up table provides a context based on a previous context, a coefficient above the current coefficient, the location of the current coefficient and a coefficient below the current coefficient.

Claim 31

Dependent Claim 32 words

The encoder defined in claim 24 further comprising a second look-up table that obtains state information from the current context look-up table for combination with newly available data for the next bitplane.

Claim 32

Dependent Claim 28 words

The encoder defined in claim 1 further comprises a finite amount of work space memory, and further wherein the reversible wavelet filter comprises wavelet transforms of different heights.

Claim 33

Dependent Claim 14 words

The encoder defined in claim 1 wherein the reversible wavelet filter comprises overlapped filters.

Claim 34

Dependent Claim 14 words

The encoder defined in claim 1 wherein the reversible wavelet filter comprises non-minimal filters.

Claim 35

Dependent Claim 22 words

The encoder defined in claim 1 wherein the reversible wavelet filter comprises filters that do not cause growth in the low pass.

Claim 36

Dependent Claim 15 words

The encoder defined in claim 1 wherein the reversible wavelet filter comprises non-linear morphological filters.

Claim 37

Dependent Claim 26 words

The encoder defined in claim 1 further comprises a memory and coefficients generated by the wavelet transform are stored in a the memory in magnitude/mantissa form.

Claim 38

Dependent Claim 15 words

The encoder defined in claim 1 wherein the ordering and modeling mechanism performs M-ary coding.

Claim 39

Dependent Claim 22 words

The encoder defined in claim 1 wherein the ordering and modeling mechanism generates an embedded codestream that is embedded by band only.

Claim 40

Dependent Claim 16 words

The encoder defined in claim 1 wherein the ordering and modeling mechanism generates a non-embedded codestream.

Claim 41

Dependent Claim 177 words

An encoder for encoding input data into a compressed data stream, said entropy coder comprising: a reversible wavelet filter for transforming the input data into a plurality of coefficients using a pyramidal decomposition with a variable number of levels; a memory having a fixed size coupled to the reversible wavelet filter, wherein the reversible wavelet filter uses the memory to store information during computation of the plurality of coefficients; a control mechanism coupled to the reversible wavelet filter and the fixed size memory to select the number of levels based on the fixed size of the memory; an ordering and modeling mechanism coupled to the reversible wavelet filter and the fixed sized memory, said ordering and modeling mechanism generating an embedded codestream in response to the plurality of coefficients, wherein the ordering and modeling mechanism orders the plurality of coefficients and order binary values within each of the plurality of coefficients; and a binary entropy coder, coupled to the ordering and modeling mechanism, operable to binary entropy code the embedded codestream to produce the compressed data stream.

Claim 42

Dependent Claim 177 words

An encoder for encoding input data into a compressed data stream, said entropy coder comprising: a reversible wavelet filter for transforming the input data into a plurality of coefficients using a pyramidal decomposition with a variable number of levels; a memory having a fixed size coupled to the reversible wavelet filter, wherein the reversible wavelet filter uses the memory to store information during computation of the plurality of coefficients; a control mechanism coupled to the reversible wavelet filter and the fixed size memory to select the number of levels based on the fixed size of the memory; an ordering and modeling mechanism coupled to the reversible wavelet filter and the fixed sized memory, said ordering and modeling mechanism generating an embedded codestream in response to the plurality of coefficients, wherein the ordering and modeling mechanism orders the plurality of coefficients and order binary values within each of the plurality of coefficients; and a binary entropy coder, coupled to the ordering and modeling mechanism, operable to binary entropy code the embedded codestream to produce the compressed data stream.

Claim 43

Independent Claim 73 words

A method for encoding input data into a compressed data stream comprising the steps of: transforming the input data into a plurality of coefficients using a reversible wavelet filter; generating an embedded codestream in response to the plurality of coefficients, including the steps of ordering the plurality of coefficients and order binary values within each of the plurality of coefficients; and binary entropy coding the embedded codestream to produce the compressed data stream.

Claim 44

Independent Claim 73 words

A method for encoding input data into a compressed data stream comprising the steps of: transforming the input data into a plurality of coefficients using a reversible wavelet filter; generating an embedded codestream in response to the plurality of coefficients, including the steps of ordering the plurality of coefficients and order binary values within each of the plurality of coefficients; and binary entropy coding the embedded codestream to produce the compressed data stream.

Claim 45

Dependent Claim 16 words

The method defined in claim 41 further comprising the step of parsing the compressed data stream.

Claim 46

Dependent Claim 24 words

The method defined in claim 41 further comprising the step of applying image processing functions to a scaled representation of the compressed data stream.

Claim 47

Dependent Claim 18 words

The method defined in claim 43 wherein the image processing functions are only applied to the lowest pass.

Claim 48

Dependent Claim 25 words

The method defined in claim 44 further comprising the step of displaying the scaled representation and only applying the image processing functions on displayed pixels.

Claim 49

Independent Claim 75 words

An apparatus for encoding input data into a compressed data stream comprising: means for transforming the input data into a plurality of coefficients using a reversible wavelet filter; means for generating an embedded codestream in response to the plurality of coefficients, including means for ordering the plurality of coefficients and ordering binary values within each of the plurality of coefficients; and means for binary entropy coding the embedded codestream to produce the compressed data stream.

Claim 50

Independent Claim 75 words

An apparatus for encoding input data into a compressed data stream comprising: means for transforming the input data into a plurality of coefficients using a reversible wavelet filter; means for generating an embedded codestream in response to the plurality of coefficients, including means for ordering the plurality of coefficients and ordering binary values within each of the plurality of coefficients; and means for binary entropy coding the embedded codestream to produce the compressed data stream.

Claim 51

Dependent Claim 15 words

The apparatus defined in claim 46 further comprising means for parsing the compressed data stream.

Claim 52

Dependent Claim 23 words

The apparatus defined in claim 46 further comprising means for applying image processing functions to a scaled representation of the compressed data stream.

Claim 53

Dependent Claim 18 words

The apparatus defined in claim 48 wherein the image processing functions are only applied to the lowest pass.

Claim 54

Dependent Claim 24 words

The apparatus defined in claim 49 further comprising means for displaying the scaled representation and only applying the image processing functions on displayed pixels.

Claim 55

Dependent Claim 40 words

The apparatus defined in claim 46 wherein the means for ordering uses a series of coefficients surrounding a particular coefficient as a context, and further wherein each of the series of coefficients contributes at least one bit for the context.

Claim 56

Dependent Claim 17 words

The apparatus defined in claim 51 wherein a predetermined number of the coefficients provide an extra bit.

Claim 57

Dependent Claim 36 words

The apparatus defined in claim 46 wherein the means for ordering comprises a context model using contexts based on neighboring and parent coefficient values, and further wherein the parent coefficient values are only of S-transform parents.

Claim 58

Dependent Claim 36 words

The apparatus defined in claim 46 wherein the means for ordering comprises a context model using contexts based on neighboring and parent coefficient values, and further wherein the parent coefficient values are only of TS-transform parents.

Claim 59

Dependent Claim 26 words

The apparatus defined in claim 46 wherein the ordering and modeling mechanism encodes a sign bit based in part on a sign of another known coefficient.

Claim 60

Dependent Claim 43 words

The apparatus defined in claim 46 wherein the means for ordering comprises a context model that codes a single decision if a plurality of head bits are to coded and their north, south, east, and west neighbors and parents all have tail-information 0.

Claim 61

Dependent Claim 22 words

The apparatus defined in claim 46 wherein coding of coefficients on a lowest level of decomposition is coded using a DPCM scheme.

Claim 62

Dependent Claim 54 words

The apparatus defined in claim 46 wherein the means for ordering comprises a context model that uses contexts based on whether a non-zero magnitude bit has been observed in a coefficient and a number of bit-planes since said first non-zero magnitude bit, and wherein bits after the first non-zero magnitude bit are not conditioned.

Claim 63

Dependent Claim 14 words

The apparatus defined in claim 46 wherein the means for ordering performs M-ary coding.

Claim 64

Dependent Claim 21 words

The apparatus defined in claim 46 wherein the means for ordering generates an embedded codestream that is embedded by band only.

Claim 65

Dependent Claim 15 words

The apparatus defined in claim 46 wherein the means for ordering generates a non-embedded codestream.

Claim 66

Dependent Claim 67 words

A decoder comprising: a model to each bit of each coefficient of a plurality of ordered coefficients containing ordered binary values; a binary entropy decoder coupled to the model to decode the plurality of ordered coefficients into a codestream of coefficients based on information from the model; and an inverse reversible wavelet filter coupled to receive the codestream of coefficients and transform the coefficients into reconstructed data.

Claim 67

Dependent Claim 67 words

A decoder comprising: a model to each bit of each coefficient of a plurality of ordered coefficients containing ordered binary values; a binary entropy decoder coupled to the model to decode the plurality of ordered coefficients into a codestream of coefficients based on information from the model; and an inverse reversible wavelet filter coupled to receive the codestream of coefficients and transform the coefficients into reconstructed data.

Claim 68

Dependent Claim 26 words

The decoder defined in claim 62 wherein the inverse reversible wavelet filter applies an inverse filter on the coefficients starting at the highest level of decomposition.

Claim 69

Dependent Claim 38 words

The decoder defined in claim 62 wherein the model uses a series of coefficients surrounding a particular coefficient as a context, and further wherein each of the series of coefficients contributes at least one bit for the context.

Claim 70

Dependent Claim 17 words

The decoder defined in claim 64 wherein a predetermined number of the coefficients provide an extra bit.

Claim 71

Dependent Claim 30 words

The decoder defined in claim 62 wherein the model uses contexts based on neighboring and parent coefficient values, and further wherein the parent coefficient values are only of S-transform parents.

Claim 72

Dependent Claim 30 words

The decoder defined in claim 62 wherein the model uses contexts based on neighboring and parent coefficient values, and further wherein the parent coefficient values are only of TS-transform parents.

Claim 73

Dependent Claim 40 words

The decoder defined in claim 62 wherein the model and binary entropy coder decode a single decision if a plurality of head bits are to coded and their north, south, east, and west neighbors and parents all have tail-information 0.

Claim 74

Dependent Claim 22 words

The decoder defined in claim 62 wherein decoding of coefficients on a lowest level of decomposition is performed using a DPCM scheme.

Claim 75

Dependent Claim 47 words

The decoder defined in claim 62 wherein the model uses contexts based on whether a non-zero magnitude bit has been observed in a coefficient and a number of bit-planes since said first non-zero magnitude bit, and wherein bits after the first non-zero magnitude bit are not conditioned.

Claim 76

Dependent Claim 16 words

The decoder defined in claim 62 wherein the model and binary entropy coder perform M-ary decoding.

Claim 77

Independent Claim 70 words

A method for decoding compressed data comprising the steps of: (a) modeling each bit of each coefficient of a plurality of ordered coefficients containing ordered binary values; (b) binary entropy decoding said each bit, based on information generated as a result of modeling, to generate a codestream of coefficients; (c) inverse wavelet filtering of coefficients in the codestream from the highest level of decomposition to consecutively lower levels of decomposition.

Claim 78

Independent Claim 70 words

A method for decoding compressed data comprising the steps of: (a) modeling each bit of each coefficient of a plurality of ordered coefficients containing ordered binary values; (b) binary entropy decoding said each bit, based on information generated as a result of modeling, to generate a codestream of coefficients; (c) inverse wavelet filtering of coefficients in the codestream from the highest level of decomposition to consecutively lower levels of decomposition.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2002-02-01	2002-08-03	2003-02-02	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2006-02-01	2006-08-03	2007-02-02	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2010-02-01	2010-08-03	2011-02-02	$7700.00	Window Closed / Lapsed

Reversible wavelet transform and embedded codestream manipulation

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag