4 ms·

Show HN: Ordered Error Diffusion Dithering

37 points by vanderZwan 7y ago

deleted 7y ago
[deleted]
mnw21cam 7y ago
Blank page? What's it meant to show?
- vanderZwan 7y 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 7y ago
    I only want a description (that I can copy, print out, or whatever); not an interactive notebook.
    - vanderZwan 7y ago
      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.
      - mnw21cam 7y ago
        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."
        vanderZwan 7y ago
        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://twitter.com/observablehq https://talk.observablehq.com/ https://talk.observablehq.com/
      - msla 7y ago
        > Is half of the feedback I'm going to get here complaints that the webpage isn't static enough? Yes. Static websites work best.
vanderZwan 7y 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-r 7y 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 https://mitpress.mit.edu/books/digital-halftoning
  - vanderZwan 7y ago
    Thank you! If it's not in there then that narrows it down to innovations since 1987 ;)
    - mark-r 7y ago
      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
      - vanderZwan 7y ago
        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/1201613029013671937/photo/1 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!
nullc 7y 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.pdf http://uwspace.uwaterloo.ca/bitstream/10012/3867/1/thesis.pd...
- vanderZwan 7y 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!
  - nullc 7y 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.
- vanderZwan 7y 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

37 points by vanderZwan 7y ago

deleted 7y ago

[deleted]

mnw21cam 7y ago

Blank page? What's it meant to show?

vanderZwan 7y 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 7y ago
  I only want a description (that I can copy, print out, or whatever); not an interactive notebook.
  - vanderZwan 7y ago
    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.
    - mnw21cam 7y ago
      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."
      - vanderZwan 7y ago
        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://twitter.com/observablehq https://talk.observablehq.com/ https://talk.observablehq.com/
    - msla 7y ago
      > Is half of the feedback I'm going to get here complaints that the webpage isn't static enough? Yes. Static websites work best.

vanderZwan 7y 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-r 7y 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 https://mitpress.mit.edu/books/digital-halftoning
- vanderZwan 7y ago
  Thank you! If it's not in there then that narrows it down to innovations since 1987 ;)
  - mark-r 7y ago
    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
    - vanderZwan 7y ago
      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/1201613029013671937/photo/1 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!

nullc 7y 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.pdf http://uwspace.uwaterloo.ca/bitstream/10012/3867/1/thesis.pd...

vanderZwan 7y 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!
- nullc 7y 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.
vanderZwan 7y 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