I'm trying to figure out whether this is a compliment, a criticism, or both. When topics related to 2D graphics come up, there's a fair chance I've done some relevant work in the area. I plan to continue shamelessly hawking my results, as that's an important part of a research pipeline :)
Wow, didn't know about that. It sounds quite similar to the more recent "electrostatic halftoning" algorithm by Weickert et al, that apparently does not cite your work:
> According to Wikipedia, “Dither is an intentionally applied form of noise used to randomize quantization error”, and is a technique not only limited to images. It is actually a technique used to this day on audio recordings […]
Dithering as a digital signal processing technique is also used frequently in the digital control of physical systems. One example of this is in the control of hydraulic servo valves[1]; these valves are usually pretty small and their performance can be dominated by a lot of external factors. One of the biggest ones is "stiction", or static friction, wherein if the moving parts of the valve are at rest it can take a large amount of current to get them going again which translates in to poor control of the valve and in turn poor control of the thing the valve is trying to move. It's common to use very high frequency/small amplitude dithering on these valves to eliminate the effects of stiction without compromising accuracy which greatly improves the control stability and responsiveness of the servo valves.
I believe this is what the engines are doing during the majority of the ascent of the Starship SN8 test vehicle[0]. You can see the engines gimbaling very slightly in a circular pattern.
I would not define it exactly like that. I would say "Dithering is any method of reducing the bit depth of a signal that prioritizes accurate representation of low frequencies over that of high frequencies". This frames it as essentially an optimization problem, with randomn noise being a heuristic way of accomplishing it.
I feel like that is still a very narrow definition. Dithering's useful anywhere quantization produces an unwanted result, and is useful in a lot of places where "bitrate" isn't even a concept
I worked with a team that included printing, low-level graphics rendering. When we were able to rename our lab at work we went with "Dithering Heights."
I think the best way of thinking about dithering, is that it's the 'whitening' of quantization noise. Quantization can be modelled by taking the difference between the originally continuous signal, and the resultant quantized image as "quantization noise". The resultant noise has a spectrum that's pretty 'spiky' due to its non-continuous nature, it has significant energy in its higher-frequency harmonics. By adding some noise before sending it off to be thresholded by the quantizer, the noise's spectrum is made a lot flatter, thus making the quantized image look more like the original image, but with a higher noise floor.
Bisqwit's discussion of dithering is outstanding. He presents a very impressive algorithm for arbitrary-palette dithering that is animation safe.
> This paper introduces a patent-free positional (ordered) dithering algorithm that is applicable for arbitrary palettes. Such dithering algorithm can be used to change truecolor animations into paletted ones, while maximally avoiding unintended jitter arising from dithering.
He demonstrates it "live coding" style in this[1] video where he writes a demo in 256 colors of a "starfield" animation with color blending and Gaussian blur style bloom. The first animation at 6:33 using traditional ordered dithering has the usual annoying artifacts. The animation at 13:00 using an optimal palette and his "gamma-aware Knoll-Yliluom positional dithering" changed my understanding of what was possible with a 256 color palette. The animation even looks decent[2] dithered all the way down to a 16 color palette!
If that wasn't crazy enough, he also "live codes" a raytracer[3] in DOS that "renders in 16-color VGA palette at 640x480 resolution."
> He presents a very impressive algorithm for arbitrary-palette dithering that is animation safe.
They do look good. This makes me want to run his animation examples on a blue noise dither, since he didn’t compare to blue noise, and it’s also animation safe...
I originally found out about Obra Dinn by reading that devlog—it's totally fascinating, and shows impressive attention to detail.
> It feels a little weird to put 100 hours into something that won't be noticed by its absence. Exactly no one will think, "man this dithering is stable as shit. total magic going on here."
Luckily, thanks to this post, we have the privilege of thinking that.
He's not entirely correct, either. I haven't played it, but I did see video of it, and I was impressed by the stability of the dithering. It takes work to avoid it looking like https://www.youtube.com/watch?v=2AKtp3XHn38 or something.
Any ordered dithering algorithm will animate pretty smoothly, but techniques based on error diffusion will have a "swimming" effect. Lucas Pope's devlog goes into considerable detail. Here's a good starting point: https://forums.tigsource.com/index.php?topic=40832.msg104520...
(ETA: also the link that gruez posted. HN seems to be having some performance issues)
Another way to think of dither (that may only make sense to people with a signals background) is that it linearizes the error introduced by the quantization step (which is a non-linear process). This has a bunch of conceptual implications (like elimination of error harmonics being natural consequence) but maybe most importantly allows you to continue using linear analysis tools and techniques in systems with a quantization filter.
Very cool paper. Something that bothers me is that the Floyd-steinberg error diffusion without dithering looks superior than the version with the dithering. I think this demonstrates that perceptible patterns in the error (non-linear) don’t always look so bad.
One thing I've found (admittedly with audio) is that you can usually get away with less dither power than is needed to completely linearize the error, at the cost of some harmonics for pathological signals which still ends up being less noticeable than the higher power dither noise.
Right, I think that’s what’s going on in my image example.
I think this is a key lesson to people who apply these types of mathematical techniques to the lossy compression of data meant to be experienced by humans. Random noise is not always preferable to non-linear error, i.e. reducing non-linear error is not necessarily the equivalent of improving the perceived quality of the data in question. It can be but the function that determines what “looks good” or what “sounds good” to humans is probably a bit more complex.
This is something I’ve run into with image compression techniques but it applies here too (quantization being a form of compression). E.g. JPEG compresses images in 8x8 blocks because doing the whole image at once would look horrible. Figuring out the redundant information that can be thrown away with the least impact to image quality is still fundamentally an art.
Shameful tangential plug alert: My sideproject is a dithering-based image-to-pattern converter for plastic fuse beads (you know them, the ones you place on a platter and iron to fuse them together): https://www.beadifier.pro/
What an odd coincidence… I just acquired an "Inkplate" for my birthday (a recycled Kindle screen glued onto a board with an Arduino and wifi) and was in the process of looking for old 1bit art for it, stumbled across the term "ditherpunk" just last night.
- https://inkplate.io
It’s fantastic. You can program in MicroPython, or C using Arduino IDE. I'm barely fluent in C and had no problem getting some basic stuff running last night.
I might have to look that up. It's hard for me to imagine what dithering and typography would have in common, other than they might both be used to produce a book.
This is such a well-written article: it describes the impetus, it is researched, it has great examples both as code and as output, and it piques interest. In the late 1990's I contracted with an embedded software company to optimize a dithering algorithm for 8-bit MCUs that was used in most laser printers & copiers, and this paper is a really good overview.
Excellent article. I've also always wondered, I was making some gradients the other day and I was curious to how I could dither between two colours. Big thank you for this article!
A few years back, when TechShop still existed and was open, I made a present for my mother: a glass laser-etched and engraved with an image from her favorite comic. Because the comic was painted in a set of watercolors, this was going to be difficult. I ended up tracing the lines (for the deeper engraving) and then stomping on the color palette for the etching. Finally, I settled on different newspaper halftone sets for each "color."
It took several tries for it to come out alright. This might have saved me a few runs.
Somewhat off-topic, but this reminds me of the impressionist/pointillist styles of painting. There the motivation is not to use a smaller palette, but to typically use a richer palette (including colors on the opposite side of the wheel) so that the image looks much more vibrant and realistic on zooming out, circumventing the limitation of one (flat) color per location.
The article mentions Bill Atkinson’s dithering algorithm, invented during his work on the original Macintosh. You can also read more about it here: https://www.evilmadscientist.com/2012/dithering/
What about dithering for the smallest possible images? I'm talking in the 300 byte - 2kb range here. Does anyone have any suggestions for what to do to really get file size down?
Author here! I don’t think many people have researched or optimized on this, but I also work on https://squoosh.app, and from that experience I know that dithering makes compression _worse_ most of the time (unless you use PNG and use a super small palette of colors). Interesting idea tho!
Hi Surma! fantastic article. You can save a lot of data switching to a lossless format as you said, and especially when using ordered dithering. Even if the color palette is quite large.
Error diffusion causes problems for certain color palettes, but usually results in a smaller image size.
I've made a tool for doing this: https://doodad.dev/dither-me-this, you can easily half the size of a jpeg by dithering it and exporting it as a png.
Quantizing to <= 256 colors will let you use a single byte per pixel, but there are other techniques like Block Truncation Coding that work well with 8bit images to go down to 2 bits per pixel or lower. Even at 2 bits per pixel, this is still quite big as raw data, so you typically will want to use compression on top such as RLE, DEFLATE, etc.
I’m currently exploring this for my own applications, compressing large 8bit sprite sheet images, and it’s producing much smaller images than most palette based image formats (GIF, WebP, PNG, etc). Follow my progress here:
https://twitter.com/mattdesl/status/1346048282494177280?s=21
I did use dithering for unimportant background images of a website. Use just 256 colors, and both PNG and GIF will use a color palette instead of describing each pixel separately. Really helps with the file size. Afterwards muck with the various lossless compression parameters in PNG with optipng to shave off a few more percent.
This article is missing a crucial pre-processing step to dithering algorithms: apply a Retinex-like filter to enhance the local contrast before doing the dithering. This gives a dramatic improvement of the final result. In fact, by exploring the scale parameter of the pre-processing step, you find a continuous family of binarisations that interpolates between global tresholding and local dithering.
That's fascinating -- do you have any links to examples?
I'm searching online but can't find anything at all. I've never heard of using Retinex in the context of dithering, and wondering what specifically you mean by Retinex-"like"?
I'm also really curious what contexts this has been most successful in. E.g. was it used for dithering in images or games back in the 1990's when we were limited to 16-bit or 256-bit color? Or is this something more recently explored in academia or in some niche imaging applications?
Without it (left), a photo remains "accurate" in terms of brightness levels.
But with it (right), it becomes far more high-contrast to feel closer to an illustration or painting. Which certainly makes it clearer. But while it brings out details in middle levels, it totally blows out shadows and highlights.
E.g. the texture of his mask, shirt, and her hand are much clearer. But on the other hand, their hair (and a background object) just turn solid black and lose all detail. But certainly, the vastly higher contrast makes for a much more compelling image IMO.
I agree; the filtered image (right) is more aesthetically pleasing; but it feels much less accurate. It would depend on the intent of the image I think. If you're creating art, and using photographs in the creation, it's not a problem. If you're reporting on the world and just want to reduce the data size (or use a monochrome output medium), I wouldn't do it like this.
Black and white images need more contrast to be pleasing. I think that's most of the effect you see here.
Maybe you'd want to start with a decent black and white photograph to get a better comparison.
No matter what you do you probably also don't want to end up with large patches of solid white or black in your source image (unless it's the background). The hair already feels like drowning in black. But to take care of that you need to use photoshop and be careful with the gradient curves :)
> I'm also really curious what contexts this has been most successful in. E.g. was it used for dithering in images or games back in the 1990's when we were limited to 16-bit or 256-bit color? Or is this something more recently explored in academia or in some niche imaging applications?
No need to speak in the past tense! It is not a "niche" application, either. Think about it: gray ink is almost never used. All printing into paper is done by dithering black ink into white paper. This includes bank notes, passports, product labels, etc. Besides dithering being used everywhere, it is a very active area of research, both in academia and in industry. In my lab we have seen a few industrial projects concerning dithering. It's a vast and very beautiful subject.
Huh, to be honest I feel like I've only ever seen halftoning when printing onto paper -- I've never associated dithering with printing at all.
And the "linear dithering" you're describing, when I think of images in certain banknotes and passports or quality seals that I'd call "engraved", I've always assumed were hand-drawn by an artist.
But I like what you're describing and linking to, as a way to achieve that hand-drawn effect algorithmically, to include a directional texture element! Thanks for sharing.
> Huh, to be honest I feel like I've only ever seen halftoning when printing onto paper -- I've never associated dithering with printing at all.
Yep, sorry about my sloppy terminology. I always use "halftoning" and "dithering" interchangeably. Yet, notice that today's printers are often matrix-based, i.e., like a high-resolution binary screen, with a bit of ink smearing depending on the type of paper/plastic.
> I've always assumed were hand-drawn by an artist.
Maybe some are still drawn by hand, but most printed stuff is at some point dithered automatically (and a lot of critical information can be embedded on the dithering patterns).
Wow! I just want to recommend the dither-me-this and find you already here :)
Also, the pattern-generator(https://doodad.dev/pattern-generator) is really amazing, applause!
202 comments
[ 5.2 ms ] story [ 243 ms ] thread[1]: https://news.ycombinator.com/item?id=25469163
[1]: https://en.wikipedia.org/wiki/Dither
https://levien.com/output_dependent_feedback.pdf
Wow, didn't know about that. It sounds quite similar to the more recent "electrostatic halftoning" algorithm by Weickert et al, that apparently does not cite your work:
https://www.mia.uni-saarland.de/Research/IP_Halftoning.shtml
Dithering as a digital signal processing technique is also used frequently in the digital control of physical systems. One example of this is in the control of hydraulic servo valves[1]; these valves are usually pretty small and their performance can be dominated by a lot of external factors. One of the biggest ones is "stiction", or static friction, wherein if the moving parts of the valve are at rest it can take a large amount of current to get them going again which translates in to poor control of the valve and in turn poor control of the thing the valve is trying to move. It's common to use very high frequency/small amplitude dithering on these valves to eliminate the effects of stiction without compromising accuracy which greatly improves the control stability and responsiveness of the servo valves.
1: https://en.wikipedia.org/wiki/Electrohydraulic_servo_valve
[0]: https://youtu.be/ap-BkkrRg-o?t=6516
[edit]
1 dimensional PIDs can end up in a sinusoidal dynamic equilibrium, and a 2 dimensional sine wave is an ellipse.
(Is there a name for this kind of curve?)
A sibling comment links to a Show HN that didn't get much attention, but is definitely worth checking out. I will also point out that it is possible to do dithering using GIMP (https://docs.gimp.org/en/gimp-image-convert-indexed.html). Alternatively, use ImageMagick if that is more your speed (https://legacy.imagemagick.org/Usage/quantize/#ordered-dithe...)
there's no better write up than https://bisqwit.iki.fi/story/howto/dither/jy/
> This paper introduces a patent-free positional (ordered) dithering algorithm that is applicable for arbitrary palettes. Such dithering algorithm can be used to change truecolor animations into paletted ones, while maximally avoiding unintended jitter arising from dithering.
He demonstrates it "live coding" style in this[1] video where he writes a demo in 256 colors of a "starfield" animation with color blending and Gaussian blur style bloom. The first animation at 6:33 using traditional ordered dithering has the usual annoying artifacts. The animation at 13:00 using an optimal palette and his "gamma-aware Knoll-Yliluom positional dithering" changed my understanding of what was possible with a 256 color palette. The animation even looks decent[2] dithered all the way down to a 16 color palette!
If that wasn't crazy enough, he also "live codes" a raytracer[3] in DOS that "renders in 16-color VGA palette at 640x480 resolution."
[1] https://www.youtube.com/watch?v=VL0oGct1S4Q
[2] https://www.youtube.com/watch?v=W3-kACj3uQA
[3] https://www.youtube.com/watch?v=N8elxpSu9pw
They do look good. This makes me want to run his animation examples on a blue noise dither, since he didn’t compare to blue noise, and it’s also animation safe...
> It feels a little weird to put 100 hours into something that won't be noticed by its absence. Exactly no one will think, "man this dithering is stable as shit. total magic going on here."
Luckily, thanks to this post, we have the privilege of thinking that.
(ETA: also the link that gruez posted. HN seems to be having some performance issues)
I can only refer to an article another comment also already mentioned. It is _excellent_ and covers animation & dithering: https://bisqwit.iki.fi/story/howto/dither/jy/
https://raw.githubusercontent.com/cyotek/Dithering/master/re...
DITHER.TXT is also available in the same folder.
http://www.markferrari.com/
....
I recall a recent kick-starter-type blog post about a work-in-progress game with huge 2d side scrolling dither art - can't find the link but :(
I expect something similar to apply to images.
I think this is a key lesson to people who apply these types of mathematical techniques to the lossy compression of data meant to be experienced by humans. Random noise is not always preferable to non-linear error, i.e. reducing non-linear error is not necessarily the equivalent of improving the perceived quality of the data in question. It can be but the function that determines what “looks good” or what “sounds good” to humans is probably a bit more complex.
This is something I’ve run into with image compression techniques but it applies here too (quantization being a form of compression). E.g. JPEG compresses images in 8x8 blocks because doing the whole image at once would look horrible. Figuring out the redundant information that can be thrown away with the least impact to image quality is still fundamentally an art.
Does it make money? There a couple other simple apps I've considered writing to see if I can make a few side bucks.
artists: - https://unomoralez.com - https://www.instagram.com/mattisdovier/?hl=en - https://wiki.xxiivv.com/site/dinaisth.html
I'm going to start raiding old Hypercard stacks next
https://mariteaux.somnolescent.net/junk/hypercard/
Raid away :)
[0]: https://surma.dev/things/c-to-webassembly/index.html
https://www.youtube.com/watch?v=9-6CKCz58A8&list=PLNYkxOF6rc...
A few years back, when TechShop still existed and was open, I made a present for my mother: a glass laser-etched and engraved with an image from her favorite comic. Because the comic was painted in a set of watercolors, this was going to be difficult. I ended up tracing the lines (for the deeper engraving) and then stomping on the color palette for the etching. Finally, I settled on different newspaper halftone sets for each "color."
It took several tries for it to come out alright. This might have saved me a few runs.
https://ditherit.com
It’s actually implemented in BitCam iOS app by icon factory: https://iconfactory.com/bc.html
And Emilio Vanni did a neat e-paper display experiment with it here: https://www.emiliovanni.com/atkinson-dithering-machine
https://www.tinrocket.com/content/hyperdither/
http://gazs.github.io/canvas-atkinson-dither/
Error diffusion causes problems for certain color palettes, but usually results in a smaller image size.
I've made a tool for doing this: https://doodad.dev/dither-me-this, you can easily half the size of a jpeg by dithering it and exporting it as a png.
I’m currently exploring this for my own applications, compressing large 8bit sprite sheet images, and it’s producing much smaller images than most palette based image formats (GIF, WebP, PNG, etc). Follow my progress here: https://twitter.com/mattdesl/status/1346048282494177280?s=21
https://pngquant.org/
I'm searching online but can't find anything at all. I've never heard of using Retinex in the context of dithering, and wondering what specifically you mean by Retinex-"like"?
I'm also really curious what contexts this has been most successful in. E.g. was it used for dithering in images or games back in the 1990's when we were limited to 16-bit or 256-bit color? Or is this something more recently explored in academia or in some niche imaging applications?
Here's a side-by-side comparison using an image from the front page of nytimes.com (be sure to click to zoom in for the full effect):
https://imgur.com/a/mrHl7FW
Without it (left), a photo remains "accurate" in terms of brightness levels.
But with it (right), it becomes far more high-contrast to feel closer to an illustration or painting. Which certainly makes it clearer. But while it brings out details in middle levels, it totally blows out shadows and highlights.
E.g. the texture of his mask, shirt, and her hand are much clearer. But on the other hand, their hair (and a background object) just turn solid black and lose all detail. But certainly, the vastly higher contrast makes for a much more compelling image IMO.
I agree; the filtered image (right) is more aesthetically pleasing; but it feels much less accurate. It would depend on the intent of the image I think. If you're creating art, and using photographs in the creation, it's not a problem. If you're reporting on the world and just want to reduce the data size (or use a monochrome output medium), I wouldn't do it like this.
Maybe you'd want to start with a decent black and white photograph to get a better comparison.
No matter what you do you probably also don't want to end up with large patches of solid white or black in your source image (unless it's the background). The hair already feels like drowning in black. But to take care of that you need to use photoshop and be careful with the gradient curves :)
No need to speak in the past tense! It is not a "niche" application, either. Think about it: gray ink is almost never used. All printing into paper is done by dithering black ink into white paper. This includes bank notes, passports, product labels, etc. Besides dithering being used everywhere, it is a very active area of research, both in academia and in industry. In my lab we have seen a few industrial projects concerning dithering. It's a vast and very beautiful subject.
> do you have any links to examples?
Take a look here for a couple of examples: http://gabarro.org/ccn/linear_dithering.html
And the "linear dithering" you're describing, when I think of images in certain banknotes and passports or quality seals that I'd call "engraved", I've always assumed were hand-drawn by an artist.
But I like what you're describing and linking to, as a way to achieve that hand-drawn effect algorithmically, to include a directional texture element! Thanks for sharing.
Yep, sorry about my sloppy terminology. I always use "halftoning" and "dithering" interchangeably. Yet, notice that today's printers are often matrix-based, i.e., like a high-resolution binary screen, with a bit of ink smearing depending on the type of paper/plastic.
> I've always assumed were hand-drawn by an artist.
Maybe some are still drawn by hand, but most printed stuff is at some point dithered automatically (and a lot of critical information can be embedded on the dithering patterns).
I'll be re-jigging it based on some info from that article, and definitely adding 'blue noise' as an option. Thanks for sharing.