US6263109B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Context-based ordering and coding of transform coefficient bit-planes for embedded bitstreams
Assignee: Qualcomm Inc
•
Filing: 1998-09-25
•
Granted: 2001-07-17
•
Expires: 2018-09-25
Abstract
Abstract A method of generating an embedded bitstream from quantized Wavelet transform coefficients includes the steps of separating the quantized coefficient bit-planes into a plurality of subsequences, ordering the subsequences according to decreasing expected distortion reduction per expected bit of description, encoding the subsequences, and appending the encoded subsequences to the bitstream as ordered. The subsequences may be ordered according to a priori assumptions about the expected distortion reduction per expected bit of description. The subsequences may be coded by adaptive run length coding such as adaptive elementary Golomb coding.
Inventors
- 👤 Erik Ordentlich
- 👤 Marcelo Weinberger
- 👤 Gadiel Seroussi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-10 01:40
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/007
Claims Analysis
Total Claims: 44
Claim 1
Independent Claim
54 words
A method of generating an embedded bitstream from input data, the method comprising separating the input data into a plurality of subsequences; ordering the subsequences according to decreasing expected distortion reduction per expected bit of description; encoding at least some of the ordered subsequences; and placing the encoded subsequences in the bitstream as ordered.
Claim 2
Independent Claim
54 words
A method of generating an embedded bitstream from input data, the method comprising separating the input data into a plurality of subsequences; ordering the subsequences according to decreasing expected distortion reduction per expected bit of description; encoding at least some of the ordered subsequences; and placing the encoded subsequences in the bitstream as ordered.
Claim 3
Dependent Claim
33 words
The method of claim 1 , wherein the ordering is performed according to an estimate of the relative magnitudes of the probabilities that bits in each of the subsequences are equal to one.
Claim 4
Dependent Claim
23 words
The method of claim 2 , wherein the ordering is performed according to a priori assumptions about the relative magnitudes of the probabilities.
Claim 5
Dependent Claim
32 words
The method of claim 2 , wherein the relative magnitudes of the probabilities are determined adaptively for the input data, and wherein the ordering is performed according to the adaptively determined probabilities.
Claim 6
Dependent Claim
26 words
The method of claim 1 , wherein the input data includes bit-planes of transform coefficient bits, and wherein the subsequences include sub-bit-planes of transform coefficient bits.
Claim 7
Dependent Claim
22 words
The method of claim 5 , wherein a subsequence determination is based upon a context of coefficient bits in previously processed bit-planes.
Claim 8
Dependent Claim
22 words
The method of claim 5 , wherein a subsequence determination is based upon the context of coefficient bits in a current bit-plane.
Claim 9
Dependent Claim
65 words
The method of claim 5 , wherein previously encoded bits in a previously processed bit-plane are used to determine which bits are encoded in a current bit-plane, wherein the current bit-plane is decomposed into the subsequences according to the previously encoded bits, and wherein the subsequences are encoded based on the previously encoded bits in order of decreasing distortion reduction per expected bit of description.
Claim 10
Dependent Claim
33 words
The method of claim 5 , wherein a bit having non-zero neighbors is assumed to have a greater expected distortion reduction per expected bit of description than a bit having all insignificant neighbors.
Claim 11
Dependent Claim
34 words
The method of claim 5 , wherein a bit having a non-zero parent is assumed to have a greater expected distortion reduction per expected bit of description than a bit having an insignificant parent.
Claim 12
Dependent Claim
22 words
The method of claim 1 , wherein the subsequences include a Run subsequence, a Non-Zero parent subsequence, and a Non-Zero Neighbor subsequence.
Claim 13
Dependent Claim
36 words
The method of claim 11 , wherein the Non-Zero Neighbor subsequence is ordered in the bitstream before the Non-Zero Parent subsequence, and wherein the Non-Zero Parent subsequence is ordered in the bitstream before the Run subsequence.
Claim 14
Dependent Claim
28 words
The method of claim 12 , wherein the subsequences further include a Refinement subsequence, and wherein the Refinement subsequence is ordered in the bitstream after the Run subsequence.
Claim 15
Dependent Claim
14 words
The method of claim 11 , wherein the subsequences further include a Refinement subsequence.
Claim 16
Dependent Claim
12 words
The method of claim 1 , wherein the subsequences are entropy encoded.
Claim 17
Dependent Claim
14 words
The method of claim 1 , wherein the subsequences are adaptive run length coded.
Claim 18
Dependent Claim
16 words
The method of claim 16 , wherein the subsequences are encoded by adaptive elementary Golomb coding.
Claim 19
Dependent Claim
18 words
The method of claim 1 , wherein the subsequences for all bit-planes are formed in a single pass.
Claim 20
Dependent Claim
14 words
The method of claim 1 , wherein the subsequences are formed over multiple passes.
Claim 21
Dependent Claim
21 words
The method of claim 1 , wherein the subsequences are ordered according to decreasing probability of bits being equal to one.
Claim 22
Dependent Claim
38 words
The method of claim 1 , further comprising the step of transforming image data into a plurality of Wavelet transform coefficients, and wherein the transform coefficients are quantized, the quantized coefficients being decomposed into the plurality of subsequences.
Claim 23
Dependent Claim
64 words
An encoder comprising: a processor; and processor memory encoded with a plurality of executable instructions that, when executed, instruct the processor to separate the input data into a plurality of subsequences, order the subsequences according to decreasing expected distortion reduction per expected bit of description, and encode at least some of the ordered subsequences; the encoded subsequences being placed in the bitstream as ordered.
Claim 24
Dependent Claim
64 words
An encoder comprising: a processor; and processor memory encoded with a plurality of executable instructions that, when executed, instruct the processor to separate the input data into a plurality of subsequences, order the subsequences according to decreasing expected distortion reduction per expected bit of description, and encode at least some of the ordered subsequences; the encoded subsequences being placed in the bitstream as ordered.
Claim 25
Dependent Claim
33 words
The encoder of claim 22 , wherein the ordering is performed according to an estimate of the relative magnitudes of the probabilities that bits in each of the subsequences are equal to one.
Claim 26
Dependent Claim
23 words
The encoder of claim 23 , wherein the ordering is performed according to a priori assumptions about the relative magnitudes of the probabilities.
Claim 27
Dependent Claim
32 words
The encoder of claim 23 , wherein the relative magnitudes of the probabilities are determined adaptively for the input data, and wherein the ordering is performed according to the adaptively determined probabilities.
Claim 28
Dependent Claim
21 words
The encoder of claim 22 , wherein subsequence determinations are based upon a context of coefficient bits in previously processed bit-planes.
Claim 29
Dependent Claim
20 words
The encoder of claim 22 , wherein subsequence determinations are based upon a context of coefficient bits in current bit-planes.
Claim 30
Dependent Claim
14 words
The encoder of claim 22 , wherein the subsequences are adaptive run length coded.
Claim 31
Dependent Claim
16 words
The encoder of claim 28 , wherein the subsequences are encoded by adaptive elementary Golomb coding.
Claim 32
Dependent Claim
62 words
Apparatus for processing input data to produce an embedded bitstream, the apparatus comprising: means for separating the input data into a plurality of subsequences; means for ordering the subsequences according to decreasing expected distortion reduction per expected bit of description; and means for encoding at least some of the ordered subsequences; whereby the encoded subsequences are placed in the bitstream as ordered.
Claim 33
Dependent Claim
62 words
Apparatus for processing input data to produce an embedded bitstream, the apparatus comprising: means for separating the input data into a plurality of subsequences; means for ordering the subsequences according to decreasing expected distortion reduction per expected bit of description; and means for encoding at least some of the ordered subsequences; whereby the encoded subsequences are placed in the bitstream as ordered.
Claim 34
Dependent Claim
36 words
The apparatus of claim 30 , further comprising means for transforming data into a plurality of transform coefficients; and means for quantizing the transform coefficients, the quantizing means providing the input data to the separating means.
Claim 35
Dependent Claim
16 words
The apparatus of claim 30 , wherein the encoding means includes an adaptive run length encoder.
Claim 36
Dependent Claim
73 words
An article of manufacture for a processor, the article comprising: processor memory; and a plurality of executable instructions encoded in the processor memory, the instructions, when executed, instructing the processor to separate the input data into a plurality of subsequences, order the subsequences according to decreasing expected distortion reduction per expected bit of description, and encode at least some of the ordered subsequences; the encoded subsequences being placed in the bitstream as ordered.
Claim 37
Dependent Claim
73 words
An article of manufacture for a processor, the article comprising: processor memory; and a plurality of executable instructions encoded in the processor memory, the instructions, when executed, instructing the processor to separate the input data into a plurality of subsequences, order the subsequences according to decreasing expected distortion reduction per expected bit of description, and encode at least some of the ordered subsequences; the encoded subsequences being placed in the bitstream as ordered.
Claim 38
Dependent Claim
32 words
The article of claim 33 , wherein the ordering is performed according an estimate of the relative magnitudes of the probabilities that bits in each of the subsequences are equal to one.
Claim 39
Dependent Claim
23 words
The article of claim 34 , wherein the ordering is performed according to a priori assumptions about the relative magnitudes of the probabilities.
Claim 40
Dependent Claim
32 words
The article of claim 34 , wherein the relative magnitudes of the probabilities are determined adaptively for the input data, and wherein the ordering is performed according to the adaptively determined probabilities.
Claim 41
Dependent Claim
23 words
The article of claim 33 , wherein the subsequences are based upon a context of coefficient bits that were encoded in previous bit-planes.
Claim 42
Dependent Claim
21 words
The article of claim 33 , wherein the subsequences are based upon the context of encoded coefficient bits in current bit-planes.
Claim 43
Dependent Claim
14 words
The article of claim 33 , wherein the subsequences are adaptive run length coded.
Claim 44
Dependent Claim
16 words
The article of claim 39 , wherein the subsequences are encoded by adaptive elementary Golomb coding.
References Cited (Backward Citations)
US5412741A
Cited
US5867602A
Cited
US5764807A
Cited
US5825929A
Cited
US5995668A
Cited
US5909513A
Cited
US5764374A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-07-16 | 2005-01-15 | 2005-07-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-07-16 | 2009-01-15 | 2009-07-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-07-16 | 2013-01-15 | 2013-07-17 | $7700.00 | Window Closed / Lapsed |