The Secret Behind JPEG Compression: Discrete Cosine Transform

(This article originates from the 2023 iThome Ironman Contest)

Behind the familiar JPG format lies a treasure trove of compression techniques worth studying. Seeing how pioneers used a variety of clever engineering tricks to compress images makes you truly appreciate living in this era.

JPEG

Strictly speaking, JPEG is not a file format, but an algorithm. The file format itself is specified by JFIF (JPEG File Interchange Format).

YCbCr

First, let’s start with how JPEG stores color. Typically, we use the three primary colors of light—R, G, and B—to represent colors. However, scientists discovered that the human eye is far more sensitive to changes in brightness than to changes in color.

To take advantage of this innate human trait, we want to minimize the amount of color information and instead use brightness variations for representation. In image processing, YCbCr is commonly used to represent color.

Here:

• Y stands for Luminance
• Cr stands for Chrominance Red
• Cb stands for Chrominance Blue

So where did G go? The answer is that it was discarded. Even though some information is lost, due to the human eye’s insensitivity to color variations, discarding this part of the information does not result in a noticeable difference.

The formulas to convert from RGB to YCbCr are:

Discrete Cosine Transform (DCT)

If there is one algorithm that allows JPEG to compress images so magically, the hero behind it is the Discrete Cosine Transform (DCT).

High and Low Frequencies in Images

To simplify and make the Discrete Cosine Transform easier to understand, let’s start with a 1D array as an example. If we treat an image as a signal and use the grayscale value of each pixel as the y-axis height, each row of pixels can be viewed as a signal segment.

What is the advantage of treating an image as a signal? Just like any other signal, we can perform frequency domain analysis on it. Through linear transformations, we can identify low-frequency and high-frequency components.

We can interpret the transformed signal as:

The proportion of each cosine frequency present in the image

Alternatively, you can think of it as: “Any image can be synthesized as a combination of cosine waves of different frequencies.” For humans, low frequencies are the crucial signals that compose an image. We can comfortably reduce the high-frequency coefficients of the original signal—or even set them to 0—without significantly affecting the original image.

And since they can be set to 0, they require no extra storage space! This is the core concept of JPEG compression.

2D Discrete Cosine Transform

The formula for the 2D Discrete Cosine Transform is more complex, but the underlying principle remains the same. The image is first divided into 8×8 blocks and converted into DCT coefficients.

The 2D DCT formula is:

Where $C(k) = \frac{1}{\sqrt{2}}$ when $k = 0$, otherwise $C(k) = 1$.

The formula may look intimidating, but the principle is simply asking: “Which basis patterns does this 8×8 block look like, and how much does it resemble each of them?”

The DCT coefficient F(u,v) is computed by taking the dot product of the original image with this basis pattern—asking “how similar is this image to this pattern?” The higher the similarity, the larger the coefficient and the higher the weight.

Interactive: DCT Visualization

The interactive tool below includes visualizations of the 64 DCT basis patterns—each (u, v) corresponds to a frequency combination. The top-left corner (0,0) represents the DC component (average brightness), and moving toward the bottom-right increases the frequency.

You can see which basis patterns are preserved (bright) or discarded (dark) during compression, with the numbers indicating the zig-zag scanning order.

After uploading an image, you can observe the actual DCT transformation results and the reconstructed image under different compression levels.

Quantization Table

If you directly save the matrix of DCT coefficients, the original image hasn’t been compressed at all.

In practice, DCT coefficients are divided by values from a quantization table and rounded to the nearest integer. This process produces a new matrix of DCT coefficients where most high-frequency coefficients drop to zero due to quantization. The JPG algorithm splits the image into several 8×8 blocks and calculates the DCT across these blocks.

When choosing a compression ratio, the coefficients in the quantization table will vary. If there is no compression, all elements in the quantization table would be 1 (preserving every pixel of the image).

Zig-zag Traversal

After dividing the DCT coefficient matrix by the quantization table, most elements in the high-frequency region become 0. The top-left of the matrix contains low frequencies, moving toward higher frequencies toward the bottom-right. To place the low-frequency numbers first, the matrix is traversed in a zig-zag pattern when compressing the image file.

For example, if the quantized matrix looks like this:

4 5 1 0
1 3 0 0
6 0 0 0
0 0 0 0

When actually encoded, it becomes:

[4, 5, 1, 1, 3, 6, 9, 5, 0, 0, 0, 0, 0, 0, 0, 0]

The consecutive zeros at the end can then be compressed very efficiently.

Huffman Coding

Huffman coding is a lossless data compression algorithm that encodes data very efficiently. During JPG encoding, a large portion of the elements are 0. Huffman coding assigns shorter codes to frequently occurring symbols and longer codes to less frequent symbols. In JPG, after the DCT matrix undergoes quantization and zig-zag traversal, it is saved using Huffman coding.

Decoding JPEG in Practice

Decoding JPEG is essentially reversing the steps above:

1. Extract the Huffman tables from the file and decode the data
2. Restore the zig-zag sequence back into an 8×8 matrix
3. Multiply the DCT coefficients by the quantization table to get approximate DCT coefficients
4. Calculate the Inverse DCT (IDCT) to restore the pixel values
5. Convert YCbCr back to RGB

A JPG file contains many segments, identified by markers starting with 0xff:

• 0xffd8 — Start of Image (SOI) marker
• 0xffc0 — Start of Frame (SOF), containing image dimensions and other information
• 0xffc4 — Huffman table (DHT)
• 0xffdb — Quantization table (DQT)
• 0xffda — Start of Scan (SOS), the actual image data
• 0xffd9 — End of Image (EOI) marker

Here is a simplified JavaScript implementation for parsing JPG markers:

function parseJPG(data) {
  const hfTables = {}
  const quantizationTables = {}
  let quantMapping
  let d = new Uint8Array(data)
  let w, h

  while (d.length > 0) {
    const marker = d.slice(0, 2)

    if (marker[0] === 0xff && marker[1] === 0xd8) {
      d = d.slice(2) // SOI
      continue
    }

    if (marker[0] === 0xff && marker[1] === 0xd9) {
      break // EOI
    }

    const len = (d[2] << 8) + d[3] + 2
    const chunk = d.slice(4, len)

    switch (marker[1]) {
      case 0xc4: { // DHT
        const { table, header } = decodeHuffman(chunk)
        hfTables[header] = table
        break
      }
      case 0xdb: { // DQT
        const { header, table } = buildQuantizationTables(chunk)
        quantizationTables[header] = table
        break
      }
      case 0xc0: { // SOF
        const { result, width, height } = baseDCT(chunk)
        quantMapping = result
        w = width
        h = height
        break
      }
      case 0xda: { // SOS
        startOfScan({ data: d, hdrlen: len, width: w, height: h,
          quantizationTables, quantMapping, hfTables })
        break
      }
    }

    d = d.slice(len)
  }
}

Afterword

In real-world applications, both GPUs and CPUs have dedicated hardware circuits for image encoding and decoding, so we rarely need to write code to process them manually. Nevertheless, the algorithm behind JPG—combining the Discrete Cosine Transform, Huffman coding, and zig-zag traversal—successfully slashes the storage space required for images.

I really enjoy taking things we take for granted every day and diving deep into them, only to discover a wealth of knowledge worth learning. JPEG compression allows us to transmit hundreds of millions of images across the internet every day, and behind it all lies the perfect marriage of mathematics, information theory, and human visual perception.