US5835034A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for lossless image compression
Assignee: Hewlett Packard Development Co LP
•
Filing: 1997-06-24
•
Granted: 1998-11-10
•
Expires: 2017-06-24
Abstract
Abstract A lossless image compression encoder/decoder system having a context determination circuit and a code table generator. The image compressor uses the context of a pixel to be encoded to predict the value of the pixel and determines a prediction error. The image compressor contains a context quantizer that quantizes the context of pixels. The image compressor counts the error values for each quantized context and uses these counts to generate context-specific coding tables for each quantized context. As it encodes a particular pixel, the encoder looks up the prediction error in the context-specific coding table for the context of the pixel and encodes that value. To decompress an image, the decompressor determines and quantizes the context of each pixel being decoded. The decompressor uses the same pixels as the compressor to determine the context. The decompressor retrieves from the context-specific coding table the error value corresponding to the coded pixel. The decompressor uses a predictor to predict the value of the pixel based on the context and adds the error value to determine the actual value of the pixel. In one embodiment the image compressor uses an alphabet extension, embedded in its context model, in specific low gradient contexts to reduce the redundancy of the encoding. Other systems and methods are disclosed.
Inventors
- 👤 Gadiel Seroussi
- 👤 Guillermo Sapiro
- 👤 Marcelo Weinberger
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 08:58
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/50; H04N19/593; H04N19/10; H04N19/102; H04N19/13; H04N19/90; H04N19/91
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
119 words
A method of decompression using a decoder, comprising: retrieving a compressed image; and decoding an individual pixel from data of the compressed image, including determining context for the individual pixel from at least one gradient between previously decoded pixels adjacent to the individual pixel, computing a predicted value for the individual pixel based on values of a predefined group of previously decoded pixels, accessing a context-specific code table (selected in response to the determined context) and retrieving an error value from the table chosen in response to encoded data corresponding to the individual pixel, and combining the error value with the predicted value to obtain an actual value of the individual pixel, whereby the individual pixel is thereby decoded.
Claim 2
Independent Claim
119 words
A method of decompression using a decoder, comprising: retrieving a compressed image; and decoding an individual pixel from data of the compressed image, including determining context for the individual pixel from at least one gradient between previously decoded pixels adjacent to the individual pixel, computing a predicted value for the individual pixel based on values of a predefined group of previously decoded pixels, accessing a context-specific code table (selected in response to the determined context) and retrieving an error value from the table chosen in response to encoded data corresponding to the individual pixel, and combining the error value with the predicted value to obtain an actual value of the individual pixel, whereby the individual pixel is thereby decoded.
Claim 3
Dependent Claim
17 words
A method according to claim 1, further comprising repeating decoding for each pixel of the compressed image.
Claim 4
Dependent Claim
45 words
A method according to claim 1, wherein accessing a code table includes accessing a Huffman table for each specific context by, each Huffman table obtained by: determining a distribution of error values; and using the distribution to build a Huffman table for each specific context.
Claim 5
Dependent Claim
48 words
A method according to claim 1, wherein determining a context includes: determining at least two different gradients between previously decoded pixels adjacent to the individual pixel; dividing expected values for each gradient into multiple regions; and identifying a vector representing each region into which actual gradient values fall.
Claim 6
Dependent Claim
79 words
A method according to claim 1, wherein determining a context includes: determining values for each of three different gradients "(d-a)," "(a-c)" and "(c-b)", where "a" represents a north pixel, "c" represents a northwest pixel, "d" represents a northeast pixel, and "b" represents a west pixel; determining which one of multiple regions associated with each gradient "(d-a)," "(a-c)" and "(c-b)" that the values fall within; and defining context as a being a vector identifying regions into which the values fall.
Claim 7
Dependent Claim
34 words
A method according to claim 5, wherein: each permutation of regions across the three different gradients provides a vector; and a single code table is associated with regions having vectors which are reciprocal pairs.
Claim 8
Dependent Claim
36 words
A method according to claim 5, wherein each gradient has associated with it one region centered at zero and at least one reciprocal pair of regions on either side of the one region centered at zero.
Claim 9
Dependent Claim
32 words
A method according to claim 1, wherein for each context, a corresponding code table includes codes identifying both actual residuals and at least one code identifying that a residual exceeds a threshold.
Claim 10
Dependent Claim
55 words
A method according to claim 8, wherein the at least one code identifying that a residual exceeds a threshold includes an escape code indicating that a non-context specific Huffman table is used for retrieving an infrequently occurring residual, and data further identifies a location within the non-context specific Huffman table for the infrequently occurring residual.
Claim 11
Dependent Claim
57 words
A method according to claim 1, wherein computing a predicted value includes predicting a value which is max(a',b), if a+b-c≧max(a',b), min(a',b), if a+b-c≦min(a',b), and a+b-c otherwise, where "a" represents a north pixel, "c" represents a northwest pixel, "d" represents a northeast pixel, "b" represents a west pixel, and "a'" is given by ##EQU7## and a otherwise. "
Claim 12
Dependent Claim
49 words
A method according to claim 1, wherein computing a predicted value includes predicting a value which is max(a,b), if a+b-c ≧max(a,b), min(a,b) if a+b-c≧min(a,b) and a+b-c otherwise, where "a" represents a north pixel, "c" represents a northwest pixel, "d" represents a northeast pixel, and "b" represents a west pixel."
Claim 13
Dependent Claim
145 words
A method according to claim 1, further comprising: receiving a first indicator indicating whether fixed Huffman tables should be used for decoding or whether Huffman tables are provided together with the compressed input image; and if the first indicator indicates that Huffman tables are provided together with the compressed image, then for each Huffman table receiving a description of a binary tree, receiving a second indicator of whether residual values follow a presumed order, and if the second indicator indicates that residual values follow a presumed order, then for each pair of residual values consisting of a positive residual and a negative of the positive residual, receiving an indicator of whether the positive residual is more probable than the negative of the positive residual, and if the second indicator does not indicate that residual values follow a presumed order, then receiving a sequence of symbols.
Claim 14
Dependent Claim
101 words
In an image decoder which converts compressed image data to decompressed images, where individual pixels are reconstructed based on both an estimate value obtained from previously decoded pixels, and a residual value, the improvement comprising determining a residual value by: determining for a particular pixel at least two different gradient values by comparison of previously decoded neighboring pixels; and applying a particular one of multiple Huffman tables to a compressed image datum corresponding to the particular pixel to thereby obtain the residual, the particular one of the multiple Huffman tables selected in response to the at least two different gradient values.
Claim 15
Dependent Claim
101 words
In an image decoder which converts compressed image data to decompressed images, where individual pixels are reconstructed based on both an estimate value obtained from previously decoded pixels, and a residual value, the improvement comprising determining a residual value by: determining for a particular pixel at least two different gradient values by comparison of previously decoded neighboring pixels; and applying a particular one of multiple Huffman tables to a compressed image datum corresponding to the particular pixel to thereby obtain the residual, the particular one of the multiple Huffman tables selected in response to the at least two different gradient values.
Claim 16
Dependent Claim
73 words
An improvement according to claim 13, further comprising: defining multiple regions for each of two gradients, each region being a non-overlapping range of possible gradient values; for the particular pixel, determining context by comparing the at least two gradient values to the multiple regions and determining a vector therefrom which identifies the regions into which the at least two gradient values fall; and selecting a context-specific Huffman table in response to the vector.
Claim 17
Dependent Claim
161 words
A decoder, comprising: a machine-readable storage mechanism that stores compressed image data, each datum corresponding to an encoded pixel; a table array memory that stores multiple code tables; a pixel predictor that predicts an estimate value of a particular pixel based upon the value of previously decoded pixels; a pixel context quantizer including a pixel comparator that compares previously decoded pixels to obtain at least one gradient value associated with the particular pixel, a quantizer that identifies one of multiple regions corresponding to a gradient value, each region representing a range of possible gradient values, and a pixel decoder that selects a residual value for the particular pixel in response to both each region identified by the quantizer and a datum corresponding to an encoded value for the particular pixel, the residual value selected from a context-specific code table; and a summing mechanism that adds the estimate value to the residual, to thereby obtain actual, decoded value of the particular pixel.
Claim 18
Dependent Claim
161 words
A decoder, comprising: a machine-readable storage mechanism that stores compressed image data, each datum corresponding to an encoded pixel; a table array memory that stores multiple code tables; a pixel predictor that predicts an estimate value of a particular pixel based upon the value of previously decoded pixels; a pixel context quantizer including a pixel comparator that compares previously decoded pixels to obtain at least one gradient value associated with the particular pixel, a quantizer that identifies one of multiple regions corresponding to a gradient value, each region representing a range of possible gradient values, and a pixel decoder that selects a residual value for the particular pixel in response to both each region identified by the quantizer and a datum corresponding to an encoded value for the particular pixel, the residual value selected from a context-specific code table; and a summing mechanism that adds the estimate value to the residual, to thereby obtain actual, decoded value of the particular pixel.
Claim 19
Dependent Claim
15 words
A decoder according to claim 15, wherein the table array memory includes multiple Huffman tables.
Claim 20
Dependent Claim
29 words
A decoder according to claim 15, wherein the pixel comparator compares multiple pixels which are previously decoded neighbors to the particular pixel, and determines two different gradient values therefrom.
Claim 21
Dependent Claim
130 words
A decoder according to claim 15, wherein: the pixel comparator compares multiple pixels which are previously decoded neighbors to the particular pixel, and determines three different gradient values therefrom, "(d-a)," "(a-c)" and "(c-b)", where "a" represents a north pixel, "c" represents a northwest pixel, "d" represents a northeast pixel, and "b" represents a west pixel; each of three different gradients has multiple regions of possible gradient values, and the quantizer determines context to be a vector which identifies a region associated with the three different gradient values for the particular pixel; and the pixel decoder selects a Huffman table associated with the vector and selects a residual value therein which is at a location within the Huffman table identified by the datum representing an encoded value for the particular pixel.
References Cited (Backward Citations)
US5680129A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-09 | 2002-05-11 | 2002-11-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-09 | 2006-05-11 | 2006-11-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-09 | 2010-05-11 | 2010-11-10 | $7700.00 | Window Closed / Lapsed |