3 ms·

Floyd-Steinberg Dithering Algorithm

11 points by ycollette 6y ago

pornel 6y ago
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.
- bjeds 6y ago
  Thank you for your work!
- nickysielicki 6y ago
  What sort of heuristic do you use to determine what areas need it? This seems like something a neural network would excel at.
  - pornel 6y ago
    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).
- tobestobestobes 6y ago
  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.
tobestobestobes 6y ago
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/ https://tgiachett.github.io/canvas-floyd-steinberg-dither/ It's a little rough around the edges, but I think the code is still readable.
- ycollette 6y ago
  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.

11 points by ycollette 6y ago

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.

bjeds 6y ago
Thank you for your work!
nickysielicki 6y ago
What sort of heuristic do you use to determine what areas need it? This seems like something a neural network would excel at.
- pornel 6y ago
  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).
tobestobestobes 6y ago
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.

tobestobestobes 6y ago

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/ https://tgiachett.github.io/canvas-floyd-steinberg-dither/ It's a little rough around the edges, but I think the code is still readable.

ycollette 6y ago
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.