Math Tools Math Tools
Share:
← Back to Blog

The Math Behind Image Compression

The Math Behind Image Compression

By Math Tools ·

The Math Behind Image Compression

A 12-megapixel photo stored as raw pixels takes about 36 MB: 12 million pixels × 3 bytes of color each. Saved as a good-quality JPEG, the same photo is often around 3 MB. More than 90% of the data is gone, and to your eye, the picture looks the same.

That isn't magic, and it isn't luck. JPEG throws away exactly the information your visual system is worst at noticing, using a sequence of mathematical transformations built on cosine waves.

Images Are Easier to Compress as Waves Than as Pixels

Look at a photo pixel by pixel and every value seems important. But neighboring pixels are usually very similar: a patch of sky, a wall, a cheek. Most of an image changes slowly across space.

If you describe a block of pixels as a sum of smooth waves instead of individual dots, most of the "energy" lands in a few low-frequency waves. The high-frequency waves, which represent fine detail, have small values that can be rounded away. Changing your basis changes what's easy to throw out.

Step 1: Separate Brightness From Color

Human eyes have far more receptors sensitive to brightness than to color. JPEG takes advantage of that by converting RGB into YCbCr:

Y  =  0.299R + 0.587G + 0.114B          (luminance)
Cb = −0.1687R − 0.3313G + 0.5B + 128    (blue difference)
Cr =  0.5R − 0.4187G − 0.0813B + 128    (red difference)

This is a linear transformation, a 3 × 3 matrix multiplied by each pixel's color vector. Notice green gets the biggest weight in Y. Our eyes are most sensitive to green light.

Next comes chroma subsampling. In the common 4:2:0 scheme, the two color channels are stored at half the width and half the height. Each color channel keeps just 25% of its samples, so total data drops by 50% before any "real" compression begins.

Step 2: The Discrete Cosine Transform

The image is split into 8 × 8 blocks. Each block's 64 values are converted into 64 DCT coefficients using the discrete cosine transform:

F(u,v) = ¼ C(u) C(v) Σₓ Σᵧ f(x,y) cos((2x+1)uπ/16) cos((2y+1)vπ/16)

Each coefficient says how much of one particular 2D cosine pattern is present in the block. F(0,0), the DC coefficient, is the average brightness. The other 63 are AC coefficients, ranging from gentle gradients to fine checkerboards.

The DCT doesn't lose any information on its own. It's perfectly reversible. It just reorganizes the data so that most values are close to zero. You can see the cosine values behind the formula with the cosine calculator or the trigonometric tables.

An Insider Reference: Nasir Ahmed's Rejected Proposal

The DCT was proposed by Nasir Ahmed, then at Kansas State University. In 1972 he applied to the U.S. National Science Foundation for funding to study it. The proposal was rejected, because reviewers thought the idea was too simple.

Ahmed pursued it anyway with his PhD student T. Natarajan and colleague K. R. Rao, publishing "Discrete Cosine Transform" in 1974. The DCT went on to become the core of JPEG (standardized in 1992), MPEG video, MP3 audio (as a modified DCT) and most streaming video.

Step 3: Quantization, Where the Loss Happens

This is the step that actually throws information away. Each DCT coefficient is divided by a value from a quantization table and rounded to the nearest integer:

Q(u,v) = round( F(u,v) / T(u,v) )

The table uses small divisors for low frequencies (kept precisely) and large divisors for high frequencies (rounded harshly, often to zero). The JPEG "quality" slider scales this table. Lower quality means bigger divisors and more zeros.

After quantization, a typical block might have only a handful of non-zero values out of 64.

Step 4: Lossless Packing

The quantized coefficients are read in a zigzag order, from low frequency to high, so the zeros bunch together at the end. Then two lossless tricks shrink the data further:

  • Run-length encoding replaces long runs of zeros with a count
  • Huffman coding gives short bit codes to common values and longer codes to rare ones

David Huffman invented his algorithm in 1952 as an MIT graduate student. It was for a term paper, offered by his professor Robert Fano as an alternative to taking the final exam. Huffman's method is provably optimal among codes that assign a whole number of bits to each symbol.

Why JPEG Artifacts Look Like Blocks

Push the quality too low and you see blocky artifacts along 8 × 8 boundaries, and ringing around sharp edges. Each block was compressed independently, and throwing away high-frequency cosines makes sharp edges wobble. That's the Gibbs phenomenon, the overshoot you get when approximating a sharp jump with a limited number of waves.

Lossless Compression: PNG

PNG never discards data. It uses prediction filters, guessing each pixel from its neighbors and storing only the difference, then compresses with DEFLATE, a combination of LZ77 and Huffman coding. That works brilliantly for screenshots, diagrams and flat colors, and poorly for noisy photographs.

Two Concepts Worth Knowing

Entropy

Shannon entropy is the theoretical minimum average number of bits needed per symbol:

H = −Σ p(x) log₂ p(x)

No lossless method can beat it on average. Quantization lowers the entropy of an image, and that's what makes big savings possible. Compute log₂ values with the logarithm calculator.

Basis Functions

A basis is a set of building blocks from which any element can be made. Pixels are one basis for an image, and cosine waves are another. Choosing the right basis is one of the most powerful ideas in applied mathematics.

Quick Answer: How Does JPEG Compression Work?

JPEG converts an image to brightness and color channels, reduces color resolution, splits the image into 8 × 8 blocks, and converts each block into cosine-wave coefficients with the discrete cosine transform. It then rounds away small high-frequency coefficients (the lossy step) and packs the rest with run-length and Huffman coding.

Try Them Yourself

Save the same photo as a JPEG at quality 90, 50 and 10, then zoom in. You'll see exactly where the quantization table started rounding detail away.

Next → Vectors: The Mathematical Language of 3D Graphics