Banding, Bit Depth, and the Trade-offs of Error Diffusion Dither

A smooth gradient written into 8-bit storage does not stay smooth. The stored values are integers, and the luminance step between adjacent integers is not constant in perceptual terms: because the transfer function compresses light, an increment of one code near black is a much larger relative luminance change than an increment near white. The result is that a dark, slow gradient crosses the thresholds where the eye can detect a difference, and the transition appears as a visible contour line rather than a ramp. Dithering does not add bit depth; it trades a regular error for an irregular one that the eye averages away.

Where the bands come from

The condition for a contour to be invisible is that the quantization step, measured in luminance, be below the contrast detection threshold. The eye’s ability to detect a small luminance step between adjacent regions is described by the contrast sensitivity function, which depends on spatial frequency and background luminance. On a bright background, a step of 1% of luminance is usually invisible; in the shadows, sensitivity is different, and the same relative step can be visible. The problem with an 8-bit sRGB ramp is that the code steps are far larger than 1% in relative terms near black.

Quantify it. The sRGB transfer function maps code to linear light with a curve whose slope near black is set by the 12.92 linear segment. From code 0 to code 1, linear luminance changes from 0 to $1/255 / 12.92 \approx 0.000304$ of peak, which is a relative step of infinity against black but a step of a few parts in ten thousand against white. In the middle of the range, around code 128, a single code step is closer to 0.7% of the local luminance, which is at the edge of visibility on a bright display. In the shadows the steps are larger as a fraction of the local value, which is where contours on a night sky or a vignette appear first.

Region of the range	Approx. code step	Linear step vs. local luminance
Code 1–2	1/255	large relative change, near black
Code 128–129	1/255	~0.7%
Code 254–255	1/255	~0.4%
10-bit equivalent	1/1023	~4× smaller everywhere

The table explains why 8-bit is enough for photographic content but not for synthetic gradients: photography carries spatial noise that masks the contours, while a synthetic ramp is noise-free and exposes the quantization at exactly the frequencies the eye detects most easily. It also explains why 10-bit displays exist — the fourth column shows that one extra bit divides every step by about four, pushing the steps below the visibility threshold across most of the range, but not eliminating the need for dither on the remaining darkest steps.

Ordered dither and its Bayer ancestor

The simplest dither adds a deterministic pattern of offsets before quantization. A Bayer matrix is a square arrangement of threshold values distributed so that the pattern has no low-frequency content: the 4×4 Bayer matrix spreads 16 threshold values evenly across the unit square, and repeated tiles produce a noise-like texture whose lowest spatial frequency is set by the tile size.

The operation is a comparison per pixel: add the threshold offset scaled to one quantization step, then round. Pixels whose fractional error is above their threshold round up, those below round down, and the local average reproduces the intended value to within a fraction of a step. The cost is one add and one compare per channel, and the pattern is static, so it is cheap in both instructions and memory.

The trade-off is visible as texture. The Bayer pattern has residual energy at low spatial frequencies, so a dithered flat field shows a faint structure that is more objectionable than the banding it replaces, especially in animation where a static pattern swims against moving content. Larger matrices push the structure to higher frequencies where the eye is less sensitive, at the price of a coarser quantization of the threshold — a 4×4 matrix has 16 levels, a 2×2 has 4.

Ordered dither is deterministic and therefore reproducible and independent of scan order. That determinism is also its weakness on animated content: the same pixel receives the same offset every frame, so the pattern does not move with the image, and the eye locks onto it. Random dither fixes the locking by drawing the offset from a fresh noise sample, at the cost of a noise generator per pixel and a visibly noisier image at low bit depths, because white noise has flat spectrum and its low frequencies are not masked.

Error diffusion and noise shaping

Floyd–Steinberg error diffusion is the other family. Instead of adding a random or ordered offset and discarding the residual, it keeps the residual and pushes it to not-yet-processed neighbours. Quantize the current pixel; compute the error, the difference between the intended value and the quantized one; distribute a weighted fraction of that error to the pixels to the right and below, which have not been processed yet. When those pixels are quantized, they have been adjusted so that the local running total of the error tends toward zero.

The weighting is what shapes the noise. The original Floyd–Steinberg kernel distributes 7/16 of the error to the right neighbour, 3/16, 5/16, and 1/16 to the three lower neighbours, summing to 1. Those fractions are not arbitrary: they place most of the energy along the scan direction and diagonally below, which pushes the resulting noise to high spatial frequencies and low visibility. The shape of the noise spectrum is a consequence of the kernel, and changing the kernel changes the texture.

Error diffusion preserves local average exactly in a way that ordered dither does not: because the total error is conserved and pushed forward rather than discarded, a uniform field quantizes to a pattern whose running sum matches the intended value. The result on a smooth ramp is no bands and little low-frequency texture, at a higher cost — several multiplies per channel and, more importantly, a data dependency that makes the operation sequential along each row. The right-neighbour term means pixel $n$ depends on pixel $n-1$, so error diffusion does not parallelize across a row the way ordered dither does.

/* Floyd-Steinberg on one row of a greyscale image, values in [0,255]. */
void error_diffuse_row(const float *in, unsigned char *out, int w,
                       float *err_next, float *err_cur) {
    for (int x = 0; x < w; x++) {
        float v = in[x] + err_cur[x];
        int q = (int)(v + 0.5f);
        if (q < 0) q = 0; else if (q > 255) q = 255;
        float e = v - q;               /* keep the error, do not discard it */
        out[x] = (unsigned char)q;
        if (x + 1 < w)
            err_cur[x + 1] += e * (7.0f / 16.0f);
        err_next[x]     += e * (5.0f / 16.0f);
        if (x > 0)
            err_next[x - 1] += e * (3.0f / 16.0f);
        if (x + 1 < w)
            err_next[x + 1] += e * (1.0f / 16.0f);
    }
}

The two-row state (the current row’s forward error and the next row’s collected error) is the minimum needed to run the serpentine or raster scan; the 5/16 term lands on the pixel directly below, the 3/16 and 1/16 on the diagonals. Serpentine scanning alternates direction per row, which reduces the directional bias of the pattern at the cost of carrying the error in the other direction on alternate rows.

What breaks

Error diffusion fails on the same content where it is most attractive. A very slow ramp near black can still show a residual pattern if the error buffer does not accumulate enough to cross a whole code step; the remedy is a larger number of bits in the accumulator, not a different kernel. High-contrast edges can produce worm trails, where the error propagates along a line and visibly clumps instead of dispersing, an artifact that motivated the many kernel variants with wider error spread.

The sequential dependency is a real cost on wide images: a 4K row is about 3840 pixels, and the chain of right-neighbour dependencies is that long, which means the operation is latency-bound when done naively and needs to be blocked across rows or performed on the GPU in a wavefront pattern that respects the dependency. Ordered dither, being independent per pixel, is trivially parallel.

Dithering interacts with compression. A dithered image is noisier than a clean ramp, and block-based compression such as JPEG or the DCT family in video spends bits encoding the noise, so dithering before compression either inflates the bit rate or, when the noise is stripped by quantization, reappears as banding in the decoded output. The rule for delivery pipelines is to dither at the last stage, after compression and scaling, which is why display pipelines and video outputs apply dither at the output rather than in the source.

Bit depth at the source does not protect the destination. A 16-bit render of a gradient must still be reduced to the 8-bit output, and the reduction is a quantization, so the dither belongs at that reduction. The relationship between the high-bit render target and the encoded output is the same one described in the sRGB transfer function, and the same concern about doing arithmetic in the right space is behind the choice of where dithering happens, which is the linear-light argument.