CHAPTER 3

THE DISCRETE COSINE TRANSFORM

**3.1 MOTIVATION FOR THE DCT—COMPRESSION**

The goal of any compression algorithm is to make the data that represent the underlying signal or image as small as possible without undue loss of information. Other considerations include simplicity, speed of computation, and flexibility.

In this chapter we present the discrete cosine transform and introduce the notion of localizing frequency analysis by breaking a signal or image into smaller pieces. One motivation for this is to give the reader an understanding of the mathematical basis of classical JPEG compression. In order to keep the discussion focused on the essential mathematical principles, we’ll make a few simplifying assumptions. First, we’ll assume that the signal or image has already been digitized, and so there are no image capture or sampling issues involved. We’ll also assume that the quantization error when the signal is captured is negligible so that the vector space models of Chapter 1 continue to apply. The quantization that occurs when the image is first digitized is in the time domain. Quantization will also be an issue at a later point, but in the frequency domain. We’ll work only with grayscale images.

Before proceeding it’s helpful to define what we mean by “lossless” and “lossy” compression.

**Definition 3.1.1** A *compression algorithm or a specific step in a compression algorithm is called* “lossless” *if it is reversible so that the input can be perfectly reconstructed from the ...*