The 2-dimensional DCT2.32003/03/262003/05/02NickKingsburyngk10@cam.ac.ukLiqunWangliqun@rice.eduNickKingsburyngk10@cam.ac.uk2-dimensionalDiscrete Cosine Transform (DCT)This module introduces the 2-dimensional DCT.
In the equation from our discussion of the Haar transform:
yTxT
and to invert:
xTyT
we saw how a 1-D transform could be extended to 2-D by pre- and
post-multiplication of a square matrix x to give a matrix result
y. Our example then
used
22 matrices, but this technique applies to square
matrices of any size.
Hence the DCT may be extended into 2-D by this method.
E.g. the
88 DCT transforms a subimage of
88 pels into a matrix of
88 DCT coefficients.
The 2-D basis functions, from which x may be reconstructed, are given
by the
n2 separate products of the columns of
T with the rows of T. These are shown for
n8 in
(a) of as 64 subimages of
size
88 pels.
The result of applying the
88 DCT to the Lenna image is shown in (b) of . Here each
88 block of pels x is replaced by the
88 block of DCT coefficients y. This shows the
88 block structure clearly but is not very meaningful
otherwise.
Part(c) of shows the same
data, reordered into 64 subimages of
3232 coefficients each so that each subimage contains all
the coefficients of a given type - e.g: the top left subimage
contains all the coefficients for the top left basis function
from (a) of . The other
subimages and basis functions correspond in the same way.
We see the major energy concentration to the subimages in the
top left corner. (d) of is
an enlargement of the top left 4 subimages of (c) of and bears a strong similarity to
the group of third level Haar subimages in (b) of
this figure. To
emphasise this the
histograms and entropies of these 4 subimages are shown in .
Comparing with this
figure, the Haar
transform equivalent, we see that the Lo-Lo bands have identical
energies and entropies. This is because the basis functions are
identical flat surfaces in both cases. Comparing the other 3
bands, we see that the DCT bands contain more energy and entropy
than their Haar equivalents, which means
less energy (and so hopefully less entropy)
in the higher DCT bands (not shown) because the total energy is
fixed (the transforms all preserve total energy). The mean
entropy for all 64 subimages is 1.3622 bit/pel, which compares
favourably with the 1.6103 bit/pel for the 4-level Haar
transformed subimages using the same
Qstep15.
(a) Basis functions of the
88 DCT; (b) Lenna transformed by the
88 DCT; (c) reordered into subimages grouped by
coefficient type; (d) top left 4 subimages from (c).
The probabilities
pi and entropies
hi for the 4 subimages from the top left of the
88 DCT ((d) of ).
(a) Mesh and (b) row plots of the entropies of the subimages
of (c) of .
Lenna transformed by the
44 DCT (a) and
1616 DCT (b).
What is the optimum DCT size?
This is a similar question to: What is the optimum number of
levels for the Haar transform?
We have analysed Lenna using DCT sizes from
22 to
1616 to investigate this. shows the
44 and
1616 sets of DCT subimages. The
22 DCT is identical to the level 1 Haar transform (so
see (b) of ) and the
88 set is in (c) of .
and
show the mesh plots of
the entropies of the subimages in .
compares the total
entropy per pel for the 4 DCT sizes with the equivalent 4 Haar
transform sizes. We see that the DCT is significantly better
than the rather simpler Haar transform.
As regards the optimum DCT size, from , the
1616 DCT seems to be marginally better than the
88 DCT, but subjectively this is not the case since
quantisation artefacts become more visible as the block size
increases. In practise, for a wide range of images and viewing
conditions,
88 has been found to be the optimum DCT block size and
is specified in most current coding standards.
(a) Mesh and (b) row plots of the entropies of the
44 DCT in (a) of .
(a) Mesh and (b) row plots of the entropies of the
1616 DCT in (b) of .
Comparison of the mean entropies of the Haar transform of
Lenna at levels 1 to 4, and of the DCT for sizes from
22 to
1616 pels with
Qstep15.