US5680129A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for lossless image compression
Assignee: Hewlett Packard Development Co LP
•
Filing: 1995-07-18
•
Granted: 1997-10-21
•
Expires: 2015-07-18
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
- 👤 Marcelo Weinberger
- 👤 Gadiel Seroussi
- 👤 Guillermo Sapiro
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 20:56
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: 49
Claim 1
Independent Claim
93 words
A method of predicting the value of a pixel in a digitized image comprising the steps of: determining a context of said pixel wherein said context comprises a first pixel located north of said pixel and having a value a, a second pixel located west of said pixel and having a value b, a third pixel located north-west of said pixel and having a value c, and a fourth pixel located north-east of said pixel and having a value d; and determining a predicted value x i+1 for said pixel according to: ##EQU7##
Claim 2
Independent Claim
93 words
A method of predicting the value of a pixel in a digitized image comprising the steps of: determining a context of said pixel wherein said context comprises a first pixel located north of said pixel and having a value a, a second pixel located west of said pixel and having a value b, a third pixel located north-west of said pixel and having a value c, and a fourth pixel located north-east of said pixel and having a value d; and determining a predicted value x i+1 for said pixel according to: ##EQU7##
Claim 3
Independent Claim
107 words
A method of operating a computer to losslessly compress digitized images comprising the steps of: a. retrieving an image to compress from an input device; and b. encoding a pixel in the image by: b.1 directing said computer to use a template of pixels adjacent to the pixel in said image to determine a predicted value for the pixel; b.2 comparing the predicted value and the actual value, thereby producing a residual; b.3 determining a context of the pixel from values of gradients between pixels adjacent to said pixel and quantizing the gradients; and b.4 retrieving a code corresponding to the residual from a context-specific Huffman table.
Claim 4
Independent Claim
107 words
A method of operating a computer to losslessly compress digitized images comprising the steps of: a. retrieving an image to compress from an input device; and b. encoding a pixel in the image by: b.1 directing said computer to use a template of pixels adjacent to the pixel in said image to determine a predicted value for the pixel; b.2 comparing the predicted value and the actual value, thereby producing a residual; b.3 determining a context of the pixel from values of gradients between pixels adjacent to said pixel and quantizing the gradients; and b.4 retrieving a code corresponding to the residual from a context-specific Huffman table.
Claim 5
Dependent Claim
17 words
The method of claim 2, further comprising the step of: c. transmitting the codes to a decoder.
Claim 6
Dependent Claim
37 words
The method of claim 2 wherein said computer determines said context-specific Huffman tables by for each context determining the distribution of error values and using said distribution for said each context to build said context-specific Huffman table.
Claim 7
Dependent Claim
21 words
The method of claim 2 wherein the step of determining said context further comprises quantizing said gradients into approximately equiprobable regions.
Claim 8
Dependent Claim
28 words
The method of claim 5 wherein said quantizing step comprises the steps of for each gradient determining within which of a predetermined number of regions said gradient is.
Claim 9
Dependent Claim
44 words
The method of claim 2 wherein each context-specific Huffman table contains codes corresponding to each member of an alphabet of encodable events, and wherein for at least one context the alphabet of encodable events is extended to include events that are not prediction residuals.
Claim 10
Dependent Claim
31 words
The method of claim 2 wherein said context-specific Huffman tables are static and wherein said computer encodes said image and said decoder decodes said image using said static context-specific Huffman tables.
Claim 11
Dependent Claim
71 words
The method of claim 2 wherein each quantized context corresponds to a context vector of quantized gradients, further comprising the steps of: for each non-zero context vector, creating a context pair having a first member corresponding to said non-zero context and a second member corresponding to the negative of said non-zero context; and for each pixel occurring in the first member of a context pair, encoding the negative of the residual.
Claim 12
Dependent Claim
79 words
The method of claim 2 further comprising the steps of: further subdividing at least one of said quantized contexts into a plurality of sub-quantized contexts; for each pixel occurring in one of said at least one of said subdivided quantized contexts, determining a particular sub-quantized context of said sub-divided quantized context wherein said pixel occurs in said particular sub-quantized context; and retrieving a code corresponding to said residual from a context-specific Huffman table corresponding to said particular sub-quantized context.
Claim 13
Dependent Claim
24 words
The method of claim 9 wherein said at least one of said quantized context is a quantized context corresponding to quantized gradients of zero.
Claim 14
Dependent Claim
25 words
The method of claim 2 further comprising the steps of: for each quantized context, building a context specific Huffman table corresponding to said quantized context.
Claim 15
Dependent Claim
74 words
The method of claim 12 wherein said step of building quantized context specific Huffman tables includes the step of excluding codes for particular residual values; and further comprising the steps of: building a non-context specific Huffman table containing codes for said particular residual values; and for each residual value for which a context-specific Huffman table does not contain a code, retrieving a code from said non-context specific Huffman table for said particular residual values.
Claim 16
Dependent Claim
54 words
The method of claim 13 further comprising the step of: transmitting the code to a decoder; for each residual value for which a context-specific Huffman table does not contain a code, transmitting a special value to the decoder indicating that the code for said residual value was retrieved from said non-context specific Huffman table.
Claim 17
Dependent Claim
15 words
The method of claim 13 wherein said particular residual values are infrequently occurring residual values.
Claim 18
Dependent Claim
14 words
The method of claim 13 wherein said particular residual values are large residual values.
Claim 19
Dependent Claim
79 words
The method of claim 2 wherein said context of said pixel comprises a first pixel located north of said pixel and having a value a, a second pixel located west of said pixel and having a value b, a third pixel located north-west of said pixel and having a value c, and a fourth pixel located north-east of said pixel and having a value d, and said step b of determining a predicted value x i+1 according to: ##EQU8##
Claim 20
Dependent Claim
17 words
The method of claim 2 wherein said codes retrieved from said context-specific Huffman tables are Golomb-Rice codes.
Claim 21
Dependent Claim
63 words
The method of operating a computer to compress digitized images of claim 2 further comprising the steps of: c. building a Huffman table for each quantized context; d. transmitting said quantized context specific Huffman tables to a decoder; e. retrieving a code corresponding to at least one of said residuals from a context-specific Huffman table; and f. transmitting said code to a decoder.
Claim 22
Dependent Claim
149 words
The method of claim 19 wherein said step f of transmitting said context specific Huffman tables further comprises the steps of: transmitting a first indicator indicating whether fixed Huffman tables should be used for decoding or whether Huffman tables are transmitted to said decoder; and if said first indicator indicates that Huffman tables are transmitted: for each said Huffman table: transmitting a description of a binary tree for said Huffman table; transmitting a second indicator of whether the residual values in said Huffman table follows a presumed order; and if such Huffman table follows said presumed order, for each pair of residual values consisting of a positive residual and the negative of said positive residual, transmitting an indicator of whether the positive residual is more probable than the negative of said positive residual; and if such Huffman table does not follow said presumed order, transmitting a sequence of symbols.
Claim 23
Dependent Claim
87 words
The method of claim 20 further comprising the steps of: (a) determining which alternative selected from transmitting Huffman tables and using fixed Huffman tables results in a more efficient compression of said image; setting said first indicator according to said determining step (a); and if sending Huffman tables is more efficient: (b) determining which alternative selected from using a presumed sequence order and sending the sequence order results in a more efficient compression of said image; and setting said second indicator according to said determining step (b).
Claim 24
Dependent Claim
88 words
The method of claim 20 wherein said context-specific Huffman tables do not include codes for infrequently occurring symbols, and further comprising the steps of: generating non-context specific Huffman tables for said infreqently occurring symbols; for such infrequently occurring symbols, transmitting an escape code indicative of such a non-context specific Huffman table is used for retrieving a code corresponding to said infrequently occurring symbol; and for each context specific Huffman table, transmitting a location for said escape code in a sequence of symbols used in constructing said Huffman table.
Claim 25
Dependent Claim
65 words
The method of claim 19 wherein each pixel value is a member of a first alphabet of values, further comprising the step of: mapping each pixel value of said image to a value in a second alphabet, wherein said second alphabet is a subset of said first alphabet; and mapping each decoded pixel value in said second alphabet to a value in a third alphabet.
Claim 26
Dependent Claim
52 words
The method of claim 23 wherein said mapping introduces an error of uniform bound e and each pixel value x i is mapped to a value y i according to a relationship: ##EQU9## and each decoded pixel value y i is mapped to a value x' i according to the relationship: x'=y(2e+1)+e.
Claim 27
Dependent Claim
55 words
The method of claim 23 wherein said mapping introduces an error of uniform bound e and each pixel value x i is mapped to a value y i according to a relationship: ##EQU10## and each decoded pixel value y i is mapped to a value x' i according to the relationship: x'.sub.i =y.sub.i (2e+1). 26.
Claim 28
Dependent Claim
194 words
An image compression encoder wherein for each pixel in an image there is a context based on the pixels that have been encoded prior to said each pixel, having an encoder comprising: a. an image buffer containing at least one digitized image; b. a pixel and context generator connected to said image buffer and operable to retrieve a value of a pixel in said image buffer and a context of said pixel; c. a predictor connected to said context generator and operable to predict the value of said pixel based on said context; d. a subtractor connected to said pixel and to said predictor and operable to subtract said pixel value from a corresponding predicted value, thereby obtaining an error value for said pixel; e. a table-memory for storing a plurality of context-specific Huffman tables; and f. a code generator connected to said pixel and context generator and to said context-specific Huffman tables and operable to retrieve a code based on said context, said pixel value, and said context-specific Huffman table corresponding to said context; wherein said error value is used by said code generator to retrieve said code from said context-specific Huffman table.
Claim 29
Dependent Claim
194 words
An image compression encoder wherein for each pixel in an image there is a context based on the pixels that have been encoded prior to said each pixel, having an encoder comprising: a. an image buffer containing at least one digitized image; b. a pixel and context generator connected to said image buffer and operable to retrieve a value of a pixel in said image buffer and a context of said pixel; c. a predictor connected to said context generator and operable to predict the value of said pixel based on said context; d. a subtractor connected to said pixel and to said predictor and operable to subtract said pixel value from a corresponding predicted value, thereby obtaining an error value for said pixel; e. a table-memory for storing a plurality of context-specific Huffman tables; and f. a code generator connected to said pixel and context generator and to said context-specific Huffman tables and operable to retrieve a code based on said context, said pixel value, and said context-specific Huffman table corresponding to said context; wherein said error value is used by said code generator to retrieve said code from said context-specific Huffman table.
Claim 30
Dependent Claim
45 words
The image compression encoder of claim 26 further comprising a context quantizer connected to said context and operable to quantize the context of a pixel, wherein said code generator uses said quantized context to select a context-specific Huffman table from which to retrieve said code.
Claim 31
Dependent Claim
27 words
The image compression encoder of claim 27 wherein said quantized context determinator determines gradients in said context and determines in which of several regions said gradients fall.
Claim 32
Dependent Claim
201 words
The image compression encoder of claim 28 wherein said context consists of a pixels to the west, northwest, north, and northeast of said pixel, and said image buffer is operable to selectively output values corresponding to said context pixels, and said quantized context determinator comprises: a. a first subtractor connected to input said west and northwest pixel outputs, and operable to output a first difference, whereby said subtractor outputs a first gradient; b. a second subtractor connected to input said northwest and north pixel outputs, and operable to output a second difference, whereby said subtractor outputs a second gradient; c. a third subtractor connected to input said northeast and north pixel outputs, and operable to output a third difference, whereby said subtractor outputs a third gradient; d. a first, a second, and a third quantizer, each having an input connected to said gradient outputs of said first, second, and third subtractor, respectively, wherein each contains a first comparator connected to said input gradient and to a threshold value and a second comparator connected to said input gradient and the negative of said threshold value, whereby said quantizer outputs a quantized gradient, and where said three quantized gradients form a quantized context.
Claim 33
Dependent Claim
58 words
The image compression encoder of claim 29 wherein for each gradient region represented by a positive range has a corresponding negative range and wherein said quantized context determinator further comprises a mapping table for mapping each context having a quantized gradient indicative of a negative range to a corresponding context with the same gradient having a positive range.
Claim 34
Dependent Claim
17 words
The method of claim 30 wherein said alphabet extensions encodes a length of consecutive constant prediction residuals.
Claim 35
Dependent Claim
47 words
The method of claim 31 wherein the context of a pixel is computed from at least one gradient between two adjacent pixels, and comprising the further step of: for each pixel where all said at least one gradient are zero, encoding the number of consecutive such pixels.
Claim 36
Dependent Claim
66 words
The method of claim 31 wherein a pixel follows said length of consecutive constant prediction residuals and comprising the further step of: for the first pixel following said length of consecutive constant prediction residuals, retrieving a code for the residual for said first pixel following said length of consecutive constant prediction residuals from a non-context specific Huffman table that does not include said constant prediction residual.
Claim 37
Dependent Claim
31 words
The image compression encoder/decoder system of claim 6 further comprising: at least one context-specific Huffman table having an alphabet of encodable events extended to include events that are not prediction residuals.
Claim 38
Dependent Claim
20 words
The image compression encoder/decoder system of claim 34 wherein said alphabet extension is a length of consecutive constant prediction residuals.
Claim 39
Dependent Claim
53 words
The image compression encoder/decoder system of claim 34 wherein for each pixel the context of said pixel is determined from at least one quantized gradient between at least two neighboring pixels; for all contexts for which all said quantized gradients are zero, said context-specific Huffman table for the number of consecutive such pixels.
Claim 40
Dependent Claim
15 words
The image compression encoded decoder system of claim 6 wherein said Huffman tables are static.
Claim 41
Dependent Claim
69 words
The image compression encode/decoder system of claim 27 wherein said context-quantizer produces a first index, further comprising: a context sub-quantizer connected to said context and operable to quantize the context of a pixel at a finer resolution than said quantizer and to produce a second index; and a multiplexer connected to said context quantizer and to said context sub-quantizer operable to select one of said first and second indexes.
Claim 42
Dependent Claim
51 words
The image compression encode/decoder system of claim 26 wherein said table memory contains a plurality of context specific Huffman tables that do not contain codes for particular residual values, and wherein said table memory is further operable to store a non-context specific Huffman table containing codes for said particular residual values.
Claim 43
Dependent Claim
18 words
The image compression encode/decoder system of claim 39 wherein said particular residual values are infrequently occurring residual values.
Claim 44
Dependent Claim
17 words
The image compression encode/decoder system of claim 39 wherein said particular residual values are large residual values.
Claim 45
Dependent Claim
27 words
The image compression encode/decoder system of claim 26 further comprising: a coding table generator connected to said table memory and operable to generate said context-specific Huffman tables.
Claim 46
Dependent Claim
19 words
The image compression encode/decoder system of claim 42 wherein said coding table generator is operable to generate Golomb-Rice codes.
Claim 47
Dependent Claim
49 words
The image compression encode/decoder system of claim 26 wherein each pixel has a value in a first alphabet and further comprising: a preprocessor for mapping each pixel value in said image into a value in a second alphabet, wherein said second alphabet is a subset of said first alphabet.
Claim 48
Dependent Claim
55 words
The image compression encode/decoder system of claim 43 wherein said preprocessor introduces an error of uniform bound e and each pixel value x i is mapped to a value y i according to the relationship: ##EQU11## and each decoded pixel value y i is mapped to a value x' i according to the relationship: x'=y(2e+1)+e.
Claim 49
Dependent Claim
57 words
The image compression encode/decoder system of claim 43 wherein said preprocessor introduces an error of uniform bound e and each pixel value x i is mapped to a value y i according to the relationship: ##EQU12## and each decoded pixel value y i is mapped to a value x' i according to the relationship: x'.sub.i =y.sub.i (2e+1).
References Cited (Backward Citations)
US4420771A
Cited
US4542411A
Cited
EP0245621A2
Cited
US4725885A
Cited
US5287200A
Cited
EP0536801A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-10-20 | 2001-04-21 | 2001-10-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-10-20 | 2005-04-21 | 2005-10-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-10-20 | 2009-04-21 | 2009-10-21 | $7700.00 | Window Closed / Lapsed |