mskuhn@immd4.informatik.uni-erlangen.de (Markus Kuhn) (06/12/91)
In Communications of the ACM, April 1991, p.31-44, Gregory K. Wallace
writes the following about the lossless coding in JPEG:
Processing Steps for Predictive Lossless Coding
After its selection of a DCT-based method in 1988, JPEG discovered that
a DCT-based lossless mode was difficult to define as a practical standard
against which encoders and decoders could be independently implemented,
without placing severe constraints on both encoder and decoder implementations.
JPEG, to meet its requirement for a lossless mode of operation, has chosen
a simple predictive method which is wholly independent of the DCT processing
described previously. Although not the result of rigorous competitive
evaluation as was the DCT-based method, the predictive method produces
results which, in light of its simplicity, are close to the state of the art
for lossless continuous-tone compression.
Table 1. Figure 5.
Predictors for lossless coding 3-Sample Prediction Neighborhood
selection C B
value prediction A X
0 no prediction Figure 4.
1 A
2 B Source Image Data
3 C V
4 A+B-C Predictor
5 A+((B-C)/2) V
6 B+((A-C)/2) Entropy Encoder <- Table Specification
7 (A+B)/2 V
Compressed Image Data
Figure 4 shows the main processing steps for a single-component image. A
predictor combines the values of up to three neighboring samples (A, B and C)
to form a prediction of the sample indicated by X in Figure 5. This prediction
is then substracted from the actual value of sample X, and the difference
is encoded losslessly by either of the entropy coding methods -- Huffman or
arithmetic. Any of the eight predictors listed in Table 1 (under "selection-
value") can be used.
Selections 1, 2 and 3 are onedimensional predictors and selections 4, 5, 6
and 7 are two-dimensional predictors. Selection-value 0 can only be used for
differential coding in the hierarchical mode of operation. The entropy coding
is nearly identical to that used for the DC coefficient as described later
(for Huffman coding).
For the lossless mode of operation, two different codecs are specified --
one for each entropy coding method. The encoders can use any source image
precision from 2 to 16 bits/sample, and can use any of the predictors except
selection-value 0. The decoders must handle any of the sample precisions and
any of the predictors.
Lossless codecs typically produce around 2:1 compression for color images
with moderately complex scenes.
[...]
---------8<------cut here-------8<------------
The complete article should be read by everyone interessted in JPEG, MPEG, ...
It contains also a list with several compression ratios for baseline JPEG:
0.25-0.5 bits/pixel: moderate to good quality, sufficient for some
applications.
0.5 -0.75 good to very good quality, sufficient for many
applications.
0.75-1.5 excellent quality, sufficient for most applications
1.5 -2.0 usually indistinguishable from the original, sufficient
for the most demanding applications.
One pixel here means of course a color pixel!
The standard that describes all this is ISO 10918 (committe draft).
The text above is of course copyrighted by ACM.
Have fun ...
Markus
---
Markus Kuhn, Computer Science student -- University of Erlangen, Germany
X.400: G=Markus;S=Kuhn;OU1=rrze;OU2=cnve;P=uni-erlangen;A=dbp;C=de
I'net: mskuhn@immd4.informatik.uni-erlangen.de