The halftone technique demonstrated here takes a palette of 2 colors and increases it to something on the order of 20 apparent colors, but even with 20 there are extremely obvious bands.
That banding can be virtually eliminated by having way more colors (say, 256 if grayscale, 256^3 if RGB) or it can be virtually eliminated via dithering. I suspect the "error diffusion" technique (which is teased at the end of this demo) does what I'm talking about.
Noise is the key to dithering, and I don't see any noise in this demo. Everything is deterministic.
But the presentation is spectacular!
One standard point of view is that what introduces noise is quantization, in the sense that the quantized image has an unwanted difference from the desired image, and dithering consists of techniques to shape that noise. The Bayer-matrix ordered dithering algorithm presented here concentrates the noise at high frequencies where the eye is less sensitive to it, but it still retains some noise at lower frequencies, which is the banding you're commenting on.
Dave Long had the sharp observation earlier today that Bresenham-style line drawing is a form of dithering, where the signal being represented is the position of the pen rather than the brightness of the visual field. (I see that dreamcompiler made the same observation two days ago: https://news.ycombinator.com/item?id=45728962 but I don't know if Dave saw it there)
We had a good discussion of dithering here a couple of days ago, connected with a significantly more comprehensive article with a less fancy presentation: https://news.ycombinator.com/item?id=45728231
Bresenham is the equivalent of a sharp quantization, with no dithering. Using true 1D dithering for line drawing would instead result in a "wobbly" almost hand-drawn output.
In color dithering A is the set of colors in the original image and B is a smaller set of colors. Often just pure black and pure white, but that doesn't have to be the case.
In Bresenham A is the relative x,y coordinates of the ideal next pixel in the line if the pixels were infinitely small (thus |A| = infinity), while B contains the relative x,y coordinates of the 3 pixels that are actually available: +1,0; 0,+1; and +1,+1 (with appropriate rotation for the other 3 quadrants).
An important feature of Bresenham's is that the error inherent in this assignment is carried forth into the decision made for the next pixel, such that the total error is diffused along the line and its average value stays close to zero. Such error diffusion is also a feature of the best color dithering algorithms, but not the one described in TFA -- ordered dithering -- because ordered dithering is not a very good algorithm and is not used much today except when its peculiar artifacts are desired.
And yes, Bresenham's original algorithm does set each pixel it chooses to pure black, but this has nothing to do with its error diffusion mechanism. Bresenham's with grayscale is also a thing and it results in even better line approximations, but it's usually referred to as antialiased Bresenham.
I'm tempted to try the wobbly algorithm now to see what it looks like!
> The above thresholding matrix approach describes the Bayer family of ordered dithering algorithms. A number of other algorithms are also known; they generally involve changes in the threshold matrix, equivalent to the "noise" in general descriptions of dithering.
Basically, I'm leaning into "general descriptions of dithering" with my noise requirement, and the lack of noise in "ordered dithering" leads me to consider it not-quite-dithering.
The very first sentence of the general Dithering article [0] connects with my perspective as well:
> preventing large-scale patterns such as color banding
Aside: I probably misspoke with the word "halftone" earlier; apparently that's a specific thing as opposed to an umbrella term. I'm not sure there's a great word (other than "dither"...) for techniques to trade resolution for color.
The threshold map of ordered dithering is still a source of noise, it just happens to be carefully pre-baked so that (original image + noise)==output makes the output more legible than what you'd get from just mapping the original image pixels to the nearest available color.
The error diffusion is static and baked into the thresholds chosen, but it's still there and choosing the error diffusion properly still matters to getting a reasonable output.
The color Next machines only had 12 bit displays, 4 bits per channel, but with careful use of dithering it was often indistinguishable from a 24-bit display (so called "true color")
Turning Images into Dots: The Magic of Dithering https://www.youtube.com/watch?v=0L2n8Tg2FwI
Coding Challenge 181: Weighted Voronoi Stippling https://www.youtube.com/watch?v=Bxdt6T_1qgc
But I find this kind of presentation much harder to read than a classic blog post. It's difficult to skim through the text to see how far it goes (and the article structure is not apparent); instead, I was kind of forced to read the text sentence by sentence (since I was familiar with the topic, I wanted to skip over the basics).
I did a bit of ordered dithering on the ZX Spectrum Raytracer (https://gabrielgambetta.com/zx-raytracer.html#fourth-iterati...), it was surprisingly easy to implement and the results were great.
I wonder why it wasn't done more in the 80s (other than manual pixel art), probably just performance. I do remember seeing ordered dithering patterns in the 90s, in Windows 3.1 and in The Secret of Monkey Island VGA (I guess the backgrounds were hand-painted and scanned?).
The banding disappears and the noise introduced by dithering should hide the lack of depth completely to human eyes.
So a modern use for graphical dithering. And I'm sure there's more. It's not all for retro art.
Indeed, but most software does not do this. It's not on people's minds.
When people hear dithering they think of palette dithering.
People think 8bit/channel is enough; but it is not.
Because it is only 256 levels of any gradient. And because of gamma correction it's practically quite a bit fewer; about 14% (i.e. 220) on a full 256 step gradient that went through an sRGB OETF.
I maintain a Rust crate that solely concerns itself with dithering for such cases as the one you mention.
The readme has a gradient on top that should make it obvious why this matters.
It can be done in hardware, or even in the graphics driver. If you can combine spatial (for high resolutions such as 1440p or 4K) and temporal dithering you should expect very good results.
Black and white digital dithering of course has it’s roots in halftoning, which printing has used for more than a century, and it continues to be used for newspapers, for example.
Photoshop dithers by default when converting from 16 bits per channel to 8 bits. Lots of other image software doesn’t do this, but you start paying attention quickly, I learned from experience, when you order a poster-sized print for $100 and it comes out with visible banding you couldn’t see on your monitor.
Temporal dithering is much simpler algorithmically since you don't have to diffuse error over an area, just flicker a specific pixel between similar shades at the refresh rate.
Is this just me being dumb or the curse of knowledge where something is so obvious to the author that they don’t even bother explaining it?
That said, it might help to keep the ‘threshold’ part in mind. The grey pixels turn into black & white via thresholding, i.e., dithered_color = (raw_color > threshold_color) ? white : black; It might have helped if at the start the point was made that using a threshold map made of solid middle grey results in the un-dithered image.
You can use a random number for the threshold, i.e., dithered_color = (raw_color > random()) ? white: black; For either random threshold or a threshold map to approximate the original gray tone, the average threshold value needs to be 0.5. That’s a big clue in how you might start making your own ordered threshold map!
The next step is thinking a little about which pixels turn white as the gray value moves slowly from black to white. It’s best if each time a dithered pixel turns white, it’s not right next to the last one that turned white; you want there to be separate between white pixels when only some of them are white. 50% gray should be a checker board, for example, maybe as opposed to an 8x8 region where the left half is black and right half is white. 25% grey should perhaps be 1 white pixel in the top left corner of every 2x2 region.
There are a few different ways to achieve those goals, with slightly different tradeoffs, but those are the main things to consider. You might have a lot of fun designing your own threshold map before reading about how others do it. This is insanely easy to experiment with on ShaderToy…
If you apply a low pass filter to a dithered image, and compare it to a low passed filtered thresholded, you’ll see that the “illusory” shades are really there in the dithered version, they’re just represented differently in the full resolution image.
Similarly, a class D amplifier emits purely off/on pulses before a low pass filter is applied, but no one would call the output an auditory “illusion”. In the case of image dithering, isn’t the low pass filter your own vision + the distance to the screen?
All the computer did was add digitally-equivalent formats that decouple the information from its representation: the image can be little dots or hex values. Sampling theory lets us perform further tricks by defining correspondences between time, frequency and amplitude. When we resample pixel art using conventional methods of image resizing, it breaks down into a smeary mess because it's relying on certain artifacts of the representational scheme that differ from a photo picture that assumes a continuous light signal.
Something I like doing when drawing digitally is to work at a high resolution using a non-antialiased pixel brush to make black and white linework, then shrink it down for coloring. This lets me control the resulting shape after it's resampled(which, of course, low-pass filters it and makes it a little more blurry) more precisely than if I work at target resolution and use an antialiased brush; with those, lines start to smudge up with repeated strokes.
If you look at analogue B&W film for instance (at least the ones I’m familiar with), each individual crystal is either black or white. But the resolution is so high you don’t perceive it unless you look under a microscope, and if you scan it, you need very high res (or high speed film) to see the grain structure.
Dithering is not an illusion because the shades are actually still there. With the correct algorithms, you could upscale an image, dither it, down res it, and get back the exact same tones. The data isn’t “faked”, it’s just represented in a different way.
If you’re calling it an illusion, you’d have to call pretty much every way we have of representing an image, from digital to analog, an illusion. Fair, but I’d rather reserve the term for when an image is actually misinterpreted.
For example if you alternate blue and red every frame at 60~120 FPS, the only thing you'll see is purple.
There is a certain warmth (or maybe it’s just nostalgia) of these older techniques that can be harvested and combined with new ideas or new takes.
(Apologies for the Instagram links).
D.Y.O.R.:
https://www.instagram.com/p/DH1AjFzi3c6
D.Y.O.R. (printed):
https://www.instagram.com/p/Cjfzy23sCOg
Titles:
https://www.instagram.com/p/DHITpNYiWtF
Experiment on controlling the amount of dithering: