JPG and the Discrete Cosine Transform

Behind the familiar JPG format lie many compression techniques worth learning. Seeing how our predecessors used various clever engineering techniques to compress images really makes you appreciate living in this era.

JPEG

Strictly speaking, JPEG is not a file format, but an algorithm. The actual file format is specified by JFIF.

Let’s start with how JPEG stores colors.

Scientists discovered that humans are far more sensitive to brightness (luminance) than to color (chrominance). Therefore, when choosing a color space, YCrCb is used for storage, separating luminance from chrominance.

Discrete Cosine Transform

If there is an algorithm that allows JPEG images to be compressed so magically, the most important hero behind it is the Discrete Cosine Transform (DCT). Why can images be compressed, and what does it have to do with the Discrete Cosine Transform?

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, using pixel grayscale values as the height along the y-axis, it can be represented like this:

What is the benefit of treating an image as a signal? Just like with any other signal, we can process it; mathematically, signals can be represented by polynomials.

The formula for the Discrete Cosine Transform is as follows:

Let’s see what it looks like after processing:

With this formula, we can interpret the transformed signal as:

What proportion each frequency of cosine waves accounts for in the image

Alternatively, you can think of it as “any image can be seen as a synthesis of cosine waves of different frequencies.” For humans, low frequencies are the signals we actually care about. We can significantly reduce the high-frequency coefficients of the original signal, or even set them to 0, without noticeably affecting the original image.

2-D 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 8x8 blocks and converted into DCT coefficients.

Quantization Table

If you directly save the DCT coefficient matrix, the original image is not compressed at all. In practice, the DCT matrix is multiplied with a quantization table, resulting in a new DCT coefficient matrix where most of the high-frequency coefficients become zero. The JPG algorithm splits the image into several 8x8 blocks and computes the DCT for each of these blocks.

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

Zig-zag

After multiplying the DCT coefficient matrix by the quantization table, most elements in the high-frequency parts become 0. The upper-left of the matrix represents low frequencies, moving towards higher frequencies toward the lower-right. To place the low-frequency numbers first, the matrix is traversed during compression as shown in the diagram below:

For example, if the matrix after multiplying with the quantization table looks like this:

Then during actual encoding, it will be transformed into:

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

This is done to facilitate subsequent compression.

Huffman Coding

Huffman coding is a lossless data compression algorithm that can encode data very efficiently. During JPG encoding, a large portion of the elements are 0. Huffman coding assigns shorter codes to symbols with higher frequencies and longer codes to those with lower frequencies. In JPG, the DCT matrix is stored after Huffman coding.

Actually Decoding a JPEG

The process of decoding a JPEG is as follows:

• Extract the Huffman coding tables from the file
• Extract the DCT coefficient matrices from the file
• Compute the inverse DCT matrix and multiply it by the quantization table coefficients to obtain the pixels for that block
• Convert YCbCr back to RGB

Below is a simple JavaScript implementation, largely based on this article (Understanding and Decoding a JPEG Image using Python). You can view the full code on CodePen, which renders the decoded result onto a canvas.

Note that instead of using putImageData, this directly reads the contents of the JPG file and renders it block by block onto the canvas. (Of course, we wouldn’t do this in production.)

function parseJPG(data) {
  const hfTables = {};
  const quantizationTables = {};
  let quantMapping;
  let d = new Uint8Array(data);
  let w;
  let h;
  while (true) {
    const marker = new Uint8Array(d.slice(0, 2));
    // console.log(marker[0].toString(16), marker[1].toString(16));
    if (marker[0] === 0xff && marker[1] === 0xd8) {
      console.log("start of image");
      d = d.slice(2);
    } else if (marker[0] === 0xff && marker[1] === 0xd9) {
      console.log("end of image");
      return;
    } else {
      const lenchunk = d.slice(2, 4);
      let len = (lenchunk[0] << 8) + lenchunk[1] + 2;

      const chunk = d.slice(4, len);

      if (marker[0] === 0xff && marker[1] === 0xc4) {
        // console.log(d, chunk);
        const { table, header } = decodeHuffman(chunk);
        hfTables[header] = table;
      } else if (marker[0] === 0xff && marker[1] === 0xdb) {
        const { header, table } = buildQuantizationTables(chunk);
        quantizationTables[header] = table;
      } else if (marker[0] === 0xff && marker[1] === 0xc0) {
        // start of frame
        const { result, width, height } = baseDCT(chunk);
        quantMapping = result;
        w = width;
        h = height;
      } else if (marker[0] === 0xff && marker[1] === 0xda) {
        // console.log(quantMapping, quantizationTables);
        len = startOfScan({
          data: d,
          hdrlen: len,
          width: w,
          height: h,
          quantizationTables,
          quantMapping,
          hfTables,
        });
      }

      d = d.slice(len);
    }
    if (d.length === 0) {
      break;
    }
  }

There are many segments inside a JPG file, identified by markers prefixed with 0xff:

• 0xffc4: Huffman table
• 0xffda: Start of scan
• 0xffdb: Quantization table
• 0xffd8: Start of Image marker
• 0xffd9: End of Image marker

First convert the binary data into the corresponding tables (Huffman tables, quantization tables), and then perform the calculations to get the matrix!

After testing, I found that it doesn’t decode successfully—there is likely a bug in the code. If you look at the implementation, you can see that the calculations are actually quite tedious. Due to time constraints, I’m sharing it here as a reference for now~

(The top seems to render with the correct colors, but the rest has a greenish tint.)

Afterword

In real-world applications, GPUs or CPUs have dedicated hardware circuits for image encoding and decoding, so we rarely need to write code to process them manually. However, the algorithm behind JPG combines the Discrete Cosine Transform, Huffman coding, and zig-zag scanning to effectively reduce image storage space. I really enjoy exploring things we take for granted in everyday life, only to discover so much knowledge worth learning once we look beneath the surface.