Databases Reference
In-Depth Information
T A B L E 7 . 3
Comparison of the file sizes obtained
using the new and old JPEG lossless
compression standards and CALIC.
Image
Old JPEG
New JPEG
CALIC
Sena
31,055
27,339
26,433
Sensin
32,429
30,344
29,213
Earth
32,137
26,088
25,280
Omaha
48,818
50,765
48,249
may not be very impressive, we should keep in mind that we are picking the best result out
of eight for the old JPEG. In practice, this would mean trying all eight JPEG predictors and
picking the best. On the other hand, both CALIC and the new JPEG standard are single-
pass algorithms. Furthermore, because of the ability of both CALIC and the new standard
to function in multiple modes, both perform very well on compound documents, which may
contain images along with text.
7.5 Prediction Using Conditional Averages
Both of the predictive schemes we have looked at for lossless image coding obtain their pre-
dictive power from the fact that neighboring pixels tend to be alike. However, this assumption
is not necessary for developing a predictive scheme. A somewhat different idea is used in
schemes like
ppm
, which assume that a similar context will result in a similar value. To obtain
a prediction using this approach, one would try to find a pixel neighborhood similar to the
neighborhood of the pixel being encoded and use that pixel as a predictor for the pixel being
encoded. Using the labeling of Figure
7.1
, we look for a pixel in the history of the image
whose neighbors are the same as the neighbors of
X
in order to find the best predictor for pixel
X
. The value of that pixel can then be used as a predictor for the pixel
X
. We briefly describe
a scheme based on this idea [
89
,
90
], which we will call
conditional average prediction (cap)
.
This can be used in place of the initial predictor in JPEG-LS.
The
ppm
approach implicitly relies on the fact that textual information contains many exact
repeats. As this situation is not duplicated in natural images, the algorithm used in
ppm
cannot
be applied directly to the problem of generating predictions. Fortunately, while we do not have
exact repeats as in textual data, our objectives are also not the same. We are not looking for
an exact match, rather we are looking for a close value that can be used as a prediction.
In the
cap
approach, we define sets of pixels in the neighborhood to be the contexts for
which we will look for a match. For example, a context of size 4 consists of the
W, N W,
N,
and
NE
pixels, and a context of size 3 consists of the
W, N W,
and
N
pixels. In order to
generate a prediction, the encoder looks for matches to the context in the already encoded
portion of the image. A match can be defined rigidly, that is, each pixel in the context has to
be exactly matched, or it can be defined more loosely, that is, two pixels are said to be matched
if the absolute difference between pixel values is less than a threshold. To guard against the
possibility of a bad prediction, the algorithm requires that at least five matches be observed
