Floyd-Steinberg Dithering Algorithm | Hacker News Reader

Floyd-Steinberg Dithering Algorithm

en.wikipedia.org

11 pointsycollette7 comments

I've improved FS dithering algorithm in pngquant. In color images standard Floyd-Steinberg tends to add noise and make whole images look fuzzy. Remapping error from high-error areas is diffused to low-error areas, which makes otherwise good areas look noisier. This is why graphics programs make dithering optional, because it is a trade-off: you either have posterization, but a cleaner look, or fuzzier images due to error diffusion.

In pngquant I have adaptive diffusion that is enabled only in areas of the image that really need it, so you still get dithered gradients, but don't get as much noise added to the image overall, which makes it look cleaner and compress better.

Thank you for your work!

What sort of heuristic do you use to determine what areas need it? This seems like something a neural network would excel at.

The actual implementation is bit of a fudge for performance reasons, but the general idea is based around amount of entropy: if a patch of an image already contains noise or intricate details, then I don't disturb it further with dithering. If it's flat, then it's safe to dither.

I also use Sobel edge detection and suppress diffusion at the edges, which fixes a particular quirk of FS where error is accumulated throughout a flat area and gets countered only at the edge when color changes (e.g. if an area should be brighter than the brightest color you have in your palette, dithering is unable to fix it, but all the "needs to be brighter!!!" error will accumulate and blow on next pixel that was supposed to be dark).

Just a shout out to this commenter. He's quite the expert on all things image. And from what I gather he's done quite a bit with image processing in Rust also.

I don't know what the context of the original post is, but I implemented this algo in Canvas/JS some time ago https://tgiachett.github.io/canvas-floyd-steinberg-dither/ It's a little rough around the edges, but I think the code is still readable.

thanks for the link :) I will check that. I certainly will try this using processing. There is already a video on youtube which details how to do this.

Reply on news.ycombinator.com