JPEG Entropy Coding2.42003/03/262006/06/15 10:14:06.479 GMT-5NickKingsburyngk10@cam.ac.ukNickKingsburyngk10@cam.ac.ukLiqunWangliqun@rice.eduCodingEntropyJPEGThis module gives a clever method of coding, JPEG entropy coding.
The entropy plots of the Quantisation of the DCT coefficients show the theoretical entropies
of each DCT sub-band. In practise this would be a poor way to code the
data because:
64 separate entropy codes would be required (each requiring many extra
states to represent run-length coding of zeros).
The statistics for each code are likely to vary significantly from
image to image.
To transmit the code table for each sub-band as header information
would involve a large coding overhead (many extra bits).
Coding the sub-bands separately does not take account of the
correlations which exist between the positions of the non-zero coefs
in one sub-band with those of nearby sub-bands (see
subfigures (c) and (d) from a previous module).
JPEG uses a clever alternative method of coding, based on combining
run-length and amplitude information into a single Huffman code for
the whole of the image (except the DC sub-band which is coded
separately because its statistics are so different).
The code is applied to each block of
88 quantised DCT coefs from a single
88 pel region. The blocks are the coefs before
reordering as shown in subfigure (b) of a previous module and comprise
one coef from each of the 64 sub-bands.
Each block of
88 quantised coefs is formed into a 1-D vector by zig-zag
scanning in the sequence:
0156141527282471316262942381217253041439111824314044531019233239455254202233384651556021343747505659613536484957586263The JPEG Code for DC coefs
The first coefficient (0) of each block (vector) is the DC coef, which
represents the mean value of the pels in the block (see the top left
basis function in subfigure (a) from previous discussion).
The DC coefs still exhibit significant local correlations (top
left of subfigure (b)), so differential coding is
used in which the value to be coded
is the difference between the current DC coef and
that of the previous block - the blocks are scanned from left to
right, row by row. The first block in each row is coded with respect
to zero.
The histogram of entropies of the DC coef differences is compared in
with that of the raw DC coefs
from this previous figure. We note the histogram peak around zero and see
that the entropy is reduced from 6.42 bits to 6.07 bits.
Histograms of the DC coefficients from the
88 DCT of Lenna, showing the entropy reduction with
differential coding.
The size of the differences can in theory be up to
±2558±2040 if the input pels occupy the range
-128 to
+127 (the DCT has a gain of 8 at very low
frequencies). Hence the Huffman code table would have to be
quite large. JPEG adopts a much smaller code by using a form
of floating-point representation, where
Size is the base-2 exponent and
Additional Bits are used to code the
polarity and precise amplitude as follows:
Only Size needs to be Huffman coded in the above scheme,
since, within a given Size, all the input values have
sufficiently similar probabilities for there to be little gain
from entropy coding the Additional Bits (hence they are coded
in simple binary as listed). Each coded Size is followed by
the appropriate number of Additional Bits (equal to Size) to
define the sign and magnitude of the coefficient difference
exactly.
There are only 12 Sizes to be Huffman coded, so specifying the
code table can be very simple and require relatively few bits
in the header.
In JPEG all Huffman code tables are defined in the image
header. Each table requires
16n bytes, where n is the
number of codewords in the table.
The first 16 bytes list the number of codewords of each length
from 1 to 16 bits (codewords longer than 16 bits are
forbidden). The remaining n
bytes list the decoded output values of the
n codewords in ascending
codeword order (
n256).
Hence
161228 bytes are needed to specify the code table for DC
coefficients.
The JPEG Run-Amplitude Code
The remaining 63 coefs (the AC coefs) of each 64-element
vector usually contain many zeros and so are coded with a
combined run-amplitude Huffman code.
The codeword represents the run-length of zeros before a
non-zero coef and the Size of that
coef. This is then followed by the Additional Bits which
define the coef amplitude and sign precisely. Size and
Additional Bits are defined just as for DC coefs.
This 2-dimensional Huffman code (Run, Size) is efficient
because there is a strong correlation between the Size of a
coef and the expected Run of zeros which precedes it - small
coefs usually follow long runs; larger coefs tend to follow
shorter runs. No single 2-D event is so probable that the
Huffman code becomes inefficient.
In order to keep the code table size
n below 256, only the following
Run and Size values are coded:
Run015Size110
These require 160 codes. Two extra codes, corresponding to
(Run,Size) = (0,0) and (15,0) are used for EOB (End-of-block)
and ZRL (Zero run length).
EOB is transmitted after the last non-zero coef in a
64-vector. It is the most efficient way of coding the final
run of zeros. It is omitted in the rare case that the final
element of the vector is non-zero.
ZRL is transmitted whenever
Run15, and represents a run of 16 zeros (15 zeros and a
zero amplitude coef) which can be part of a longer run of any
length. Hence a run of 20 zeros followed by -5 would be coded
as
When the code tables are defined in the image header, each
codeword is assigned to a given (Run,Size) pair by making the
decoded output byte Code Byte equal to (
16RunSize).
The default JPEG code for (Run,Size) of AC luminance DCT
coefficients is summarised below in order of decreasing code
probability:
As an example, let us code the following
88 block:
-13-32000106000000000000000-1000000000000000000000000000000000000000
Concerting this to (DC Size) or (Run,Size) and values for the
Additional Bits gives:
The compressed bitstream for this block is listed on the lower
line, assuming that the default Huffman code tables, given
above, are used.
shows the histogram of
probabilities for the (Run,Size) codewords used to code Lenna
using the
Qlum quantisation matrix. The bin number represents the
decoded byte value.
shows the equivalent
histogram when the quantisation matrix is
2Qlum.
Histogram of the (Run,Size) codewords for the DCT of Lenna,
quantised using
Qlum.
Histogram of the (Run,Size) codewords for the DCT of Lenna,
quantised using
2Qlum.
Note the strong similarity between these histograms, despite
the fact that
represents only
23 as many events. Only the EOB probability changes
significantly, because its probability goes up as the number
of events (non-zero coefs) per block goes down.
It turns out that the (Run,Size) histogram remains relatively
constant over a wide range of image material and across
different regions of each image. This is because of the strong
correlation between the run lengths and expected coef
sizes. The number of events per block varies considerably
depending on the local activity in the image, but the
probability distribution of those events (except for EOB)
changes much less.
and also give the mean bit rates
to code Lenna for the two quantisation matrices. Comparing
these with the theoretical entropies from this figure (lower row)
we get:
Q matrix
Mean Entropy (b/pel)
JPEG Bit Rate (b/pel)
JPEG efficiency
Qlum
0.8595
0.8709
98.7%
2Qlum
0.5551
0.5595
99.21%
Hence we see the high efficiency of the (Run,Size) code at two
quite different compression factors. This tends to apply over
a wide range of images and compression factors and is an
impressive achievement.
There is even very Little efficiency lost if a single code
table is used for many images, which can avoid the need to
transmit the
16n (168 bytes) of code definition in the header of each
image. Using the recommended JPEG default luminance tables
(Annex K.3.3) the above efficiencies drop to 97.35% and 95.74%
respectively.