Wait, What?
A black-and-white printer can suggest grey without ever printing a grey pixel.
Floyd–Steinberg dithering works because the algorithm treats every rounding mistake as a quantity that must be carried forward rather than discarded. A pixel that becomes slightly too dark creates an error; that error is distributed to nearby pixels that have not yet been quantized. The eye then integrates the resulting pattern and perceives intermediate tone.
Quick Answer
Learn Floyd–Steinberg through quantization → residual error → the 7/16, 3/16, 5/16, 1/16 diffusion stencil → scan order → boundary handling → colour channels → numerical precision → visual artifacts → production testing. The key idea is not the famous fractions by themselves. It is the conservation and controlled placement of quantization error.
1. Begin With Quantization, Not Dithering
Suppose a grayscale pixel has value 150 on a 0–255 scale, but the output device can represent only black 0 or white 255. A threshold rule might choose white. The quantization error is then 150 − 255 = −105. A naive converter throws that error away. Floyd–Steinberg passes most of it to future pixels.
This gives the learner the first invariant: after a pixel is quantized, its residual error is redistributed into pixels that have not yet been processed. Dithering is therefore a feedback process over a spatial signal.
2. The Classic Diffusion Stencil
For a left-to-right scan, the classic weights are:
current 7/16
3/16 5/16 1/16The four fractions sum to 1. The error is sent to the pixel on the right and three pixels in the next row. If the current quantization error is e, the additions are 7e/16, 3e/16, 5e/16 and e/16 respectively.
The sum matters because, away from image boundaries and clipping, the scheme approximately preserves the accumulated tone error rather than silently losing it.
3. A One-Pixel Worked Example
Take a pixel value of 100 with a two-level threshold at 128. It becomes 0, so the error is +100. The next pixel receives 43.75, the lower-left receives 18.75, the lower pixel receives 31.25, and the lower-right receives 6.25. Those adjusted values are then quantized when their turn arrives.
A beginner should calculate several such steps by hand. This exposes an important fact: the algorithm is stateful. The value being quantized is not always the original image value; it may already include error arriving from earlier pixels.
4. Write the Baseline Algorithm Clearly
for y from 0 to height-1:
for x from 0 to width-1:
old = working[y][x]
new = nearest_palette_value(old)
output[y][x] = new
error = old - new
add 7/16 * error to (x+1, y)
add 3/16 * error to (x-1, y+1)
add 5/16 * error to (x, y+1)
add 1/16 * error to (x+1, y+1)The “working” image should have enough precision to accumulate fractional error. If the implementation repeatedly truncates intermediate values, the intended diffusion process changes.
5. Boundary Conditions Are Part of Correctness
At the left, right and bottom edges, some neighbours do not exist. Never wrap the error around unless the image model explicitly requires toroidal boundaries. The normal implementation simply omits out-of-range updates. This means some residual error is lost at boundaries, which is acceptable and preferable to contaminating unrelated pixels.
6. Scan Order Changes the Texture
Pure left-to-right scanning can create directional patterns because every row propagates error in the same orientation. A common variation is serpentine scanning: process one row left-to-right, the next right-to-left, and mirror the diffusion stencil on alternate rows. This can reduce directional bias, although the exact visual result depends on the image and palette.
Professional learning begins when the student stops asking only “is the code correct?” and also asks “what visual artifact does this implementation choice create?”
7. Understand What the Algorithm Is Optimizing — and What It Is Not
Floyd–Steinberg is a local error-diffusion heuristic. It does not globally optimize a formal perceptual loss over the whole image. It works well because the spatial distribution of binary or low-palette pixels can preserve local average tone and push quantization noise into patterns that are often less objectionable to human vision.
That distinction matters when comparing it with ordered dithering, blue-noise masks, modern halftoning methods or perceptually optimized palette conversion.
8. Move From Grayscale to Colour Carefully
With colour images, one simple method diffuses error independently per RGB channel. But RGB Euclidean distance is not perceptually uniform, and the nearest palette entry may not be the perceptually nearest colour. Production systems may perform palette search in another colour space, use precomputed lookup structures, or optimize for device-specific colour behaviour.
The teaching progression should therefore separate two jobs: choosing the quantized colour and diffusing the resulting error. Floyd–Steinberg specifies the latter pattern; palette design is a related but distinct problem.
9. Precision, Clamping and Numeric Type Choices
- Floating point: easiest for learning and normally clear enough for offline image processing.
- Fixed point: useful when reproducibility or hardware constraints matter; the denominator 16 makes integer-scaled arithmetic convenient.
- Clamping: decide whether accumulated working values are clipped immediately, before quantization, or only when needed. Different choices alter error flow.
- In-place versus buffer: in-place working buffers are memory efficient, but do not overwrite the original image if it will be needed for comparison or another pipeline stage.
10. Complexity Is Simple; Memory Traffic Is Not
Each pixel is processed once, so the algorithm is O(width × height). The extra storage can be O(width) if only the current and next error rows are retained. At professional scale, however, cache locality, image format conversion, palette lookup and memory bandwidth can dominate arithmetic cost.
The left-to-right dependency also limits straightforward parallelism: neighbouring outputs depend on previously diffused error. Parallel image systems may tile carefully, accept seams, use alternative dithering strategies, or redesign the diffusion schedule.
11. Compare With Ordered Dithering
Ordered dithering uses a threshold matrix and can process pixels with much less data dependence, making it highly parallel and predictable. Floyd–Steinberg often produces a more noise-like local tone but introduces sequential dependencies. Neither method is universally “better.” The application may care about print texture, animation stability, GPU throughput, reproducibility, file format, or palette size.
12. Validate With Images Designed to Expose Failure
Do not test only on photographs. Use smooth gradients, flat mid-grey fields, diagonal ramps, thin lines, checkerboards, saturated colour patches and near-threshold values. These reveal banding, worm-like textures, directional bias, clipping and palette mistakes far more clearly than a visually busy photograph.
Common Failure States
- Diffusing the original pixel value instead of the quantization residual.
- Applying weights to neighbours that have already been processed.
- Using integer arithmetic that truncates almost all small error contributions.
- Forgetting to mirror the stencil during serpentine scanning.
- Allowing out-of-bounds updates to wrap into another row.
- Assuming independent RGB error is perceptually optimal.
- Comparing dithered images only by pixel-wise numerical error and ignoring perceived texture.
Practice Ladder
- Beginner: quantize a ten-pixel grayscale row by threshold only, then calculate the error after each decision.
- Foundation: implement classic Floyd–Steinberg on a small grayscale matrix using floating point.
- Intermediate: add serpentine scanning and compare the resulting gradient texture.
- Advanced: implement RGB palette quantization with explicit nearest-colour search and channel-wise error diffusion.
- Professional: build a streaming O(width)-memory version, benchmark memory traffic, and compare against ordered dithering on quality and throughput.
- Verification: compare selected outputs with established image libraries that expose Floyd–Steinberg dithering.
Learning Hall Boundary
This article owns Floyd–Steinberg error diffusion as an algorithm-learning job: quantization residuals, diffusion weights, scan order, numerical implementation and image-quality trade-offs. It does not replace broader image-processing, colour-science or compression material.
Evidence Boundary
Robert W. Floyd and Louis Steinberg published “An Adaptive Algorithm for Spatial Greyscale” in Proceedings of the Society for Information Display, volume 17, number 2, 1976, pages 75–77. Current image software continues to expose Floyd–Steinberg-style dithering; the algorithm remains a canonical example of error diffusion. Its classic 7/16, 3/16, 5/16 and 1/16 coefficients should be taught as the historical stencil, while production implementations must still define palette selection, scan order, precision and edge policy explicitly.
Professional rule: you understand Floyd–Steinberg when you can trace where every unit of quantization error goes, predict how implementation choices change visible texture, and explain when a different dithering strategy is the better engineering choice.
eduKate Sengkang 