IEEE Geoscience and Remote Sensing Magazine - September 2014 - 21

Since the near-lossless compression paradigm above can
be applied to any predictor, it can also be used to design
a near-lossless version of the CCSDS-123 lossless compression algorithm leveraging the predictor described in Section II. The elements that need to be added to CCSDS-123
are the following.
◗◗ A scalar uniform quantizer with odd quantization
Q
step size that maps e i, j, k to e i, j, k, and the corresponding
Q
reconstruction function that maps e i, j, k to Ue i, j, k .
◗◗ All calculations of local sums and predictor values are
based on the past decoded samples Ux i, j, k and not the
original samples x i, j, k .
Q
◗◗ The weight update rule employs e i, j, k instead of e i, j, k
◗◗ Importantly, the entropy coder defined by CCSDS-123
has to be changed if one wants to achieve bit-rates below
1 bpppb. This is because the Golomb code encodes
one symbol at a time. Since the minimum length of a
Golomb codeword is one bit, the average length can not
be less than 1 bpppb. It is indeed possible to achieve bitrates below 1 bpp, but this requires some kind of block
coding, which can be as simple as a run-length encoder
to take advantages of long sequences of zeros, or a fullyfledged block coder such as an arithmetic or range
encoder. In the experiments provided in Section IV-C
the quantized residuals have been coded using a range
encoder, which has a better coding efficiency than a
Golomb code.
B. Generalization to varyinG
quality levels and rate control
Since near-lossless compression can indeed achieve a specific maximum absolute error on every individual pixel,
the question arises whether it has any interest at all to
make the maximum error a variable quantity D i, j, k, which
can be set to a different value for each pixel by selecting an
appropriate quantization step size d i, j, k . There are several
reasons why one may want to do so.
◗◗ In some applications, rather than setting a constant
maximum error for each pixel, it is of interest to bound
the maximum relative error. For example, in astronomy
it is often the case that the level of noise is proportional
to the signal level, so that a larger error may be tolerated
on the pixels with higher values, and vice versa.
◗◗ In some applications there could be areas of the image
which are more important to the scientists ("regions of
interest"), and pixels belonging to these regions could
be represented with a higher quality.
◗◗ By varying the quality in different areas of the image,
one could obtain the rate control functionality, or a
hybrid rate and quality control.
Achieving the first two functionalities is rather simple,
and is readily done via a proper selection of quantization
step sizes for each pixel to obtain the desired quality. This
is not difficult since in near-lossless compression quality
can be modulated in a natural way. On the other hand,
modulating the quality to obtain rate control is a more
SEPTEMBER 2014

ieee Geoscience and remote sensing magazine

involved issue, significantly more so than in the case of
transform coding. The main reason behind this is the following. In transform coding, one typically assumes that
the transform coefficients are statistically independent.
Therefore, the problem of choosing quantization step
sizes can be solved disregarding the interactions among
the different quantization choices applied to data units in
the transform domain. Unfortunately, the same cannot be
done for predictive coding. Because of the way the prediction mechanism works, a quantization choice on a given
pixel will affect the rate and quality of that pixel, but also
the rate of the subsequent pixels that are predicted from it.
In general, if we represent a pixel with very good quality
using an appropriately high bit-rate, then this pixel will
retain most of its correlation with the subsequent ones, so
that the predictor employing that pixel will yield a small
prediction error. Conversely, a pixel that is represented
coarsely will typically generate higher prediction error
values in the next pixels. The interaction between the ratedistortion choices for a pixel
and their effects on the next
pixels are difficult to model.
A neAr-lossless version
In [56] it is shown that the
of the CCsDs-123 lossless
problem can be solved by
Compression Algorithm
representing all sets of posCAn be DesigneD,
sible coding options as states
leverAging the
on a trellis, and then runpreDiCtor effiCienCy.
ning the Viterbi algorithm.
This approach, however, is
unfeasible in practice due to
its complexity.
Practical solutions must find an allocation of quantizers that is greedy, since not all the image data can be stored
in memory at the same time, and that has low complexity.
One possible solution would be to consider near-lossless
compression with a single maximum error T throughout
the image, and choose T so as to obtain the desired bit-rate,
as sweeping T from very low to very high values will yield
rate-distortion points from high quality to low quality. Incidentally, this solution is rather good in terms of quality, as
it can be shown to be optimal in minimax distortion sense
under a Gaussian assumption on the image pixels [57].
Although not necessarily optimal in MSE sense, this solution has the desirable property that the quality is balanced
throughout the image. In practice, however, this approach
is not viable. Indeed, there is only one parameter to be chosen for the whole image, and it has to be selected in a greedy
way without the possibility to perform adaptation to the
image content. This makes the process prone to large errors
in the rate control.
In [58] a solution to this problem has been proposed,
which adapts well to the multispectral and hyperspectral
imaging case, since it performs greedy allocation of quantizers so as to achieve the desired bit-rate. The purpose of
the algorithm is to control the output rate of a predictive
encoder of hyperspectral and multispectral images under
21

Table of Contents for the Digital Edition of IEEE Geoscience and Remote Sensing Magazine - September 2014