Show HN: Ordered Error Diffusion Dithering

https://observablehq.com/@jobleonard/ordered-error-diffusion-dithering

by vanderZwan • 7 years ago

37 25 7 years ago

observablehq.com

mnw21cam2• 7 years ago

Blank page? What's it meant to show?

vanderZwan12• 7 years ago

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.

zzo38computer• 7 years ago

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

vanderZwan12• 7 years ago

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.

mark-r4• 7 years ago

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

vanderZwan12• 7 years ago

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

svat3• 7 years ago

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)

vanderZwan12• 7 years ago

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.

nullc2• 7 years ago

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

vanderZwan12• 7 years ago

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!

nullc2• 7 years ago

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.

vanderZwan12• 7 years ago

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

Show HN: Ordered Error Diffusion Dithering

Related Stories