The discrete cosine transform (dct)

The main standard for image compression in current use is the JPEG (Joint Picture Experts Group) standard, devised and refinedover 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 discretecosine 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^{(-1)}=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:

A 4-point orthonormal transform matrix that is equivalent to 2 levels of the Haar transform is:

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: $$\forall , i=1\to n\colon t_{1, i}=\sqrt{\frac{1}{n}}$$

The 8-point DCT matrix ( $n=8$ ) is:

When we take the transform of an $n$ -point vector using $y=Tx$ , $x$ is decomposed into a linear combination of the basis function(rows) of $T$ , whose coefficients are the samples of $y$ , because $x=T^Ty$ .

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 $2n$ -point DFT to a vector: $$x_{2n}=\begin{pmatrix}x\\ x_{\mathrm{rev}}\\ \end{pmatrix}$$ where $x_{\mathrm{rev}}=\begin{pmatrix}x(n)\\ \dots \\ x(1)\\ \end{pmatrix}$ . $x_{2n}$ is symmetric about its centre and so the $2n$ Fourier coefficients are all purely real and symmetric about zero frequency. The $n$ DCT coefficients are then the first $n$ Fourier coefficients.

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 TVand video) and H.263 (for video-phones). Hence we shall concentrate on it as our main example, but bear in mind thatDCTs may be defined for a wide range of sizes $n$ .