Show HN: Ordered Error Diffusion Dithering | Hacker News Reader

Show HN: Ordered Error Diffusion Dithering

observablehq.com

37 pointsvanderZwan25 comments

So as I mentioned somewhere in the wall of text, I'm fairly convinced that combining error diffusion with ordered dithering must already exist. It feels like such an obvious and fundamental idea to not have been discovered already at some point by one of the many, many people who have spent time implementing and tinkering with dithering algorithms.

So part of the reason why I submitted this was that I hoped that it would result in some feedback from people saying "oh yeah, that's actually pretty standard stuff, Knuth mentions it on page X", but maybe the topic is a bit too niche even for HN.

I have a copy of "Digital Halftoning" from Robert Ulichney at home, if it's anywhere it would be there. I'll try to remember to look at that tonight.

https://mitpress.mit.edu/books/digital-halftoning

Thank you! If it's not in there then that narrows it down to innovations since 1987 ;)

Section 8.3 on page 265 has the following:

In 1983, Billotet-Hoffman and Bryngdahl [11] suggested using an ordered dither threshold array in place of the fixed threshold used in error diffusion. However, the resulting halftoned output differs little from conventional ordered dither.

Later in the chapter they explore the idea of using a random threshold instead of an ordered pattern.

[11] Billotet-Hoffman, C. and O. Bryngdahl (1983) "On the error diffusion technique for electronic halftoning", Proc. SID, vol. 24, pp. 253-258

Great, that's a perfect start for Google Scholar! Now I can see which papers cited it, and so on.

I disagree with their conclusions though, look at this crosshatching dither that emerges from totally different parents:

https://mobile.twitter.com/JobvdZwan/status/1201613029013671...

The two-bit version looks pretty neat with it's pseudo-crosshatching effect, no?

Although I have to add that I had to rework the error-diffusion implementation to minimize rounding error. Before I did that the results weren't so great. So if we make the relatvely safe assumption that they used a "classic" eight-bit in-place optimized implementation , it might be true that it did not produce good results. And I'm sure that in their day they did not have the computer resources to quickly experiment with different combinations of dithering and ordering like I did.

Anyway, thank you so much for taking the time to look this up!

I'm not sure what you mean by rounding error. The whole point of error diffusion is that any errors are propagated so that they average out. I've coded Floyd-Steinberg many times myself, and the only problem I ever had was when my outputs didn't include 0% and 100% leaving the error to build without correction.

I basically mean clipping the diffused error - for example if I propagate a positive error to a pixel that is already white, and don't propagate that error again to the next pixels.

In the linked notebook, I use a separate error array made out of Int32 values (which is probably overkill, Int16 would suffice) and postpone division until the last moment. It's a small detail but it makes a significant difference in the hybrid output.

Error is error, it would never have occurred to me to clip it. I can see how that would make a big difference.

Me neither, but it doesn't even have to be a conscious choice! Let's you want to implement an in-place algorithm to save memory (which I'm presume was a realistic trade-off to consider back in the early eighties), and your inputs are single bytes for each channel, then your only option is to do saturating arithmetic. Clipping just falls out of that as a side-effect.

> combining error diffusion with ordered dithering must already exist.

> people saying "oh yeah, [...] Knuth mentions it on page X"

Though the following answers your question only in a literal sense, you might find it interesting to read Knuth's article "Fonts for Digital Halftones", originally published in TUGboat (the magazine of the TeX Users Group), Volume 8 (1987), No. 2: http://mirror.tug.org/TUGboat/tb08-2/tb18knut.pdf (Reprinted with revisions as Chapter 21 of Digital Typography.) Though it technically mentions "ordered dither" (on the first page), it uses it in a different sense/purpose (to get an initial patterns of dots that make up a "font" called "odith"). It does do error diffusion though (details are in appendix).

Ah, the next chapter of Digital Typography (Knuth's paper "Digital Halftones by Dot Diffusion") seems even more relevant. It mentions "It would be nice to have a solution that retains both the sharpness of the Floyd-Steinberg method [of error diffusion] and the parallelism of ordered dither" and does something that seems to combine the two. (DOI 10.1145/35039.35040)

> Digital Halftones by Dot Diffusion

Is that the same dot diffusion that is also mentioned here?

http://caca.zoy.org/study/part3.html

If I understand the description that page correctly, dot diffusion visits pixels in Bayer order (instead of from left to right, top to bottom), and propagates error to all surrounding pixels that have not been visited yet. So yes, that does combine ordered dithering with error diffusion, but in a very different fashion than I do. The output (at least on the page that I've linked) is very half-tone ish.

It's possibly the same (I'm not an expert, just aware of this reference from skimming through the book). Also, the first sentence of the abstract is "This paper describes a technique for approximating real-valued pixels by two-valued pixels" and the title says "halftones" so it wouldn't be surprising if the examples look half-tone ish :)

Could you implement it and compare? Also, on your original page, what do the three columns under each algorithm (e.g. the three images under "Floyd-Steinberg" in the "Quick Refresher" section) mean?

Haha just read the page again properly:

> Do not get fooled by Knuth’s apparent good results. They specifically target dot printers and do not give terribly good results on a computer screen.

But of course! Knuth, as is his wont, was obviously not targeting computer screens or even targeting dot printers in general but a specific (Imagen) printer that happened to be on the Stanford campus. :-)

Ah, that explanation makes a lot of sense actually! :)

I consider this thesis one of the best works on dither and noise shaping (error diffusion is just another name for noise shaping): http://uwspace.uwaterloo.ca/bitstream/10012/3867/1/thesis.pd...

Looks like a great resource! It seems mostly focused on one-dimensional cases, based on a quick skim, so that would take some time to grok and "translate" to 2D images, but it looks like it's full of in-depth theory and other useful information to make sense of what I'm experimenting with. Thanks!

The generalization to 2D is relatively straight-forward.

My own interest in the subject has mostly been 1D signals which might also serve to explain my affection for that thesis... but it really is much easier to understand first in 1D.

Me after skimming to page 60 our of 120: "Oh, an image! And the title actually says it's about images. So I guess the rest is just prep-work! Probably exactly what I'm looking for then!"

Thanks again

Blank page? What's it meant to show?

Observable uses JavaScript to render the page, I presume that's why it's broken for you (I use uMatrix myself as well).

It's supposed to show an interactive notebook with canvas-based images, describing how ordered dithering can be composed with error diffusion dithering to create a form of hybrid dithering that is somewhere in-between.

I only want a description (that I can copy, print out, or whatever); not an interactive notebook.

Really? Is half of the feedback I'm going to get here complaints that the webpage isn't static enough?

Look, it's a simple page with text and images describing what happens. There is a description of the algorithm.

But one of the neat things of this method is that you can combine any error diffusion method with any threshold map, so to illustrate the point I implemented the idea in an interactive page where you can combine 14 different error diffusion methods with 12 threshold maps and 3 input images, for a total of 504 possible combinations. My apologies for giving you easy tools to experiment.

If I go to a web site, and it's a blank page, that gives me zero information. It's quite trivial to have a fallback, even if it just says "Really sorry, I see you have Javascript off, but this web page does cool things that need Javascript, so you won't see much here unless you switch it on. I promise not to do evil things."

Well, I suggest you either tweet at Observable, or open a feedback topic on their forums. Either way, I'm not in charge of their website (and would not have been able to implement this stuff in a day on any other platform, so no, building a static site from scratch is not a realistic option for me).

https://twitter.com/observablehq

https://talk.observablehq.com/

> Is half of the feedback I'm going to get here complaints that the webpage isn't static enough?

Yes. Static websites work best.

Reply on news.ycombinator.com