System and method for lossless image compression having improved sequential determination of golomb parameter

• US 5,764,374 A
• Filed: 08/30/1996
• Issued: 06/09/1998
• Est. Priority Date: 02/05/1996
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Weinberger, Marcelo, Seroussi, Gadiel
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): WALLERSON, MARK E
• Application Number:
  US08/706,010
• Time in Patent Office: 648 Days
• Field of Search: 358/426, 358/427, 358/470, 358/261.2, 358/261.3, 382/232, 382/233, 382/246, 382/237, 382/238, 382/239, 382/252, 341/65
• US Class Current: 382/244
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

A lossless image compression encoder/decoder system having a context determination circuit and a code 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 and maps the prediction error to a mapped value having a distribution suitable for Golomb encoding. The image compressor contains a context quantizer that quantizes the context of pixels. The image compressor determines a Golomb parameter based on the context and historical information gathered during the coding of an image. To avoid systematic prediction biases in an image, the image compressor adjusts the distribution of prediction residuals to a distribution suitable for Golomb coding. As it encodes a particular pixel, the encoder uses the Golomb parameter to determine a Golomb code for the prediction error 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 uses the context and historical information gathered during the decompression of the image to determine a Golomb parameter for the context in which the pixel occured. The decompressor retrieves from the compressed image the code for the pixel. Using the Golomb parameter and the retrieved code, the decompressor determines the mapped value of the code. The decompressor then uses the inverse mapping to determine the error value. 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.

Claims

1. A method for compressing a digitized image composed of an array of pixels each having a value, the method including a method of determining a Golomb-power-of-two code, comprising:

initializing an array of counters, N, each counter for counting the number of pixels in each of at least one context;

initializing an array of accumulators, A, each accumulator for accumulating a sum of magnitudes of prediction residuals encountered in each of at least one context;

for each pixel in the image;

determining in which context the pixel occurs;

incrementing the counter N for the context;

predicting the value of the pixel;

determining a prediction residual, ε

, for the pixel by subtracting the predicted value from the pixel value;

mapping the prediction residual ε

to a non-negative value M(ε

)

determining a parameter k as a function of the values A and N;

adding the magnitude of the prediction residual to the accumulator A for the context;

encoding the mapped value M(ε

) in a first portion and in a second portion, the first portion being a binary representation of M(ε

) mod m and the second portion being a unary representation of .left brkt-bot.M(ε

)/m.right brkt-bot., where m=2^k.

2. The method of claim 1, wherein:

if ε

is less than zero (0), M(ε

)=2|ε

|-1, and

if ε

is greater than or equal to zero (0), M(ε

)=2|ε

|.

3. The method of claim 1, wherein k is determined from the following relationship:

##EQU12##

4. The method of claim 1, wherein k is determined using instructions equivalent to the C language statement:

space="preserve" listing-type="equation">for (k=0;

(N<

<

k)<

A;

k++).

5.

5. The method of claim 1, wherein k is determined by:

a. storing N in a shift register;

b. left-shifting the shift register until the shifted value is greater than or equal to the value of A; and

c. setting k to the number of left-shifts from step 5.b.

6. The method of claim 1, 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.

7. The method of claim 6, wherein after decoding said mapping introduces an error of uniform bound E and each pixel value x_i is mapped to a value y_i according to the relationship:

##EQU13##

8. A method for operating a computer to compress a digitized image composed of an array of pixels each having a value, the method including a method of determining a Golomb code, comprising:

initializing an array of counters, N, each counter for counting number of pixels in each of at least one context;

initializing an array of accumulators, A, each accumulator for accumulating a sum of magnitudes of prediction residuals encountered in each of at least one context;

for each pixel in the image;

determining in which context the pixel occurs;

incrementing the counter N for the context;

predicting the value of the pixel;

determining a prediction residual, ε

, for the pixel by subtracting the predicted value from the pixel value;

mapping the prediction residual ε

to a non-negative value M(ε

);

determining a parameter m as a function of values A'"'"' and N'"'"';

where A'"'"'=A^q and N'"'"'=N^q and wherein q is a positive integer;

adding the magnitude of the prediction residual ε

to the accumulator A for the context;

encoding the mapped prediction residual M(ε

) in a first portion and in a second portion, the first portion being a binary representation of M(ε

) mod m and the second portion being a unary representation of .left brkt-bot.M(ε

)/m.right brkt-bot..

9. The method of claim 8 wherein q=2 and the step of determining the parameter m comprises the steps of operating the computer to:

computing a quantity k'"'"' by executing instructions equivalent to the C language statement;

space="preserve" listing-type="equation">for (k'"'"'=0;

(N'"'"'<

<

k'"'"')<

A'"'"', k'"'"'++); and

computing setting the value m to an integer value close to ##EQU14##

10. 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;

b. for each pixel in the image;

i. directing the computer to determine a context for the pixel;

ii. directing the computer to use the context of a pixel in the image to determine a predicted value for the pixel;

iii. comparing the predicted value and the actual value, thereby producing a residual value ε

,

iv. mapping the residual value ε

to a mapped value M(ε

);

v. computing a Golomb corresponding to the residual from a context-specific value N and a context-specific value A, where N is a count of pixels encountered in the context, and A is an accumulation of magnitudes of prediction residuals for pixels in the context; and

c. transmitting the code to a decoder.

11. The method of claim 10 further comprising the step of computing the context by determining values of gradients between pixels adjacent to the pixel.

12. The method of claim 11 further comprising the step of computing the context by quantizing the gradients into approximately equiprobable regions.

13. The method of claim 10, wherein the mapping M(ε

) is an alphabet of encodable events, the method further comprising the step of;

defining a first special context; and

when processing a pixel that occurs in the first special context, encoding using a Golomb code an event that is an extension of the alphabet of encodable events.

14. The method of claim 13 wherein the alphabet extension is a length of consecutive constant values.

15. The method of claim 23 wherein the constant values are constant pixel values.

16. The method of claim 23 wherein the constant values are constant prediction residuals.

17. The method of claim 14 farther comprising the step of ranking the lengths of consecutive constant prediction residuals by occurrence counts;

and

for an occurrence of a length r of consecutive constant prediction residuals, encoding the length as a Golomb code for the rank of the length, i(r).

18. The method of claim 17 wherein the step of encoding the rank of the length i(r) as a Golomb code, further comprises the steps of:

determining a Golomb parameter k by executing instructions equivalent to the C statements;

space="preserve" listing-type="equation">for (k=0;

(N<

<

k)<

=A;

k++);

space="preserve" listing-type="equation">if (k≠

0)k--;

encoding the rank of the length i(r) as a first portion and as a second portion, said first portion being a binary representation of i(r) mod m and the second portion being a unary representation of .left brkt-bot.i(r)/m.right brkt-bot., where m=2^k.

19. The method of claim 14 further comprising the steps of:

definining a second special context;

when encoding a pixel immediately following the encoding of an event in the first special context;

encoding the pixel immediately following the encoding of an event in the first special context using a Golomb parameter obtained from values A and N for the second special context; and

updating the values A and N for the second special context.

20. The method of claim 19 wherein the constant values are constant pixel values;

and

a pixel occurring in the second special context is the first pixel following a run of constant pixel values.

21. The method of claim 17 wherein the context is computed from values of pixels previously encoded and adjacent to the pixel being processed, and wherein a pixel occurs in said special context when gradients between pairs of the adjacent pixels are all zero (0).

22. The method of claim 10, wherein the prediction residuals in an image have a distribution, and further comprising the step of:

cancelling biases in the distribution of prediction residuals in images being compressed by adjusting the distribution of prediction residuals to a distribution matched to Golomb encoding and the mapping M(ε

).

23. The method of claim 22 wherein biases in prediction are cancelled, further comprising the steps of:

for each context centering the distribution of prediction residuals occurring in that context by;

for each context, computing a correction value C as a function of an accumulation of prediction residuals B encountered in the context and a count N of occurences of the context; and

for each pixel, prior to encoding the pixel, correcting the predicted value of the pixel by adding the correction value C to the predicted value for the pixel.

24. The method of claim 23 wherein:

the accumulation of prediction residuals B is the accumulation of prediction residuals prior to correction of the predicted value; and

the correction value C is computed by dividing B by N.

25. The method of claim 23 further comprising the step of:

adjusting the value C as a function of the values B and N.

26. The method of claim 10 further comprising the step of:

if the value N for a particular context exceeds a predetermined threshold value N₀, resetting the values for N and A.

27. The method of claim 26 wherein N and A are reset to half their values prior to being reset, respectively.

28. The method of claim 23 wherein:

the accumulation of prediction residuals B is the accumulation of prediction residuals after correction of the predicted value; and

further comprising the step of computing C and B by;

if B is a large negative number, decrementing C and adding N to B; and

if B is a large positive number, incrementing C and subtracting N from B.

29. The method of claim 28, wherein the large negative number is a number less than or equal to the negative of N divided by 2, and wherein the large positive number is a number greater than N divided by 2.

30. The method of claim 23 further comprising the steps of:

if B is less than or equal to the negative of N, decrementing C and adding N to B; and

if B is greater than 0, incrementing C and subtracting N from B.

31. The method of claim 11 the step of quantizing the context further comprises the step of:

quantizing each gradient into one of a small number of regions defined by at least one integer valued threshold parameter.

32. The method of claim 31 wherein the context of a pixel being encoded is determined from a causal template of neighboring pixels, including a first pixel immediately north of the pixel being encoded, a second pixel west of the pixel being encoded, a third pixel northwest of the pixel being encoded, and a fourth pixel northeast of the pixel being encoded, each having a value, and the step of determining the context further comprises the steps of:

determining a first gradient between the values of the fourth and the first pixels;

determining a second gradient between the values of the first and the third pixels; and

determining a third gradient between the values of the third and the second pixels.

33. The method of claim 32 wherein the causal template further includes a fifth pixel immediately west of said second pixel, and the step of determining the context further comprises the step of:

determining a fourth gradient between the values of the second and fifth pixels.

34. An image compression encoder system wherein for each pixel in an image there is a context based on the pixels that have been encoded prior to the each pixel, having an encoder comprising:

a. an image buffer containing a portion of at least one digitized image;

b. a pixel generator connected to the image buffer and operable to determine the value of a pixel in the image buffer and the context of the pixel;

c. a predictor for predicting the value of the pixel;

d. a comparator connected to the pixel generator to obtain the value of the pixel and connected to the predictor to obtain the predicted value, and operable to compute a prediction residual for the pixel;

e. a context quantizer operable to compute a quantized context for the pixel;

f. a storage unit connected to the context quantizer and operable to store a count N of occurrences of each quantized context and an accumulation of magnitudes of prediction residuals A for pixels in each context;

g. a Golomb code parameter generator connected to the storage unit and the context quantizer and operable to compute a Golomb parameter m as a function of the value N and the value A for the context of the pixel; and

h. a code generator connected to the comparator and the Golomb code parameter generator and operable to produce a Golomb code for the pixel based on the Golomb parameter m and the predicted value.

35. The image compression encoder system of claim 34 wherein the Golomb code parameter generator generates the Golomb parameter m using instructions equivalent to a C language statement comprising:

space="preserve" listing-type="equation">for (k=0;

(N<

<

k)<

A;

k++); and

wherein m=2^k.

36. The image compression encoder system of claim 35 wherein the Golomb code parameter generator for a special context generates the Golomb parameter m using instructions equivalent to the C language statements comprising:

space="preserve" listing-type="equation">for (k=0;

(N<

<

k)<

A;

k++);

space="preserve" listing-type="equation">if (k≠

0) k--; and

wherein m=2^k.

37. The image compression encoder system of claim 34 wherein the Golomb code parameter generator further comprises:

a circuit for generating the Golomb parameter m, the operation of the circuit being defined by the C language statements;

space="preserve" listing-type="equation">for (k=0;

(N<

<

k)<

A;

k++); and

wherein m=2^k.

38. The image compression encoder system of claim 34 wherein the Golomb code parameter generator further comprises:

a first comparator having an output k₀ and operable to compare the length of N to the length of A, and if the length of A is greater than the length of N, setting the output k₀ to the difference in the length of A and the length of N, otherwise the output k₀ to zero (0);

a shift register for storing the value N connected to k₀ and operable to left shift N k₀ times, thereby outputting a quantity N<

<

k₀ ;

a second comparator connected to the quantity N<

<

k₀ and to A, and operable to output a one (1) if N<

<

k₀ is less than A, otherwise to output a zero (0); and

an adder connected to the quantity k₀ and to the output of the second comparator, and operable output the quantity k equal to the sum of k₀ and the output of the second comparator.

39. The image compression encoder system of claim 34 wherein the Golomb code parameter generator generates the Golomb parameter m using instructions equivalent to a C language statement comprising:

space="preserve" listing-type="equation">for (k'"'"'=0;

(N'"'"'<

<

k'"'"')<

A'"'"';

k'"'"'++);

wherein m=(2^l/q)^k'"'"', N'"'"'=N^q, A'"'"'=A^q, and q is a positive integer.

40. The image compression encoder system of claim 34, further having bias cancellation circuitry comprising:

a first storage unit for maintaining an occurence count N for each context;

a second storage unit for maintaining an accumulation of prediction residuals B for each context;

a third storage unit for maintaining a correction value C for each context;

a first multiplexer connected to the third storage unit for selectively causing the value C for each context to be incremented, decremented or left unchanged;

an adder connected to a predicted value for the pixel to be encoded and to the third storage unit and operable to cause the value C for the context of the pixel to be added to the predicted value for the pixel, thereby producing a corrected predicted value;

a subtractor connected to the pixel value and to the corrected predicted value to produce a prediction residual; and

a control circuit connected to accept the value B and the value N as inputs and to connected to the first multiplexer to select whether the value C for each context to be incremented, decremented or left unchanged based on the value B and the value N for the context.

41. The image compression encoder system of claim 40 further comprising:

a second multiplexer connected to the second storage unit for selectively adding the value N for the context to the value B for the context, subtracting the value N for the context from the value B for the context, or adding the residual value to the value B for the context.

42. An image decoder system wherein for each pixel in a compressed image there is a context based on the pixels that have been decoded prior to the each pixel, the decoder comprising:

a. means for retrieving encoded pixels of a compressed image;

b. a decompressed image buffer for storing a portion of at least one decompressed digitized image;

c. a context generator connected to the decompressed image buffer and operable to determine the value of a context of a pixel being decoded;

d. a context quantizer operable to compute a quantized context for the pixel being decoded;

e. a storage unit connected to the context quantizer and operable to store a count N of occurrences of each quantized context and an accumulation of magnitudes of prediction residuals A for pixels in each context;

f. a Golomb code parameter generator connected to the storage unit and the context quantizer and operable to compute a Golomb parameter m as a function of the value N and the value A for the context of the pixel being decoded;

g. a code decoder connected to the means for retrieving encoded pixels to obtain a Golomb code for the pixel being decoded and to the Golomb code parameter generator and operable to produce a prediction residual value for the pixel being decoded;

h. a predictor for predicting the value of the pixel being decoded; and

i. an adder connected to the code decoder to obtain the prediction residual value for the pixel being decoded and connected to the predictor to obtain the predicted value, and operable to add the prediction residual value to the predicted value, thereby producing a decoded value for the pixel.

43. The image compression decoder system of claim 42 wherein the Golomb code parameter generator generates the Golomb parameter m using instructions equivalent to a C language statement comprising:

space="preserve" listing-type="equation">for (k=0;

(N<

<

k)<

A;

k++); and

wherein m=2^k.

44. The image compression decoder system of claim 43 wherein the Golomb code parameter generator for a special context generates the Golomb parameter m using instructions equivalent to C language statements comprising:

space="preserve" listing-type="equation">for (k=0;

(N<

<

k)<

A;

k++);

space="preserve" listing-type="equation">if (k≠

0)k--; and

wherein m=2^k.

45. The image compression decoder system of claim 43 wherein the Golomb code parameter generator further comprises:

a circuit for generating the Golomb parameter m, the operation of the circuit being defined by the C language statements;

space="preserve" listing-type="equation">for (k=0;

(N<

<

k)<

A;

k++); and

wherein m=2^k.

46. The image compression decoder system of claim 43 wherein the Golomb code parameter generator further comprises:

a first comparator having an output k₀ and operable to compare the length of N to the length of A, and if the length of A is greater than the length of N, setting the output k₀ to the difference in the length of A and the length of N, otherwise the output k₀ to zero (0);

a shift register for storing the value N connected to k₀ and operable to left shift N k₀ times, thereby outputting a quantity N<

<

k₀ ;

a second comparator connected to the quantity N<

<

k₀ and to A, and operable to output a one (1) if N<

<

k₀ is less than A, otherwise to output a zero (0); and

an adder connected to the quantity k₀ and to the output of the second comparator, and operable output the quantity k equal to the sum of k₀ and the output of the second comparator.

47. The image compression encoder system of claim 43 wherein the Golomb code parameter generator generates the Golomb parameter m using instructions equivalent to a C language statement comprising:

space="preserve" listing-type="equation">for (k'"'"'=0;

(N'"'"'<

<

k'"'"')<

A'"'"';

k'"'"'++);

wherein m is an integer close to (2^l/q)^k'"'"', N'"'"'=N^q, A'"'"'=A^q, and q is a positive integer.

48. The image compression encoder system of claim 43, further having bias cancellation circuitry comprising:

a first storage unit for maintaining an occurence count N for each context;

a second storage unit for maintaining an accumulation of prediction residuals B for each context;

a third storage unit for maintaining a correction value C for each context;

a first multiplexer connected to the third storage unit for selectively causing the value C for each context to be incremented, decremented or left unchanged;

an adder connected to a predicted value for the pixel to be encoded and to the third storage unit and operable to cause the value C for the context of the pixel to be added to the predicted value for the pixel, thereby producing a corrected predicted value;

a subtractor connected to the pixel value and to the corrected predicted value to produce a prediction residual; and

a control circuit connected to accept the value B and the value N as inputs and to connected to the first multiplexer to select whether the value C for each context to be incremented, decremented or left unchanged based on the value B and the value N for the context.

49. The image compression encoder system of claim 48 further comprising:

a second multiplexer connected to the second storage unit for selectively adding the value N for the context to the value B for the context, subtracting the value N for the context from the value B for the context, or adding the residual value to the value B for the context.

50. A method of operating a computer to decompress encoded digitized images comprising the steps of:

a. retrieving a compressed image to decompress from an input device;

b. for each pixel to be decompressed from the compressed image;

i. directing the computer to determine a context for the pixel from previously decompressed pixels;

ii. directing the computer to use the context of a pixel in the decompressed image to determine a predicted value for the pixel;

iii. retrieving a Golomb code for the pixel from the compressed image;

iv. computing a Golomb parameter corresponding to a context-specific value N and a context-specific value A, where N is a count of pixels encountered in the context, and A is an accumulation of magnitudes of prediction residuals for pixels in the context;

v. decoding the Golomb code using the Golomb parameter, thereby producing a mapped value, M(ε

);

vi. mapping the mapped value M(ε

) to a residual value ε

vii. and adding the residual value ε

to the predicted value, thereby producing the decoded value for the pixel.

51. The method of claim 50, wherein the mapping M(ε

) is an alphabet of decodable events, the method further comprising the step of;

defining a first special context; and

when processing a pixel that occurs in the first special context, decoding using a Golomb code an event that is an extension of the alphabet of decodable events.

52. The method of claim 51 wherein the alphabet extension is a length of consecutive constant values.

53. The method of claim 52 wherein the consequtive constant values are consecutive constant prediction residuals, the method further comprising:

the step of ranking the lengths of consecutive constant prediction residuals by occurrence counts; and

for an occurrence of a length r of consecutive constant prediction residuals, decoding the length as a Golomb code for the rank of the length, i(r).

54. The method of claim 53 wherein the step of decoding the rank of the length i(r) as a Golomb code, further comprises the steps of:

determining a Golomb parameter k by executing instructions equivalent to the C statements;

space="preserve" listing-type="equation">for (k=0;

(N<

<

k)<

=A;

k++);

space="preserve" listing-type="equation">if (k≠

0)k--;

decoding the rank of the length i(r) as a first portion and as a second portion, said first portion being a binary representation of i(r) mod m and the second portion being a unary representation of .left brkt-bot.i(r)/m.right brkt-bot., where m=2_k.

55. The method of claim 52 further comprising the steps of:

definining a second special context;

when decoding a pixel immediately following the decoding of an event in the first special context;

decoding the pixel immediately following the decoding of an event in the first special context using a Golomb parameter obtained from values A and N for the second special context; and

updating the values A and N for the second special context.

56. The method of claim 55 wherein the constant values are constant pixel values;

and

a pixel occurring in the second special context is the first pixel following the decoding of a run of constant pixel values.

57. The method of claim 50, wherein the prediction residuals in an image have a distribution, and further comprising the step of:

cancelling biases in the distribution of prediction residuals in images being decompressed by adjusting the distribution of prediction residuals to a distribution matched to Golomb encoding and the mapping M(ε

).

58. A computer storage media having computer executable instructions for controlling the operation of a computer to compress digitized images, comprising:

instructions for causing said computer to, for each pixel in the image;

i. determine a context for the pixel;

ii. use the context of a pixel in the image to determine a predicted value for the pixel;

iii. compare the predicted value and the actual value, thereby producing a residual value ε

,

iv. map the residual value ε

to a mapped value M(ε

); and

v. compute a Golomb code corresponding to the residual from a context-specific value N and a context-specific value A, where N is a count of pixels encountered in the context, and A is an accumulation of magnitudes of prediction residuals for pixels in the context.

59. A computer storage media having computer executable instructions for controlling the operation of a computer to decompress compressed digitized images, comprising:

instructions for causing said computer to, for each encoded pixel in the compressed digitized image;

i. determine a context for the pixel;

ii. use the context of a pixel in the image to determine a predicted value for the pixel;

iii. retrieve a Golomb code from the compressed digitized image;

iv. determining a Golomb code parameter from the context using a context-specific value N and a context-specific value A, where N is a count of pixels encountered in the context, and A is an accumulation of magnitudes of prediction residuals for pixels in the context;

v. decoding the retrieved Golomb code using the Golomb code parameter, thereby obtaining a mapped prediction residual M(ε

);

vi. map M(ε

) to a prediction residual ε

; and

vii. add the prediction residual ε

to the predicted value, thereby producing a decompressed pixel value.