The Discrete Cosine Transform (DCT) 2.2 2003/03/26 2003/05/02 Nick Kingsbury ngk10@cam.ac.uk Liqun Wang liqun@rice.edu Nick Kingsbury ngk10@cam.ac.uk Discrete Cosine Transform (DCT) Image Compression JPEG Standard This module briefly outlines the energy compression technique - the discrete cosine transform (DCT). The main standard for image compression in current use is the JPEG (Joint Picture Experts Group) standard, devised and refined over the period 1985 to 1993. It is formally known as ISO Draft International standard 10981-1 and CCITT Recommendation T.81, and is described in depth in The JPEG Book by W B Pennebaker and J L Mitchell, Van Nostrand Reinhold 1993. We shall briefly outline the baseline version of JPEG but first we consider its energy compression technique - the discrete cosine transform (DCT).

The Discrete Cosine Transform (DCT) In this equation from our discussion of the Haar transform, we met the 2-point Haar transform and in this equation we saw that it can be easily inverted if the transform matrix T is orthonormal so that T T . If T is of size n x n, where n 2 m , then we may easily generate larger orthonormal matrices, which lead to definitions of larger transforms. An n-point transform is defined as: y 1 … y n T x 1 … x n where T t 1 1 … t 1 n ⋮ ⋮ ⋮ t n 1 … t n n A 4-point orthonormal transform matrix that is equivalent to 2 levels of the Haar transform is: T 1 2 1 0 1 0 1 0 -1 0 0 2 0 0 0 0 0 2 1 2 1 1 0 0 1 -1 0 0 0 0 1 1 0 0 1 -1 1 2 1 1 1 1 1 1 -1 -1 2 2 0 0 0 0 2 2 where 1 2 1 0 1 0 1 0 -1 0 0 2 0 0 0 0 0 2 is Haar level 2 and 1 2 1 1 0 0 1 -1 0 0 0 0 1 1 0 0 1 -1 is Haar level 1. Similarly 3 and 4 level Haar transforms may be expressed using 8 and 16 point transform matrices respectively. However for n 2 , there are better matrices than those based on the Haar transform, where better means with improved energy compression properties for typical images. Discrete Cosine Transforms (DCTs) have some of these improved properties and are also simple to define and implement. The n rows of an n-point DCT matrix T are defined by: i 1 n t 1 i 1 n i 1 n k 2 n t k i 2 n 2 i 1 k 1 2 n It is straightforward to show that this matrix is orthonormal for n even, since the norm of each row is unity and the dot product of any pair of rows is zero (the product terms may be expressed as the sum of a pair of cosine functions, which are each zero mean). The 8-point DCT matrix ( n 8 ) is: T 0.3536 0.3536 0.3536 0.3536 0.3536 0.3536 0.3536 0.3536 0.4904 0.4157 0.2778 0.0975 -0.0975 -0.2778 -0.4157 -0.4904 0.4619 0.1913 -0.1913 -0.4619 -0.4619 -0.1913 0.1913 0.4619 0.4157 -0.0975 -0.4904 -0.2778 0.2778 0.4904 0.0975 -0.4157 0.3536 -0.3536 -0.3536 0.3536 0.3536 -0.3536 -0.3536 0.3536 0.2778 -0.4904 0.0975 0.4157 -0.4157 -0.0975 0.4904 -0.2778 0.1913 -0.4619 0.4619 -0.1913 -0.1913 0.4619 -0.4619 0.1913 0.0975 -0.2778 0.4157 -0.4904 0.4904 -0.4157 0.2778 -0.0975 The rows of T, known as basis function, are plotted as asterisks in . The asterisks are superimposed on the underlying continuous cosine functions, used in all sizes of DCT. Only the amplitude scaling and the maximum frequency vary with the size n.

The 8-point DCT basis functions(*) and their underlying continuous cosine waves.

When we take the transform of an n-point vector using y T x , x is decomposed into a linear combination of the basis function (rows) of T, whose coefficients are the samples of y, because x T y . The basis functions may also be viewed as the impulse responses of FIR filters, being applied to the data x. The DCT is closely related to the discrete Fourier transform (DFT). It represents the result of applying the 2 n -point DFT to a vector: x 2 n x xrev where xrev x n … x 1 . x 2 n is symmetric about its centre and so the 2 n Fourier coefficients are all purely real and symmetric about zero frequency. The n DCT coefficients are then the first n Fourier coefficients. The DFT must be defined with a half sample period offset on the indexing of the input samples for the above to be strictly true.

Standards The 8-point DCT is the basis of the JPEG standard, as well as several other standards such as MPEG-1 and MPEG-2 (for TV and video) and H.263 (for video-phones). Hence we shall concentrate on it as our main example, but bear in mind that DCTs may be defined for a wide range of sizes n.