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.

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

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-...

But I'll definitely revisit the article to add proper linearization to my implementation when I have the time. Thanks again for mentioning this!

To some extent I think this comes down to a preference, like many things in dithering. If the black and white results look good, that may be the right answer!

I've played with dithering tools that provide both options, and I prefer the output of the simple version..

Haha, yeah I was kind of thinking that as well! Like with different error-diffusion patterns, one method may be more visually appealing than the other.

Although, with either approach, I definitely feel that the fact that sRGB is non-linear should be acknowledged, and that’s something I was completely unaware of. So, I’m happy I learned something new today :)

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.

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.

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.

Nice ! Thank you for the link! :)

(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.

Somewhat related and worth watching:

Surface-stable fractal dithering explained

https://youtu.be/HPqGaIMVuLs

There's a follow-up video to that one.

That was mind-blowing

> 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.

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?

> 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.

> 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 think you'll find something similar with audio, image, and video compression algorithms in general. The majority of these are explicitly designed to spend more bits on the parts that humans care about and fewer bits on the parts we won't notice. E.g. MP3 uses perceptual coding/masking: when there's loud sound at frequency f0 and a quieter sound at nearby f1=f0+(small delta f) most people won't hear the sound at f1 so the codec just throws it away. You'd be able to see the difference on a spectrogram but you wouldn't be able to hear it.

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...

Why can't you resize it? Because of the filtering? You can turn that off in css, right?

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-...

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.

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 love the small image previews to the left of the lines of code loading and saving images. Which editor is this?

I love them too :)

Visual Studio Code with this extension: https://marketplace.visualstudio.com/items/?itemName=kisstko...

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 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

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.