Why do some images compress and others don’t?

Same data, different information

A 16×16 grayscale image is 256 pixels — 256 bytes if you store one byte per pixel. That’s the data. But how many bits of information does the image actually contain? That’s a different question, and the answer can be much less than 8 bits/pixel. If every pixel is the same shade, you need almost no bits to describe the picture: “all of them, value 7.” If every pixel is independent random noise, you need close to 8 bits each, because there’s no pattern to exploit. Real photos sit between, and the gap between data and information is exactly what a compressor harvests.

The histogram bound

The first place to look is the pixel value distribution — the histogram (we’ll wrap it shortly). Count how many pixels are at each level, divide by total to get probabilities, plug into $H = -Σ p \log₂ p$. The number you get is the average bits per pixel needed if you encoded each pixel independently, ignoring its neighbors.

For our 16-level patch where each level appears exactly 16 times, every level has probability $1/16$, so $H = \log₂ 16 = 4$ bits/pixel. That’s the histogram bound — the Shannon limit for symbol-by-symbol encoding. Halving 8 bits/pixel to 4 already explains why a 16-shade image compresses to half the size of a 256-shade one.

import numpy as np
from collections import Counter
from math import log2

# A 16x16 patch with each of 16 grayscale levels appearing exactly 16 times.
# We'll build three layouts that share this histogram and compare entropies.
def gradient():
    img = np.zeros((16, 16), dtype=np.int32)
    for i in range(16):
        img[i, :] = i           # row i is constant level i
    return img

def blocks():
    img = np.zeros((16, 16), dtype=np.int32)
    for i in range(16):
        for j in range(16):
            img[i, j] = (i // 4) * 4 + (j // 4)
    return img

def scrambled(seed=0):
    rng = np.random.default_rng(seed)
    flat = gradient().flatten()
    rng.shuffle(flat)
    return flat.reshape(16, 16)

# Histogram entropy — bits/pixel if you encoded each pixel independently.
def histogram_entropy(img):
    flat = img.flatten()
    counts = Counter(flat)
    N = len(flat)
    return sum(-(c / N) * log2(c / N) for c in counts.values() if c > 0)

[histogram_entropy(p()) for p in (gradient, blocks, scrambled)]
# → [4.0, 4.0, 4.0]   identical — same histogram, same H.

What the histogram doesn't see

Toggle between gradient, blocks, and scrambled in the widget. The pixels are exactly the same multiset — same 16 copies of each level. Histogram entropy: $4.0$ bits/pixel for all three. Identical.

But the pictures don’t look the same, and they don’t compress the same. The gradient is smooth: every adjacent pair is either equal or differs by 1. The scrambled patch has neighbors that fight each other — adjacent levels are essentially independent. Same histogram, very different spatial structure, and that structure is where most of the real compression happens.

# Neighbor-difference entropy — what a real compressor sees.
# For each pair of adjacent pixels (right + down), count abs(diff). The
# resulting distribution carries the spatial structure the histogram missed.
def neighbor_diff_entropy(img):
    diffs = []
    H, W = img.shape
    for i in range(H):
        for j in range(W):
            if j + 1 < W: diffs.append(abs(int(img[i, j]) - int(img[i, j+1])))
            if i + 1 < H: diffs.append(abs(int(img[i, j]) - int(img[i+1, j])))
    counts = Counter(diffs)
    N = len(diffs)
    return sum(-(c / N) * log2(c / N) for c in counts.values() if c > 0)

[neighbor_diff_entropy(p()) for p in (gradient, blocks, scrambled)]
# → [0.34, 1.34, 4.07]   gradient ~0, scrambled ~log2(16) ≈ 4.
# Histograms saw three identical sources; neighbor differences see three
# very different ones. That gap is the entire point of spatial compression.

Neighbor differences — entropy of a different alphabet

The trick: instead of encoding each pixel as a value 0..15, encode each pixel as the difference from its left or top neighbor. The first pixel still costs full bits, but every subsequent one is usually a small number — often zero. Now run $H = -Σ p \log₂ p$ on the distribution of differences. For the gradient: most differences are 0 or 1, entropy is well under 1 bit/pixel. For scrambled: differences are uniform across the full range, entropy is back near 4. The widget shows both numbers side by side; the ratio is the speedup a structure-aware compressor delivers over a histogram-only one.

This is the page in one sentence: histograms see what pixels appear, neighbor differences see how they sit next to each other. Real lossless compressors (PNG, gzip on raw pixel arrays) operate on the second view.

Lossless vs lossy — two ways out of the histogram bound

Histogram entropy is a hard floor for lossless compression: no scheme can encode the source in fewer bits per symbol than its entropy, on average. But there are two escape hatches. One — change the alphabet. Encode neighbor differences instead of raw pixels; encode pairs instead of singletons; encode 8×8 blocks via a transform (DCT for JPEG, wavelets for JPEG-2000). The new alphabet has lower entropy because real images are not symbol-independent. PNG and FLAC live here.

Two — give up exactness. Lossy compression decides what to throw away based on what humans don’t notice — fine color shifts, high-frequency texture, sub-millisecond audio. The decompressed file is not the original; it’s a perceptual approximation. JPEG, MP3, H.264 live here. They aren’t bound by entropy at all — only by how much quality you’ll trade for size.

# Real-world check: encode all three with PNG and compare file sizes.
# PNG uses filter prediction (essentially neighbor differences) followed by
# DEFLATE (LZ77 + Huffman). Same pixel multiset, very different output.
import io
from PIL import Image

def png_size(img):
    buf = io.BytesIO()
    Image.fromarray((img * 16).astype('uint8'), mode='L').save(buf, 'PNG')
    return len(buf.getvalue())

sizes = {p.__name__: png_size(p()) for p in (gradient, blocks, scrambled)}
# → {'gradient': ~120, 'blocks': ~140, 'scrambled': ~310}
#
# The histograms predicted 4 bits × 256 pixels = 128 bits = 16 bytes of
# *symbol payload*; PNG's framing overhead is fixed. The interesting number
# is the ratio of payloads: gradient ≈ 1×, scrambled ≈ 2-3× larger. Same
# histogram, different file size — the signature of spatial compression.