US5966465A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Compression/decompression using reversible embedded wavelets
Assignee: Ricoh Co Ltd
•
Filing: 1996-05-03
•
Granted: 1999-10-12
•
Expires: 2016-05-03
Abstract
Abstract A compression and decompression system in which a reversible wavelet filter are used to generates coefficients from input data, such as image data. The reversible wavelet filter is an efficient transform implemented with integer arithmetic that has exact reconstruction. The present invention uses the reversible wavelet filter in a lossless system (or lossy system) in which an embedded codestream is generated from the coefficients produced by the filter. An entropy coder performs entropy coding on the embedded codestream to produce the compressed data stream.
Inventors
- 👤 Alexander F. Keith
- 👤 Edward L. Schwartz
- 👤 Ahmad Zandi
- 👤 Martin Boliek
- 👤 Michael J. Gormish
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 06:51
CPC Classifications
H; H04; H04N; H04N21/00; H04N21/60; H04N21/65; H04N21/658; G; G06; G06F; G06F17/00; G06F17/10; G06F17/14; G06F17/148; H03; H03M; H03M7/00; H03M7/30; H04N19/00; H04N19/10; H04N19/102; H04N19/12; H04N19/122; H04N19/129; H04N19/134; H04N19/136; H04N19/14; H04N19/146; H04N19/15; H04N19/156; H04N19/162; H04N19/167; H04N19/169; H04N19/17; H04N19/176; H04N19/186; H04N19/1883; H04N19/30; H04N19/36; H04N19/46; H04N19/50; H04N19/593; H04N19/60; H04N19/61; H04N19/63; H04N19/635; H04N19/64; H04N19/647; H04N19/90; H04N19/98; H04N21/63; H04N21/637; H04N21/6377; H04N19/115; H04N19/13; H04N19/42
Claims Analysis
Total Claims: 53
Claim 1
Independent Claim
116 words
An encoder comprising: a memory; and a forward transform operating on data in the memory, wherein the transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information such that the forward transform is computed in place in the memory; wherein the memory comprises: a plurality of lines of memory; and a line buffer having a plurality of entries containing pointers to the plurality of lines of memory, wherein each of the plurality of entries are associated with an individual memory lines, wherein the pointers are moved between entries in the line access buffer to resemble scrolling of the memory without moving the data in the memory lines.
Claim 2
Dependent Claim
116 words
An encoder comprising: a memory; and a forward transform operating on data in the memory, wherein the transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information such that the forward transform is computed in place in the memory; wherein the memory comprises: a plurality of lines of memory; and a line buffer having a plurality of entries containing pointers to the plurality of lines of memory, wherein each of the plurality of entries are associated with an individual memory lines, wherein the pointers are moved between entries in the line access buffer to resemble scrolling of the memory without moving the data in the memory lines.
Claim 3
Dependent Claim
15 words
The encoder defined in claim 1 wherein the forward transform comprises a critically sampled transform.
Claim 4
Dependent Claim
14 words
The encoder defined in claim 1 wherein the forward transform comprises a reversible wavelet.
Claim 5
Dependent Claim
25 words
The encoder defined in claim 1 wherein an initial calculation causes a detail output to replace a partial product required to derive the detail output.
Claim 6
Dependent Claim
19 words
The encoder defined in claim 4 wherein input values are replaced by a smooth output and a partial product.
Claim 7
Dependent Claim
26 words
The encoder defined in claim 1 further comprising: an embedded order quantizer coupled to the forward transform; a context model coupled to the embedded order quantizer.
Claim 8
Dependent Claim
14 words
The encoder defined in claim 6 further comprising an embedded binary style coding mechanism.
Claim 9
Dependent Claim
93 words
The encoder defined in claim 7 further comprising: a binary entropy coder coupled to the context model and the embedded binary style coding mechanism, wherein the forward transform, the embedded order quantizer, and the context model are operable to compress image data using reversible embedded wavelets and the binary style coding mechanism is operable to compress image data using the binary coding scheme; and selection control coupled to select wavelet or binary style based on whether portions of the image data have characteristics of continuous-tone image data or of binary image data, respectfully.
Claim 10
Dependent Claim
14 words
The encoder defined in claim 1 further comprising software to manage the line buffer.
Claim 11
Dependent Claim
40 words
The encoder defined in claim 1 wherein the forward transform is applied to only as many lines of the image that are necessary to completely compute a set of wavelets that make up at least one band of wavelet units.
Claim 12
Dependent Claim
15 words
The encoder defined in claim 1 further comprising a context model, and an entropy coder.
Claim 13
Dependent Claim
22 words
The encoder defined in claim 11 computed sets wavelet coefficients in the memory are modeled, entropy coded and removed from the memory.
Claim 14
Dependent Claim
28 words
The encoder defined in claim 1 wherein the forward transform is applied to an entire image while storing in the memory only a band image at a time.
Claim 15
Dependent Claim
24 words
The encoder defined in claim 1 wherein the pointers in the line buffer are rearranged to give the appearance that the memory is scrolling.
Claim 16
Dependent Claim
49 words
An encoder comprising: a memory; and a Two-Six transform operating on data in the memory, wherein the Two-Six transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the Two-Six transform is computed in place in the memory.
Claim 17
Dependent Claim
49 words
An encoder comprising: a memory; and a Two-Six transform operating on data in the memory, wherein the Two-Six transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the Two-Six transform is computed in place in the memory.
Claim 18
Dependent Claim
49 words
An encoder comprising: a memory; and a Two-Ten transform operating on data in the memory, wherein the Two-Ten transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the Two-Ten transform is computed in place in the memory.
Claim 19
Dependent Claim
49 words
An encoder comprising: a memory; and a Two-Ten transform operating on data in the memory, wherein the Two-Ten transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the Two-Ten transform is computed in place in the memory.
Claim 20
Dependent Claim
74 words
The encoder defined in claim 16 wherein the memory comprises: a plurality of lines of memory; and a line buffer having a plurality of entries containing pointers to the plurality of lines of memory, wherein each of the plurality of entries are associated with an individual memory lines, wherein the pointers are moved between entries in the line access buffer to resemble scrolling of the memory without moving the data in the memory lines.
Claim 21
Dependent Claim
58 words
The system defined in claim 17 wherein encoded data is transferred out of the memory and the locations are overwritten with new image data, and further wherein the pointers in the line access buffer are moved such that the top line of the previously stored data that remains in the memory appears as the top of the memory.
Claim 22
Dependent Claim
27 words
The encoder defined in claim 16 further comprising: an embedded order quantizer coupled to the forward transform; and a context model coupled to the embedded order quantizer.
Claim 23
Dependent Claim
14 words
The encoder defined in claim 16 further comprising an embedded binary style coding mechanism.
Claim 24
Dependent Claim
93 words
The encoder defined in claim 16 further comprising: a binary entropy coder coupled to the context model and the embedded binary style coding mechanism, wherein the forward transform, the embedded order quantizer, and the context model are operable to compress image data using reversible embedded wavelets and the binary style coding mechanism is operable to compress image data using the binary coding scheme; and selection control coupled to select wavelet or binary style based on whether portions of the image data have characteristics of continuous-tone image data or of binary image data, respectfully.
Claim 25
Dependent Claim
14 words
The encoder defined in claim 16 further comprising software to manage the line buffer.
Claim 26
Dependent Claim
40 words
The encoder defined in claim 16 wherein the forward transform is applied to only as many lines of the image that are necessary to completely compute a set of wavelets that make up at least one band of wavelet units.
Claim 27
Dependent Claim
15 words
The encoder defined in claim 16 further comprising a context model, and an entropy coder.
Claim 28
Dependent Claim
22 words
The encoder defined in claim 16 computed sets wavelet coefficients in the memory are modeled, entropy coded and removed from the memory.
Claim 29
Dependent Claim
28 words
The encoder defined in claim 16 wherein the forward transform is applied to an entire image while storing in the memory only a band image at a time.
Claim 30
Dependent Claim
24 words
The encoder defined in claim 16 wherein the pointers and the line buffer are rearranged to give the appearance that the memory is scrolling.
Claim 31
Dependent Claim
129 words
An encoder comprising: a buffer comprising a plurality of lines of memory and a line buffer having a plurality of entries containing pointers to the plurality of lines of memory, wherein each of the plurality of entries are associated with an individual memory lines, wherein pointers are moved between entries in the line access buffer to resemble scrolling of the buffer without moving the data in the memory lines; a forward transform operating on data in the buffer, wherein the forward transform is computed and stored in the buffer by storing calculation results in locations containing no longer necessary information, such that the transform is computed in place in the buffer memory; an embedded quantizer coupled to the forward transform; and an entropy coder coupled to the embedded quantizer.
Claim 32
Dependent Claim
129 words
An encoder comprising: a buffer comprising a plurality of lines of memory and a line buffer having a plurality of entries containing pointers to the plurality of lines of memory, wherein each of the plurality of entries are associated with an individual memory lines, wherein pointers are moved between entries in the line access buffer to resemble scrolling of the buffer without moving the data in the memory lines; a forward transform operating on data in the buffer, wherein the forward transform is computed and stored in the buffer by storing calculation results in locations containing no longer necessary information, such that the transform is computed in place in the buffer memory; an embedded quantizer coupled to the forward transform; and an entropy coder coupled to the embedded quantizer.
Claim 33
Dependent Claim
14 words
The encoder defined in claim 28 wherein the forward transform comprises a Two-Six transform.
Claim 34
Dependent Claim
14 words
The encoder defined in claim 28 wherein the forward transform comprises a Two-Ten transform.
Claim 35
Independent Claim
98 words
A method for encoding data comprising: applying a first one dimensional wavelet transform to each line in a buffer having a plurality of memory lines; applying a second one dimensional wavelet transform to each column in the buffer; modeling a set of completely computed wavelet coefficients; entropy coding the set of completely computed wavelet coefficients; removing the set of completely computed wavelet coefficients from the buffer after entropy coding; moving pointers between entries in a line access buffer associated with the buffer to resemble scrolling of the buffer without moving the data in the plurality of memory lines.
Claim 36
Independent Claim
98 words
A method for encoding data comprising: applying a first one dimensional wavelet transform to each line in a buffer having a plurality of memory lines; applying a second one dimensional wavelet transform to each column in the buffer; modeling a set of completely computed wavelet coefficients; entropy coding the set of completely computed wavelet coefficients; removing the set of completely computed wavelet coefficients from the buffer after entropy coding; moving pointers between entries in a line access buffer associated with the buffer to resemble scrolling of the buffer without moving the data in the plurality of memory lines.
Claim 37
Dependent Claim
21 words
The method defined in claim 31 wherein the first one dimensional wavelet transform and the second wavelet transform are the same.
Claim 38
Dependent Claim
52 words
A decoder comprising: a buffer memory; and an inverse transform operating on data in the buffer memory, wherein the inverse transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the inverse transform is computed in place in the buffer memory.
Claim 39
Dependent Claim
52 words
A decoder comprising: a buffer memory; and an inverse transform operating on data in the buffer memory, wherein the inverse transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the inverse transform is computed in place in the buffer memory.
Claim 40
Dependent Claim
15 words
The decoder defined in claim 33 wherein the inverse transform comprises a critically sampled transform.
Claim 41
Dependent Claim
15 words
The decoder defined in claim 33 wherein the inverse transform comprises a reversible wavelet transform.
Claim 42
Dependent Claim
25 words
The decoder defined in claim 33 wherein an initial calculation causes a detail output to replace a partial product required to derive the detail output.
Claim 43
Dependent Claim
19 words
The decoder defined in claim 36 wherein input values are replaced by a smooth output and a partial product.
Claim 44
Dependent Claim
52 words
A decoder comprising: a buffer memory; and an Two-Six transform operating on data in the buffer memory, wherein the Two-Six transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the Two-Six transform is computed in place in the buffer memory.
Claim 45
Dependent Claim
52 words
A decoder comprising: a buffer memory; and an Two-Six transform operating on data in the buffer memory, wherein the Two-Six transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the Two-Six transform is computed in place in the buffer memory.
Claim 46
Dependent Claim
51 words
A decoder comprising: a buffer memory: and an Two-Ten transform operating on data in the buffer memory, wherein Two-Ten transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the Two-Ten transform is computed in place in the buffer memory.
Claim 47
Dependent Claim
51 words
A decoder comprising: a buffer memory: and an Two-Ten transform operating on data in the buffer memory, wherein Two-Ten transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the Two-Ten transform is computed in place in the buffer memory.
Claim 48
Dependent Claim
132 words
An encoder comprising: a buffer comprising a plurality of lines of memory and a line buffer having a plurality of entries containing pointers to the plurality of lines of memory, wherein each of the plurality of entries are associated with an individual memory lines; a reversible wavelet transform coupled to the buffer to receive image data and generate a plurality of coefficients, wherein the buffer stores the plurality of coefficients; an ordering mechanism coupled to receive coefficients from the buffer for ordering, wherein the ordering mechanism stores ordered coefficients in the buffer; and a coder coupled to receive ordered coefficients from the buffer and generate encoded data; wherein pointers are moved between entries in the line access buffer to resemble scrolling of the buffer without moving the data in the memory lines.
Claim 49
Dependent Claim
132 words
An encoder comprising: a buffer comprising a plurality of lines of memory and a line buffer having a plurality of entries containing pointers to the plurality of lines of memory, wherein each of the plurality of entries are associated with an individual memory lines; a reversible wavelet transform coupled to the buffer to receive image data and generate a plurality of coefficients, wherein the buffer stores the plurality of coefficients; an ordering mechanism coupled to receive coefficients from the buffer for ordering, wherein the ordering mechanism stores ordered coefficients in the buffer; and a coder coupled to receive ordered coefficients from the buffer and generate encoded data; wherein pointers are moved between entries in the line access buffer to resemble scrolling of the buffer without moving the data in the memory lines.
Claim 50
Dependent Claim
13 words
The system defined in claim 40 wherein the transform comprises an overlapping transform.
Claim 51
Dependent Claim
58 words
The system defined in claim 40 wherein encoded data is transferred out of the buffer and the locations are overwritten with new image data, and further wherein the pointers in the line access buffer are moved such that the top line of the previously stored data that remains in the buffer appears as the top of the buffer.
Claim 52
Dependent Claim
116 words
A computer software product including a computer readable medium having executable instructions stored therein, which when executed by the processor, causes the processor to: apply a first one dimensional wavelet transform to each line in a buffer having a plurality of memory lines; apply a second one dimensional wavelet transform to each column in the buffer; model a set of completely computed wavelet coefficients; entropy code the set of completely computed wavelet coefficients; remove the set of completely computed wavelet coefficients from the buffer after entropy coding; move pointers between entries in a line access buffer associated with the buffer to resemble scrolling of the buffer without moving the data in the plurality of memory lines.
Claim 53
Dependent Claim
116 words
A computer software product including a computer readable medium having executable instructions stored therein, which when executed by the processor, causes the processor to: apply a first one dimensional wavelet transform to each line in a buffer having a plurality of memory lines; apply a second one dimensional wavelet transform to each column in the buffer; model a set of completely computed wavelet coefficients; entropy code the set of completely computed wavelet coefficients; remove the set of completely computed wavelet coefficients from the buffer after entropy coding; move pointers between entries in a line access buffer associated with the buffer to resemble scrolling of the buffer without moving the data in the plurality of memory lines.
References Cited (Backward Citations)
US3580655A
Cited
US3950103A
Cited
US4155097A
Cited
US4190861A
Cited
US4136954A
Cited
US4223354A
Cited
US4393456A
Cited
US4569075A
Cited
US4674125A
Cited
US4599567A
Cited
US4652881A
Cited
US4799179A
Cited
US4701006A
Cited
US4821223A
Cited
US4760563A
Cited
US4929223A
Cited
US4839889A
Cited
US4663660A
Cited
US4922544A
Cited
US4868868A
Cited
US4785348A
Cited
US4805129A
Cited
US4815023A
Cited
US4817182A
Cited
WO1988010049A1
Cited
US4894713A
Cited
US4864398A
Cited
US4837517A
Cited
US4785349A
Cited
US5156943A
Cited
US4936665A
Cited
GB2211691A
Cited
US4827336A
Cited
US4985927A
Cited
US5095447A
Cited
US5018210A
Cited
US5001764A
Cited
US4897717A
Cited
US5109451A
Cited
US4982283A
Cited
US4829378A
Cited
US4904073A
Cited
US5000183A
Cited
US5124930A
Cited
US4918524A
Cited
US5101280A
Cited
US5072308A
Cited
US4987480A
Cited
US4974187A
Cited
US5073964A
Cited
US5241395A
Cited
US5014134A
Cited
WO1991003902A1
Cited
US5173880A
Cited
US5068911A
Cited
US5103306A
Cited
US4999705A
Cited
WO1991018361A1
Cited
US5152953A
Cited
US5101446A
Cited
US5128757A
Cited
US5182645A
Cited
US5148498A
Cited
US5081645A
Cited
US5128791A
Cited
US5097331A
Cited
US5049992A
Cited
US5049993A
Cited
US5335016A
Cited
US5121191A
Cited
US5262958A
Cited
EP0510933A1
Cited
US5235434A
Cited
US5315670A
Cited
US5347479A
Cited
US5563690A
Cited
US5321776A
Cited
EP0593013A2
Cited
EP0611051A1
Cited
US5412741A
Cited
US5497435A
Cited
US5381145A
Cited
US5420891A
Cited
EP0622741A2
Cited
WO1994023385A2
Cited
US5546477A
Cited
US5537493A
Cited
US5495292A
Cited
GB2284121A
Cited
GB2285374A
Cited
US5453945A
Cited
WO1995019683A1
Cited
US5534925A
Cited
EP0701375A2
Cited
US5602589A
Cited
WO1996009718A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-10-11 | 2003-04-12 | 2003-10-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-10-11 | 2007-04-12 | 2007-10-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-10-11 | 2011-04-12 | 2011-10-12 | $7700.00 | Window Closed / Lapsed |