Adaptive graylevel image compression system

• US 4,725,885 A
• Filed: 12/22/1986
• Issued: 02/16/1988
• Est. Priority Date: 12/22/1986
• Status: Expired due to Fees

• Current Assignee: Lenovo Singapore Pte Limited (Lenovo Group Ltd.)
• Original Assignee: International Business Machines Corporation
• Inventors: Mitchell, Joan L., Gonzales, Cesar A., Pennebaker, William B.
• Primary Examiner(s): Britton, Howard W.
• Application Number:
  US06/946,542
• Time in Patent Office: 421 Days
• Field of Search: 358/135, 358/133, 358/136, 358/13, 375/27, 375/122
• US Class Current: 375/240.14
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/50 using predictive coding H04N19/61 takes precedence
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques

Abstract

Apparatus and method for modelling differential pulse code modulation (DPCM) input data for entropy coding. In particular, the sign and magnitude of one piece of DPCM data after another are modelled to provide a magnitude state input and a sign state input to provide context for DPCM magnitude input and DPCM sign input, respectively, to an entropy encoder or decoder. That is, the DPCM magnitudes of earlier pieces of (context) DPCM magnitude data are re-mapped for each such earlier piece of data, the re-mapped data being aggregated to form a combined value indicative of the magnitude state input. Similarly, the DPCM signs of earlier pieces of (context) DPCM sign data are re-mapped for each such earlier piece of data, the re-mapped data being aggregated to form a combined value indicative of the sign state input. In an image data compression system, the magnitude state input serves as an activity indicator for picture elements (pixels) neighboring a "subject" pixel. According to the invention, the DPCM signal is derived from a difference value calculated by subtracting one of a plurality of predictor values from the graylevel value X of the subject pixel. The selection of predictor value P is based on the value of the magnitude state (activity indicator). In addition, the difference value is subject to adaptive quantization in which one of a plurality of quantizers is employed in assigning the (X-P) difference value to a quantization level. The selection of quantizers is also based on the value of the magnitude state (activity indicator).

Claims

1. A differential pulse code modulation (DPCM) data compression system in which a predicted value P is subtracted from an input signal value X to provide a difference signal value which is to be quantized, the system comprising:

a plurality of selectable quantizers for quantizing a difference signal input;

a plurality of selectable predictor calculators;

entropy encoder means for producing code outputs in response to decision inputs and state inputs, the state inputs providing a context for the decision inputs received;

activity indicator means for indicating the level of input signal activity based on quantized difference history;

first selector means, which receives the output of the activity indicator means as input, for selecting one of the quantizers based on the activity indicator output; and

second selector means, which receives the output of the activity indicator means as input, for selecting as the predictor P the output of one of the predictor calculators based on the activity indicator output;

wherein said entropy encoding means receives the output of the activity indicator means as a state input thereto.

2. The system of claim 1 wherein the system is an image processing system in which an input signal corresponds to the value for a subject pixel and wherein said activity indicator means is based on values of prescribed pixels neighboring the subject pixel, said activity indicator means including:

(a) means for re-mapping quantized difference values to a reduced set of values;

(b) means for assigning re-mapped values to prescribed neighboring pixels which have previously determined quantized difference values; and

(c) aggregating means for combining the re-mapped values of the prescribed neighboring pixels to provide a state value;

the state value being received by the entropy encoding means as a magnitude state input.

3. The system of claim 1 further comprising:

means for assigning a sign value to each possible quantized difference value; and

means for computing a sign state value for a subject pixel based on the sign values for prescribed neighboring pixels for which sign values have been previously determined;

wherein said entropy encoder means includes means for alternately receiving as input (i) the difference signal sign and the sign state value for entropy encoding the DPCM sign or (ii) the difference signal magnitude and the output of the activity indicator means for entropy encoding the DPCM magnitude.

4. The system of claim 3 further comprising:

decoder means for retrieving the graylevel value of the subject pixel from (i) the entropy encoded DPCM magnitude and (ii) the entropy encoded DPCM sign; and

means for conveying the entropy encoded DPCM magnitude and DPCM sign for one subject pixel after another from said encoder means to said decoder means.

5. In a data compression system including an entropy encoder which encodes decision inputs in a context defined by a corresponding state input, a machine-implemented method of modelling differential pulse code modulation (DPCM) image data for entropy coding comprising the steps of:

(a) for a subject pixel, evaluating a predictor value P;

(b) subtracting P from a graylevel value X for the subject pixel to provide a difference value;

(c) quantizing a DPCM signal having a sign and a magnitude from the difference value;

(d) modelling the DPCM signal sign to provide a sign state input to the entropy encoder;

(e) modelling the DPCM signal magnitude to provide a magnitude state input to the entropy encoder;

(f) the entropy encoder encoding the DPCM signal sign in the context defined by the sign state input; and

(g) the entropy encoder encoding the DPCM signal magnitude in the context defined by the magnitude state input.

6. The method of claim 5 wherein the entropy encoder and decoder process binary decision data, the method comprising the further step of:

(u) correlating each quantization level with a corresponding binary sequence according to a binary decision tree.

7. The method of claim 5 further comprising the steps of:

(v) entropy encoding the DPCM decision data according to the context thereof; and

(w) decoding the graylevel value of the subject pixel from (i) the entropy encoded DPCM magnitude and (ii) the entropy encoded DPCM sign.

8. The method of claim 5 further comprising the step of:

(x) repeating steps (a) through (g) for one pixel after another in an image.

9. The method of claim 5 further comprising the steps of:

(y) for the subject pixel, calculating a plurality of alternate predictors;

(z) selecting one of the calculated predictors based on the magnitude state input for the subject pixel provided in step (d); and

(aa) repeating steps (a) through (g), (y), and (z) for one pixel after another in an image;

wherein step (c) includes the steps of;

(aa) storing a plurality of quantization tables, each table providing a quantized value for each possible difference value; and

(bb) selecting one of the quantization tables wherein the selection is based on the magnitude state input for the subject pixel provided in step (d).

10. The method of claim 5 wherein step (a) includes the steps of:

(h) for the subject pixel, calculating a plurality of alternate predictors; and

(j) selecting one of the calculated predictors based on the magnitude state input for the subject pixel provided in step (e).

11. The method of claim 10 wherein step (c) includes the steps of:

(k) storing a plurality of quantization tables, each table providing a quantized value for each possible difference value; and

(l) selecting one of the quantization tables wherein the selection is based on the magnitude state input for the subject pixel provided in step (e).

12. The method of claim 5 wherein the subject pixel has neighboring pixels A, B, C, and D in which (i) pixel A is adjacent to and along the scan line of the subject pixel, and (ii) pixels B, C, and D are adjacent to the subject pixel and are positioned along a previous scan line, wherein step (d) includes the steps of:

(r) identifying each neighboring pixel as having a sign value assigned thereto according to the representations;

000 for no sign;

010 for weak plus sign;

001 for weak minus sign;

110 for strong plus sign; and

101 for strong minus sign;

(s) ORing the sign value representations of pixels A, B, C, and D; and

(t) appending the result of the ORing to the sign value representation of one of the pixels adjacent to the subject pixel to provide a 6-bit sign state input for the subject pixel.

13. The method of claim 12 wherein pixel A is to the left of the subject pixel, pixel B is to the upper left diagonal of the subject pixel, pixel C is directly up from the subject pixel, and pixel D is to the upper right diagonal of the subject pixel.

14. The method of claim 5 wherein the subject pixel has neighboring pixels A, B, C, and D in which (i) pixel A is adjacent to and along the scan line of the subject pixel, and (ii) pixels B, C, and D are adjacent to the subject pixel and are positioned along a previous scan line, wherein step (e) includes the step of:

(m) assigning each quantization level of 2α

possible quantization levels to one of λ

re-mapped binary values in which the bits set for a binary value depend on the magnitude of the quantization levels assigned thereto, where α

is an integer and where λ

<

2α

.

15. The method of claim 14 wherein step (e) further includes the steps of:

(n) for each pixel A, B, C, and D neighboring the subject pixel, each of which has a respective predetermined quantized value, re-mapping the quantized values of the neighboring pixels as MMA, MMB, MMC, and MMD, respectively, wherein the re-mapped values are 4-bits in length and wherein re-mapped values corresponding to larger quantization levels have more consecutive set bits starting at the least significant bit then re-mapped values corresponding to smaller quantization levels;

(p) ORing the assigned re-mapped values for pixels A, B, C, and D to obtain a value Mmax; and

(q) determining a magnitude state value according to the following conditions;

if Mmax=0000, setting the value to 0;

if Mmax=0001, setting the state value to 1;

if Mmax=0011, setting the state value to 2;

if Mmax=0111, setting the state value to 3;

or

if Mmax=1111, setting the state value to 4.

16. The method of claim 15 wherein pixel A is to the left of the subject pixel, pixel B is to the upper left diagonal of the subject pixel, pixel C is directly up from the subject pixel, and pixel D is to the upper right diagonal of the subject pixel.