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/
Playing around with the distribution matrices and exploring the resulting patterns is great fun.
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.
(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))
(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)))
(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)))
Somewhat related and worth watching:
Surface-stable fractal dithering explained
There's a follow-up video to that one.
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/6b2e5f4014ed95c9b883...
* https://github.com/racket/racket/commit/f2a1773422feaa4ec112...
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.msg136374...
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
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_ditherin...
Cool links about dithering: - https://beyondloom.com/blog/dither.html - https://blog.maximeheckel.com/posts/the-art-of-dithering-and...
One style suggestion: nested `for` expressions can be combined into a single `for*`, helping reduce indentation depth:
(for* ([i height]
[j width])
...)> 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.
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.
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.
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
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.
I love the small image previews to the left of the lines of code loading and saving images. Which editor is this?
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.
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/...
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/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.