Entropy of source information was discussed in the third-year E5
Information and Coding course. For an image
xx, quantised to
MM levels, the entropy
Hx
Hx
is defined as:
Hx=∑i=0M-1pilog21pi=-∑i=0M-1pilog2pi
Hx
i
0
M
1
pi
2
1
pi
i
0
M
1
pi
2
pi
(1)
where
pi
pi
,
i=0
i
0
to
M-1
M
1
, is the probability of the
ith
ith
quantiser level being used (often obtained from a
histogram of the pel intensities).
Hx
Hx
represents the mean number of bits per pel with which
the quantised image xx can be
represented using an ideal variable-length entropy code. A
Huffman code usually approximates this bit-rate quite closely.
To obtain the number of bits to code an image (or subimage)
xx containing
NN pels:
-
A histogram of xx is measured
using MM bins corresponding to
the MM quantiser levels.
-
The MM histogram counts are
each divided by NN to give the
probabilities
pi
pi
, which are then converted into entropies
hi=-pilog2pi
hi
pi
2
pi
. This conversion law is illustrated in Figure 1 and shows that probabilities
close to zero or one produce low entropy and intermediate
values produce entropies near 0.5.
-
The entropies
hi
hi
of the separate quantiser levels are summed to
give the total entropy
Hx
Hx
for the subimage.
-
Multiplying
Hx
Hx
by NN gives the
estimated total number of bits needed to code
xx, assuming an ideal entropy
code is available which is matched to the histogram of
xx.
Figure 2 shows the probabilities
pi
pi
and entropies
hi
hi
for the original Lenna image and Figure 3 shows these for each of the
subimages in this previous figure, assuming a uniform quantiser with a step-size
Qstep=15
Qstep
15
in each case. The original Lenna image contained pel
values from 3 to 238 and a mean level of 120 was subtracted from
each pel value before the image was analysed or transformed in
order that all samples would be approximately evenly distributed
about zero (a natural feature of highpass subimages).
The Haar transform preserves energy and so the expected
distortion energy from quantising the transformed image
yy with a given step size
Qstep
Qstep
will be approximately the same as that from quantising
the input image xx with the same
step size. This is because quantising errors can usually be
modeled as independent random processes with variance (energy)
=
Qstep212
Qstep
2
12
and the total squared quantising error (distortion)
will tend to the sum of the variances over all pels. This
applies whether the error energies are summed before or after
the inverse transform (reconstruction) in the decoder.
Hence equal quantiser step sizes before and after an
energy-preserving transformation should generate equivalent
quantising distortions and provide a fair estimate of the
compression achieved by the transformation.
The first two columns of Figure 4
(original and level 1) compare the entropy (mean bit rate) per
pel for the original image (3.71 bit / pel) with that of the
Haar transformed image of this previous figure (2.08 bit /
pel), using
Qstep=15
Qstep
15
. Notice that the entropy of the original image is
almost as great as the 4 bit / pel that would be needed to code
the 16 levels using a simple fixed-length code, because the
histogram is relatively uniform.
The level 1 column of Figure 4
shows the contribution of each of the subimages of this previous figure to the total
entropy per pel (the entropies from Figure 3 have been divided by 4 since each subimage has
one quarter of the total number of pels). the Lo-Lo subimage
contributes 56% to the total entropy (bit rate) and has similar
spatial correlations to the original image. Hence it is a
logical step to apply the Haar transform again to this subimage.
