Encoder Implementation | Sahithyan's Notes

This note gives a working baseline encoder and surveys the codecs that implement the standard.

Baseline Encoder

The encoder below writes a baseline stream with 4:2:0 subsampling and the Annex K tables. It uses dct_matrix and dct2 from the DCT note. ZIGZAG comes from the zig-zag scan, the Huffman constants from the standard Huffman tables and the quantization tables Q_LUM and Q_CHR from the Annex K tables, flattened row by row.

Steps:

Scale the quantization tables for the chosen quality.
Convert to YCrCb, pad to a multiple of 16 pixels by replicating the edge pixels, and average each 2x2 group of Cb and Cr.
Visit the MCUs in raster order. In each, visit the blocks in the order Y top-left, Y top-right, Y bottom-left, Y bottom-right, Cb, Cr.
For each block, level shift, apply the DCT, divide by the table, round and scan in zig-zag order.
Code the DC difference and the AC run and size symbols, writing bits with byte stuffing.
Pad the last byte with 1 bits.
Write the headers, then the entropy-coded data, then EOI.

Preprocessing Code

def scale_table(base, quality):
    s = 5000 / quality if quality < 50 else 200 - 2 * quality
    return [min(255, max(1, int((s * q + 50) // 100))) for q in base]

def rgb_to_ycc(r, g, b):
    y = 0.299 * r + 0.587 * g + 0.114 * b
    cb = -0.168736 * r - 0.331264 * g + 0.5 * b + 128
    cr = 0.5 * r - 0.418688 * g - 0.081312 * b + 128
    return y, cb, cr

Quantization Code

T = dct_matrix(8)

def round_half_away(x):
    return int(x + 0.5) if x >= 0 else -int(-x + 0.5)

def quantize_block(block, Q):
    """block[y][x]: 8x8 level-shifted samples. Returns 64 coefficients in zig-zag order."""
    F = dct2(block, T)
    flat = [F[v][u] for v in range(8) for u in range(8)]
    return [round_half_away(flat[ZIGZAG[k]] / Q[ZIGZAG[k]]) for k in range(64)]

Entropy Coding Code

make_huffman applies the canonical code assignment from the Huffman tables. category and extra_bits implement the magnitude categories.

def make_huffman(bits, vals):
    """Returns {symbol: (code, length)}."""
    table, code, k = {}, 0, 0
    for length in range(1, 17):
        for _ in range(bits[length - 1]):
            table[vals[k]] = (code, length)
            code += 1
            k += 1
        code <<= 1
    return table

class BitWriter:
    def __init__(self):
        self.out, self.acc, self.n = bytearray(), 0, 0

    def put(self, code, length):
        self.acc = (self.acc << length) | code
        self.n += length
        while self.n >= 8:
            byte = (self.acc >> (self.n - 8)) & 0xFF
            self.out.append(byte)
            if byte == 0xFF:
                self.out.append(0x00)          # byte stuffing
            self.n -= 8
        self.acc &= (1 << self.n) - 1

    def flush(self):
        if self.n:
            self.put((1 << (8 - self.n)) - 1, 8 - self.n)   # pad with 1 bits

def category(a):
    return abs(a).bit_length()

def extra_bits(a, s):
    return a if a > 0 else a + (1 << s) - 1

def encode_block(zz, prev_dc, dc_tab, ac_tab, bw):
    """Writes one block. Returns its DC value, the predictor for the next block."""
    diff = zz[0] - prev_dc
    s = category(diff)
    bw.put(*dc_tab[s])
    if s:
        bw.put(extra_bits(diff, s), s)
    run = 0
    for k in range(1, 64):
        v = zz[k]
        if v == 0:
            run += 1
            continue
        while run > 15:
            bw.put(*ac_tab[0xF0])              # ZRL
            run -= 16
        s = category(v)
        bw.put(*ac_tab[(run << 4) | s])
        bw.put(extra_bits(v, s), s)
        run = 0
    if run > 0:
        bw.put(*ac_tab[0x00])                  # EOB
    return zz[0]

Stream Assembly Code

def segment(marker, payload):
    return bytes([0xFF, marker]) + (len(payload) + 2).to_bytes(2, "big") + payload

def encode_jpeg(rgb, width, height, quality=75):
    """rgb[y][x] = (r, g, b) with values 0 to 255. Returns the bytes of a JPEG file."""
    ql, qc = scale_table(Q_LUM, quality), scale_table(Q_CHR, quality)
    mw, mh = (width + 15) // 16, (height + 15) // 16      # MCUs across and down
    W, H = mw * 16, mh * 16

    Y = [[0.0] * W for _ in range(H)]
    Cb = [[0.0] * W for _ in range(H)]
    Cr = [[0.0] * W for _ in range(H)]
    for y in range(H):
        for x in range(W):
            r, g, b = rgb[min(y, height - 1)][min(x, width - 1)]   # replicate edges
            Y[y][x], Cb[y][x], Cr[y][x] = rgb_to_ycc(r, g, b)

    def half(P):
        return [[(P[2*y][2*x] + P[2*y][2*x+1] + P[2*y+1][2*x] + P[2*y+1][2*x+1]) / 4
                 for x in range(W // 2)] for y in range(H // 2)]
    Cb, Cr = half(Cb), half(Cr)

    def block_at(P, bx, by):
        return [[P[by * 8 + y][bx * 8 + x] - 128 for x in range(8)] for y in range(8)]

    dc = [make_huffman(DC_LUM_BITS, DC_LUM_VALS), make_huffman(DC_CHR_BITS, DC_CHR_VALS)]
    ac = [make_huffman(AC_LUM_BITS, AC_LUM_VALS), make_huffman(AC_CHR_BITS, AC_CHR_VALS)]
    bw, pred = BitWriter(), [0, 0, 0]
    for my in range(mh):
        for mx in range(mw):
            # (component, plane, block column, block row, quantization table, table set)
            blocks = [(0, Y, 2*mx,   2*my,   ql, 0), (0, Y, 2*mx+1, 2*my,   ql, 0),
                      (0, Y, 2*mx,   2*my+1, ql, 0), (0, Y, 2*mx+1, 2*my+1, ql, 0),
                      (1, Cb, mx, my, qc, 1),        (2, Cr, mx, my, qc, 1)]
            for comp, P, bx, by, Q, t in blocks:
                zz = quantize_block(block_at(P, bx, by), Q)
                pred[comp] = encode_block(zz, pred[comp], dc[t], ac[t], bw)
    bw.flush()

    def dht(cls, i, bits, vals):
        return bytes([cls << 4 | i]) + bytes(bits) + bytes(vals)

    out = bytearray(b"\xFF\xD8")                                          # SOI
    out += segment(0xE0, b"JFIF\x00" + bytes([1, 1, 0]) + (1).to_bytes(2, "big") * 2
                         + bytes([0, 0]))                                  # APP0
    out += segment(0xDB, bytes([0]) + bytes(ql[ZIGZAG[k]] for k in range(64))
                         + bytes([1]) + bytes(qc[ZIGZAG[k]] for k in range(64)))   # DQT
    out += segment(0xC0, bytes([8]) + height.to_bytes(2, "big") + width.to_bytes(2, "big")
                         + bytes([3, 1, 0x22, 0, 2, 0x11, 1, 3, 0x11, 1]))         # SOF0
    out += segment(0xC4, dht(0, 0, DC_LUM_BITS, DC_LUM_VALS) + dht(1, 0, AC_LUM_BITS, AC_LUM_VALS)
                         + dht(0, 1, DC_CHR_BITS, DC_CHR_VALS) + dht(1, 1, AC_CHR_BITS, AC_CHR_VALS))
    out += segment(0xDA, bytes([3, 1, 0x00, 2, 0x11, 3, 0x11, 0, 63, 0]))           # SOS
    out += bw.out + b"\xFF\xD9"                                                     # data, EOI
    return bytes(out)

Encoder Checks

The output starts with FF D8 and ends with FF D9
Inside the entropy-coded data, every FF is followed by 00
A standard decoder opens the file. Any such decoder works, since the stream is valid baseline JPEG
The quantization and Huffman tables in the DQT and DHT segments match the ones libjpeg writes for 4:2:0 at the same quality. libjpeg puts each table in its own segment
A flat image gives, for every block after the first block of each component, a DC difference of 0 and an AC part of a single EOB

The code above was run on a 75x53 test image at quality 90. libjpeg decoded the result without error, and the decoded image had a PSNR of 27.9 dB, within 0.02 dB of libjpeg’s own encoder on the same input. The entropy-coded data is not byte-identical to libjpeg’s, which uses integer arithmetic for the colour conversion and DCT.

Codecs

The standard fixes the compressed stream and the decoder. The encoder is free to choose the quantization tables, the Huffman tables, the chroma subsampling, the scan layout and every quantized value. Codecs differ in how well they use this freedom.

libjpeg
Reference implementation from the Independent JPEG Group (first released in 1991). Source of the quality scaling formula. Most software descends from its baseline and progressive encoders.
libjpeg-turbo
Fork of libjpeg with SIMD-accelerated DCT, colour conversion, sampling and Huffman coding. Keeps the libjpeg API and produces the same kind of stream, several times faster. Common default in browsers and operating systems.
MozJPEG
Fork of libjpeg-turbo from Mozilla, tuned for file size. It applies the optimizations below and produces standard streams that any decoder reads.
Guetzli
Encoder from Google that searches for quantization choices using a perceptual model. Very slow, and produces smaller files than libjpeg at the same perceived quality.
Hardware and GPU codecs
Fixed-function blocks in cameras and phones, and GPU libraries such as nvJPEG. They trade compression efficiency for throughput, usually with fixed tables.
Platform codecs
Image frameworks of operating systems, such as Apple ImageIO and Windows Imaging Component, wrap one of these or their own implementation.

All of them decode any baseline stream. The compressed size of the same image can differ by a large margin between encoders, while the quality settings are numerically the same.

Encoder Optimizations

Optimized Huffman tables
Count the symbol frequencies of the whole image in a first pass, then build the codes for that distribution. Standard tables are fitted to typical photographs and cost more on other content.
Custom quantization tables
Tables tuned for a metric such as PSNR or SSIM, or for a specific viewing distance, replace the Annex K tables.
Trellis quantization
Chooses the quantized values by rate-distortion cost, described below.
Progressive scan scripts
The split of coefficients over scans is chosen to compress well. Grouping similar statistics in a scan lets the Huffman tables fit each scan.
Overshoot deringing
Near a sharp edge on a saturated background, decoders clamp values above 255. The encoder can raise those pixels beyond 255 before the DCT. The clamp restores them, and the block needs fewer high-frequency coefficients.
Chroma subsampling choice
Photographs use 4:2:0. Text and sharp coloured edges use 4:4:4 to avoid colour bleeding.

Trellis Quantization

Treats the rounding of each coefficient as a choice. For every block, it picks the quantized values that minimize the rate-distortion cost.

J = D + \lambda R

Here:

$D$: squared error between the original and the dequantized coefficients
$R$: number of bits the choice costs after run-length and Huffman coding
$\lambda$: weight that sets the exchange rate between error and bits

Rounding a coefficient of magnitude 1 to 0 often removes a whole run symbol and a long Huffman code, and costs little error. Trellis quantization therefore zeroes many isolated small values that plain rounding keeps.

These produce streams that are still baseline or progressive JPEG. A typical result is a file about 10 percent smaller than libjpeg at the same quality.