Databases Reference
In-Depth Information
1
2
5
7
2
−
2
0
−
5
−
3
−
1
1
−
2
−
7
−
4
−
2
1
3
4
If we consider this sample to be fairly typical of the sequence, we can see that the probability
of any given number being in the range from
7 to 7 is about the same. If we were to encode
this sequence using a Huffman or arithmetic code, we would use almost 4 bits per symbol.
Instead of encoding this sequence directly, we could do the following: add two to the
previous number in the sequence and send the difference between the current element in the
sequence and this
predicted
value. The transmitted sequence would be
−
1
−
1
1
0
−
7
−
4
0
−
7
0
0
0
−
5
−
7
1
0
1
0
−
1
This method uses a rule (add two) and the history (value of the previous symbol) to generate
the new sequence. If the rule by which this
residual sequence
was generated is known to the
decoder, it can recover the original sequence from the residual sequence. The length of the
residual sequence is the same as the original sequence. However, notice that the residual
sequence is much more likely to contain 0s, 1s, and
−
1s than other values. That is, the
−
probability of 0, 1, and
1 will be significantly higher than the probabilities of other numbers.
This, in turn, means that the entropy of the residual sequence will be low, and, therefore, the
residual sequence can be encoded using fewer bits.
We used a particular method of prediction in this example (add two to the previous element
of the sequence) that was specific to this sequence. In order to get the best possible performance,
we need to find the prediction approach that is best suited to the particular data we are dealing
with. We will look at several prediction schemes used for lossless image compression in the
following sections.
7.2.1 The Old JPEG Standard
The Joint Photographic Experts Group (JPEG) is a joint International Standards Organization/
International TelecommunicationUnion (ISO/ITU) committee responsible for developing stan-
dards for continuous-tone still-picture coding. The more famous standard produced by this
group is the lossy image compression standard. However, at the time of the creation of the
famous JPEG standard, the committee also created a lossless standard [
82
]. It is more or less
obsolete, having been overtaken by the much more efficient JPEG-LS standard described later
in this chapter. However, the old JPEG standard is still useful as a first step into examining
predictive coding in images.
The old JPEG lossless still compression standard [
82
] provides eight different predictive
schemes from which the user can select. The first scheme makes no prediction. The next
seven are listed below. Three of the seven are one-dimensional predictors, and four are two-
dimensional prediction schemes. Here,
I
(
i
,
j
)
is the
(
i
,
j
)
th pixel of the original image, and
I
(
i
,
j
)
is the predicted value for the
(
i
,
j
)
th pixel.
