Patent US5903676A successfully refreshed from Google Patents.
US5903676A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Context-based, adaptive, lossless image codec
Assignee: WU XIAOLIN (1% RETAINED)
•
Filing: 1995-11-08
•
Granted: 1999-05-11
•
Expires: 2015-11-08
Abstract
Abstract An encoding/decoding method is provided for lossless compression of digital pictures of all types, including continuous-tone images, graphics, multimedia images of mixed text, graphics and photographs, binary documents and drawings. Continuous-tone mode and binary mode are identified on a pixel-by-pixel basis. In continuous-tone mode, context modeling and prediction are employed involving mostly integer arithmetic and simple logic in a conceptually sophisticated scheme. Both the encoding and decoding techniques are suitable for sequential and progressive transmission, although different specific algorithms may be employed for the different specific cases.
Inventors
- 👤 Xiaolin Wu
- 👤 Nasir Memon
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 22:02
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/41; G; G06; G06T; G06T9/00; G06T9/004
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
171 words
A method for lossless image data compression comprising the steps of: dynamically and automatically choosing between a binary level compression mode and a continuous-tone level compression mode for each current image element based on local context of said current image element; thereafter in said binary mode, compressing a ternary coded signal consisting of binary image data or a mode switch command by context-based, adaptive ternary entropy encoding, storing first results in a memory as a first compressed portion of the image data and switching to said continuous-tone level compression mode if said ternary coded signal consists of said mode switch command; compressing continuous-tone level image data of said current image element, in said continuous-tone mode, by context-based, adaptive, non-linear predictive entropy encoding and storing second results in said memory as a second compressed portion of the image data; wherein said binary mode entropy encoding is a first selected context-sensitive entropy-encoding process; and wherein said continuous-tone mode entropy encoding is a second selected context-sensitive entropy-encoding process wherein prediction error is entropy encoded.
Claim 2
Independent Claim
171 words
A method for lossless image data compression comprising the steps of: dynamically and automatically choosing between a binary level compression mode and a continuous-tone level compression mode for each current image element based on local context of said current image element; thereafter in said binary mode, compressing a ternary coded signal consisting of binary image data or a mode switch command by context-based, adaptive ternary entropy encoding, storing first results in a memory as a first compressed portion of the image data and switching to said continuous-tone level compression mode if said ternary coded signal consists of said mode switch command; compressing continuous-tone level image data of said current image element, in said continuous-tone mode, by context-based, adaptive, non-linear predictive entropy encoding and storing second results in said memory as a second compressed portion of the image data; wherein said binary mode entropy encoding is a first selected context-sensitive entropy-encoding process; and wherein said continuous-tone mode entropy encoding is a second selected context-sensitive entropy-encoding process wherein prediction error is entropy encoded.
Claim 3
Dependent Claim
31 words
The method according to claim 1 wherein first selected specific compression techniques are used for sequential transmission of said first compressed portion and said second compressed portion of the image data.
Claim 4
Dependent Claim
31 words
The method according to claim 1 wherein second selected specific compression techniques are used for progressive transmission of said first compressed portion and said second compressed portion of the image data.
Claim 5
Dependent Claim
26 words
The method according to claim 3 further comprising subsampling images in four passes; and forming from subsampling data enclosing contexts in the form of causal templates.
Claim 6
Dependent Claim
35 words
The method according to claim 1 wherein said current image element is a pixel, and wherein in said continuous-tone mode compressing step comprises predicting values for each said pixel based on local intensity gradient estimates.
Claim 7
Dependent Claim
35 words
The method according to claim 5 wherein said predicting step further includes estimating energy of prediction errors based on both local gradient and prediction errors of preceding pixels together to obtain an error energy estimator.
Claim 8
Dependent Claim
31 words
The method according to claim 5 wherein said continuous-tone mode entropy encoding further includes estimating energy of prediction errors based on both local gradient and prediction errors of preceding pixels together.
Claim 9
Dependent Claim
24 words
The method according to claim 7 further including reversing sign of a prediction error to sharpen the conditional error probability densities for entropy coding.
Claim 10
Dependent Claim
61 words
The method according to claim 7 further including adaptive bit shifting in each encoding context in order to scale d h and d v , where d h and d v are estimates, within a scaling factor, of gradients of the intensity function near pixel I i,j! in horizontal and vertical directions, such that encoding schemes are independent of intensity resolutions.
Claim 11
Dependent Claim
24 words
The method according to claim 6 further including quantizing the error energy estimator to form conditioning classes for entropy encoding in the continuous-tone mode.
Claim 12
Dependent Claim
21 words
The method according to claim 5, further including forming modeling contexts by causal templates using a prediction value of a pixel.
Claim 13
Dependent Claim
25 words
The method according to claim 11, further including quantizing the modeling contexts, wherein said quantizing of the modeling contexts comprises binarization of spatial texture patters.
Claim 14
Dependent Claim
17 words
The method according to claim 5, further including selecting an optimal modeling context in a context hierarchy.
Claim 15
Dependent Claim
27 words
The method according to claim 5 further including combining a quantized texture pattern and a quantized error energy estimator into a compound context for modeling prediction errors.
Claim 16
Dependent Claim
26 words
The method according to claim 5 further including using conditional expectations of the prediction errors to model errors at low model cost and low computational cost.
Claim 17
Dependent Claim
19 words
The method according to claim 5 further including reducing weight of past statistics in adapting to non-stationary image data.
Claim 18
Dependent Claim
19 words
The method according to claim 5 further including correcting prediction via context modeling of prediction errors and error feedback.
Claim 19
Dependent Claim
36 words
The method according to claim 1 wherein said choosing step comprises selecting between said binary level compression mode and said continuous-tone level compression mode based on local context information only and without use of side information.
Claim 20
Dependent Claim
22 words
The method according to claim 1 wherein said binary mode compressing step comprises forming a modeling context for adaptive binary entropy encoding.
Claim 21
Independent Claim
350 words
A method for lossless image data compression comprising the steps of: dynamically and automatically choosing between a binary level compression mode and a continuous-tone level compression mode for each current image element based on local context of said current image element, said current image element being a pixel; thereafter, in said binary mode, compressing a ternary coded signal consisting of binary image data or a mode switch command by context-based, adaptive ternary entropy encoding, storing first results in a memory as a first compressed portion of the image data and switching to said continuous-tone level compression mode if said ternary coded signal consists of said mode switch command; compressing continuous-tone level image data of said current image element, in said continuous-tone mode, by context-based, adaptive, non-linear predictive entropy encoding and storing second results in said memory as a second compressed portion of the image data; wherein said binary mode entropy encoding is a first selected context-sensitive entropy-encoding process; and wherein said continuous-tone mode entropy encoding is a second selected context-sensitive entropy-encoding process wherein prediction error is entropy encoded; wherein said continuous-tone mode compressing step further includes: predicting values for each said pixel based on local intensity gradient estimates, including estimating energy of prediction errors based on both local gradient and prediction errors of preceding pixels together to obtain an error energy estimator; forming modeling contexts by causal templates using a prediction value of a pixel; selecting an optimal modeling context in a context hierarchy; combining a quantized texture pattern and a quantized error energy estimator into a compound context for modeling prediction errors; using conditional expectations of the prediction errors to model errors at low model cost and computational cost; correcting prediction via context modeling of prediction errors and error feedback; and wherein said continuous-tone mode entropy encoding further includes: estimating energy of prediction errors based on both local gradient and prediction errors of preceding pixels together; quantizing the error energy estimator to form conditioning classes for entropy encoding in the continuous-tone mode; and reversing sign of a prediction error to sharpen the conditional error probability densities for entropy encoding.
Claim 22
Independent Claim
350 words
A method for lossless image data compression comprising the steps of: dynamically and automatically choosing between a binary level compression mode and a continuous-tone level compression mode for each current image element based on local context of said current image element, said current image element being a pixel; thereafter, in said binary mode, compressing a ternary coded signal consisting of binary image data or a mode switch command by context-based, adaptive ternary entropy encoding, storing first results in a memory as a first compressed portion of the image data and switching to said continuous-tone level compression mode if said ternary coded signal consists of said mode switch command; compressing continuous-tone level image data of said current image element, in said continuous-tone mode, by context-based, adaptive, non-linear predictive entropy encoding and storing second results in said memory as a second compressed portion of the image data; wherein said binary mode entropy encoding is a first selected context-sensitive entropy-encoding process; and wherein said continuous-tone mode entropy encoding is a second selected context-sensitive entropy-encoding process wherein prediction error is entropy encoded; wherein said continuous-tone mode compressing step further includes: predicting values for each said pixel based on local intensity gradient estimates, including estimating energy of prediction errors based on both local gradient and prediction errors of preceding pixels together to obtain an error energy estimator; forming modeling contexts by causal templates using a prediction value of a pixel; selecting an optimal modeling context in a context hierarchy; combining a quantized texture pattern and a quantized error energy estimator into a compound context for modeling prediction errors; using conditional expectations of the prediction errors to model errors at low model cost and computational cost; correcting prediction via context modeling of prediction errors and error feedback; and wherein said continuous-tone mode entropy encoding further includes: estimating energy of prediction errors based on both local gradient and prediction errors of preceding pixels together; quantizing the error energy estimator to form conditioning classes for entropy encoding in the continuous-tone mode; and reversing sign of a prediction error to sharpen the conditional error probability densities for entropy encoding.
Claim 23
Independent Claim
160 words
A system for lossless image data compression comprising: a first subsystem for dynamically and automatically choosing between a binary level compression mode and a continuous-tone level compression mode for each current image element of an input image based on local context of said current image element, including a values predictor operative on each said image element wherein prediction is based on local intensity gradient estimates; a second subsystem for compressing, in said binary mode, ternary data consisting of binary image data of said current image element or a mode switch command by context-based, adaptive, ternary entropy encoding as a first compressed portion of the image data and switching to said continuous-tone level compression mode if said ternary data consists of said mode switch command; and a third subsystem for compressing, in said continuous-tone mode, the image data of said current image element by context-based, adaptive, non-linear predictive entropy encoding as entropy-encoded prediction errors of a second portion of the image.
Claim 24
Independent Claim
160 words
A system for lossless image data compression comprising: a first subsystem for dynamically and automatically choosing between a binary level compression mode and a continuous-tone level compression mode for each current image element of an input image based on local context of said current image element, including a values predictor operative on each said image element wherein prediction is based on local intensity gradient estimates; a second subsystem for compressing, in said binary mode, ternary data consisting of binary image data of said current image element or a mode switch command by context-based, adaptive, ternary entropy encoding as a first compressed portion of the image data and switching to said continuous-tone level compression mode if said ternary data consists of said mode switch command; and a third subsystem for compressing, in said continuous-tone mode, the image data of said current image element by context-based, adaptive, non-linear predictive entropy encoding as entropy-encoded prediction errors of a second portion of the image.
Claim 25
Independent Claim
162 words
A method for lossless image data decompression comprising the steps of: dynamically and automatically choosing between image data compressed by a binary level compression and image data compressed by continuous-tone level compression for each current image element based on local context of said current image element; thereafter either decompressing, in said binary mode, image data of said current image element consisting of binary image data or a mode switch command by context-based, adaptive, ternary entropy decoding to produce a first decompressed portion of the image data and switching to said image data compressed by continuous-tone level compression if said image data consists of said mode switch command; and decompressing, in said continuous-tone mode, the image data of said current image element by context-based, adaptive, non-linear predictive entropy decoding as a second decompressed portion of the image; and directing the first decompressed portion and the second decompressed portion to an output utilization device to produce a binary level and continuous-tone level composite image.
Claim 26
Independent Claim
162 words
A method for lossless image data decompression comprising the steps of: dynamically and automatically choosing between image data compressed by a binary level compression and image data compressed by continuous-tone level compression for each current image element based on local context of said current image element; thereafter either decompressing, in said binary mode, image data of said current image element consisting of binary image data or a mode switch command by context-based, adaptive, ternary entropy decoding to produce a first decompressed portion of the image data and switching to said image data compressed by continuous-tone level compression if said image data consists of said mode switch command; and decompressing, in said continuous-tone mode, the image data of said current image element by context-based, adaptive, non-linear predictive entropy decoding as a second decompressed portion of the image; and directing the first decompressed portion and the second decompressed portion to an output utilization device to produce a binary level and continuous-tone level composite image.
Claim 27
Independent Claim
220 words
A method for substantially lossless image data compression comprising the steps of: dynamically and automatically choosing between a binary level compression mode and a continuous-tone level compression mode for each current image element based on local context of said current image element; thereafter in said binary mode, compressing ternary data consisting of binary image data of said current image element or a mode switch command by functionally-lossless context-based, adaptive, ternary entropy encoding, storing first results in a memory as a first compressed portion of the image data, such that errors in a decompressed version of said image data do not exceed 1 and never occur consecutively in image space and switching to said continuous-tone level compression mode if said ternary data consists of said mode switch command; compressing continuous-tone level image data of said current image element, in said continuous-tone mode, by functionally-lossless context-based, adaptive, non-linear predictive entropy encoding and storing second results in said memory as a second compressed portion of the image data, such that errors in a decompressed version of said image data do not exceed 1 and never occur consecutively in image space; wherein said binary mode entropy encoding is a first selected context-sensitive entropy-encoding process; and wherein said continuous-tone mode entropy encoding is a second selected context-sensitive entropy-encoding process wherein prediction error is entropy encoded.
Claim 28
Independent Claim
220 words
A method for substantially lossless image data compression comprising the steps of: dynamically and automatically choosing between a binary level compression mode and a continuous-tone level compression mode for each current image element based on local context of said current image element; thereafter in said binary mode, compressing ternary data consisting of binary image data of said current image element or a mode switch command by functionally-lossless context-based, adaptive, ternary entropy encoding, storing first results in a memory as a first compressed portion of the image data, such that errors in a decompressed version of said image data do not exceed 1 and never occur consecutively in image space and switching to said continuous-tone level compression mode if said ternary data consists of said mode switch command; compressing continuous-tone level image data of said current image element, in said continuous-tone mode, by functionally-lossless context-based, adaptive, non-linear predictive entropy encoding and storing second results in said memory as a second compressed portion of the image data, such that errors in a decompressed version of said image data do not exceed 1 and never occur consecutively in image space; wherein said binary mode entropy encoding is a first selected context-sensitive entropy-encoding process; and wherein said continuous-tone mode entropy encoding is a second selected context-sensitive entropy-encoding process wherein prediction error is entropy encoded.
References Cited (Backward Citations)
US4870695A
Cited
US5023611A
Cited
EP0547528A1
Cited
US5550540A
Cited
EP0613290A1
Cited
US5539842A
Cited
US5432871A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-05-10 | 2002-11-09 | 2003-05-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-05-10 | 2006-11-09 | 2007-05-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-05-10 | 2010-11-09 | 2011-05-11 | $7700.00 | Window Closed / Lapsed |