Method and device for digital data compression

Abstract

The invention relates to a method for compressing an input data set, wherein the coefficients in the input data set are grouped in groups of coefficients, a number of bit planes, GCLI, needed for representing each group is determined, a quantization is applied, keeping a limited number of bit planes, a prediction mechanism is applied to the GCLIs for obtaining residues, and an entropy encoding of the residues is performed. The entropy-encoded residues, and the bit planes kept allow the decoder to reconstruct the quantized data, at a minimal cost in meta-data.

Claims

1. A method for compressing an input data set into a corresponding compressed data set, the compressed data set comprising a magnitude compressed data set and a meta-data compressed data set, the method comprising: receiving the input data set, where the input data set comprises a sequence of M coefficients, each coefficient having m bits coding a magnitude between 0 and 2.sup.m−1; determining compression parameters; grouping the coefficients into one or more successive groups of n coefficients, a grouping factor n being greater than or equal to 2, each group of coefficients having m magnitude bit planes for different weights of the coefficients; for each group i of coefficients: determining a value of a Greatest Coded Line Index (GCLI), with GCLI.sub.1 being an index of a highest weight non-zero bit among bits of a magnitude of the coefficients in group i, the index being counted from 1 for a least significant bit to m for a most significant bit, the GCLI being zero for a group wherein all of the coefficients are equal to zero; performing a quantization such that quantized coefficients are in a range 0 to 2.sup.(m-t)−1, providing n quantized coefficients, t being a quantization level; if GCLI.sub.i≥t+1, for each bit plane of the group, then copying bit planes having weight 1 to weight GCLI.sub.i−t of the quantized coefficients to the magnitude compressed data set; computing a predictor, pred.sub.i, of GCLI.sub.i, in function of the GCLIs of one or more groups of antecedent coefficients in the sequence of coefficients, the predictor pred.sub.i being equal to pred_init, for a first group of coefficients of the sequence of coefficients; computing a residue r.sub.i according to
r.sub.i=max(GCLI.sub.i−t,0)−max(pred.sub.i−t,0); mapping the residue r.sub.1 to a code C; providing an entropy encoding of the code C; and copying the encoding into the meta-data compressed data set.

2. The method according to claim 1, wherein the entropy encoding is a Rice coding, with k=0, 1 or 2.

3. The method according to claim 1, wherein n is smaller than or equal to 8.

4. The method according to claim 1, wherein the quantization is performed by removing t lowest bit planes of the groups of coefficients.

5. The method according to claim 1, wherein the input data set is obtained by performing a decorrelative transform on a non-decorrelated input data set.

6. The method according to claim 1, wherein the sequence of M coefficients corresponds to: a sequence of pixels of one or more rows of a display image comprising rows and columns of pixels; or one or more rows of a subband of a decorrelative transform of a display image comprising rows and columns of pixels.

7. The method according claim 6, wherein when computing the predictor pred.sub.i of GCLI.sub.i when a prediction mode is vertical prediction mode, the predictor pred.sub.i is: the GCLI of a group of pixels in a same column of a previous row of pixels if the GCLI is larger than t, zero if the GCLI is smaller than or equal to t, or pred_init for the groups of pixels of the first row of pixels.

8. The method according to claim 7, wherein: the input data set comprises a first input data set having a quantization level t.sub.1, a second input data set having a quantization level t.sub.2, the last row of pixels of the first input data set being above the first row of pixels of the second input data set, in a display image, and a predictor for a group of pixels of a first row of pixels of the second input data set is equal to: a GCLI of a group of pixels of a last row of pixels in a same column of the first input data set if the GCLI>t.sub.1; and equal to zero if the GCLI≤t.sub.1.

9. The method according to claim 1, wherein when computing the predictor pred.sub.i of GCLI.sub.i when a prediction mode is horizontal prediction mode, the predictor pred.sub.i is: the GCLI of a previous group of coefficients in the sequence of coefficients, or pred_init for the first group of coefficients in the sequence of coefficients.

10. The method of claim 1, further comprising a decompression of the compressed data sets into decompressed data sets each comprising a sequence of coefficients, each coefficient having m bits coding a magnitude, wherein the decompression comprises: initializing a predictor pred.sub.i′ to pred_init; initializing a row of GCLIs prev.sub.i to pred_init if the prediction mode is vertical; extracting a code c.sub.i from the meta-data compressed data set; and iteratively, for each code and bit plane until all codes in the meta-data compressed data set have been processed: computing, if the prediction mode is vertical,
pred.sub.i′=prev.sub.i; obtaining a residue r.sub.i corresponding to the code c.sub.i from a table comprising values of r between r.sub.min and r.sub.max and corresponding values of code c; computing a number of bit planes n.sub.bp stored for a group corresponding to the code—according to
n.sub.bp=r.sub.i+pred.sub.i′; providing, if the number of bit planes n.sub.bp equals zero, a sequence of n m-bit words having all bit planes from t+1 to m at zero in the decompressed data set; providing, if the number of bit planes n.sub.bp is different from zero, a sequence of n m-bit words having t+1 to t+n.sub.bp bit planes extracted from subsequent n-bit bit planes from the magnitude compressed data set and having t+1+n.sub.bp to m bit planes equal to zero; replacing, if the prediction mode is horizontal, pred.sub.i′ by n.sub.bp; and replacing, if the prediction mode is vertical, prev.sub.i=n.sub.bp.

11. The method according to claim 10, further comprising, for the first row of the second data set, setting the predictor pred.sub.i′ to the corresponding value of prev.sub.i obtained for a last row of the first data set.

12. The method according to claim 1 wherein pred_init is equal to zero or equal to int(m/2).

13. The method according to claim 1, wherein the compression parameters comprise at least one of: a value of M; a value of m; a value of n; a value of t; a type of quantization; a mapping mode, being either negative-first or positive-first; a number of rows and a number of columns of a display image, if the input data set represents the display image; a number of rows of a subband, if the sequence of pixels is a decorrelative transform of the display image; a prediction mode, that is a horizontal or vertical prediction; a way initial values of predictors are determined; an entropy coding mode; a value of a parameter k of a Rice coding if the entropy coding mode is Rice coding; or a bounding mode being one of “bounded by min”, “bounded by min/max”, “bounded by max”, and “not bounded”.

14. The method according to claim 13, wherein the mapping is obtained by: computing a smallest value of the residues r.sub.min for all possible values of GCLI.sub.i, according to
r.sub.min=−max(pred.sub.1−t,0); computing a largest value of the residues r.sub.max for all possible values of GCLI.sub.i, according to
r.sub.max=max(m−max(pred.sub.i,t),0); computing
C.sub.first=−1 if the mapping mode is negative-first,
C.sub.first=+1 if the mapping mode is positive-first; computing
trigger=|r.sub.min| if a bounding mode is “bounded by min”;
trigger=MIN(|r.sub.min|,r.sub.max) if the bounding mode is “bounded by min/max”;
trigger=r.sub.max if the bounding mode is “bounded by max”;
trigger=m if the bounding mode is “not bounded”; and computing
C=2*|r.sub.i|−1 if |r.sub.i|<=trigger and r.sub.i*C.sub.first>0;
C=2*|r.sub.i| if |r.sub.i|<=trigger and ri*C.sub.first<0; and
C=trigger+|r.sub.i| if |r.sub.i|>trigger.

15. A compression system, comprising: a processor; and a memory device storing instructions executable by the processor to perform operations for compressing one or more input data sets into one or more corresponding compressed data sets, each compressed data set comprising a magnitude compressed data set and a meta-data compressed data set, the operations comprising: receiving one or more input data sets, each input data set comprising a sequence of M coefficients, each coefficient having m bits coding a magnitude between 0 and 2.sup.m−1; determining compression parameters; grouping the coefficients into one or more successive groups of n coefficients, a grouping factor n being greater than or equal to 2, each group of coefficients having m magnitude bit planes for different weights of the coefficients; for each group i of coefficients: determining a value of a Greatest Coded Line Index (GCLI), with GCLI being an index of a highest weight non-zero bit among bits of a magnitude of the coefficients in group i, the index being counted from 1 for a least significant bit to m for a most significant bit, the GCLI being zero for a group wherein all of the coefficients are equal to zero; performing a quantization such that quantized coefficients are in a range 0 to 2.sup.(m-t)−1, providing n quantized coefficients, t being a quantization level; if GCLI.sub.i≥t+1, for each bit plane of the group, copying bit planes having weight 1 to weight GCLI.sub.1−t of the quantized coefficients to the magnitude compressed data set; computing a predictor, pred.sub.i, of GCLI.sub.i, in function of the GCLIs of one or more groups of antecedent coefficients in the sequence of coefficients, the predictor pred.sub.i being equal to pred_init, for a first group of coefficients of the sequence of coefficients; computing a residue r.sub.i according to
r.sub.i=max(GCLI.sub.i−t,0)−max(pred.sub.i−t,0); mapping the residue r.sub.i to a code C; providing an entropy encoding of the code C; and copying the encoding into the meta-data compressed data set.

16. The system according to claim 15, wherein the compression parameters comprise at least one of: a value of M; a value of m; a value of n; a value of t; a type of quantization; a mapping mode, being either negative-first or positive-first; a number of rows and a number of columns of a display image, if the input data set represents the display image; a number of rows of a subband, if the sequence of pixels is a decorrelative transform of the display image; a prediction mode, that is a horizontal or vertical prediction; a way initial values of predictors are determined; an entropy coding mode; a value of a parameter k of a Rice coding if the entropy coding mode is Rice coding; or a bounding mode being one of “bounded by min”, “bounded by min/max”, “bounded by max”, and “not bounded”.

17. The method according to claim 16, wherein the mapping is obtained by: computing a smallest value of the residues r.sub.min for all possible values of GCLI.sub.i according to
r.sub.min=−max(pred.sub.1−t,0); computing a largest value of the residues r.sub.max for all possible values of GCLI.sub.i according to
r.sub.max=max(m−max(pred.sub.i,t),0); computing
C.sub.first=−1 if the mapping mode is negative-first,
C.sub.first=+1 if the mapping mode is positive-first; computing
trigger=|r.sub.min| if a bounding mode is “bounded by min”;
trigger=MIN(|r.sub.min|,r.sub.max) if the bounding mode is “bounded by min/max”;
trigger=r.sub.max if the bounding mode is “bounded by max”;
trigger=m if the bounding mode is “not bounded”; and computing
C=2*|r.sub.i|−1 if |r.sub.i|<=trigger and r.sub.i*C.sub.first>0;
C=2*|r.sub.i| if |r.sub.i|<=trigger and r.sub.i*C.sub.first<0; and
C=trigger+|r.sub.i| if |r.sub.i|>trigger.

18. The system according to claim 15, wherein the entropy encoding is a Rice coding, with k=0, 1 or 2.

19. The system according to claim 15, wherein n is smaller than or equal to 8.

20. A decompression system, comprising: a processor; and a memory device storing instructions executable by the processor to perform operations for decompressing a compressed data set into a decompressed data set, the operations comprising: receiving a meta-data compressed data set comprising a sequence of entropy encoded codes c.sub.i and a magnitude compressed data set comprising bit planes of coefficients; initializing a predictor pred.sub.i′ to pred_init; initializing a row of Greatest Coded Line Indexes (GCLIs) prev.sub.i to pred_init if a prediction mode is vertical; extracting a code c.sub.i from the meta-data compressed data set; and iteratively, for each code and bit plane until all codes in the meta-data compressed data set have been processed: computing, if the prediction mode is vertical,
pred.sub.i′=prev.sub.i; obtaining a residue r.sub.i corresponding to the code c.sub.i from a table comprising values of r between r.sub.in and r.sub.max and corresponding values of code c; computing a number of bit planes n.sub.bp stored for a group corresponding to the code according to
n.sub.bp=r.sub.i+pred.sub.i′; providing, if a number of bit planes n.sub.bp equals zero, a sequence of n m-bit words having all bit planes from t+1 to m at zero in the decompressed data set; providing, if the number of bit planes n.sub.bp is different from zero, a sequence of n m-bit words having t+1 to t+n.sub.bp bit planes extracted from subsequent n-bit bit planes from the magnitude compressed data set and having t+1+n.sub.bp to m bit planes equal to zero; replacing, if the prediction mode is horizontal, pred.sub.i′ by n.sub.bp; and replacing, if the prediction mode is vertical, prev.sub.i=n.sub.bp.

Description

SHORT DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a schematic representation of the data flow between a device for compression and a device for decompression of the invention;

(2) FIG. 2 is a represents schematically two input data sets and how the vertical prediction is performed at the boundary of the two data sets. the residue in function of the GCLI, without quantization.

(3) FIG. 3 is a graph representing the residue in function of the GCLI, without quantization.

(4) FIG. 4 is a graph representing the residue in function of the GCLI, with quantization.

(5) FIGS. 5 and 6 are graphs representing the mapping between the residues and the code, starting by mapping a negative value first and a positive value first, respectively, in a case where |r.sub.min| is smaller than r.sub.max.

(6) FIGS. 7 and 8 are graphs representing the mapping between the residues and the code, starting by mapping a negative value first and a positive value first, respectively, in a case where |r.sub.min| is larger than r.sub.max.

(7) FIG. 9 show the results obtained for different images and different embodiments of the invention.

(8) FIG. 10 contains Table I that is an example of a sequence of M=12 coefficients, each coefficient having m=15 magnitude bits, grouped in three groups of n=4 coefficients.

(9) The drawings of the figures are neither drawn to scale nor proportioned.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

(10) FIG. 1 is a schematic representation of the data flow between a device for compression and a device for decompression of the invention. The input dataset may comprise a sequence of M coefficients, each having m bits coding a magnitude. The input data set may represent a display image having a number of rows and columns, or a transformation of a display image, such as sub-bands of a wavelet transform of an image. The device for compression processes the input data set and produces a compressed data set. The compressed data set may comprise a magnitude compressed data set and a meta-data compressed data set. In addition, the device for compressing may produce a set of compression parameters. These compression parameters may comprise: M, the number of coefficients in the input data set; m, the number of bits in the magnitude of the coefficients of the input data set; n, the grouping factor; t, the quantization level; the type of quantization; the mapping mode, being either negative-first or positive-first; the number of rows and columns of a display image, if the input data set represents a display image; the number of rows, and the subband, if the sequence of pixels is a decorrelative transform of a display image; the prediction mode, which may be horizontal or vertical prediction; the initial predictor pred_init, used when no antecedent GCLI is available for determining a predictor; the way the initial values of the predictors are determined; the entropy coding mode; the value of the parameter k of the Rice coding if the entropy coding is a Rice coding; and the bounding mode, being one of bounded by min; bounded by min/max; bounded by max; not bounded.
These compression parameters are used by the device for compression and by the device for decompression. Some of these parameters may be communicated from the compression device to the decompression device, or be fixed and agreed upon beforehand between the compression and the decompression device. The device for decompression produces a decompressed data set similar to the input data set, but with some loss of quality due to the quantization.

(11) Table I shown in FIG. 10 is an example of a sequence of M=12 coefficients, each coefficient having m=15 magnitude bits, grouped in three groups of n=4 coefficients. For each group, the GCLI is represented, the GCLI being the Greatest Coded Line Index, i.e. the index of the highest weight non-zero bit among the bits of the magnitude of the coefficients in said group. A simple quantization, is represented, where the t=4 lowest bit planes of the coefficients are truncated, i.e. the quantization level t is 4.

(12) The GCLIs of the three successive groups are 8, 7 and 3. If one uses a prediction method and replaces the GCLIs by a residue, given by equation 1
r.sub.i=GCLI.sub.i−pred.sub.i  (equ. 1),
one obtains smaller values to be coded. In addition, when a quantization is performed, the residue n needed by the decompression device for decoding the data may be computed as
r.sub.i=max(GCLI.sub.i−t,0)−max(pred.sub.i−t,0)  (equ. 2)
The residue n according to equation 2 provides the necessary information to the decoder, while keeping the values to be coded as small as possible. Assuming that the predictor is taken as the previous GCLI in the sequence, (horizontal prediction) and that the GCLI of the group preceding the first one of the example is 7, the residues n are as follows:

(13) TABLE-US-00001 TABLE II GCLI 8 7 3 pred.sub.i 7 8 7 r.sub.i 1 −1 −3 n.sub.bp 4 3 0
As can be seen in this example, the residues n are smaller values. The number of bit planes to be transmitted, n.sub.bp i.e. the number of bit planes above the dashed line in table I is equal to GCLI-t when GCLI>t and equal to zero if GCLI≤t.

(14) Table III is an example showing the treatment of a sequence of coefficients grouped in seven groups producing seven GCLIs. The quantization level t is 6. At the encoder, an initial predictor for the first group is taken as pred_init=0. The subsequent predictors are taken as the GCLI of the previous group in the sequence GCLI.sub.i-1. This prediction mode applies in the general case, and when the input data set represents an image and horizontal prediction mode is used. The residues n are computed according to equation 2. The n.sub.bp bit planes are copied from the quantized coefficients to the magnitude compressed data set. The sequence of residues and bit planes are provided to the decoder.

(15) At the decoder, the initial predictor for the first group is taken in the same way as at the encoder (in the example, predi_init=0). The number of bit planes n.sub.bp is computed using equation 3.
n.sub.bp=r.sub.i+pred.sub.i′  (equ. 3)
The predictor for the subsequent group is taken as the n.sub.bp of the current group, which corresponds to the GCLI of the quantized coefficients. The GCLI′ of the decompressed data set coefficients may be obtained by adding t to the n.sub.bp values when they are not null, and keeping a zero value when they are null. As one can see these GCLI's are equal to the GCLIs if the input data set, if the GCLI of the input data set is larger than t, and are equal to zero if the GCLI≤t, since in that case all the coefficients bitplanes have been removed, yielding null coefficients at the decoder.

(16) TABLE-US-00002 TABLE III t = 6 at encoder i 1 2 3 4 5 6 7 GCLI.sub.i 7 4 5 10 8 9 6 pred.sub.i 0 7 4 5 10 8 9 r.sub.i 1 −1 0 4 −2 1 −3 n.sub.bp 1 0 0 4 2 3 0 at decoder r.sub.i 1 −1 0 4 −2 1 −3 pred.sub.i′ 0 1 0 0 4 2 3 n.sub.bp, i 1 0 0 4 2 3 0 GCLI.sub.i′ 7 0 0 10 8 9 0

(17) When the input data set corresponds to a sequence of pixels of one or more rows of a display image comprising rows and columns of pixels or one or more rows of a subband of a decorrelative transform of a display image comprising rows and columns of pixels, vertical prediction is possible. It has been observed that vertical prediction gives good results.

(18) Table IV shows an example similar to the example of table III, but applying vertical prediction. Row I of GCLIs is processed, taking into account previous row I−1. The predictor pred.sub.i is determined as follows:
IF GCLI.sub.i(I−1)≤t THEN pred.sub.i=0 ELSE pred.sub.i=GCLI.sub.i(I-1)
The residues are computed according to equation 2.
At the decoder, the set of GCLI's corresponding to the quantized coefficients of the previous row (row I−1) are kept in a buffer for use in processing row I. The predictor pred′.sub.i is computed with
pred′.sub.i=GCLI′.sub.i(I−1)  (equ. 4)
and the number of bit planes is computed according to equation 3. The GCLI's for the current row are equal to the number of bit planes n.sub.bp,i and stored for use by the subsequent row. For the first row of a data set, a row initialized to values pred_init is used.

(19) TABLE-US-00003 TABLE IV t = 6 at encoder i 1 2 3 4 5 6 7 GCLI.sub.i(I-1) 5 3 7 13 12 9 8 GCLI.sub.i(I) 7 4 5 10 8 9 6 pred.sub.i 0 0 7 13 12 9 8 r.sub.i 1 0 −1 −3 −4 0 −2 n.sub.bp, i 1 0 0 4 2 3 0 at decoder GCLI.sub.i′(I-1) 0 0 1 7 6 3 2 r.sub.i 1 0 −1 −3 −4 0 −2 pred.sub.i′ 0 0 1 7 6 3 2 n.sub.bp, i 1 0 0 4 2 3 0 GCLI.sub.i′(I) 1 0 0 4 2 3 0

(20) When the input data represents images and comprises two or more input data sets, and when the last row of a first data set is immediately above the first row of a second data set, these two data sets may be processed independently, with the initializations of the predictors for the first rows as discussed in the previous paragraph. However, in a preferred embodiment of the invention, the last row of the first data set may be used as predictor for the first row of the second data set. A special situation occurs when the quantization level t.sub.1 of the first data set is different from the quantization level t.sub.2 of the second data set. FIG. 2 represents a situation where a first data set is quantized with a quantization level t.sub.1. The last row of the first data set (row I−1) comprises a group 11 having a GCLI g.sub.1. The second data set 20 comprises a first row (row I) having a GCLI g.sub.2, immediately below the group of g.sub.1.

(21) Table V is an example where the first data set has a quantization level t.sub.1=10, the second data set has a quantization level t.sub.2=6.

(22) The differences with respect to the case of Table IV is that at the encoder, the predictor is determined as follows:
IF GCLI.sub.i(I−1)≤t.sub.1 THEN pred.sub.i=0 ELSE pred.sub.i=GCLI.sub.i(I−1)  (equ. 5)
where t.sub.1 is used instead of t. At the decoder, the predictor is taken from the prev.sub.i element of the last row of first data set.

(23) TABLE-US-00004 TABLE V t = 6 at encoder i 1 2 3 4 5 6 7 GCLI.sub.i(I-1) 5 3 7 13 12 9 8 GCLI.sub.i(I) 7 4 5 10 8 9 6 pred.sub.i 0 0 7 13 12 9 8 r.sub.i 1 0 −1 −3 −4 0 −2 n.sub.bp, i 1 0 0 4 2 3 0 at decoder GCLI.sub.i′(I-1) 0 0 1 7 6 3 2 r.sub.i 1 0 −1 −3 −4 0 −2 pred.sub.i′ 0 0 1 7 6 3 2 n.sub.bp, i 1 0 0 4 2 3 0 GCLI.sub.i′(I) 1 0 0 4 2 3 0

(24) FIG. 3 is a graph representing the residue in function of the GCLI, given by equation 1, without quantization, for two values of the predictor pred=2 and pred=8. The number of possible values of the residue is equal to the number of values of the GCLI. If the predictor is a good predictor, the residue is near or equal to zero.

(25) FIG. 4 is a graph representing the residue in function of the possible values of GCLI between 0 and 15 (or, more generally, m), with quantization, the quantization level t being equal to 4, as given by equation 2. For pred=8, the residue has a lower bound r.sub.min equal to −4. For pred=2, the residue has a lower bound r.sub.min equal to 0. The upper bounds r.sub.max are the same as the ones on FIG. 3, r.sub.max=13. A graph for the case t=1, pred=8 has also been represented. The lowed bound r.sub.min is zero and the upper bound r.sub.max is 5. The general expressions of the lower bounds r.sub.min and upper bounds r.sub.max of the residues are given by equations
r.sub.min=−max(pred.sub.i−t,0)  (equ. 6)
and
r.sub.max=max(m−max(pred.sub.i,t),0)  (equ. 7)
The range of values of the residues after quantization, is reduced with respect to the range of values without quantization.

(26) According to the invention, the values of the residues may be mapped to non-negative integers C. This is illustrated on FIGS. 5, 6, 7 and 8. The residues between r.sub.min and r.sub.max may be mapped to a range of non-negative integers by mapping the value r=0, to C=0, and then mapping r=−1 to C=1, r=1 to C=2, r=−2 to C=3, etc. This is represented by the square markers FIGS. 5 to 8. In FIGS. 5 and 7, the negative value r=−1 is first mapped to C=1 (negative-first mapping). In FIGS. 6 and 8, the positive value r=1 is first mapped to C=1 (positive-first mapping). FIGS. 5 and 6 are graphs representing the situation where m=15, pred=8, and t=4. The value of r.sub.max is larger than the absolute value of r.sub.min. The possible value of GCLI are in the range 0 to 15. In this way, the most probable values of r, i.e. values or r around zero, are mapped to the smallest values of C. C may then be coded efficiently as discussed below. FIGS. 7 and 8 are graphs representing the situation where m=15, pred=12, and t=2.

(27) According to a preferred embodiment of the invention, the mapping of the residues to a non-negative integer C may be improved by taking into account that when r.sub.max is larger than |r.sub.min| the range of values of C may be reduced by mapping the residues above r.sub.min to successive values of C (and not stepping by 2). This is referred to as the “Bounded C” method and represented on FIG. 5 and FIG. 6 by the round markers. The value of C reaches a maximum of 11, instead of a maximum of 14, for the negative-first case (FIG. 5) and instead of a maximum of 13 for the positive-first case (FIG. 6). Similar results may be obtained when r.sub.max is smaller than |r.sub.min|, as illustrated by the round markers on FIGS. 7 and 8: The value of C reaches a maximum of 13, instead of a maximum of 19, for the negative-first case (FIG. 7) and instead of a maximum of 20 for the positive-first case (FIG. 8). Therefore, the maximum value of C is bounded with respect to the value of C without the “Bounded C” method.

(28) In the option “bounded by min”, the values of the codes C for the residues comprised between trigger and r.sub.max, if any, are smaller than without the “Bounded C” method.

(29) In the option “bounded by max”, the values of the codes C for the residues comprised between −trigger and r.sub.min, if any, are smaller than without the “Bounded C” method.

(30) In the option “bounded by min/max”, the values of the codes C for the residues comprised between −trigger and r.sub.min, if any, and the residues comprised between trigger and r.sub.max, if any, are smaller than without the “Bounded C” method.

(31) The codes C corresponding to a range of residues, according to the negative-first or the positive-first mapping mode, may be obtained by performing the following steps of the mapping algorithm:

(32) We first define the two following parameters:

(33) C.sub.first=−1 if negative-first, +1 if positive-first

(34) When using the “Bounded C” improvement of the invention, a bounding mode is selected, being one of bounded by min; bounded by min/max; bounded by max; not bounded.
A trigger is determined as follows:
trigger=|r.sub.min| if bounded by min,
trigger=MIN(|r.sub.min|,r.sub.max) if bounded by min/max,
trigger=r.sub.max if bounded by max.
trigger=m if not bounded.
The code C can then be computed by performing the following steps:

(35) TABLE-US-00005 IF |r| <= trigger THEN IF r*C.sub.first > 0 THEN C = 2*|r| − 1 ELSE C = 2*|r| ELSE C = trigger + |r|
The option “negative-first” is more interesting since it ensures shorter codes for all values below the predictor, which includes all the values that have been removed by quantization. This is shown in FIG. 9, in which the relative advantage of “negative-first” methods is clearly superior to “positive-first” methods.
The bounding mode “bounded by min/max” does not offer a significant advantage over the bounding mode “bounded by min” bonding method, and thus the method may safely be simplified should its implementation offer a gain by not taking r.sub.max into account.
Also, the mapping may be obtained from predetermined lookup tables. The inverse mapping is bijective and thus its inverse may be performed at de the decoder.
Table VI below provides an example of eight successive GCLI's from 1 to 8, for groups of coefficients, coded in m=15 bits. The quantization level is t=4. The initial predictor, for i=1, has been selected as int(m/2), i.e. 7. For each subsequent GCLI, the predictor has been determined as being the previous GCLI. For each successive GCLIs, the residues n have been computed according to equation 2, and the r.sub.min and r.sub.max, have been determined according to equations 6 and 7 respectively. The values of the triggers, according to the different options, have been computed for each GCLI. In the last line, the code C has been in the option “bounded by min”, and negative first. Each GCLI is processed independently of the other GCLIs in the input data set, in dependence of the predictor pred.sub.i of the current GCLI.

(36) TABLE-US-00006 TABLE VI 1 2 3 4 5 6 7 8 i GCLI.sub.i 4 3 8 12 5 4 7 4 pred.sub.i 7 4 3 8 12 5 4 7 r.sub.i −3 0 4 4 −7 −1 3 −3 r.sub.min −3 0 0 −4 −8 −1 0 −3 r.sub.max 8 11 11 7 3 10 11 8 Triggers, bounded by min 3 0 0 4 8 1 0 3 min/max 3 0 0 4 3 1 0 3 max 8 11 11 7 3 10 11 8 not bounded 15 15 15 15 15 15 15 15 C 5 0 4 8 13 1 3 5
Table VII gives the number of bits required for coding the 8 codes C according to the different bounding modes and mapping modes.

(37) TABLE-US-00007 TABLE VII bounding Negative Positive mode first first min 47 50 min/max 44 46 max 51 51 not bound 54 55
The bold value corresponds to the example shown in table VI. It can be seen that negative first give better results. The “bounded by min/max” bounding mode gives the better results, but the “bounded by min” are also good.

(38) The information that is prepared at the encoder, i.e. the bitplanes and the codes C coding the residues are such that the decoder can from the received codes C, and a reconstructed predictor, determine the number of bit planes n.sub.bp to be extracted from the magnitude compressed data set for reconstruction the original quantized data set. The trigger used at the encoder for coding the residue is not needed at the decoder and not transmitted in the meta-data compressed data set.

(39) The decoder receives a value of C and has a value of pred, from the previous step or from pred_init. From these two values, the decoder can compute r.sub.min and r.sub.max, according to equations 6 and 7 respectively. Having a knowledge of the mapping mode and the bounding mode, the decoder computes the trigger. The decoder then may compute the code C corresponding to all values of r between r.sub.min and r.sub.max, according to the above steps of the mapping algorithm. This produces a table giving the correspondence between the values of r between r.sub.min and r.sub.max, and corresponding values of C. The decoder then obtains the value of r as the value corresponding to C in this table.
In an example of table VIII, a code C=5 has been received, with a predictor equal to 7, and a quantization level t=4. The values of r.sub.min and r.sub.max can be computed and a table for all possible residues between r.sub.min and r.sub.max built. The code C for each of these 11 values of r is computed and inserted in the table. The value of the received code C=5 is then search in the table for finding the corresponding value of r, r=−3. Other equivalent methods for performing the decoding of the codes C, such as a (binary) search in the table, or a formula.

(40) TABLE-US-00008 TABLE VIII r.sub.i C r.sub.max 8 11 7 10 6 9 5 8 4 7 3 6 2 4 1 2 0 0 −1 1 −2 3 r.sub.min −3 5

(41) The codes C obtained for the residues in the method of the invention are non-negative integers. If the predictor is an accurate predictor, the residues will be small values. An entropy coding is used for coding C in the meta-data. A preferred entropy coding for C is the Rice coding. Rice coding of a non-negative integer N in dependence of parameter k is as follows: one divides N by 2.sup.k and the resulting quotient is unary coded; the remainder of the division is binary coded in k bits.
Example values for N between 0 and 10, and k=0, 1 and 2 are given in the table below:

(42) TABLE-US-00009 Rice code Rice code Rice code N Binary code k = 0 k = 1 k = 2 0 0 0    0 0  0 00 1 1 10    0 1  0 01 2 10 110   10 0  0 10 3 11 1110   10 1  0 11 4 100 11110   110 0  10 00 5 101 111110   110 1  10 01 6 110 1111110  1110 0  10 10 7 111 11111110  1110 1  10 11 8 1000 111111110  11110 0 110 00 9 1001 1111111110  11110 1 110 01 10 1010 11111111110 111110 0 110 10
With k=0, the length of the code, for N=0, is one bit. Therefore, the value k=0 is the preferred value for the method of the invention, when the prediction is accurate, and the value 0 is frequent among the residuals to be coded. However, if the accuracy of the prediction is not perfect, larger values of N might occur, and a larger value of k, such a as k=1 or 2, where larger values of N require less bits, may be optimal. Rice coding is a prefix code. Therefore, no code in the set of possible codes is a prefix of another code in the set of possible codes. No special markers are needed between the codes, and the decoder can unambiguously extract successive codes from the meta-data compressed data set.

(43) The quantization step applies the set of 2.sup.m values of the magnitudes of the coefficients, between 0 and 2.sup.m−1, to a set of 2.sup.m-t values between 0 and 2.sup.(m-t)−1. A simple way to perform this quantization is by removing the t lowest-weight bits of the unquantized coefficients. However, other quantization methods may be used in the invention.

(44) FIG. 9 show the results obtained for different images and different embodiments of the invention. For each of 16 test images, the bar graphs show the PSNR (Peak Signal to Noise Ratio) with respect to a method where the encoding of the invention is not used, but where residues are coded using unary encoding, such as in document SMPTE RDD 35:2016. The bar graphs represent successively the case where only the |r.sub.min| bound is used, with the negative-first mapping mode (min_neg1st); the case where only the |r.sub.min| bound is used, with the positive-first mapping mode (min_pos1st); the case where both |r.sub.min| and r.sub.max bounds are used, with the negative-first mapping mode (minmax_neg1st); the case where both |r.sub.min| and r.sub.max bounds are used, with the positive-first mapping mode (minmax_pos1st). the case where neither |.sub.min| nor r.sub.max bounds are used, with the negative-first mapping mode (no_minmax).
These results show that using both |r.sub.min| and r.sub.max bounds provides a very small improvement with respect to using only the |r.sub.min| bound. In both cases using the negative-first mapping mode is significantly better than using the positive-first mapping mode.

(45) The present description addresses the processing of the magnitudes of the coefficients. The methods apply to unsigned coefficients. The methods apply as well when the input data comprise signed coefficients. These signed coefficients may be coded as sign+magnitude or transformed to sign+magnitude format. The sign bits of the coefficients of a group are grouped as a sign bit plane, and the sign bit plane is processed along with the magnitude bit planes. The invention relates to a method for compressing an input data set, wherein the coefficients in the input data set are grouped in groups of coefficients, a number of bit planes, GCLI, needed for representing each group is determined, a quantization is applied, keeping a limited number of bit planes, a prediction mechanism is applied to the GCLIs for obtaining residues, and an entropy encoding of the residues is performed. The entropy-encoded residues, and the bit planes kept allow the decoder to reconstruct the quantized data, at a minimal cost in meta-data.