Dithering – Part 1
visualrambling.space425 points by Bogdanp a day ago
425 points by Bogdanp a day ago
This is halftone (i.e., an apparent palette with more colors than the actual palette, by ensuring that you aren't just rounding the same way everywhere) but it isn't dithering in my opinion. To me, dithering means fading away the banding that occurs when the palette (or the apparent palette achieved via halftone) isn't large enough to avoid banding on its own.
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!
Error-diffusion dithering or dithering with a precomputed blue-noise or white-noise pattern are also deterministic.
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
> 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.
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.
You're still thinking about dithering being about colors. It's about finding the best member of set B to stand in for a member of set A when |A|>|B|.
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 think zozbot was talking about the position and not the color, and they are correct that the positions of the pixels that get drawn in Bresenham are the nearest neighbors of the ideal positions, rather than having any sort of dithering applied to them. (I'm reluctant to call "nearest neighbor" a sort of dithering.) What's getting dithered is the slope, not the position. I was wrong about that.
It's error-diffusion dithering. You maintain an error accumulator from one pixel to the next, which keeps track of your departure from the desired slope, and you make a diagonal rather than paraxial move when it overflows. (Or is that only DDA?) But I guess you're right that the position isn't being dithered. It's the slope.
I'm tempted to try the wobbly algorithm now to see what it looks like!
The cool thing about Bresenham is that you're constantly picking the pixel closest to the desired slope but you never have to do the explicit division of deltaY/deltaX. The division happens implicitly as you draw the line, using only addition and subtraction of integers. Which was quite handy for the primitive computers circa 1960 when Jack Bresenham invented it.
You made me curious. It looks like dithering is still an accepted name for this kind of technique: https://en.wikipedia.org/wiki/Ordered_dithering
Glad I snuck in that it's just my opinion! But the article you linked to sort of admits what I'm saying:
> 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.
Dithering is the right term. It was called this even as far back as the Win 3.1 era where program installers typically showed you a full screen window with a background gradient that went from dark blue to black and used ordered dithering to make it look semi-respectable.
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.
I think that text is somewhat misleading because it leads people to believe that ordered dithering is not a kind of dithering, and also because the noise in general descriptions of dithering is not equivalent to changes in the threshold matrix. Rather, it is equivalent to differences between the input image and the output image. So I've fixed it.
Dithering as a mechanism to reduce/remove banding can be very impressive.
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")
I'm a pixel artist and everyone I know who uses this kind of technique calls it dithering.
Two videos from Daniel Shiffman's Coding Train:
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
Interesting topic. I appreciate the effort that went into this, there are some good animations.
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).
It may be more appropriate to compare this to a video than a blog post. This is an interactive video where you control the pacing, such that you don't have to pause if you need more time to read, and can advance as soon as you're done reading the current slide. I generally prefer text content over video content myself, but this seems fine as a variation of the latter.
I used different types of dithering (ordered, error diffusion) in many of my design projects as a visual language, static or animated, mostly for projects related to tech/computers/blockchain, sometimes combined with ASCII art.
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:
Great links. I just did my portfolio in a retro-ish style and started getting into making retro shaders. Check it out: https://olsz.me.
Very cool way to visualize it but I will be honest the threshold map doesn’t make sense. This didn’t seem to explain how to form the map, how to choose the threshold values, and so on. It showed grey pixels passing through white, black, and grey pixels and moved onto generalizing this pattern.
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?
How to build the ordered threshold map isn’t obvious, there are some very clever ideas & techniques.
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…
They say that part 2 will discuss how that’s formed, and 3 will discuss error diffusion dithering.
An incredibly beautiful visualisation but I felt the same. As well as being confused by the threshold map, at first the text seems to suggest that the 'binary' image is the input to the dithering algorithm in order to 'flip' some of the whites to black and vice versa but then it uses a gray area as input to the threshold map.
I wanted to love this so much but my eyeballs were screaming trying to read the text over the crawling dither pattern.
Surely dithering is good enough to display 10-bit colour on a non-10-bit monitor with good colour.
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.
> Surely dithering is good enough to display 10-bit colour on a non-10-bit monitor with good colour.
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.
> Indeed, but most software does not do this. It's not on people's minds.
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.
Modern printing uses dithering. When you’re going from a high bit rate down to 10 bits or 8 bits, it’s completely fine to use random dithering. Random might not be as fun to write about as Bayer dither patterns, or error diffusion, but for higher dynamic ranges, random is as effective.
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.
LCDs have actually used temporal dithering for ages to fake higher bit depth-- it let TN panels with 6 bits if precision per channel appear to have 8 bits of precision, and now it's being used for HDR-10 too!
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.
Yep and you can really tell on certain shades of grey when the screen is mysteriously flickering. Thanks Dell.
Great presentation, loved the format! Looking forward to the other two parts.
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?).
Beautiful demo, but I’m not sure it’s accurate to call dithering an “illusion” of more shades than is available?
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?
I would call it an illusion because if you pay attention you can clearly see that the color you perceive isn't actually present. You can see white on an RBG computer screen since your eyes simply don't have the resolution to discern the subpixel colors. However, in a dithered image with only black and white, you perceive gray, but you can also tell what the reality is without much effort. Personally, I think that fits the definition of an illusion.
In the case of dithering, that’s only because the monitor has insufficient resolution. Put a 1:1 Floyd steinberg dithered image on your phone, hold it at arm’s length, and unless you have superhuman vision you’ll already start having a hard time seeing the structure.
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.
I would define an illusion as something where your perception of a thing differs from the reality of the thing in a way that matters in the current context. If we were discussing how LCD screens work, I would call the color white an illusion, but if we were discussing whether to make a webpage background white or red, I would not call the color white an illusion.
That's verisimilitude. We were doing that with representational art way before computers, and even doing stipple and line drawing to get "tonal indications without tonal work". Halftone, from elsewhere in the thread, is a process that does similar. When you go deeper into art theory verisimilitude comes up frequently as something that is both of practical use(measure carefully, use corrective devices and appropriate drafting and markmaking tools to make things resemble their observed appearance) and also something that usually isn't the sole communicative goal.
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.
Do you consider the color yellow on your RGB monitor an illusion? (I do)
Same. A fun fact about this is as you increase the bit depth, the percentage of faked outputs actually increases as well. With just 8 bits, you have more 9's than AWS this year!
You can also add a temporal dimension (-> temporal dithering, also known as FRC).
For example if you alternate blue and red every frame at 60~120 FPS, the only thing you'll see is purple.
With red/blue artifacts visible when the viewer’s gaze passes rapidly across it.
Good lord this is a beautiful web experience
Once I made a transition between two ditherings: https://github.com/bntre/dithering-gradient-py
Obligatory link to the in-progress forum post about the development of The Return of the Obra Dinn's dithering effect: https://forums.tigsource.com/index.php?topic=40832.msg136374...
The difficulty for dithering on an interactive 3d scene is in making the dithering stable on camera rotation, otherwise you get a twinkling stars effect, not dissimilar to the "fireflies" in reflections in ray-traced games.
And here's a couple videos about a technique that was inspired by the Obra Dinn's dither, but making it surface stable:
https://www.youtube.com/watch?v=HPqGaIMVuLs (explanation)
These are absolutely amazing, thank you! I had wondered whether something like this was possible because I have this 1-bit-deep screen here, and now I'm delighted to see that it is. I'm just not sure if my machine has enough CPU to manage it.
We had another dithering post a few days ago and nobody answered my question... I'm reposting in case someone who comes here knows the answer:
"Does anyone know of any application/tool that can perform palette dithering? The idea is "here is a n-color palette specified in their RGB values, here is the full-color RGB image, give me the best possible dithered image using the provided palette". The tools that I've used were underwhelming and produced results full of banding and artifacts.
Basically, great dithering in color instead of B/W."
EDIT: Thank you for the answers! I'll check all links.
I left a comment [0] on the other thread, and this is irrelevant if you aren't using Photoshop, but there's a plugin called DITHERTONE Pro that gives you a lot of control over the dither algorithm used + color grade. For actual design, I tend to use this since I'm already in PS cobbling together an image, and you can tweak the results in realtime to dial it in how you want.
I also have used didder [1] a couple times for dithering via CLI / script. Its results can be pretty good too, just more for repeatable batch operations and you need to make sure your palettes and chosen algorithms will produce what you're actually looking for.
Cole (the author of didder) also has a GUI version called Dithertime: https://makew0rld.itch.io/dithertime
That’s going to be a tricky problem full of compromises, and entirely up to how you formalize your definition for “the best possible dithered image”.
Do you care about preserving relative brightness, contrast, edges,… etc.
Human color perception is tricky, and in the outline you give it’s entirely possible that the provided n-color palette (also, what order of magnitude n are we talking about here?) would be inadequate for a satisfactory rendering of the provided full color image.
I responded in that post (though not to you, and probably not what you're after) with a link to my JS canvas library's "reduce palette" filter. It includes both supplying an array of colors to act as the palette, and setting the required number of colors for which the filter can calculate a "commonest colors" palette, calculating color distances in the OKLAB color space - https://scrawl-v8.rikweb.org.uk/demo/filters-027.html
If anyone wants to see the filter code, it in the GitHub repo here: https://github.com/KaliedaRik/Scrawl-canvas/blob/064469928a3...
I’m using this for making some quake inspired textures - it’s a bit clunky but works for me https://captain4lk.itch.io/slk-img2pixel
ImageMagick with `-dither` and `-remap` could also work. For remap you would need an image with your desired palette, and IIRC you could use ImageMagick to produce that image but I cannot recall the incantation required for that.
Use Google's Squoosh.app: https://squoosh.app
When editing an image you can choose the 'Reduce palette' option to bring up a way to reduce the number of images used, and the palette reduction panel will let you optionally apply dithering or not.
The dithering algorithm is not selectable but it's worth trying to see if you like it.
This is common functionality in graphics software, but there isn't such a thing as "the best possible dithered image using the provided palette"; there are unavoidable tradeoffs between sharpness and color precision, so different ways of dithering may be better for different purposes.
I don't know if it's exactly what you're looking for but I made a free tool https://app.dithermark.com . It only allows 18 colors max, but it has a lot of options, including the ability to determine what color palette to use.
The gimp can do this.
Define your palette, then via the dialog spawned through image->format menu, pick your palette from the list.
Yes, but the algorithm isn't that great... That's what I'm using now
"Positional" is a single, relatively boring hardcoded pattern, and the other options are Floyd–Steinberg error diffusion.
I do agree it would be nice to extend gimp to do all sorts of fancy dithering, and imagine it's just that nobody has put on the work yet.
Floyd–Steinberg is pretty great when your palette has reasonably-close colors.
This was an amazing presentation! In one of the earliest screens, it is demonstrated that there are more or less 8 different shades of gray from just different patterns of black/white pixel arrangement. Is it possible to use the “blow up” view to classify the different shades of gray in an image to determine what the pattern should be for a given pixel grouping should be? Maybe this would be accomplishing the same thing the threshold filter accomplishes and have the same end result or possibly a different dithering method. Just trying to integrate this into my brain.
Somehow my first time seeing Visual Rambling, absolutely beautiful site
This is really cool! I always thought dithering was just blending two colors by alternating adjacent pixels, I didn't know there was more ways to do it than one.
I've been working on an implementation of this in Rust actually, weird timing. Cool article.
A friend of mine wrote one for Go with the goal of creating the best and most complete dithering library out there and I think he did a decent job. Worth a look if you're looking for reference implementations!
Here's his: https://github.com/makew0rld/dither
Hei, if someone wants to implement this, feel free to contribute this to my Phomemo M02 (a cheap < 15$) black and white thermal printer, web app.
I can appreciate the passion and consideration that went into this presentation of the subject!
Amazing animations!
Few things brighten my browsing day as much as a virtual ode to dithering.
Amazing!!!
unbelievable. gifted explainer!
To the webpage author, I'd suggest adding WASD navigation as an alternative to cursor keys.
Ah, yes, the usual "Umm, ackshully this issunt dithering IMHO" segment of the audience is here.
There's a weird subset of graphic design grifters on social media obsessed with dithering right now.
Submission from the dev earlier https://news.ycombinator.com/item?id=45694750
Why do you think the term “grifter” applies here?
not here as in HN, out on social posts.... some unhinged claims about inventing dithering trends and a lot of startup/techbro types putting the 'aesthetic' forward as the goto way to success. shrug.
I don't think GP meant "here" the way you are interpreting "here" (i.e., this site / that site). Rather, I think they meant "here" to mean "in the sentence you wrote."
Put another way, I think GP was asking why you think the term "grifter" has anything to do with graphic designers who are obsessed with dithering right now. Basically, you aren't asserting that they're obtaining value illicitly (i.e., swindling, conning), as would need to be the situation for a grift to occur. If they're convincing customers that their dithering product is a must-buy because dithering is the best thing ever, and the customer hands over their money upon being convinced, that really isn't a grift unless the product somehow ends up not doing the thing.
If I lie on a website, and the subsequent wave of additional readers leads me to collect tons of ad revenue, the readers have not been grifted (they still have their money) and the ad network was not grifted (I gave them legitimate traffic). If I lie to a reader in order to take the reader's money, then at that point yes, the reader was grifted.
While I enjoyed the whole presentation, my favorite part after progressing through the entire deck was pressing my back button once and landing right back here on HN :)