Image Compression

Image compression represents an image in fewer bits than its raw samples need. A lossless method lets the decoder recover every sample exactly. A lossy method gives up exactness in return for much smaller files and lets the user choose how much error to accept. JPEG and JPEG 2000, the two standard lossy codecs this article examines, are both built from three stages. A transform concentrates the image’s energy in a few coefficients. A quantizer rounds those coefficients onto a coarse grid, which is the only stage that loses information. An entropy coder then writes the quantized values with as few bits as their statistics allow. JPEG follows this pattern with an $8 \times 8$ discrete cosine transform, and JPEG 2000 follows it with a wavelet transform. The field is also called image coding, and the transform-quantize-code design transform coding.

The prerequisite articles cover the transforms themselves: why the DCT packs the energy of correlated blocks almost as well as the optimal Karhunen–Loève transform, and why images are sparse in a wavelet basis. This article covers what a codec does with the coefficients:

how the quantizer is set;
how quantized values become symbols and bits;
how the size of the result is measured against its error.

Definition

An encoder maps an image $x$ to a bit string, and a decoder maps the bit string to a reconstruction $\hat{x}$ . Two numbers describe the result:

Rate. The rate $R$ is the length of the bit string divided by the number of pixels, in bits per pixel (bpp). For an 8-bit greyscale image, the compression ratio is $8 / R$ .
Distortion. The distortion $D$ measures the difference between $x$ and $\hat{x}$ . As PSNR reports from Wang and Bovik (2009), competing compression algorithms have most often been compared by the mean squared error or by PSNR. Perceptual indices such as SSIM are also used.

A codec is lossless when $D = 0$ for every image. A lossy codec has a parameter, such as JPEG’s quality setting, that moves it along a curve of $(R, D)$ points. Codecs are compared on this rate–distortion curve: at the same rate, the one with the lower distortion is better.

Intuition

A raw 8-bit image spends eight bits on every pixel, whatever the pixel holds. Compression exploits two facts.

Redundancy. Neighbouring pixels are strongly correlated, so most of a pixel’s value can be predicted from its neighbours. A lossless coder removes this redundancy by coding prediction errors or transform coefficients, which are small and concentrated around zero, instead of raw values. A good code gives frequent values short codewords and rare values long ones.

Irrelevance. Not every detail matters equally to a viewer. A lossy coder removes information on purpose:

It transforms each block so that energy is concentrated, and so that each coefficient corresponds to a spatial frequency.
It quantizes the coefficients, with coarse steps where errors are least visible.

T.81’s example luminance table (Table K.1) grows from a step of 16 for the block mean to steps of around 100 for the highest frequencies. The standard describes its two example tables as based on psychovisual thresholding and derived empirically (CCITT, 1992, Annex K.1). After coarse quantization most high-frequency coefficients become zero. A run of zeros costs almost nothing to code.

The quantizer decides how much is lost. The entropy coder decides how efficiently the result is written, and it loses nothing.

Formal Definition

Quantization

T.81 defines JPEG’s quantizer and dequantizer for a DCT coefficient $S_{vu}$ with step $Q_{vu}$ from the quantization table (section A.3.4):

Sq_{vu} = \operatorname{round}\!\left(\frac{S_{vu}}{Q_{vu}}\right), \qquad R_{vu} = Sq_{vu} \times Q_{vu}.

It calls the quantization informative and the dequantization normative, and notes that the quantization equation contains a term no real implementation may represent with perfect accuracy. The reconstruction error of each coefficient is at most $Q_{vu}/2$ in magnitude. Since the orthonormal DCT preserves energy, the mean squared error in the pixels equals the mean squared error in the coefficients, before the final rounding and clipping to 8 bits. A coefficient whose magnitude is below half its step is set to zero.

Entropy and the cost of a code

Let a stream contain $N$ symbols, with symbol $i$ occurring $n_i$ times. Its first-order empirical entropy is

H = -\sum_i \frac{n_i}{N} \log_2 \frac{n_i}{N} \quad \text{bits per symbol.}

No prefix code that gives each symbol one fixed codeword can write the stream in fewer than $NH$ bits (our derivation, by two standard inequalities). A prefix code with codeword lengths $l_i$ satisfies the Kraft inequality $\sum_i 2^{-l_i} \le 1$ . Gibbs’ inequality, applied to the distributions $p_i = n_i/N$ and $2^{-l_i}$ , then gives

\sum_i n_i l_i \;\ge\; -\sum_i n_i \log_2 \frac{n_i}{N} = N H,

with equality only when every $n_i/N$ is a power of $\tfrac12$ . So the first-order entropy is a lower bound for every prefix code that assigns one fixed codeword to each symbol. A code built from the image’s own counts approaches the bound, and a fixed table designed for other images exceeds it by more. The bound ignores dependence between successive symbols, and a coder that models such dependence can go below it.

Rate–distortion

For a codec with parameter $\theta$ and image $x$ , each $\theta$ gives a point $(R(\theta), D(\theta))$ . Plotting PSNR against bits per pixel for several settings gives the curve on which codecs are compared. Two curves can only be compared at the same rate, or at the same distortion. A quality setting is not comparable between codecs, nor between implementations of one codec with different tables.

The Baseline JPEG Process

T.81 specifies two classes of coding process: lossy processes based on the DCT, and lossless processes that are not (CCITT, 1992, section 4.2). The simplest DCT-based process, the baseline sequential process, must be present in every decoder of the extended DCT processes. It works on 8-bit samples and codes with Huffman codes. For one component, such as a greyscale image or the luminance of a colour image, it has six steps.

1. Level shift and transform. The image is cut into $8 \times 8$ blocks. 128 is subtracted from every sample (section A.3.1), and each block is transformed by the forward DCT into one DC coefficient and 63 AC coefficients (section 4.3). The Discrete Cosine Transform article shows that T.81’s formula is the orthonormal 2D DCT-II.

2. Quantization. Each of the 64 coefficients is quantized with its own step from a quantization table. T.81 specifies no default tables and leaves them to applications (section 4.3). Its Annex K gives two example tables, which it describes as examples only and not necessarily suitable for any particular application. It adds that halving them usually gives a reconstruction nearly indistinguishable from the source (Annex K.1). In baseline coding the quantized values are 11-bit two’s-complement integers (section F.1.1.4).

3. Zig-zag scan. The 63 AC coefficients are read in a zig-zag order that walks the anti-diagonals of the block, from low to high spatial frequency (section A.3.6, Figure A.6). After quantization the high-frequency end of this sequence is mostly zeros: in the example below, 70–98% of the quantized AC coefficients are zero.

4. DC prediction. The quantized DC coefficient is coded as the difference DIFF from the previous block’s quantized DC. The prediction starts at 0 at the beginning of the scan and of each restart interval (sections A.3.5 and F.1.1.5.1).

5. Symbols. Each value is split into a size category and an exact value (Tables F.1 and F.2):

The size category SSSS is the number of bits of the magnitude: 0 for the value 0, 1 for ±1, 2 for ±2 and ±3, and so on, up to 11 for DC differences and 10 for AC coefficients.
A DC difference becomes the symbol SSSS followed by SSSS additional bits. These are the low-order bits of DIFF when DIFF is positive, and of DIFF − 1 when it is negative.
Each nonzero AC coefficient becomes a composite symbol RRRRSSSS, whose four high bits give the run of zeros before it, followed by its additional bits.
Two special AC symbols handle zeros. ZRL (X’F0’) stands for a run of 16 zeros. EOB (X’00’) ends a block whose remaining coefficients are all zero, and is left out when the last coefficient is nonzero (section F.1.2.2).

6. Huffman coding. DC symbols and AC symbols are coded with separate Huffman tables. Codes are at most 16 bits long, and no code consists entirely of 1-bits (section F.1.2). A table is transmitted as two lists:

BITS: the number of codes of each length from 1 to 16;
HUFFVAL: the symbols in order of increasing code length.

Annex C (section C.2) turns these lists into codes. Codes of each length are consecutive integers, and the first code of the next length is found by adding one to the last code and shifting it left by one bit. T.81 specifies no default Huffman tables either (section 4.6). Annex K.3 gives typical tables for luminance and chrominance, developed from the average statistics of a large set of images (video images, in the text for the DC tables). Annex K.2 gives a procedure for building a table from an image’s own symbol counts, reserving one code point so that no code is all 1-bits.

The coded bits are packed into bytes, and the last byte is padded with 1-bits. Whenever the byte X’FF’ appears in the coded data, a zero byte is stuffed after it, so that a decoder can find markers without decoding (section F.1.2.3). A JPEG file is a sequence of marker segments around this entropy-coded data:

the start of image (SOI);
the quantization tables (DQT);
the frame header (SOF), with size, precision and components;
the Huffman tables (DHT);
the scan header (SOS);
the coded data;
the end of image (EOI).

The decoder runs the steps backwards. It decodes the symbols, rebuilds the zig-zag sequence, dequantizes and applies the inverse DCT, and its output differs from the input only by what quantization removed and by rounding.

The quality setting

Where does a “quality 75” come from? Not from the standard, which has no quality parameter. It comes from the encoder. The Independent JPEG Group’s libjpeg, which Pillow calls, converts a quality $q$ from 1 to 100 into a percentage scale $s$ :

s = \begin{cases} \lfloor 5000 / q \rfloor & q < 50 \\ 200 - 2q & q \ge 50 \end{cases}

Each entry of T.81’s example table $K$ then becomes $\lfloor (K \cdot s + 50) / 100 \rfloor$ , limited to at least 1, and to at most 255 when baseline compatibility is forced (jpeg_quality_scaling and jpeg_add_quant_table in libjpeg 9f’s jcparam.c). At $q = 50$ the example table is used unchanged, and at $q = 100$ every step is 1. Pillow passes the quality with baseline compatibility forced (JpegEncode.c). Its documentation gives 75 as the default and advises against values above 95, warning that 100 disables portions of the algorithm and gives large files with hardly any gain in quality (Pillow 12.0.0 documentation). With libjpeg’s defaults, the encoder writes the Annex K.3 Huffman tables. Pillow’s optimize=True instead makes an extra pass to build tables from the image’s own statistics, which libjpeg does with the K.2 procedure (jchuff.c). A comment in jchuff.c notes that K.2’s way of limiting code lengths to 16 bits is not optimal, though libjpeg’s authors judged the loss negligible.

Other JPEG Modes and Lossless Coding

T.81 defines four modes of operation (section 4.5):

Sequential DCT-based: the baseline above, in which each block is coded completely before the next.
Progressive DCT-based: all quantized coefficients are buffered and sent in several scans. With spectral selection, each scan carries a band of the zig-zag sequence. With successive approximation, the most significant bits of the coefficients are sent first and the lower bits in later scans. A decoder can therefore show a coarse image early.
Lossless: this mode uses no DCT. A predictor combines up to three previously coded neighbours, to the left, above and above-left, and the difference between the prediction and the actual sample is entropy coded (section 4.4). The standard adds that reducing the input precision by one or more bits first gives more compression, and limits the worst-case sample error to the amount of precision removed.
Hierarchical: the image is coded as a sequence of frames. After the first, differential frames code the difference between the source and a reference reconstructed from earlier frames. With downsampling and upsampling filters this gives a pyramid of resolutions, in the sense of Image Pyramid, which describes Burt and Adelson’s coding of Laplacian bands. The hierarchical mode can also end with a lossless stage.

The baseline process uses Huffman coding, while the extended DCT-based and lossless processes may use either Huffman or arithmetic coding (section 4.6). Colour images are coded component by component. T.81 leaves the colour space to applications (section 4.1). Pillow’s documentation notes that libjpeg converts RGB images to YCbCr by default, and Digital Camera describes how JPEG subsamples the chroma. Pillow exposes subsampling as an option; it does not apply to a single-component greyscale image.

JPEG 2000

JPEG 2000 replaces the block DCT with a multilevel discrete wavelet transform of the whole image, or of tiles if the encoder is asked for them. The options of Pillow 12.0.0, which writes JPEG 2000 through OpenJPEG, show the main choices of the format:

Transform. The irreversible 9/7 wavelet transform is used for lossy coding, and the reversible 5/3 transform for lossless coding. Pillow’s default is the reversible one (irreversible=False).
Resolutions. num_resolutions sets the number of decomposition levels plus one. OpenJPEG 2.5.4 defaults to 6 resolutions (opj_common.h), and Pillow lowers the number for images or tiles too small for them (Jpeg2KEncode.c). A decoder can skip the finest resolutions: Pillow’s reduce discards them on loading, halving the size for each one dropped.
Code blocks. The wavelet coefficients are coded in code blocks. Each side of a code block must lie between 4 and 1,024, and a block may hold at most 4,096 coefficients; OpenJPEG’s default is $64 \times 64$ .
Quality layers. The coded data can be arranged in layers, each specified either as an approximate size reduction (quality_mode="rates") or as a target signal-to-noise ratio in decibels. A decoder can stop after any layer. In OpenJPEG a rate is a compression ratio against the raw image size. A rate of 1 or less, or no layers at all, means lossless coding (j2k.c).
Progression order. LRCP, RLCP, RPCL, PCRL or CPRL sets whether quality layers, resolutions, positions or components come first in the stream. For example, LRCP lets a decoder refine quality as data arrive, and RLCP lets it refine resolution.

So JPEG 2000, as OpenJPEG implements it, has a rate control that a JPEG quality setting lacks: the encoder is given a target size, which j2k.c converts into a byte budget for the layer. In our reading, because the wavelet basis functions overlap and span several scales, there is no fixed $8 \times 8$ grid for errors to line up on. As Whole-Slide Imaging reports from DICOM Supplement 145, JPEG 2000 gives higher compression and fewer artifacts than JPEG, at a higher computational cost.

Properties

Only quantization loses information. The transform is invertible, and the symbol mapping and Huffman coding are lossless. Re-encoding the same quantized coefficients with different Huffman tables changes the file size but not one decoded pixel; the example checks this. JPEG’s lossiness, and the accumulation of errors when an image is decoded and re-encoded that Digital Image notes, come from quantization.
Rate depends on content. At a fixed quality setting the quantization table is fixed, but the number of nonzero coefficients, and so the rate, depends on how much detail the image has. A quality setting does not fix a file size.
Artifacts follow the transform. A block transform quantizes each block independently, so reconstructed blocks no longer join smoothly at their borders. The Discrete Cosine Transform article reports Strang’s remark that this blocking becomes severe as the compression ratio grows. Digital Camera lists block artifacts and “mosquito noise” among compression artifacts. Zeroing high frequencies also blurs texture and causes ringing at edges. In vision pipelines these artifacts are structure that is not in the scene.
The setting is a modelling choice for data. Compression is part of a dataset. Model Deployment reports Parmar et al.’s finding that face images saved as JPEG at Pillow’s default quality of 75 gave an FID of 20.96 against their lossless originals, although the copies were perceptually indistinguishable, and real-world super-resolution methods train on synthetic degradations that include JPEG at random qualities.

Examples

The script below implements the baseline JPEG process for one component, from the level shift to a file on disk, and compares it with Pillow’s JPEG encoder at the same quality setting. It then compares both with Pillow’s JPEG 2000 encoder at the same rate.

Images. The data are two images bundled with scikit-image 0.25.2, each $512 \times 512$ (262,144 pixels): camera, which is greyscale, and astronaut, converted to luma with Pillow’s convert("L"). Nothing in the script is random.

The hand codec follows the six steps above:

the IJG quality rule applied to Table K.1;
quantization rounding half away from zero, as libjpeg 9f’s jcdctmgr.c does;
the zig-zag scan, generated by walking anti-diagonals;
DC differences and (run, size) symbols with ZRL and EOB;
the Annex K.3 Huffman tables, typed in from the BITS and HUFFVAL lists of section K.3.3 and turned into codes by the Annex C rule;
1-bit padding and byte stuffing;
a minimal baseline file containing SOI, DQT, SOF0, two DHT segments, SOS and EOI.

It also computes the first-order entropy bound of the previous section for its own DC and AC symbol streams, plus the amplitude bits, which every code must spend.

Encoder settings. These were fixed in the plan before any run, each for a reason:

Pillow JPEG. The image is in mode "L": one component, so no colour conversion and no chroma subsampling, and the subsampling option is not passed. quality is passed explicitly, so Pillow calls libjpeg with baseline-limited tables, the same tables as the hand codec. progressive=False, because the hand codec is baseline sequential. Pillow is run twice:
- with optimize=False, so that libjpeg writes the same Annex K.3 tables as the hand codec and the two bit streams are directly comparable;
- with optimize=True, to show what image-specific tables save.
Everything else is at its default: libjpeg 9f’s accurate integer DCT, and no smoothing and no restart markers, which are libjpeg’s defaults (jcparam.c) and the values Pillow passes unless asked otherwise (JpegImagePlugin.py).
JPEG 2000. The writer gets no_jp2=True (a raw codestream without the JP2 file boxes) and irreversible=True (the 9/7 transform). It uses one quality layer, given in "rates" mode as the compression ratio $8/b$ , where $b$ is the file rate of Pillow’s optimize=False JPEG at the same quality. The JPEG 2000 file is therefore aimed at the same file size as the JPEG it is compared with. Every other setting is left at its default: 6 resolutions and $64 \times 64$ code blocks (OpenJPEG 2.5.4), and no tiling (Pillow).
Lossless. For a lossless reference, the script writes JPEG 2000 with the reversible 5/3 transform and no layers, and PNG with Pillow’s defaults. It also prints each image’s zeroth-order pixel entropy.

Measures.

Rates are file sizes in bits per pixel. A second rate, “scan bpp”, counts only the entropy-coded data, with stuffed zero bytes removed. For the hand codec it is the exact number of coded bits.
PSNR is computed on the 8-bit decoded image.
Two further columns give the share of quantized AC coefficients that are zero, and the share of the hand codec’s coded bits spent on DC differences.

Planned checks (each with its tolerance):

C0: the images are 2-D uint8 with sides divisible by 8.
C1: the generated zig-zag order matches the table in Pillow’s JPEG plugin.
C2: the quantization table Pillow writes equals the hand codec’s table exactly.
C3: decoding the symbol lists reproduces the quantized coefficients exactly.
C4: Pillow’s decoding of the hand-written file differs from the hand decoder by at most 2 grey levels.
C5: the coded data in the hand-written file have exactly the predicted length.
C6: the hand codec’s coded data are within 1.5% of the size of Pillow’s.
C7: the PSNRs agree within 0.01 dB.
C8: both lossless coders reconstruct exactly.
C9: the JPEG 2000 file is within 3% of its target rate.
C10: decoded pixels are identical with optimize=True and optimize=False.

The tolerances of C4, C6, C7 and C9 were set before the pilot, from a planning run of the same set-up. The first version of that planning script had a fault in the decoder used by the round-trip check: it advanced 15 positions instead of 16 for a ZRL symbol. It was repaired before the plan’s criteria were written.

Planned hypotheses:

H1: optimize=True gives less coded data than optimize=False at every quality. This was expected but not guaranteed, since K.2’s length limiting is not optimal.
H2a: the entropy bound lies below the hand codec’s coded bits.
H2b: the entropy bound lies below Pillow’s optimized coded data.
H3: rate and PSNR both rise strictly with quality, for the hand codec and for Pillow.
H4: JPEG 2000 reaches a higher PSNR than JPEG at the matched rate, at every quality.
H5: the share of zero AC coefficients does not increase with quality.

H2a and H5 hold by construction:

H2a is the Kraft–Gibbs bound derived above. It applies to each of the two symbol streams, and the amplitude bits are the same in both counts.
H5 follows from monotonicity. The coefficients are the same at every quality. The scale $s$ does not increase with $q$ , so no table entry increases. And $\lfloor |c|/Q + \tfrac12 \rfloor$ does not increase as $Q$ grows. A coefficient that is zero at one quality is therefore zero at every lower quality.

For these two, the output illustrates the derivations rather than testing them.

The script uses NumPy 2.3.5, SciPy 1.16.3, scikit-image 0.25.2 and Pillow 12.0.0, which links libjpeg 9f and OpenJPEG 2.5.4. It runs in about a second on one thread, and two runs printed identical output.

import os
os.environ["OPENBLAS_NUM_THREADS"] = "1"  # single-threaded BLAS, set before NumPy is imported
os.environ["OMP_NUM_THREADS"] = "1"
os.environ["MKL_NUM_THREADS"] = "1"
import io
from collections import Counter
import numpy as np
from scipy.fft import dctn, idctn
from skimage import data
from PIL import Image
from PIL.JpegImagePlugin import zigzag_index

# ---------- the codec: T.81 baseline sequential, one component ----------
K1 = np.array([16, 11, 10, 16, 24, 40, 51, 61, 12, 12, 14, 19, 26, 58, 60, 55,       # T.81 Table K.1
               14, 13, 16, 24, 40, 57, 69, 56, 14, 17, 22, 29, 51, 87, 80, 62,
               18, 22, 37, 56, 68, 109, 103, 77, 24, 35, 55, 64, 81, 104, 113, 92,
               49, 64, 78, 87, 103, 121, 120, 101, 72, 92, 95, 98, 112, 100, 103, 99]).reshape(8, 8)
DC_BITS = [0, 1, 5, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]          # T.81 K.3.3.1, Table K.3
DC_VALS = list(range(12))
AC_BITS = [0, 2, 1, 3, 3, 2, 4, 3, 5, 5, 4, 4, 0, 0, 1, 0x7D]       # T.81 K.3.3.2, Table K.5
AC_VALS = bytes.fromhex(
    "01020300041105122131410613516107227114328191a1082342b1c11552d1f0"
    "2433627282090a161718191a25262728292a3435363738393a434445464748494a"
    "535455565758595a636465666768696a737475767778797a838485868788898a"
    "92939495969798999aa2a3a4a5a6a7a8a9aab2b3b4b5b6b7b8b9bac2c3c4c5c6"
    "c7c8c9cad2d3d4d5d6d7d8d9dae1e2e3e4e5e6e7e8e9eaf1f2f3f4f5f6f7f8f9fa")


def ijg_table(q):                       # IJG quality rule (libjpeg jcparam.c), baseline-clipped
    s = 5000 // q if q < 50 else 200 - 2 * q
    return np.clip((K1 * s + 50) // 100, 1, 255)


# zig-zag: walk the anti-diagonals, alternating direction; ZZ[k] = row-major index of the k-th coefficient
ZZ = np.array([r * 8 + c for r, c in sorted(((r, c) for r in range(8) for c in range(8)),
                                            key=lambda p: (p[0] + p[1], p[0] if (p[0] + p[1]) % 2 else -p[0]))])


def encode(img, Q):                     # level shift, 8 x 8 DCT, quantize (round half away from zero)
    h, w = img.shape
    b = img.reshape(h // 8, 8, w // 8, 8).transpose(0, 2, 1, 3).astype(float) - 128
    c = dctn(b, axes=(2, 3), norm="ortho")
    return (np.sign(c) * np.floor(np.abs(c) / Q + 0.5)).astype(int)


def decode(qc, Q):                      # dequantize, inverse DCT, undo level shift, round and clip
    nb, mb = qc.shape[:2]
    rec = idctn(qc * Q, axes=(2, 3), norm="ortho") + 128
    return np.clip(np.round(rec.transpose(0, 2, 1, 3).reshape(nb * 8, mb * 8)), 0, 255).astype(np.uint8)


def size(v):                            # SSSS category, T.81 Tables F.1 and F.2
    return int(abs(v)).bit_length()


def symbols(qc):                        # per block: DC difference, then (run, size) AC symbols, ZRL, EOB
    events, pred = [], 0
    for blk in qc.reshape(-1, 64)[:, ZZ]:
        diff = int(blk[0]) - pred
        pred = int(blk[0])
        ev = [("DC", size(diff), diff)]
        run = 0
        for v in blk[1:]:
            v = int(v)
            if v == 0:
                run += 1
                continue
            while run > 15:
                ev.append(("AC", 0xF0, 0))          # ZRL: sixteen zeros
                run -= 16
            ev.append(("AC", run * 16 + size(v), v))
            run = 0
        if run:
            ev.append(("AC", 0x00, 0))              # EOB
        events.append(ev)
    return events


def unsymbols(events, shape):           # inverse of symbols(), for the round-trip check
    out, pred = np.zeros((len(events), 64), int), 0
    for i, ev in enumerate(events):
        pred += ev[0][2]
        out[i, 0] = pred
        k = 1
        for _, rs, v in ev[1:]:
            if rs == 0x00:
                break
            if rs == 0xF0:
                k += 16
                continue
            k += rs >> 4
            out[i, k] = v
            k += 1
    nat = np.zeros_like(out)
    nat[:, ZZ] = out
    return nat.reshape(shape)


def entropy_bits(events):               # first-order entropy of the DC and AC symbols + amplitude bits
    bits = 0.0
    for kind in ("DC", "AC"):
        n = np.array(list(Counter(s for ev in events for k, s, _ in ev if k == kind).values()), float)
        bits += -np.sum(n * np.log2(n / n.sum()))
    return bits + sum(s & 15 for ev in events for _, s, _ in ev)


def huff_codes(bits, vals):             # T.81 Annex C: canonical codes from BITS and HUFFVAL
    codes, code, i = {}, 0, 0
    for length in range(1, 17):
        for _ in range(bits[length - 1]):
            codes[vals[i]] = (code, length)
            code += 1
            i += 1
        code <<= 1
    return codes


DC_CODES, AC_CODES = huff_codes(DC_BITS, DC_VALS), huff_codes(AC_BITS, AC_VALS)


def scan_bytes(events):                 # Huffman code + amplitude bits, 1-padding, byte stuffing
    parts, dc_bits = [], 0
    for ev in events:
        for kind, sym, v in ev:
            code, n = (DC_CODES if kind == "DC" else AC_CODES)[sym]
            s = sym & 15
            parts.append(format(code, f"0{n}b"))
            if s:                       # v > 0: low s bits of v; v < 0: low s bits of v - 1
                parts.append(format(v if v > 0 else v - 1 + (1 << s), f"0{s}b"))
            dc_bits += (n + s) if kind == "DC" else 0
    bits = "".join(parts)
    nbits = len(bits)
    bits += "1" * (-nbits % 8)
    raw = int(bits, 2).to_bytes(len(bits) // 8, "big")
    return raw.replace(b"\xff", b"\xff\x00"), nbits, dc_bits


def jpeg_file(img, Q, events):          # minimal baseline JPEG: SOI DQT SOF0 DHT DHT SOS data EOI
    h, w = img.shape
    seg = lambda m, p: bytes([0xFF, m]) + (len(p) + 2).to_bytes(2, "big") + p
    dqt = seg(0xDB, bytes([0]) + bytes(int(x) for x in Q.ravel()[ZZ]))
    sof = seg(0xC0, bytes([8]) + h.to_bytes(2, "big") + w.to_bytes(2, "big") + bytes([1, 1, 0x11, 0]))
    dht = seg(0xC4, bytes([0x00] + DC_BITS + DC_VALS) + bytes([0x10] + AC_BITS) + AC_VALS)
    sos = seg(0xDA, bytes([1, 1, 0x00, 0, 63, 0]))
    scan, nbits, dc_bits = scan_bytes(events)
    return b"\xff\xd8" + dqt + sof + dht + sos + scan + b"\xff\xd9", nbits, dc_bits


def entropy_coded_bytes(f):             # length of the scan data in a JPEG file, stuffed zeros removed
    i = 2
    while True:
        m, L = f[i + 1], int.from_bytes(f[i + 2:i + 4], "big")
        if m == 0xDA:
            j = k = i + 2 + L
            while not (f[k] == 0xFF and f[k + 1] != 0x00):
                k += 1
            return (k - j) - f[j:k].count(b"\xff\x00")
        i += 2 + L


def psnr(a, b):
    return 10 * np.log10(255 ** 2 / np.mean((a.astype(float) - b) ** 2))


def pil_save(img, fmt, **kw):
    buf = io.BytesIO()
    Image.fromarray(img).save(buf, fmt, **kw)
    return buf.getvalue()


def pil_load(f):
    return np.asarray(Image.open(io.BytesIO(f)))


# ---------- the comparison ----------
images = {"camera": data.camera(),
          "astronaut": np.asarray(Image.fromarray(data.astronaut()).convert("L"))}
QS = [10, 25, 50, 75, 90]
print("C0 data 2-D uint8, sides divisible by 8:",
      all(i.ndim == 2 and i.dtype == np.uint8 and i.shape[0] % 8 == 0 and i.shape[1] % 8 == 0
          for i in images.values()))
print("C1 zig-zag equals Pillow's table:", all(zigzag_index[ZZ[k]] == k for k in range(64)))
ok = {f"C{i}": True for i in range(2, 11)}
hyp = {h: True for h in ("H1", "H2a", "H2b", "H3", "H4", "H5")}
for name, img in images.items():
    npx = img.size
    bpp = lambda nbytes: 8 * nbytes / npx
    p0 = np.bincount(img.ravel(), minlength=256) / npx
    lossless = {"PNG": pil_save(img, "PNG"),
                "J2K 5/3": pil_save(img, "JPEG2000", no_jp2=True, irreversible=False)}
    err = {k: int(np.abs(pil_load(f).astype(int) - img).max()) for k, f in lossless.items()}
    ok["C8"] &= max(err.values()) == 0
    print(f"\n{name} {img.shape}: pixel entropy {-np.sum(p0[p0 > 0] * np.log2(p0[p0 > 0])):.4f} bpp; lossless "
          + ", ".join(f"{k} {bpp(len(f)):.4f} bpp (max error {err[k]})" for k, f in lossless.items()))
    print("   |       hand codec, standard tables       | Pillow optimize=False  | optimize=True  "
          "|  JPEG 2000 9/7  |  zero    DC")
    print("  q|  PSNR   entropy  scan bpp  file bpp     |  PSNR   scan bpp file  | scan bpp file  "
          "|  PSNR  file bpp |  AC     bits")
    rows = []
    for q in QS:
        Q = ijg_table(q)
        qc = encode(img, Q)
        rec = decode(qc, Q)
        ev = symbols(qc)
        mine, nbits, dc_bits = jpeg_file(img, Q, ev)
        est = entropy_bits(ev)
        fstd = pil_save(img, "JPEG", quality=q, optimize=False, progressive=False)
        fopt = pil_save(img, "JPEG", quality=q, optimize=True, progressive=False)
        dstd = pil_load(fstd)
        fj2k = pil_save(img, "JPEG2000", no_jp2=True, irreversible=True, quality_mode="rates",
                        quality_layers=[8 / bpp(len(fstd))])
        r = dict(q=q, psnr=psnr(img, rec), est=est / npx, scan=nbits / npx, file=bpp(len(mine)),
                 p_psnr=psnr(img, dstd), p_scan=bpp(entropy_coded_bytes(fstd)), p_file=bpp(len(fstd)),
                 o_scan=bpp(entropy_coded_bytes(fopt)), o_file=bpp(len(fopt)),
                 j_psnr=psnr(img, pil_load(fj2k)), j_file=bpp(len(fj2k)),
                 zero=np.mean(qc.reshape(-1, 64)[:, 1:] == 0), dc=dc_bits / nbits)
        rows.append(r)
        print(f"{q:3d}| {r['psnr']:6.3f}  {r['est']:7.4f}  {r['scan']:7.4f}  {r['file']:7.4f}     "
              f"| {r['p_psnr']:6.3f}  {r['p_scan']:7.4f} {r['p_file']:6.4f} | {r['o_scan']:7.4f} {r['o_file']:6.4f} "
              f"| {r['j_psnr']:6.3f}  {r['j_file']:6.4f} | {r['zero']:.4f} {r['dc']:.4f}")
        c = dict(C2=int(np.abs(np.array(Image.open(io.BytesIO(fstd)).quantization[0]).reshape(8, 8) - Q).max()),
                 C3=int(np.sum(unsymbols(ev, qc.shape) != qc)),
                 C4=int(np.abs(pil_load(mine).astype(int) - rec).max()),
                 C5=entropy_coded_bytes(mine) == -(-nbits // 8),
                 C6=100 * abs(entropy_coded_bytes(mine) - entropy_coded_bytes(fstd)) / entropy_coded_bytes(fstd),
                 C7=abs(r["psnr"] - r["p_psnr"]),
                 C9=100 * (r["j_file"] - r["p_file"]) / r["p_file"],
                 C10=int(np.abs(pil_load(fopt).astype(int) - dstd).max()))
        r["checks"] = c
        ok["C2"] &= c["C2"] == 0
        ok["C3"] &= c["C3"] == 0
        ok["C4"] &= c["C4"] <= 2
        ok["C5"] &= c["C5"]
        ok["C6"] &= c["C6"] <= 1.5
        ok["C7"] &= c["C7"] <= 0.01
        ok["C9"] &= abs(c["C9"]) <= 3
        ok["C10"] &= c["C10"] == 0
        hyp["H1"] &= entropy_coded_bytes(fopt) < entropy_coded_bytes(fstd)
        hyp["H2a"] &= est <= nbits
        hyp["H2b"] &= est <= 8 * entropy_coded_bytes(fopt)
        hyp["H4"] &= r["j_psnr"] > r["p_psnr"]
    print("  q| C2 qtable diff  C3 round-trip errors  C4 max|Pillow-mine|  C5 writer  "
          "C6 scan diff %  C7 PSNR diff dB  C9 J2K rate dev %  C10 opt-std")
    for r in rows:
        c = r["checks"]
        print(f"{r['q']:3d}| {c['C2']:14d}  {c['C3']:20d}  {c['C4']:19d}  {str(c['C5']):9s}  "
              f"{c['C6']:13.3f}  {c['C7']:15.4f}  {c['C9']:+17.3f}  {c['C10']:10d}")
    inc = lambda key: all(a[key] < b[key] for a, b in zip(rows, rows[1:]))
    hyp["H3"] &= inc("psnr") and inc("file") and inc("p_psnr") and inc("p_file")
    hyp["H5"] &= all(a["zero"] >= b["zero"] for a, b in zip(rows, rows[1:]))
print("\nchecks:", " ".join(f"{k} {'held' if v else 'FAILED'}" for k, v in ok.items()))
print("hypotheses:", " ".join(f"{k} {'held' if v else 'FAILED'}" for k, v in hyp.items()))

C0 data 2-D uint8, sides divisible by 8: True
C1 zig-zag equals Pillow's table: True

camera (512, 512): pixel entropy 7.2317 bpp; lossless PNG 4.3431 bpp (max error 0), J2K 5/3 3.9550 bpp (max error 0)
   |       hand codec, standard tables       | Pillow optimize=False  | optimize=True  |  JPEG 2000 9/7  |  zero    DC
  q|  PSNR   entropy  scan bpp  file bpp     |  PSNR   scan bpp file  | scan bpp file  |  PSNR  file bpp |  AC     bits
 10| 28.428   0.1685   0.2179   0.2278     | 28.428   0.2181 0.2288 |  0.1721 0.1790 | 30.344  0.2263 | 0.9777 0.2196
 25| 30.807   0.3758   0.4125   0.4230     | 30.807   0.4135 0.4247 |  0.3793 0.3869 | 32.695  0.4180 | 0.9398 0.1408
 50| 32.600   0.6324   0.6576   0.6696     | 32.599   0.6592 0.6729 |  0.6410 0.6484 | 35.403  0.6630 | 0.8935 0.1034
 75| 35.080   1.0161   1.0328   1.0464     | 35.081   1.0368 1.0520 |  1.0299 1.0398 | 39.593  1.0496 | 0.8262 0.0774
 90| 40.340   1.7701   1.7855   1.8008     | 40.339   1.7959 1.8117 |  1.7924 1.8062 | 46.186  1.8043 | 0.6977 0.0568
  q| C2 qtable diff  C3 round-trip errors  C4 max|Pillow-mine|  C5 writer  C6 scan diff %  C7 PSNR diff dB  C9 J2K rate dev %  C10 opt-std
 10|              0                     0                    1  True               0.070           0.0007             -1.054           0
 25|              0                     0                    1  True               0.229           0.0002             -1.567           0
 50|              0                     0                    1  True               0.241           0.0002             -1.474           0
 75|              0                     0                    1  True               0.386           0.0004             -0.232           0
 90|              0                     0                    1  True               0.576           0.0009             -0.409           0

astronaut (512, 512): pixel entropy 7.4536 bpp; lossless PNG 4.2435 bpp (max error 0), J2K 5/3 3.8510 bpp (max error 0)
   |       hand codec, standard tables       | Pillow optimize=False  | optimize=True  |  JPEG 2000 9/7  |  zero    DC
  q|  PSNR   entropy  scan bpp  file bpp     |  PSNR   scan bpp file  | scan bpp file  |  PSNR  file bpp |  AC     bits
 10| 28.956   0.2525   0.2907   0.3005     | 28.957   0.2910 0.3014 |  0.2562 0.2630 | 32.425  0.3016 | 0.9643 0.2188
 25| 32.224   0.4700   0.4913   0.5024     | 32.225   0.4919 0.5029 |  0.4761 0.4837 | 36.102  0.5028 | 0.9284 0.1601
 50| 34.746   0.7141   0.7268   0.7390     | 34.747   0.7286 0.7412 |  0.7223 0.7301 | 39.182  0.7404 | 0.8894 0.1277
 75| 37.524   1.0421   1.0545   1.0686     | 37.525   1.0577 1.0725 |  1.0525 1.0630 | 42.223  1.0688 | 0.8385 0.1041
 90| 41.823   1.7250   1.7653   1.7827     | 41.824   1.7747 1.7932 |  1.7440 1.7554 | 46.581  1.7888 | 0.7350 0.0783
  q| C2 qtable diff  C3 round-trip errors  C4 max|Pillow-mine|  C5 writer  C6 scan diff %  C7 PSNR diff dB  C9 J2K rate dev %  C10 opt-std
 10|              0                     0                    1  True               0.073           0.0009             +0.071           0
 25|              0                     0                    1  True               0.112           0.0008             -0.012           0
 50|              0                     0                    1  True               0.239           0.0013             -0.111           0
 75|              0                     0                    1  True               0.303           0.0005             -0.344           0
 90|              0                     0                    1  True               0.530           0.0010             -0.245           0

checks: C2 held C3 held C4 held C5 held C6 held C7 held C8 held C9 held C10 held
hypotheses: H1 held H2a held H2b held H3 held H4 held H5 held

Checks: every planned check held.

C0 and C1 held: both printed True.
C2 and C3 held, with 0 for every quality on both images: Pillow writes exactly the IJG-scaled Table K.1, and the symbols decode back to the quantized coefficients.
C4 held: it is 1 everywhere, within its tolerance of 2. When Pillow decodes the hand-written file, the result differs from the hand decoder’s by at most one grey level. In our reading, this is the difference between libjpeg’s integer inverse DCT and the floating-point one, both rounding to 8 bits. Either way, the hand-written file is a valid baseline JPEG.
C5 held, printing True everywhere: the parsed coded data have exactly the predicted length.
C6 held, with a worst difference of 0.576% (camera, $q = 90$ ). The hand codec’s coded data are slightly smaller than Pillow’s at every quality. Since the quantization tables (C2) and Huffman tables are the same, the two codecs must have quantized some coefficients differently; in our reading, the cause is libjpeg’s integer forward DCT, which is not exact. The output shows the effect on size but not where it occurs.
C7 held, with PSNR differences of at most 0.0013 dB.
C8 held: both lossless coders reconstructed both images exactly.
C9 held. The JPEG 2000 files fell 0.012–1.567% under their target in 9 of the 10 cells, and 0.071% over it in the remaining one (astronaut, $q = 10$ ).
C10 held: changing the Huffman tables did not change a single decoded pixel, as the Properties section requires.

Where the bits go. At the same quality, the two images need different rates. At $q = 50$ the hand codec’s files are 0.6696 bpp for camera and 0.7390 bpp for astronaut, compression ratios of about 11.9 and 10.8. The difference between the file and scan columns is the cost of the headers and tables plus the stuffed bytes. It is about 0.01 bpp for the hand-written files and grows slightly with the rate.

At $q = 10$ , 97.8% of camera’s quantized AC coefficients are zero, and 22% of the coded bits go to DC differences. At $q = 90$ , 69.8% are zero and the DC share is 5.7%. The zero share falls with quality on both images, so H5 held, as its derivation requires.

Fixed against fitted Huffman tables. The entropy column shows what the fixed Annex K.3 tables cost:

At $q = 10$ , the hand codec’s coded bits exceed the entropy bound by 29% on camera (0.2179 against 0.1685 bpp) and by 15% on astronaut.
At $q = 90$ the excess is 0.9% and 2.3%.
Pillow’s optimize=True recovers most of the excess. It reduces the coded data by 21% for camera at $q = 10$ , and its scan rate comes within about 2% of the entropy bound there (0.1721 against 0.1685 bpp).

H1 held at every quality on both images. Its smallest margin is camera at $q = 90$ , 1.7924 against 1.7959 bpp. H2a held in every cell, as its derivation requires. H2b held in every cell too, although Pillow’s symbols come from its own integer DCT; the smallest printed margins are on camera at $q = 10$ and $q = 25$ , 0.1685 against 0.1721 and 0.3758 against 0.3793 bpp.

Rate and distortion. H3 held on both images: each step up in quality raised both the file rate and the PSNR, for the hand codec and for Pillow. At the same quality the two codecs agree on rate and PSNR to the printed tolerances, so their rate–distortion points coincide.

H4 held in every cell. At the matched rate, JPEG 2000’s PSNR exceeds JPEG’s by 1.89–5.85 dB on camera and 3.47–4.76 dB on astronaut, with the largest gap at $q = 90$ on both images. The JPEG 2000 files were slightly smaller than their targets in 9 of 10 cells (C9), so the comparison does not favour JPEG 2000 on size. Another reading of the same table: on camera, JPEG 2000 at 0.4180 bpp reaches 32.695 dB, more than JPEG at $q = 50$ reaches with 0.6729 bpp (32.599 dB). This is one codec implementation of each standard at one set of settings, on two images, with PSNR as the only measure of distortion.

Lossless. The lossless line puts the lossy rates in proportion. Both images have a zeroth-order pixel entropy above 7.2 bits. PNG needs 4.34 and 4.24 bpp, and reversible JPEG 2000 needs 3.96 and 3.85 bpp, about 2:1. So exact storage costs about twice the rate of JPEG at $q = 90$ (1.81 and 1.79 bpp in Pillow’s files), and five to six and a half times its rate at $q = 50$ . Both lossless coders go well below the zeroth-order entropy. As the entropy section notes, that bound ignores the dependence between neighbouring pixels, which, in our reading, both coders’ models exploit.

Common Misconceptions

“Quality 75 means 75% of the information is kept.” The number is an encoder’s index into a table-scaling rule, not a measure of information. In libjpeg it scales T.81’s example table, and other encoders may use other tables or rules. The rate it produces depends on the image: in the example, quality 50 gives 0.67 bpp on one image and 0.74 bpp on the other.
“JPEG has standard quantization and Huffman tables.” T.81 specifies no default tables of either kind. Table K.1 and the K.3 Huffman tables are examples that encoders such as libjpeg adopted.
“Optimizing the Huffman tables lowers the quality.” Entropy coding is lossless. optimize=True changes the file size and not a single decoded pixel, as check C10 shows.
“The DCT is what compresses.” The orthonormal DCT is invertible and preserves energy. Information is lost only in quantization, and bits are saved by entropy coding the many zeros that quantization creates.
“A lossless format can be made smaller by choosing a lower quality.” Quality settings exist only for lossy coders. A lossless coder’s size is fixed by the image and the coder’s model; in the example, two lossless coders give two different sizes for the same exact image.
“Re-saving a JPEG at the same quality changes nothing.” Each decode rounds to 8 bits and each encode quantizes again, so errors can accumulate over repeated re-encoding, as Digital Image notes.

Where It Is Used

Cameras and image files. The image signal processor of a digital camera usually ends with compression, such as JPEG, and Digital Image describes how lossless formats such as PNG and TIFF differ from lossy ones such as JPEG.
Medical and scientific imaging. Whole-Slide Imaging and Digital Pathology describe how slide scanners store gigapixel images with JPEG and JPEG 2000. They cover the ratios at which, according to DICOM Supplement 145’s summary, pathologists found no loss of diagnostic information, and the DICOM attribute that records whether an image has ever been lossy-compressed.
Image quality assessment. PSNR and SSIM list compression among their main uses. Mean Squared Error, SSIM and Image Quality Assessment build JPEG-like distortions by quantizing block DCTs with scaled copies of Table K.1, without the entropy-coding stage that sets the rate.
Multiresolution coding. Image Pyramid describes Burt and Adelson’s coding of quantized Laplacian bands and progressive transmission; JPEG’s hierarchical mode and JPEG 2000’s resolution levels are also multiresolution.
Learned compression. Autoencoder describes the codec of Ballé, Laparra and Simoncelli (2017). It is built from a convolutional analysis transform, a uniform quantizer and a synthesis transform, trained end to end for rate–distortion, and on an independent test set it generally beat JPEG and JPEG 2000 in rate–distortion.
Artefact removal and robustness. Restoration networks are also trained to remove JPEG artifacts, as Super-Resolution notes for SwinIR, and real-world super-resolution models are trained on degradations that include JPEG at random qualities. Deepfake Detection describes detectors trained with JPEG augmentation and evaluated after JPEG compression.