Counting LZW codes to see why dithered GIFs come out bigger

#webdev #javascript

When someone says "turn dithering off and the GIF gets smaller", I want a number I can reproduce before I repeat it in a code review. File size alone does not say why, so I wrote a script that counts how many codes a GIF-style LZW encoder emits for the same frames with dithering off and on. It needs Pillow and numpy and runs locally, so nothing leaves the machine, which matters when the animation is a pre-release product screen.

The sample is MORPH.gif from Wikimedia Commons, by Kowloonese, CC BY-SA 3.0: 675×599, 10 frames, 100 ms each, 3,003,893 bytes. It is a photo-like fade with text, and nearly every pixel changes between frames. I blurred each frame slightly (Gaussian radius 0.8) to flatten noise already baked into the original. That blur is my own processing, so every number below belongs to the blurred copy. One sample, one laptop, one run each, sizes in plain bytes.

The script

It builds one median-cut palette for all frames, maps each frame onto it with dithering off and then Floyd–Steinberg on, and runs a plain LZW over each frame's index stream. The coder follows the GIF idea: 8-bit minimum code size, table reset at 4096 entries. It counts codes instead of writing bits, so it models the encoder and is not a GIF writer.

import numpy as np
from PIL import Image, ImageFilter, ImageSequence

def codes(data):
    d, nxt, cur, n = {}, 258, b"", 0
    for ch in data:
        t = cur + bytes([ch])
        if len(t) == 1 or t in d:
            cur = t
            continue
        n, d[t], nxt, cur = n + 1, nxt, nxt + 1, bytes([ch])
        if nxt >= 4096:
            n, d, nxt = n + 1, {}, 258
    return n + 1

N = 32
fr = [f.convert("RGB").filter(ImageFilter.GaussianBlur(0.8)) for f in ImageSequence.Iterator(Image.open('MORPH.gif'))]
pal = Image.fromarray(np.vstack(fr)).quantize(N, Image.MEDIANCUT, dither=Image.NONE)
for name, mode in (("off", Image.NONE), ("on", Image.FLOYDSTEINBERG)):
    print(name, sum(codes(np.array(f.quantize(palette=pal, dither=mode)).tobytes()) for f in fr))

With N = 32 it printed:

off 418303
on 628637

What the counts say

Dithering took the code count from 418,303 to 628,637 at 32 colours, which is +50.3%. Setting N = 256 gave 964,706 and 1,273,047, which is +32.0%. The sample has 4,043,250 pixels, so each code covers 9.67 pixels without dithering and 6.43 with it at 32 colours, and 4.19 against 3.18 at 256. A side check on the share of pixels equal to their left neighbour (not in the listing, to keep it short) fell from 85.8% to 55.8% at 32 colours.

Real files tell the same story. I saved the same indexed frames as GIFs and ran gifsicle -O3, which barely helped because every frame changes. At 32 colours they came to 572,768 bytes without dithering and 861,321 with it, +50.4%. At 256 colours: 1,364,178 and 1,800,055, +32.0%. Code count and byte count grow almost in step. Bytes × 8 ÷ codes works out near 10.95 bits per code at 32 colours and 11.31 at 256, inside the 9 to 12 bit range a GIF code can use.

Why not just compare file sizes? Because they can differ for reasons unrelated to dithering, such as a local palette or a transparency trick. The code count depends only on the index stream, so it isolates what the dithering switch touches. When the two numbers move together, as they do here, I trust the explanation a bit more. If they had diverged, I would have gone looking for a second effect before writing anything down.

Why I think it happens

This part is an inference the script does not prove. LZW builds its dictionary from strings that repeat. Without dithering, a flat region is a long run of one index, so the dictionary learns long strings and each code swallows many pixels. Error diffusion scatters neighbouring indices to fake in-between colours, which breaks those runs. The left-neighbour numbers fit that story, but I did not test it by dithering only part of a frame.

Two limits on the counter: the files use gifsicle's optimized frames while my counter reads full-frame streams, so the two are close but not the same quantity. And "dithering" here means Floyd–Steinberg only, not ordered patterns.

Trying the same switch in a tool

If you want to see the effect without a script, ImgIng ( https://imging.ai/ ) has an animation workshop in the desktop browser where colour count and dithering can be set by hand for GIF output. On the same MORPH.gif, loaded as the original and not my blurred copy, its export was 811,310 bytes at 32 colours with dithering off and 1,110,431 with it on, +36.9%. The gap differs from the script's +50.3% because the source, palette and encoder differ. At 256 colours the gap shrank to +0.7%, 1,525,126 against 1,535,115. My guess is that the source already behaves like a 256-colour image, so dithering has little error to spread, but I did not verify that. In my network capture, compression sent no request carrying the file.

What this does not cover

This is one photographic fade, 10 frames, about one second long. Screen recordings with flat UI colours, long clips, ordered dithering and frame dropping were not tested, and a flat-colour animation may show a much smaller gap. Dithering exists to hide banding in gradients, and I did not measure that, so whether the smaller file looks acceptable is a call to make by eye on your own content. If you copy anything, copy the script, and run it on the file and palette size you actually ship. If the gap on your file is a few percent, dithering is not your problem, and frame count or dimensions deserve the time instead.

DEV Community