6 ms·

Writing my own dithering algorithm in Racket

172 points by venusgirdle 1y ago

pixelpoet 1y ago
The thresholding should be done in linear space I think, not directly on the sRGB encoded values. Also I think the final result has some pretty distracting structured artifacts compared to e.g. blue noise dithering.
_ache_ 1y ago
I did the same like 2 weeks ago. In Rust. ^^ I'm still trying to improve it a little. https://git.ache.one/dither/tree/?h=%f0%9f%aa%b5 https://git.ache.one/dither/tree/?h=%f0%9f%aa%b5 I didn't published it because it's hard to actually put dithered images on the web, you can't resize a dithered image. So on the web, you have to dither it on the fly. It's why, in the article, there is some artifacts in the images. I still need to learn about dithering. Reference: https://sheep.horse/2022/12/pixel_accurate_atkinson_dithering_for_images_in_ht.html https://sheep.horse/2022/12/pixel_accurate_atkinson_ditherin... Cool links about dithering: - https://beyondloom.com/blog/dither.html https://beyondloom.com/blog/dither.html - https://blog.maximeheckel.com/posts/the-art-of-dithering-and-retro-shading-web/ https://blog.maximeheckel.com/posts/the-art-of-dithering-and...
- 01HNNWZ0MV43FF 1y ago
  Why can't you resize it? Because of the filtering? You can turn that off in css, right?
  - AndrewStephens 1y ago
    I am the author of the sheep.horse link above, although here[0] is an updated link. Even with filtering turned off you get slightly incorrect results, especially if you are resizing down where aliasing might completely ruin your image. Harsh black-and-white dithering is very susceptible to scaling artifacts. If you want pixel perfect dithering for the screen you are viewing the page on, you need to do it client side. Whether or not this is worth the bother is up to you. [0] https://sheep.horse/2023/1/improved_web_component_for_pixel-accurate_atkinson.html https://sheep.horse/2023/1/improved_web_component_for_pixel-...
    - pixelpoet 1y ago
      Note that this isn't a problem for blue noise based dithering; nevertheless, it's better if dithering is the last operation, and the result displayed 1:1 with pixel output.
v9v 1y ago
I love the small image previews to the left of the lines of code loading and saving images. Which editor is this?
- venusgirdle 1y ago
  I love them too :) Visual Studio Code with this extension: https://marketplace.visualstudio.com/items/?itemName=kisstkondoros.vscode-gutter-preview https://marketplace.visualstudio.com/items/?itemName=kisstko...
Aryezz 1y ago
Great read and nice drawings! I made some impractical dithering algorithms a while ago, such as distributing the error to far away pixels or distributing more than 100% of the error: https://burkhardt.dev/2024/bad-dithering-algorithms/ https://burkhardt.dev/2024/bad-dithering-algorithms/ Playing around with the distribution matrices and exploring the resulting patterns is great fun.
- _ache_ 1y ago
  Nice ! Thank you for the link! :)
turnsout 1y ago
This is awesome! But be careful, if you dig much further you're going to get into blue noise, which is a very deep rabbit hole.
deleted 1y ago
[deleted]
qwertox 1y ago
Somewhat related and worth watching: Surface-stable fractal dithering explained https://youtu.be/HPqGaIMVuLs https://youtu.be/HPqGaIMVuLs There's a follow-up video to that one.
- jszymborski 1y ago
  That was mind-blowing
jansan 1y ago
I think implementing a dithering algorithm is one of the most satisfying projects, because it is fun, small(ish) and you know when you are done. Of course, unless you are trying to implement something completely insane like Surface-Stable Fractal Dithering https://www.youtube.com/watch?v=HPqGaIMVuLs https://www.youtube.com/watch?v=HPqGaIMVuLs
lampiaio 1y ago
Wouldn't it make more sense to display the samples at 100% in the article? Had to open the images in a new tab to fully appreciate the dithering.
- sho_hn 1y ago
  Thanks for pointing this out. The embedded scaled version (which isn't clickable) had artifacts for me, and wasn't very nice.
neilv 1y ago
(Kudos on doing this in Racket. Besides being a great language to learn and use, using Racket (or another Scheme, or other less-popular language) is a sign that the work comes from genuine interest, not (potentially) just pursuit of keyword employability.) Side note on Lisp formatting: The author is doing a mix of idiomatic cuddling of parenthesis, but also some more curly-brace-like formatting, and then a cuddling of a trailing small term such that it doesn't line up vertically (like people sometimes do in other languages, like, e.g., a numeric constant after a multi-line closure argument in a timer or event handler registration). One thing some Lisp people like about the syntax is that parts of complex expression syntax can line up vertically, to expose the structure. For example, here, you can clearly see that the `min` is between 255 and this big other expression: (define luminance (min (exact-round (+ (* 0.2126 (bytes-ref pixels-vec (+ pixel-pos 1))) ; red (* 0.7152 (bytes-ref pixels-vec (+ pixel-pos 2))) ; green (* 0.0722 (bytes-ref pixels-vec (+ pixel-pos 3))))) ; blue 255)) Or, if you're running out of horizontal space, you might do this: (define luminance (min (exact-round (+ (* 0.2126 (bytes-ref pixels-vec (+ pixel-pos 1))) ; red (* 0.7152 (bytes-ref pixels-vec (+ pixel-pos 2))) ; green (* 0.0722 (bytes-ref pixels-vec (+ pixel-pos 3))))) ; blue 255))) Or you might decide those comments should be language, and do this: (define luminance (let ((red (bytes-ref pixels-vec (+ pixel-pos 1))) (green (bytes-ref pixels-vec (+ pixel-pos 2))) (blue (bytes-ref pixels-vec (+ pixel-pos 3)))) (min (exact-round (+ (* red 0.2126) (* green 0.7152) (* blue 0.0722))) 255))) One of my teachers would still call those constants "magic numbers", even when their purpose is obvious in this very restricted context, and insist that you bind them to names in the language. Left as an exercise to the reader.
crazygringo 1y ago
> Atkinson dithering is great, but what's awesome about dithering algorithms is that there's no definitive "best" algorithm! I've always wondered about this. Sure, if you're changing the contrast then that's a subjective change. But it's easy to write a metric to confirm the degree to which brightness and contrast are maintained correctly. And then, is it really impossible to develop an objective metric for the level of visible detail that is maintained? Is that really psychovisual and therefore subjective? Is there really nothing we can use from information theory to calculate the level of detail that emerges out of the noise? Or something based on maximum likelihood estimation? I'm not saying it has to be fast, or that we can prove a particular dithering algorithm is theoretically perfect. But I'm surprised we don't have an objective, quantitative measure to prove that one algorithm preserves more detail than another.
- zamadatix 1y ago
  I think the problem is less with the possibility of developing something to maximize a metric (though that could be hard depending how you define the metric) and more with no single metric meeting all use cases so you're not going to end up with a definitive answer anyways. Some images may be better suited for an algorithm with the metric of preserving the most literal detail. Others for preserving the most psychovisual detail. Others for something which optimize visibility even if it's not as true to the source. No one metric will be definitively the best thing to measure against for every image and use case fed to it. You find the same in image resizing. No one algorithm can be the definitive best for e.g. pixel art and movie upscaling. At the same time nobody can agree what the best average metric of all of that could be. Of course if you define a non-universally important metric as the only thing which matters you can end up with certain solutions like sinc being mathematically optimal. It does lead to the question though: are there well defined objective metrics of dithering quality for which we don't have a mathematically optimal answer?
  - crazygringo 1y ago
    > more with no single metric meeting all use cases Is it, though? Dithering to black-and-white is pretty simple. If the only thing you want to do is maximize detail while preserving accurate brightness, I don't really see a lot of leeway there. Now sure, you can choose to artistically adjust some tradeoff of less detail for... something? But it feels like there ought to at least be an objectively correct starting point for a metric, no? I'm curious if that really doesn't exist.
virtualritz 1y ago
The dithered images have the wrong brightness mapping. The reason is that the described approach will estimate the error correction term wrong as the input RGB value is non-linear sRGB. The article doesn't mention anything about this so I assume the author is oblivious to what color spaces are and that an 8bit/channel RGB value will most likely not represent linear color. This is not bashing the article; most people who start doing anything with color in CG w/o reading up on the resp. theory first get this wrong. And coming up with your own dither is always cool. See e.g. [1] for an in-depth explanation why the linearization stuff matters. [1] http://www.thetenthplanet.de/archives/5367 http://www.thetenthplanet.de/archives/5367
- Lerc 1y ago
  Are dithering patterns proportional in perceived brightness to a uniform grey for any percentage of set pixels? I can see them not being linearly proportional to a smooth perceptual grey gradient as the ratio of black to white changes, but I suspect it might change also with the clustering of light and dark at the same ratio.
- venusgirdle 1y ago
  Hi, OP here! Thank you so much for pointing this out! Just read the post you linked and did some of my own research on the non-linearity of sRGB - really fascinating stuff :) For now, I've acknowledged this limitation of my implementation so that any new readers are aware of it: https://amanvir.com/blog/writing-my-own-dithering-algorithm-in-racket#ack https://amanvir.com/blog/writing-my-own-dithering-algorithm-... But I'll definitely revisit the article to add proper linearization to my implementation when I have the time. Thanks again for mentioning this!
  - DistractionRect 1y ago
    You're already 99% of the way there, you're just have the order of operations wrong. What you're doing is sRGB -> linear perceived luminance space -> sRGB (greyscale, where R=G=B) -> dithering When you should be applying dithering in the linear perceived luminance space, then covering the dithered image back into sRGB space.
SillyUsername 1y ago
The square artifacts in the dithered image are caused by the distribution not doing second passes over the pixels already with error distributed, this is a byproduct of the "custom" approach the OP uses, they've traded off (greater) individual colour error for general picture cohesion. Me, I adjusted Atkinson a few years ago as I prefer the "blown out" effect: https://github.com/KodeMunkie/imagetozxspec/blob/master/src/main/java/uk/co/silentsoftware/core/converters/image/errordiffusionstrategy/LowErrorAtkinsonDitherStrategy.java https://github.com/KodeMunkie/imagetozxspec/blob/master/src/... A similar custom approach to prevent second pass diffusion is in the code too; it is slightly different implementation - processes the image in 8x8 pixel "attribute" blocks, where the error does not go out of these bounds. The same artifacts occur there too but are more distinct as a consequence. https://github.com/KodeMunkie/imagetozxspec/blob/3d41a99aa04d27d62ea410920c86569a37ed2564/src/main/java/uk/co/silentsoftware/config/OptionsObject.java#L395 https://github.com/KodeMunkie/imagetozxspec/blob/3d41a99aa04... Nb. 8x8 is not arbitrary, the ZX Spectrum computer this is used for only allowed 2 colours in every 8x8 block so this seeing the artifact on a real machine is less important as the whole image potentially had 8x8 artifacts anyway.
shawn_w 1y ago
One style suggestion: nested `for` expressions can be combined into a single `for*`, helping reduce indentation depth: (for* ([i height] [j width]) ...)
kleiba 1y ago
For anyone who hasn't seen it yet, here's Lukas Pope's forum post on finding a dithering approach that works well with animations: https://forums.tigsource.com/index.php?topic=40832.msg1363742#msg1363742 https://forums.tigsource.com/index.php?topic=40832.msg136374...
- itsgabriel 1y ago
  You may also enjoy Surface Stable Dithering: https://youtube.com/watch?v=HPqGaIMVuLs https://youtube.com/watch?v=HPqGaIMVuLs
ralphc 1y ago
I'll start off admitting to not digging into the article yet, but is this something that can be broken up and done in parallel? I'm an Elixir fanboy so I try to parallelize anything I can, either to speed it up or because I'm an Elixir fanboy.
- archerx 1y ago
  Most image processing can be multithreaded, you just have to chunk the image and send each chunk to a thread. You might have to pad the chunk based on the processing you’re doing i.e convolution which needs the neighboring pixels per pixel to work.
dyoo1979 1y ago
This reminds me a bit of the octree quantization implementation I hacked up to improve speed of generating Racket's animated gifs. * https://github.com/racket/racket/commit/6b2e5f4014ed95c9b8839248d8ee249edbb4f073 https://github.com/racket/racket/commit/6b2e5f4014ed95c9b883... * https://github.com/racket/racket/commit/f2a1773422feaa4ec112e97467c6a671a3123008 https://github.com/racket/racket/commit/f2a1773422feaa4ec112...

172 points by venusgirdle 1y ago

The thresholding should be done in linear space I think, not directly on the sRGB encoded values. Also I think the final result has some pretty distracting structured artifacts compared to e.g. blue noise dithering.

_ache_ 1y ago

I did the same like 2 weeks ago. In Rust. ^^ I'm still trying to improve it a little. https://git.ache.one/dither/tree/?h=%f0%9f%aa%b5 https://git.ache.one/dither/tree/?h=%f0%9f%aa%b5 I didn't published it because it's hard to actually put dithered images on the web, you can't resize a dithered image. So on the web, you have to dither it on the fly. It's why, in the article, there is some artifacts in the images. I still need to learn about dithering. Reference: https://sheep.horse/2022/12/pixel_accurate_atkinson_dithering_for_images_in_ht.html https://sheep.horse/2022/12/pixel_accurate_atkinson_ditherin... Cool links about dithering: - https://beyondloom.com/blog/dither.html https://beyondloom.com/blog/dither.html - https://blog.maximeheckel.com/posts/the-art-of-dithering-and-retro-shading-web/ https://blog.maximeheckel.com/posts/the-art-of-dithering-and...

01HNNWZ0MV43FF 1y ago
Why can't you resize it? Because of the filtering? You can turn that off in css, right?
- AndrewStephens 1y ago
  I am the author of the sheep.horse link above, although here[0] is an updated link. Even with filtering turned off you get slightly incorrect results, especially if you are resizing down where aliasing might completely ruin your image. Harsh black-and-white dithering is very susceptible to scaling artifacts. If you want pixel perfect dithering for the screen you are viewing the page on, you need to do it client side. Whether or not this is worth the bother is up to you. [0] https://sheep.horse/2023/1/improved_web_component_for_pixel-accurate_atkinson.html https://sheep.horse/2023/1/improved_web_component_for_pixel-...
  - pixelpoet 1y ago
    Note that this isn't a problem for blue noise based dithering; nevertheless, it's better if dithering is the last operation, and the result displayed 1:1 with pixel output.

v9v 1y ago

I love the small image previews to the left of the lines of code loading and saving images. Which editor is this?

venusgirdle 1y ago
I love them too :) Visual Studio Code with this extension: https://marketplace.visualstudio.com/items/?itemName=kisstkondoros.vscode-gutter-preview https://marketplace.visualstudio.com/items/?itemName=kisstko...

Aryezz 1y ago

Great read and nice drawings! I made some impractical dithering algorithms a while ago, such as distributing the error to far away pixels or distributing more than 100% of the error: https://burkhardt.dev/2024/bad-dithering-algorithms/ https://burkhardt.dev/2024/bad-dithering-algorithms/ Playing around with the distribution matrices and exploring the resulting patterns is great fun.

_ache_ 1y ago
Nice ! Thank you for the link! :)

turnsout 1y ago

This is awesome! But be careful, if you dig much further you're going to get into blue noise, which is a very deep rabbit hole.

deleted 1y ago

[deleted]

qwertox 1y ago

Somewhat related and worth watching: Surface-stable fractal dithering explained https://youtu.be/HPqGaIMVuLs https://youtu.be/HPqGaIMVuLs There's a follow-up video to that one.

jszymborski 1y ago
That was mind-blowing

jansan 1y ago

I think implementing a dithering algorithm is one of the most satisfying projects, because it is fun, small(ish) and you know when you are done. Of course, unless you are trying to implement something completely insane like Surface-Stable Fractal Dithering https://www.youtube.com/watch?v=HPqGaIMVuLs https://www.youtube.com/watch?v=HPqGaIMVuLs

lampiaio 1y ago

Wouldn't it make more sense to display the samples at 100% in the article? Had to open the images in a new tab to fully appreciate the dithering.

sho_hn 1y ago
Thanks for pointing this out. The embedded scaled version (which isn't clickable) had artifacts for me, and wasn't very nice.

neilv 1y ago

(Kudos on doing this in Racket. Besides being a great language to learn and use, using Racket (or another Scheme, or other less-popular language) is a sign that the work comes from genuine interest, not (potentially) just pursuit of keyword employability.) Side note on Lisp formatting: The author is doing a mix of idiomatic cuddling of parenthesis, but also some more curly-brace-like formatting, and then a cuddling of a trailing small term such that it doesn't line up vertically (like people sometimes do in other languages, like, e.g., a numeric constant after a multi-line closure argument in a timer or event handler registration). One thing some Lisp people like about the syntax is that parts of complex expression syntax can line up vertically, to expose the structure. For example, here, you can clearly see that the `min` is between 255 and this big other expression: (define luminance (min (exact-round (+ (* 0.2126 (bytes-ref pixels-vec (+ pixel-pos 1))) ; red (* 0.7152 (bytes-ref pixels-vec (+ pixel-pos 2))) ; green (* 0.0722 (bytes-ref pixels-vec (+ pixel-pos 3))))) ; blue 255)) Or, if you're running out of horizontal space, you might do this: (define luminance (min (exact-round (+ (* 0.2126 (bytes-ref pixels-vec (+ pixel-pos 1))) ; red (* 0.7152 (bytes-ref pixels-vec (+ pixel-pos 2))) ; green (* 0.0722 (bytes-ref pixels-vec (+ pixel-pos 3))))) ; blue 255))) Or you might decide those comments should be language, and do this: (define luminance (let ((red (bytes-ref pixels-vec (+ pixel-pos 1))) (green (bytes-ref pixels-vec (+ pixel-pos 2))) (blue (bytes-ref pixels-vec (+ pixel-pos 3)))) (min (exact-round (+ (* red 0.2126) (* green 0.7152) (* blue 0.0722))) 255))) One of my teachers would still call those constants "magic numbers", even when their purpose is obvious in this very restricted context, and insist that you bind them to names in the language. Left as an exercise to the reader.

crazygringo 1y ago

> Atkinson dithering is great, but what's awesome about dithering algorithms is that there's no definitive "best" algorithm! I've always wondered about this. Sure, if you're changing the contrast then that's a subjective change. But it's easy to write a metric to confirm the degree to which brightness and contrast are maintained correctly. And then, is it really impossible to develop an objective metric for the level of visible detail that is maintained? Is that really psychovisual and therefore subjective? Is there really nothing we can use from information theory to calculate the level of detail that emerges out of the noise? Or something based on maximum likelihood estimation? I'm not saying it has to be fast, or that we can prove a particular dithering algorithm is theoretically perfect. But I'm surprised we don't have an objective, quantitative measure to prove that one algorithm preserves more detail than another.

zamadatix 1y ago
I think the problem is less with the possibility of developing something to maximize a metric (though that could be hard depending how you define the metric) and more with no single metric meeting all use cases so you're not going to end up with a definitive answer anyways. Some images may be better suited for an algorithm with the metric of preserving the most literal detail. Others for preserving the most psychovisual detail. Others for something which optimize visibility even if it's not as true to the source. No one metric will be definitively the best thing to measure against for every image and use case fed to it. You find the same in image resizing. No one algorithm can be the definitive best for e.g. pixel art and movie upscaling. At the same time nobody can agree what the best average metric of all of that could be. Of course if you define a non-universally important metric as the only thing which matters you can end up with certain solutions like sinc being mathematically optimal. It does lead to the question though: are there well defined objective metrics of dithering quality for which we don't have a mathematically optimal answer?
- crazygringo 1y ago
  > more with no single metric meeting all use cases Is it, though? Dithering to black-and-white is pretty simple. If the only thing you want to do is maximize detail while preserving accurate brightness, I don't really see a lot of leeway there. Now sure, you can choose to artistically adjust some tradeoff of less detail for... something? But it feels like there ought to at least be an objectively correct starting point for a metric, no? I'm curious if that really doesn't exist.

virtualritz 1y ago

The dithered images have the wrong brightness mapping. The reason is that the described approach will estimate the error correction term wrong as the input RGB value is non-linear sRGB. The article doesn't mention anything about this so I assume the author is oblivious to what color spaces are and that an 8bit/channel RGB value will most likely not represent linear color. This is not bashing the article; most people who start doing anything with color in CG w/o reading up on the resp. theory first get this wrong. And coming up with your own dither is always cool. See e.g. [1] for an in-depth explanation why the linearization stuff matters. [1] http://www.thetenthplanet.de/archives/5367 http://www.thetenthplanet.de/archives/5367

Lerc 1y ago
Are dithering patterns proportional in perceived brightness to a uniform grey for any percentage of set pixels? I can see them not being linearly proportional to a smooth perceptual grey gradient as the ratio of black to white changes, but I suspect it might change also with the clustering of light and dark at the same ratio.
venusgirdle 1y ago
Hi, OP here! Thank you so much for pointing this out! Just read the post you linked and did some of my own research on the non-linearity of sRGB - really fascinating stuff :) For now, I've acknowledged this limitation of my implementation so that any new readers are aware of it: https://amanvir.com/blog/writing-my-own-dithering-algorithm-in-racket#ack https://amanvir.com/blog/writing-my-own-dithering-algorithm-... But I'll definitely revisit the article to add proper linearization to my implementation when I have the time. Thanks again for mentioning this!
- DistractionRect 1y ago
  You're already 99% of the way there, you're just have the order of operations wrong. What you're doing is sRGB -> linear perceived luminance space -> sRGB (greyscale, where R=G=B) -> dithering When you should be applying dithering in the linear perceived luminance space, then covering the dithered image back into sRGB space.

SillyUsername 1y ago

The square artifacts in the dithered image are caused by the distribution not doing second passes over the pixels already with error distributed, this is a byproduct of the "custom" approach the OP uses, they've traded off (greater) individual colour error for general picture cohesion. Me, I adjusted Atkinson a few years ago as I prefer the "blown out" effect: https://github.com/KodeMunkie/imagetozxspec/blob/master/src/main/java/uk/co/silentsoftware/core/converters/image/errordiffusionstrategy/LowErrorAtkinsonDitherStrategy.java https://github.com/KodeMunkie/imagetozxspec/blob/master/src/... A similar custom approach to prevent second pass diffusion is in the code too; it is slightly different implementation - processes the image in 8x8 pixel "attribute" blocks, where the error does not go out of these bounds. The same artifacts occur there too but are more distinct as a consequence. https://github.com/KodeMunkie/imagetozxspec/blob/3d41a99aa04d27d62ea410920c86569a37ed2564/src/main/java/uk/co/silentsoftware/config/OptionsObject.java#L395 https://github.com/KodeMunkie/imagetozxspec/blob/3d41a99aa04... Nb. 8x8 is not arbitrary, the ZX Spectrum computer this is used for only allowed 2 colours in every 8x8 block so this seeing the artifact on a real machine is less important as the whole image potentially had 8x8 artifacts anyway.

shawn_w 1y ago

One style suggestion: nested `for` expressions can be combined into a single `for*`, helping reduce indentation depth: (for* ([i height] [j width]) ...)

kleiba 1y ago

For anyone who hasn't seen it yet, here's Lukas Pope's forum post on finding a dithering approach that works well with animations: https://forums.tigsource.com/index.php?topic=40832.msg1363742#msg1363742 https://forums.tigsource.com/index.php?topic=40832.msg136374...

itsgabriel 1y ago
You may also enjoy Surface Stable Dithering: https://youtube.com/watch?v=HPqGaIMVuLs https://youtube.com/watch?v=HPqGaIMVuLs

ralphc 1y ago

I'll start off admitting to not digging into the article yet, but is this something that can be broken up and done in parallel? I'm an Elixir fanboy so I try to parallelize anything I can, either to speed it up or because I'm an Elixir fanboy.

archerx 1y ago
Most image processing can be multithreaded, you just have to chunk the image and send each chunk to a thread. You might have to pad the chunk based on the processing you’re doing i.e convolution which needs the neighboring pixels per pixel to work.

dyoo1979 1y ago

This reminds me a bit of the octree quantization implementation I hacked up to improve speed of generating Racket's animated gifs. * https://github.com/racket/racket/commit/6b2e5f4014ed95c9b8839248d8ee249edbb4f073 https://github.com/racket/racket/commit/6b2e5f4014ed95c9b883... * https://github.com/racket/racket/commit/f2a1773422feaa4ec112e97467c6a671a3123008 https://github.com/racket/racket/commit/f2a1773422feaa4ec112...