Back when I worked at Marvell Semiconductor (circa 2005), we made laser printer ASICs for HP. We did a lot of dithering in hardware. We had a hardware block that did error diffusion, we had a hardware block that did regular diffusion. We also had a hardware block that did Blue Noise. I was responsible for implementing the firmware that drove those printers' scan/copy path: scan an image in monochrome, run through the dither hardware to create the bit pattern fed to the laser engine.
No one could explain to me how to use the blue noise block. I couldn't understand what the blue noise block was doing. This is the first article that explained, in terms I could understand, how blue noise dithering works.
Now that's amazing. Not only because it was hardware based, but because you were solving a real problem, a limitation, instead of just aesthetic endeavor. It was an engineering solution. There is a lot of aesthetic beauty in mundane engineering, rarely seen by anyone. So kudos to designers to pick out something interesting and giving it the light :) It's all cool.
Not the OP, but since repeatability is not a problem you can just use any cheap and insecure random number generator and hardcode a constant for the seed.
We had to generate values in firmware then populate a LUT. IIRC we just used a simple pseudo-random number generator from the C library. Non-crypto so it didn't matter too much.
Well, LFSR RNG-s are pretty efficient in terms of HW space. You take a single-bit wide shift registers of length n, and feed back its output to the beginning XOR-ed with predefined bits in the shift register.
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.
> 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 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 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.
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 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.
If you don't mind, I'll plug a little innovation of my own: mixing ordered and error diffusion dithering. The idea behind it is actually pretty simple: technically all forms of dithering use a threshold map, we just don't tend to think of it when it's one flat threshold for the entire image. So there is nothing stopping us from decoupling the threshold map from the rest of the dithering algorithm, meaning it's trivial to combine error diffusion with more complex threshold maps:
(For the record, I picked a default example that highlighted a "hybrid" dither with a very dramatic difference from its "parents" instead of the prettiest result)
Interestingly, and perhaps not surprisingly, a variable threshold map interacts with the error diffusion itself, making it amplify local contrast and recover some fine detail in shadows and highlights (although also possibly overdoing it and crushing the image again).
What's also somewhat interesting (to me at least) that this is really simple to implement: take any error diffusion dithering kernel and make it use the threshold map from ordered dithering. In principle it should have been possible to use them on any old hardware that can handle error diffusion dithering.
I'll also plug an invention of my own: error diffusion with a random parameter in the diffusion matrix, keeping the sum of weights constant (and equal to 4/5, so boosting contrast slightly).
I came up with this for a Code Golf challenge a few years ago, personally I think it looks really good. I haven't seen it elsewhere.
Disclaimer: yes I like to write ugly Fortran code for fun (and profit).
That is a very elegant trick, I love it! I wonder what comes out of that when applied to a flat grayscale image - perhaps it leads to a decent blue noise pattern, or an approximation of it? EDIT: The reason I'm half-expecting that is because semi-randomizing the diffusion matrix reminds me a bit of Bridson's Algorithm, in that it mixes constraints with randomization[0].
And kudos for sticking to the programming language you love and feel comfortable in :)
EDIT: Something I never noticed before: a black and white dithered image causes flickering when scrolling on an LCD screen, as least on mine, and it amplifies regions with patterns, like the checkerboards in ordered dithering, or the regular artifacts like in the example image of the challenge.
However, your "randomized Sierra Lite" version seems to mask that flickering: it's still there, but feels much more like white noise that is relatively easy to ignore.
I am in the same boat as the author of having only recently played Return of the Obra Dinn between Christmas and new years. I cannot recommend it enough, if you haven't played it and like puzzlers you should pick it up.
It's an extremely engaging story, and a narrative tool I have not previously encountered. No spoilers as this is revealed immediately, but essentially you are navigating past events through frozen timepoints at the moments when people died, and have to determine the identities and fates of all the about 60 crew aboard the boat, which requires a bit of puzzling things together across the different events that lead to peoples deaths.
I doubt we'll see a similar follow up game from Lucas Pope, as he has commented this game grew much larger than he expected and he would scale back for his next projects. Also from papers-please to Obra Dinn he seems to be one to break the mold at each iteration, but I really wish there where more games like this, with different stories to investigated.
I share your love for Return of the Obra Dinn, truly a masterpiece and a game which shocked me out of my usual apathy towards recent videogames.
I have faith in Lucas Pope for whatever project he decides to tackle next. Two of his games are masterpieces, this one and Papers Please, and I also liked Helsing's Fire a lot. Whatever he does next, regardless of scope and theme, will surely please me.
This game was so freaking good, and I also agree, I'd become sort of bored of video games until this was recommended. I stayed glued to the game until I 100%ed it (didn't take me too long, maybe around 20 hours). I really really wish I could forget the game and replay it, or that there was a part 2, or something. Incredibly creative and well-made.
Not in the same boat as the author but in the past few weeks I've been getting into e-Ink displays and making gadgets and framed art with them, and most of the displays I can get a hold of are either 1-bit or 4-bit greyscale, so this is super relevant.
My "crude" dithering algorithm I wrote though seems not mentioned in the article. What I do is (in the case of 1-bit) just let the grey value (from 0.0=black to 1.0=white) determine the probability that the pixel is on or off, and render pseudorandom numbers according to those probabilities. In the case of 4-bit greyscale I do the same but within 16 bins.
I'm not sure how it compares to the methods in the article but maybe I can test this sometime.
You can actually combine error diffusion with your probability-based approach, which helps reduce patterns if I remember correctly (it's been a very long time).
May as well ask here, the ESRB rating at the bottom of the Obra Dinn page [1] highlights "intense violence". Is this accurate? I'm a big wimp about visceral violence, so I'd prefer to have some idea before paying up. If 1/4 of the crew got disemboweled or something, I'm probably out.
There definitely is violent scenes and sounds in the game. I would not recommend playing it with young children for instance. However I would myself not put in the same box as other games in the "intense violence" category.
Mostly because and this may sound silly, but it's not "violence in motion". You are viewing a murder scene, and someone died, and you might hear someone take the last breaths of their life. Which has a very high emotional impact which should not be ignored. But that to me is still fundamentally different from gory/bloody games with often fast visceral violence.
As mentioned by others, the scenes themselves are calmed a lot by the dithering art-style.
I would say about the emotional content though that this hits differently from other stories where characters die because of the narrative tool. You never have a Game of Thrones moment where a character you are heavily invested in suddenly dies, because even though you learn about the passengers and feel for them in their misery, you also realize up front even before you learn about them that they have died and you are just looking at memories before that event.
I have only played for a few hours, but all the violence (so far) has been communicated via sound effects during blacked out cut scenes (no visuals). The sound effects in the game are really well done and visceral, but otherwise you just see the low res frozen time ‘results’ of these cut scenes (e.g. a dead body under a cannon, a skeleton crushed and distorted, etc).
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?
> 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.
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:
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 :)
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.
It's so interesting to read about the rediscovery and reengagement with dithering by newer generations. I grew up when dithering was simply a fact of life because of the extremely limited graphics capabilities of early computers.
I love the reference to Obra Dinn as the graphics remind me of very fond feelings I had for the first black and white Macintoshes. There was something wonderful about the crisp 1-bit graphics, on a monitor designed for only those two colors, that made it look "better" than contemporary color displays in most respects -- almost higher resolution than it actually was. It's kind of almost impossible to replicate how it looked on modern color displays.
I didn't experience that feeling looking at an electronic display again until the Kindle. It also had the funny side-effect of making art assets on Macintoshes a fraction of the size as on color systems, making both the software smaller, and the hard-drives hold more.
There's also something somewhat unsatisfying about automatically generated dithering patterns used to recast color graphics into 1-bit b&w. It seems to really take an artist's hand to make it look beautiful. However, the author of this post ends up with some very nice examples and it's really well written.
If anybody is interested in seeing how the old systems looked, and some great uses of dithering throughout, I'd recommend checking out this amazing Internet Archive Mac in a Browser - https://archive.org/details/mac_MacOS_7.0.1_compilation
You get dithering literally at the system startup background.
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/
> However, sRGB is not linear, meaning that (0.5,0.5,0.5) in sRGB is not the color a human sees when you mix 50% of (0,0,0) and (1,1,1). Instead, it’s the color you get when you pump half the power of full white through your Cathod-Ray Tube (CRT).
While true, to avoid confusion, it might be better rephrased without bringing human color perception or even colors into the mix.
sRGB uses non-linear (gamma) values, which are good for 8-bit representation. However, operating on them as normal (linear) numbers using average (expecting blur) or addition, multiplication (expecting addition, multiplication of corresponding light) - gives nonsensical, mathematically and physically inaccurate results, perceived by any sensor, human or animal as not what was expected.
RGB colorspace in it's linear form is actually very good for calculations, it's the gamma that messes things up.
In simplified monochrome sRGB/gamma space, a value v means k·v^g units of light, for some k and gamma g = 2.2.
Attempting to calculate an average like below is simply incorrect - you need to degamma¹ (remove the ^g), calculate and then re-gamma (reapply ^g).
I always feel we have way too many historical burdens (which were good compromises at the time) in (digital) image/video field.
In no particular order (and some are overlapping), I can immediately think of gamma, RGB/YCbCr/whatever color models, different (and often limited) color spaces, (low-)color depth and dithering, chroma subsampling, PAL/NTSC, 1001/1000 in fps (think 29.97), interlaced, TV/PC range, different color primaries, different transfer functions, SDR/HDR, ..
the list can go on and on, and almost all of them constantly cause problems in all the places you consume visual media (I do agree gamma is one of the worst ones). Most of them are not going anywhere in near future, either.
I often fantasize a world with only linear, 32-bit (or better), perception-based-color-model-of-choice, 4:4:4 digital images (similar for videos). It can save us so much trouble.
That's a bit like saying that we shouldn't use lossy image/video compression.
Do you realize the amount of 'waste' that a 32bpc†, 4:4:4, imaginary color triangle gamut picture would have ?
†it looks like the human eye has a sensitivity of 9 orders of magnitude, with roughly 1% discrimination (so add 2 orders of magnitude). So, looks like you would need at least 37 bits per color with a linear coding, the overwhelming majority of which would be horribly wasted !
I don't think of colorspaces as "historical burdens". I don't like that CRT monitors are brought up every time sRGB is mentioned though. I know it has historical relevance, but it's not relevant anymore, and it's not needed to understand the difference between linear and non-linear colorspaces.
Are you sure about sRGB being already good enough for averaging ? (As long as we don't want to go to a wider color space of course.)
We have been recently taught how to do it 'properly', and we had to go through CIELAB 76 (which, AFAIK, is still an approximation, as human perception is actually non-euclidean).
If you want physically accurate averaging (resize, blur etc), then RGB is fine, as long as you use linear values (or do long-winded transformed math). AFAIU it is by definition 100% physically accurate. As was said, sRGB uses gamma values, where typical math creates ill effects, as in many if not most typical programs.
If you want to do perceptually uniform averaging of colors, color mixing / generating / artistic effects, that's something else entirely.
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...
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/
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.
Frustrated that Firefox doesn't support "image-rendering: pixelated". FF supports "crisp-edges" and happens to implement that as nearest-neighbor filtering but the spec says that is not the meaning of "crisp-edges".
I don't understand why Firefox is dragging their feet on this. It seems like such an easy thing to add. In fact given their current implementation they could just make `pixelated` a synonym for `crisp-edges` and ship it
I'm surprised the algorithm for producing blue noise is so complicated.
Could you not generate white noise, then apply a high-pass filter? Say, by blurring it and then subtracting the blurred version from the original?
Could you split the map into blocks, fill each block with a greyscale ramp, then shuffle the pixels inside the block?
Could you take a random sudoku approach, where you start with a blank map, then randomly select pixels, look at the distribution of pixels in their neighbourhood, randomly pick one of the greyscale values not present (or least present) for that pixel, then repeat?
The first technique is challenging because the filter needs to have a specific frequency response, without shortcuts. Such high quality filtering can be done more simply and more exactly with an inverse Fourier transform.
The second technique doesn't seem promising because shuffling is very crude: differently shuffled small blocks are going to have border artifacts, repeating small blocks are going to have worse periodic artifacts, large blocks are going to approximate white noise rather than blue noise. Higher quality would require precomputing blue noise images, losing the advantage of on-the-fly computation.
The third technique, being sequential, is unlikely to be practically cheaper than an inverse Fourier transform.
I only went as far as generating threshold maps, not actually using them. Couldn't see how to do that using ImageMagick, and didn't want to write it manually!
The high-pass filter maps "look okay", but i haven't looked at their spectrum. How important is it that they have a specific frequency response? What is the failure mode if they don't?
The shuffling maps don't "look" so hot. There aren't border artifacts or repeating blocks (and you wouldn't expect these a priori - not sure why you think that), but indeed, it's not very different to white noise.
> “Bayer dithering” uses a Bayer matrix as the threshold map. They are named after Bryce Bayer, inventor of the Bayer filter, which is in use to this day in digital cameras.
Dynamic Rounding, developed by Quantel back in the 90s for digital video+film, is underappreciated. Dynamic Rounding + Blue Noise is severely underappreciated.
You still need dither for print, where subtle gradients on-screen can suddenly become very visible. I’ve had some large format giclee prints surprise me with nasty color banding.
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.
iirc, back in ~99, Unreal Engine was doing dithering on the u/v coordinates (!!) for texture mapping instead of bilinear interpolation. They used fixed Bayer matrix.
This was quite faster, visually pleasant, and was adapting nicely to viewing distance.
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.
I always thought the floyd-steinberg algorithm produced images that looked like they were made from a nest of worms, at least in the implementations I came across in the Amiga era, so it's interesting to look at his FS image and realize that, most likely, it was an artifact of the low resolution display more than anything else.
> With HDR and wide gamut on the horizon, things are moving even further away to ever requiring any form of dithering.
My impression is that, if anything, the almost total dominance of sRGB (in the consumer space) is coming at an end in the digital mediums, on one side from the generalization of wide gamut and high dynamic range transmissive LCD/LED screens, and on the other end the rising wave of both (higher frequency) black & white and color e-ink. (And I'm still hopeful for the resurrection of transflective LCDs, like in Pebble.)
So I would expect dithering to come back, either to avoid banding on lower bit per color displays, and/or 'add' colors to lower color gamut ones.
For instance, my 2009 LCD is a 8bpc wide gamut one (and fairly high dynamic range too). So if I were to take full advantage of it (leaving sRGB), I would require dithering to avoid banding.
If you want to play around with dithering on macOS or iOS, vImage in the Accelerate framework provides most of the algorithms discussed in the article (including Atkinson!), with performance more than adequate for most applications (and with convenient vImage utilities to fit them into a CV pixel buffer pipeline for video work). vImage also supports dithering to other bit depths, though one-bit output is what you want for that vintage look.
The default Ubuntu photo viewer shows it in the same way.
Also, for his second 'improved' dithering, the dithering clearly doesn't correspond to the undithered gradient (both undithered gradients seem to be the same in both pictures ??)
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)
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.
I think both gradients are "wrong" in that they themselves interpolate without correcting for RGB. I think the first example thte original and dither are wrong in the same way, while in the second the dither is more right than the gradient is.
Basically I'm afraid the author of this post is a bit of a "careless eager student" archetype who, while generously pointing out the gotchas that to an expert might be second nature, is also introducing unintentional errors that add some confusion right back.
I'm not expert in color, but with anything with soo many layers of abstractions (physical, astronomical, psycological, various models that approximate each), it helps to work symbolically as long as you possibly can so the work can be audited. Trying to correct from the current "baked" state is numerical hell.
If it does, then it probably means you've got some funky substandard or non-standard LCD panel or gamma setting or color correction on whatever you're viewing it on.
Which isn't terribly unusual. But if your screen is well calibrated, then no -- the sRGB gradient should by definition be identical. That's literally the specification.
(And it is on my MacBook, as Apple screens tend to be among the most accurate of general consumer screens.)
The sRGB version is evenly balanced bitwise yet 'gamma free'. The linear RGB version appears bitwise imbalanced due to gamma correction, but cross your eyes and blur your vision, and you'll see the linear RGB is actually more gamma correct! (Better contrast and luminosity)
Interesting, I "dither" (shift the telescope around between photos) my astrophotos to go from noise to less noise - funny seeing it go from image to noise. Does anyone have any papers on dithering + image integration to go in this direction? always been interested in knowing more about it.
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!
3 minutes to generate 64 by 64 pixels blue noise? I think one should be able to instead draw white noise in frequency domain, multiply with a noise amplitude profile and then a 2D FFT...should only take some milliseconds..
That's right! I was so confused when I read the article, and being satisfied with getting just a 50% boost from using your home brew FFT, was somewhat disheartening.
That is truly like if you're happy that your implementation of quicksort is 50% faster than your insertion sort. It's just that bad of a result, that you really have to stop and wonder if perhaps you did it wrong.
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.
I had never read about dithering before, but this article sparks interest. Coupled with sample images, it is fun to read about the different dithering algorithms. Thanks for sharing!
Slightly offtopic, but this is a greate opportunity to ask what I always wanted to know. Can anybody tell me how protraits like the one in the linked article below are made? I always loved this dithering style.
I think there is a trade-off between spatial resolution and color depth. Dithering reduces the former to simulate increasing the latter.
Perhaps we can get a similar result by interpreting the original signal (after linearization) in a different way. It could represent (after normalization) the probability each pixel would be 1 or 0. That way, brighter areas would have more density of bright pixels, and darker areas would have more density of dark pixels.
Here’s a cool rust crate that does color quantization and dithering at the same time. Ie picking the palette to use and dithering the picture with that palette as an evolving context.
https://github.com/okaneco/rscolorq
It’s a port of an older c library that’s based on a paper/algorithm called spatial color quantization.
Great resource!
I played myself with dithering, applying it to images fetched from nasa's apis, from the rovers on mars and open sourced it. I really enjoyed the visual outcome, you can see it here:
https://github.com/danieledep/rovers-dithering-playground
Here's a trick. Before you do anything.... Add noise. Then use error diffusion. Looks pretty good for how crazy fast it is.
Figuring out the strength of the noise is tricky. Usually 5 to 10 percent. I'd suggest random RGB and not monochrome noise(so not quite how you've coded the randomness, but similar idea), as this should create more unique values and reduce patterned artifacts.
Another good article about dithering algorithms is https://www.freesion.com/article/3406137250/. It goes through most of the matrix-based dithering algorithms, including the more obscure ones.
Tangential, but when I view certain dithered images in that article and on the demo page, my entire monitor drops in brightness by a bit. As soon as I scroll away, the monitor returns to normal brightness.
I wonder if this is a result of hardware or something on the software / driver side.
The author didn't cover it, but it's common to alternate the direction of error diffusion passes line-by-line. This improves Floyd-Steinberg dithering by a lot in my experience.
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!
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.
Since printers do this, I always wondered if there's a good way to undo dithering (at the cost of resolution) for scans. Would it just be scaling down the image?
it's also possible to get a little better results by cheating a little bit with the error distribution, Ulichneys ξ1 and ξ2 as in "Simple gradient-based error-diffusion method" Journal of Electronic Imaging jul/aug 2016.
Back when I worked at Marvell Semiconductor (circa 2005), we made laser printer ASICs for HP. We did a lot of dithering in hardware. We had a hardware block that did error diffusion, we had a hardware block that did regular diffusion. We also had a hardware block that did Blue Noise. I was responsible for implementing the firmware that drove those printers' scan/copy path: scan an image in monochrome, run through the dither hardware to create the bit pattern fed to the laser engine.
No one could explain to me how to use the blue noise block. I couldn't understand what the blue noise block was doing. This is the first article that explained, in terms I could understand, how blue noise dithering works.
I can die happy. Thank you.
This is a lovely compliment. Thank you for taking the time to write it :)
Thank you for such a great blog post that even years later, I could catch up and understand!
(We never did turn on the blue noise block. Even today, it sits idle. Sad.)
Folks interested in learning more about dithering in genreal or blue noise dithering in particular should read Bart Wronski's blog posts here:
https://bartwronski.com/2016/10/30/dithering-in-games-mini-s...
Now that's amazing. Not only because it was hardware based, but because you were solving a real problem, a limitation, instead of just aesthetic endeavor. It was an engineering solution. There is a lot of aesthetic beauty in mundane engineering, rarely seen by anyone. So kudos to designers to pick out something interesting and giving it the light :) It's all cool.
There is no math.Random() in hardware, so I have to ask: what algorithm did the noise block use? :)
Not the OP, but since repeatability is not a problem you can just use any cheap and insecure random number generator and hardcode a constant for the seed.
8 replies →
We had to generate values in firmware then populate a LUT. IIRC we just used a simple pseudo-random number generator from the C library. Non-crypto so it didn't matter too much.
Well, LFSR RNG-s are pretty efficient in terms of HW space. You take a single-bit wide shift registers of length n, and feed back its output to the beginning XOR-ed with predefined bits in the shift register.
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.
Thanks for the kind words!
This guys' articles are wonderful. I was experimenting with compiling C to WASM[0] and Surma's was really helpful.
[0]: https://surma.dev/things/c-to-webassembly/index.html
His HTTP203 series with Jake Archibald is amazing if you happen to be a frontend developer.
https://www.youtube.com/watch?v=9-6CKCz58A8&list=PLNYkxOF6rc...
1 reply →
> 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.
1: https://en.wikipedia.org/wiki/Electrohydraulic_servo_valve
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
Good image dithering algorithms do maintain sharp features like edges.
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.
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 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.
[0]: https://youtu.be/ap-BkkrRg-o?t=6516
Anything controlled by a PID can easily end up in a circular pattern, so it's not a given that this was to avoid stiction.
[edit]
1 dimensional PIDs can end up in a sinusoidal dynamic equilibrium, and a 2 dimensional sine wave is an ellipse.
1 reply →
PWM signals are dithered by definition, and are probably the most common interface, no?
Servo valve dithering is overlaid on top of the PWM duty cycle.
If you don't mind, I'll plug a little innovation of my own: mixing ordered and error diffusion dithering. The idea behind it is actually pretty simple: technically all forms of dithering use a threshold map, we just don't tend to think of it when it's one flat threshold for the entire image. So there is nothing stopping us from decoupling the threshold map from the rest of the dithering algorithm, meaning it's trivial to combine error diffusion with more complex threshold maps:
https://observablehq.com/@jobleonard/ordered-error-diffusion...
(For the record, I picked a default example that highlighted a "hybrid" dither with a very dramatic difference from its "parents" instead of the prettiest result)
Interestingly, and perhaps not surprisingly, a variable threshold map interacts with the error diffusion itself, making it amplify local contrast and recover some fine detail in shadows and highlights (although also possibly overdoing it and crushing the image again).
What's also somewhat interesting (to me at least) that this is really simple to implement: take any error diffusion dithering kernel and make it use the threshold map from ordered dithering. In principle it should have been possible to use them on any old hardware that can handle error diffusion dithering.
I'll also plug an invention of my own: error diffusion with a random parameter in the diffusion matrix, keeping the sum of weights constant (and equal to 4/5, so boosting contrast slightly).
I came up with this for a Code Golf challenge a few years ago, personally I think it looks really good. I haven't seen it elsewhere.
Disclaimer: yes I like to write ugly Fortran code for fun (and profit).
https://codegolf.stackexchange.com/a/26569
That is a very elegant trick, I love it! I wonder what comes out of that when applied to a flat grayscale image - perhaps it leads to a decent blue noise pattern, or an approximation of it? EDIT: The reason I'm half-expecting that is because semi-randomizing the diffusion matrix reminds me a bit of Bridson's Algorithm, in that it mixes constraints with randomization[0].
And kudos for sticking to the programming language you love and feel comfortable in :)
EDIT: Something I never noticed before: a black and white dithered image causes flickering when scrolling on an LCD screen, as least on mine, and it amplifies regions with patterns, like the checkerboards in ordered dithering, or the regular artifacts like in the example image of the challenge.
However, your "randomized Sierra Lite" version seems to mask that flickering: it's still there, but feels much more like white noise that is relatively easy to ignore.
[0] https://observablehq.com/@techsparx/an-improvement-on-bridso...
I am in the same boat as the author of having only recently played Return of the Obra Dinn between Christmas and new years. I cannot recommend it enough, if you haven't played it and like puzzlers you should pick it up.
It's an extremely engaging story, and a narrative tool I have not previously encountered. No spoilers as this is revealed immediately, but essentially you are navigating past events through frozen timepoints at the moments when people died, and have to determine the identities and fates of all the about 60 crew aboard the boat, which requires a bit of puzzling things together across the different events that lead to peoples deaths.
I doubt we'll see a similar follow up game from Lucas Pope, as he has commented this game grew much larger than he expected and he would scale back for his next projects. Also from papers-please to Obra Dinn he seems to be one to break the mold at each iteration, but I really wish there where more games like this, with different stories to investigated.
I share your love for Return of the Obra Dinn, truly a masterpiece and a game which shocked me out of my usual apathy towards recent videogames.
I have faith in Lucas Pope for whatever project he decides to tackle next. Two of his games are masterpieces, this one and Papers Please, and I also liked Helsing's Fire a lot. Whatever he does next, regardless of scope and theme, will surely please me.
This game was so freaking good, and I also agree, I'd become sort of bored of video games until this was recommended. I stayed glued to the game until I 100%ed it (didn't take me too long, maybe around 20 hours). I really really wish I could forget the game and replay it, or that there was a part 2, or something. Incredibly creative and well-made.
Not in the same boat as the author but in the past few weeks I've been getting into e-Ink displays and making gadgets and framed art with them, and most of the displays I can get a hold of are either 1-bit or 4-bit greyscale, so this is super relevant.
My "crude" dithering algorithm I wrote though seems not mentioned in the article. What I do is (in the case of 1-bit) just let the grey value (from 0.0=black to 1.0=white) determine the probability that the pixel is on or off, and render pseudorandom numbers according to those probabilities. In the case of 4-bit greyscale I do the same but within 16 bins.
I'm not sure how it compares to the methods in the article but maybe I can test this sometime.
>(in the case of 1-bit) just let the grey value (from 0.0=black to 1.0=white) determine the probability that the pixel is on or off
This is equivalent to the random noise [-0.5; 0.5] before quantization example.
1 reply →
You can actually combine error diffusion with your probability-based approach, which helps reduce patterns if I remember correctly (it's been a very long time).
May as well ask here, the ESRB rating at the bottom of the Obra Dinn page [1] highlights "intense violence". Is this accurate? I'm a big wimp about visceral violence, so I'd prefer to have some idea before paying up. If 1/4 of the crew got disemboweled or something, I'm probably out.
[1] https://obradinn.com/
There definitely is violent scenes and sounds in the game. I would not recommend playing it with young children for instance. However I would myself not put in the same box as other games in the "intense violence" category.
Mostly because and this may sound silly, but it's not "violence in motion". You are viewing a murder scene, and someone died, and you might hear someone take the last breaths of their life. Which has a very high emotional impact which should not be ignored. But that to me is still fundamentally different from gory/bloody games with often fast visceral violence. As mentioned by others, the scenes themselves are calmed a lot by the dithering art-style.
I would say about the emotional content though that this hits differently from other stories where characters die because of the narrative tool. You never have a Game of Thrones moment where a character you are heavily invested in suddenly dies, because even though you learn about the passengers and feel for them in their misery, you also realize up front even before you learn about them that they have died and you are just looking at memories before that event.
I have only played for a few hours, but all the violence (so far) has been communicated via sound effects during blacked out cut scenes (no visuals). The sound effects in the game are really well done and visceral, but otherwise you just see the low res frozen time ‘results’ of these cut scenes (e.g. a dead body under a cannon, a skeleton crushed and distorted, etc).
1 reply →
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?
> 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.
> do you have any links to examples?
Take a look here for a couple of examples: http://gabarro.org/ccn/linear_dithering.html
2 replies →
GIMP has it: Colors > Tone Mapping > Retinex
3 replies →
I wonder how "Retinex" relates to levels, contrast, white and black point cutoff....
Output dependent feedback is another good way to get creamy, evenly dispersed dots in highlight and shadow areas:
https://levien.com/output_dependent_feedback.pdf
> Output dependent feedback
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
Pretty shameless Raph :P
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 :)
2 replies →
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
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
I started extracting images from old Hypercard stacks, and then found this page which has done all of this work!
https://mariteaux.somnolescent.net/junk/hypercard/
Raid away :)
... I think I need to buy an Inkplate now
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.
It's so interesting to read about the rediscovery and reengagement with dithering by newer generations. I grew up when dithering was simply a fact of life because of the extremely limited graphics capabilities of early computers.
I love the reference to Obra Dinn as the graphics remind me of very fond feelings I had for the first black and white Macintoshes. There was something wonderful about the crisp 1-bit graphics, on a monitor designed for only those two colors, that made it look "better" than contemporary color displays in most respects -- almost higher resolution than it actually was. It's kind of almost impossible to replicate how it looked on modern color displays.
I didn't experience that feeling looking at an electronic display again until the Kindle. It also had the funny side-effect of making art assets on Macintoshes a fraction of the size as on color systems, making both the software smaller, and the hard-drives hold more.
There's also something somewhat unsatisfying about automatically generated dithering patterns used to recast color graphics into 1-bit b&w. It seems to really take an artist's hand to make it look beautiful. However, the author of this post ends up with some very nice examples and it's really well written.
If anybody is interested in seeing how the old systems looked, and some great uses of dithering throughout, I'd recommend checking out this amazing Internet Archive Mac in a Browser - https://archive.org/details/mac_MacOS_7.0.1_compilation
You get dithering literally at the system startup background.
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/
Nice. A conceptually simple program made into a nice app. Well, I assume it's a nice app ;-)
Does it make money? There a couple other simple apps I've considered writing to see if I can make a few side bucks.
Yeah, it's a doing-one-thing-and-doing-it-well kind of mentality. It even makes (a little) money.
Omg I didn’t think of this application for dithering. Love that.
It would work great for LEGO mosaics as well
You could probably adapt this to rug hooking kits pretty easily. Random example site (first one in DDG search results: https://woolery.com/rug-hooking/kits.html)
> However, sRGB is not linear, meaning that (0.5,0.5,0.5) in sRGB is not the color a human sees when you mix 50% of (0,0,0) and (1,1,1). Instead, it’s the color you get when you pump half the power of full white through your Cathod-Ray Tube (CRT).
While true, to avoid confusion, it might be better rephrased without bringing human color perception or even colors into the mix.
sRGB uses non-linear (gamma) values, which are good for 8-bit representation. However, operating on them as normal (linear) numbers using average (expecting blur) or addition, multiplication (expecting addition, multiplication of corresponding light) - gives nonsensical, mathematically and physically inaccurate results, perceived by any sensor, human or animal as not what was expected.
RGB colorspace in it's linear form is actually very good for calculations, it's the gamma that messes things up.
In simplified monochrome sRGB/gamma space, a value v means k·v^g units of light, for some k and gamma g = 2.2. Attempting to calculate an average like below is simply incorrect - you need to degamma¹ (remove the ^g), calculate and then re-gamma (reapply ^g).
¹ gamma function in sRGB is a bit more complex than f(x) = x^2.2
I always feel we have way too many historical burdens (which were good compromises at the time) in (digital) image/video field.
In no particular order (and some are overlapping), I can immediately think of gamma, RGB/YCbCr/whatever color models, different (and often limited) color spaces, (low-)color depth and dithering, chroma subsampling, PAL/NTSC, 1001/1000 in fps (think 29.97), interlaced, TV/PC range, different color primaries, different transfer functions, SDR/HDR, ..
the list can go on and on, and almost all of them constantly cause problems in all the places you consume visual media (I do agree gamma is one of the worst ones). Most of them are not going anywhere in near future, either.
I often fantasize a world with only linear, 32-bit (or better), perception-based-color-model-of-choice, 4:4:4 digital images (similar for videos). It can save us so much trouble.
That's a bit like saying that we shouldn't use lossy image/video compression.
Do you realize the amount of 'waste' that a 32bpc†, 4:4:4, imaginary color triangle gamut picture would have ?
†it looks like the human eye has a sensitivity of 9 orders of magnitude, with roughly 1% discrimination (so add 2 orders of magnitude). So, looks like you would need at least 37 bits per color with a linear coding, the overwhelming majority of which would be horribly wasted !
2 replies →
I don't think of colorspaces as "historical burdens". I don't like that CRT monitors are brought up every time sRGB is mentioned though. I know it has historical relevance, but it's not relevant anymore, and it's not needed to understand the difference between linear and non-linear colorspaces.
13 replies →
Are you sure about sRGB being already good enough for averaging ? (As long as we don't want to go to a wider color space of course.)
We have been recently taught how to do it 'properly', and we had to go through CIELAB 76 (which, AFAIK, is still an approximation, as human perception is actually non-euclidean).
If you want physically accurate averaging (resize, blur etc), then RGB is fine, as long as you use linear values (or do long-winded transformed math). AFAIU it is by definition 100% physically accurate. As was said, sRGB uses gamma values, where typical math creates ill effects, as in many if not most typical programs.
If you want to do perceptually uniform averaging of colors, color mixing / generating / artistic effects, that's something else entirely.
3 replies →
As for arbitrary-palette positional dithering,
there's no better write up than https://bisqwit.iki.fi/story/howto/dither/jy/
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."
[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
> 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...
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/
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
An old acquaintance of mine, John Balestrieri, made a Mac app based on Bill Atkinson's dither algorithm too:
https://www.tinrocket.com/content/hyperdither/
Also, drop an image here:
http://gazs.github.io/canvas-atkinson-dither/
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.
Great article!
Frustrated that Firefox doesn't support "image-rendering: pixelated". FF supports "crisp-edges" and happens to implement that as nearest-neighbor filtering but the spec says that is not the meaning of "crisp-edges".
I don't understand why Firefox is dragging their feet on this. It seems like such an easy thing to add. In fact given their current implementation they could just make `pixelated` a synonym for `crisp-edges` and ship it
Here's the 8yr old issue
https://bugzilla.mozilla.org/show_bug.cgi?id=856337
Here is a cross-browser compatible workaround, courtesy of Gavin Kistner from phrogz.net:
And if you want to do pixelated upscaling while drawing an image on a <canvas> element:
[0] http://phrogz.net/tmp/canvas_image_zoom.html
[1] https://developer.mozilla.org/en-US/docs/Web/API/CanvasRende...
[2] https://observablehq.com/@jobleonard/gotta-keep-em-pixelated
TIL! I just redeployed with these styles added. Should be live in a couple minutes. Thank you.
Send a patch!
I'm surprised the algorithm for producing blue noise is so complicated.
Could you not generate white noise, then apply a high-pass filter? Say, by blurring it and then subtracting the blurred version from the original?
Could you split the map into blocks, fill each block with a greyscale ramp, then shuffle the pixels inside the block?
Could you take a random sudoku approach, where you start with a blank map, then randomly select pixels, look at the distribution of pixels in their neighbourhood, randomly pick one of the greyscale values not present (or least present) for that pixel, then repeat?
The first technique is challenging because the filter needs to have a specific frequency response, without shortcuts. Such high quality filtering can be done more simply and more exactly with an inverse Fourier transform.
The second technique doesn't seem promising because shuffling is very crude: differently shuffled small blocks are going to have border artifacts, repeating small blocks are going to have worse periodic artifacts, large blocks are going to approximate white noise rather than blue noise. Higher quality would require precomputing blue noise images, losing the advantage of on-the-fly computation.
The third technique, being sequential, is unlikely to be practically cheaper than an inverse Fourier transform.
I tried the first couple of ideas:
https://gist.github.com/tomwhoiscontrary/337cb8aaef013327a89...
I only went as far as generating threshold maps, not actually using them. Couldn't see how to do that using ImageMagick, and didn't want to write it manually!
The high-pass filter maps "look okay", but i haven't looked at their spectrum. How important is it that they have a specific frequency response? What is the failure mode if they don't?
The shuffling maps don't "look" so hot. There aren't border artifacts or repeating blocks (and you wouldn't expect these a priori - not sure why you think that), but indeed, it's not very different to white noise.
See also, DITHER.txt: http://web.archive.org/web/20190316064436/http://www.efg2.co...
DHALF.TXT might also be useful.
https://raw.githubusercontent.com/cyotek/Dithering/master/re...
DITHER.TXT is also available in the same folder.
> “Bayer dithering” uses a Bayer matrix as the threshold map. They are named after Bryce Bayer, inventor of the Bayer filter, which is in use to this day in digital cameras.
My Dad! I can hear him talking about this...
Dynamic Rounding, developed by Quantel back in the 90s for digital video+film, is underappreciated. Dynamic Rounding + Blue Noise is severely underappreciated.
https://en.wikipedia.org/wiki/Quantel
https://patents.google.com/patent/US6281938B1
Are there any sample images floating around on the Internet?
There recently was a Show HN thread of an interactive dithering tool called Dither Me This[1]. I think you will like it if you liked this article
[1]: https://news.ycombinator.com/item?id=25469163
A few more error dithering algorithms are seen in https://tannerhelland.com/2012/12/28/dithering-eleven-algori...
With HDR and wide gamut on the horizon, things are moving even further away to ever requiring any form of dithering.
You still need dithering to prevent visible banding in really subtle color gradients.
You still need dither for print, where subtle gradients on-screen can suddenly become very visible. I’ve had some large format giclee prints surprise me with nasty color banding.
I suspect some of the lines that were showing up in the OP's error diffusion test might be paralleling color banding lines in the original images.
In case anyone wants to play around with some basic dithering, I run a webapp called Dither it! that does just this:
https://ditherit.com
http://www.effectgames.com/demos/worlds/
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 :(
Video of Mark talking about his process https://www.youtube.com/watch?v=aMcJ1Jvtef0
yes! That is it. The game is https://thimbleweedpark.com/
semi-related: The origin of the word "dither" as explained by this wonderful little wikipedia page[1] is worth reading about.
[1]: https://en.wikipedia.org/wiki/Dither
It was nice to see a mention of Robert Ulichney. His 1987 book "Digital Halftoning" covers most of the ground that this blog post does, plus more.
I saw this book mentioned a couple of times during my research. I guess I should read it.
Donald Knuth also has two nice chapters in "Digital Typography".
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.
1 reply →
This is a great counterpart to this slightly more implementation-focused article on the Obra Dinn aesthetic: https://danielilett.com/2020-02-26-tut3-9-obra-dithering/
iirc, back in ~99, Unreal Engine was doing dithering on the u/v coordinates (!!) for texture mapping instead of bilinear interpolation. They used fixed Bayer matrix.
This was quite faster, visually pleasant, and was adapting nicely to viewing distance.
Try freezing some close-up frames around 0:45 here: https://www.youtube.com/watch?v=aXA3360awec
Tim Sweeney called this technique "ordered texture coordinate space dither", apparently:
https://www.flipcode.com/archives/Texturing_As_In_Unreal.sht...
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.
This thesis on noise shaping and dither http://uwspace.uwaterloo.ca/bitstream/10012/3867/1/thesis.pd... is an excellent mathematical treatment of the subject.
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.
2 replies →
I always thought the floyd-steinberg algorithm produced images that looked like they were made from a nest of worms, at least in the implementations I came across in the Amiga era, so it's interesting to look at his FS image and realize that, most likely, it was an artifact of the low resolution display more than anything else.
> color palettes are mostly a thing of the past
> With HDR and wide gamut on the horizon, things are moving even further away to ever requiring any form of dithering.
My impression is that, if anything, the almost total dominance of sRGB (in the consumer space) is coming at an end in the digital mediums, on one side from the generalization of wide gamut and high dynamic range transmissive LCD/LED screens, and on the other end the rising wave of both (higher frequency) black & white and color e-ink. (And I'm still hopeful for the resurrection of transflective LCDs, like in Pebble.)
So I would expect dithering to come back, either to avoid banding on lower bit per color displays, and/or 'add' colors to lower color gamut ones.
For instance, my 2009 LCD is a 8bpc wide gamut one (and fairly high dynamic range too). So if I were to take full advantage of it (leaving sRGB), I would require dithering to avoid banding.
If you want to play around with dithering on macOS or iOS, vImage in the Accelerate framework provides most of the algorithms discussed in the article (including Atkinson!), with performance more than adequate for most applications (and with convenient vImage utilities to fit them into a CV pixel buffer pipeline for video work). vImage also supports dithering to other bit depths, though one-bit output is what you want for that vintage look.
https://developer.apple.com/documentation/accelerate/1533024...
> As this image shows, the dithered gradient gets bright way too quickly.
sigh
Not in Firefox on Linux.
I vaguely recall seeing a multi-year-old bug related to subtly broken gamma behavior in either Firefox or Chrome, but can't seem to find it right now.
Ah, this happens when Firefox/Chrome scales the image. I added a note to the article a couple hours ago, not sure if you saw that.
If you open the image in question in a new tab (to prevent any scaling) you’ll see the image as intended with the “desired” effect.
Are you sure about that ?
The default Ubuntu photo viewer shows it in the same way.
Also, for his second 'improved' dithering, the dithering clearly doesn't correspond to the undithered gradient (both undithered gradients seem to be the same in both pictures ??)
See also :
https://news.ycombinator.com/item?id=25644176
How would you apply dithering to animations (without the screen looking noisy from the different starting conditions of each frame)?
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)
Author here!
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/
Is this what Steam uses for the "News" animated gifs?
discussed by the author of the mentioned game (return of the obra dinn) here: https://forums.tigsource.com/index.php?topic=40832.msg136374...
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.
1 reply →
Oh boy, I think it's about time to hack on some dithered generative art. What an inspiration this article was!
Is it just my eyes or does the gradient dithered in sRGB look more accurate that the one dithered in linear space?
I think both gradients are "wrong" in that they themselves interpolate without correcting for RGB. I think the first example thte original and dither are wrong in the same way, while in the second the dither is more right than the gradient is.
Basically I'm afraid the author of this post is a bit of a "careless eager student" archetype who, while generously pointing out the gotchas that to an expert might be second nature, is also introducing unintentional errors that add some confusion right back.
I'm not expert in color, but with anything with soo many layers of abstractions (physical, astronomical, psycological, various models that approximate each), it helps to work symbolically as long as you possibly can so the work can be audited. Trying to correct from the current "baked" state is numerical hell.
Yes, this is also my impression.
But see also :
https://news.ycombinator.com/item?id=25644176
If it does, then it probably means you've got some funky substandard or non-standard LCD panel or gamma setting or color correction on whatever you're viewing it on.
Which isn't terribly unusual. But if your screen is well calibrated, then no -- the sRGB gradient should by definition be identical. That's literally the specification.
(And it is on my MacBook, as Apple screens tend to be among the most accurate of general consumer screens.)
The sRGB version is evenly balanced bitwise yet 'gamma free'. The linear RGB version appears bitwise imbalanced due to gamma correction, but cross your eyes and blur your vision, and you'll see the linear RGB is actually more gamma correct! (Better contrast and luminosity)
Interesting, I "dither" (shift the telescope around between photos) my astrophotos to go from noise to less noise - funny seeing it go from image to noise. Does anyone have any papers on dithering + image integration to go in this direction? always been interested in knowing more about it.
This article is very well put together, and a helpful reference, thanks for sharing!
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...)
I just finished making an online dithering tool, doodad.dev/dither-me-this if anyone wants to play around with dithering.
I'll be re-jigging it based on some info from that article, and definitely adding 'blue noise' as an option. Thanks for sharing.
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!
3 minutes to generate 64 by 64 pixels blue noise? I think one should be able to instead draw white noise in frequency domain, multiply with a noise amplitude profile and then a 2D FFT...should only take some milliseconds..
That's right! I was so confused when I read the article, and being satisfied with getting just a 50% boost from using your home brew FFT, was somewhat disheartening.
That is truly like if you're happy that your implementation of quicksort is 50% faster than your insertion sort. It's just that bad of a result, that you really have to stop and wonder if perhaps you did it wrong.
Since we're all posting our favorite dithering-related links: https://loopit.dk/banding_in_games.pdf
This is a great overview.
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.
I had never read about dithering before, but this article sparks interest. Coupled with sample images, it is fun to read about the different dithering algorithms. Thanks for sharing!
Slightly offtopic, but this is a greate opportunity to ask what I always wanted to know. Can anybody tell me how protraits like the one in the linked article below are made? I always loved this dithering style.
https://www.wsj.com/articles/SB10001424052702304418404579467...
Edit: I found that the style seems to be called "hedcut".
The traditional WSJ Hedcut portraits are drawn by hand, although they now have a ML tool that makes a reasonable facsimile: https://www.wsj.com/articles/whats-in-a-hedcut-depends-how-i...
I think there is a trade-off between spatial resolution and color depth. Dithering reduces the former to simulate increasing the latter.
Perhaps we can get a similar result by interpreting the original signal (after linearization) in a different way. It could represent (after normalization) the probability each pixel would be 1 or 0. That way, brighter areas would have more density of bright pixels, and darker areas would have more density of dark pixels.
Here’s a cool rust crate that does color quantization and dithering at the same time. Ie picking the palette to use and dithering the picture with that palette as an evolving context. https://github.com/okaneco/rscolorq
It’s a port of an older c library that’s based on a paper/algorithm called spatial color quantization.
Great resource! I played myself with dithering, applying it to images fetched from nasa's apis, from the rovers on mars and open sourced it. I really enjoyed the visual outcome, you can see it here: https://github.com/danieledep/rovers-dithering-playground
Here's a trick. Before you do anything.... Add noise. Then use error diffusion. Looks pretty good for how crazy fast it is.
Figuring out the strength of the noise is tricky. Usually 5 to 10 percent. I'd suggest random RGB and not monochrome noise(so not quite how you've coded the randomness, but similar idea), as this should create more unique values and reduce patterned artifacts.
Since we're talking about monochromatic art... anyone else here a fan of the Atari ST game Bolo?
https://www.mobygames.com/game/atari-st/bolo
Probably the best monochromatic aesthetics I've ever seen in a game. The screen shots don't do it justice.
I use the excellent imageworsener compiled to WASM to dither the images in my label printer electron app, https://label.live
Read more at http://entropymine.com/imageworsener/
Another good article about dithering algorithms is https://www.freesion.com/article/3406137250/. It goes through most of the matrix-based dithering algorithms, including the more obscure ones.
I messed with the source of this and I came up with an entirely local dithering algorithm based on the van der Corput sequence.
https://tjsomething.neocities.org/ditherpunk-demo/
Tangential, but when I view certain dithered images in that article and on the demo page, my entire monitor drops in brightness by a bit. As soon as I scroll away, the monitor returns to normal brightness.
I wonder if this is a result of hardware or something on the software / driver side.
Probably dynamic contrast ratio by graphic driver and/or monitor that is tricked/triggered by unusual dithered patterns during scrolling.
I've done a library which is capable of using various dithering algorithms by plugin the dithering method you wish: https://github.com/esimov/dithergo
Easy ditherpunk video treatment:
ffmpeg -i video-input.mp4 -i palette.png -lavfi "paletteuse=dither=sierra2" video-output.mp4
You'll need to create a 16px by 16px PNG with only black and white pixels. Also, there are other dithering algos that paletteuse offers.
The author didn't cover it, but it's common to alternate the direction of error diffusion passes line-by-line. This improves Floyd-Steinberg dithering by a lot in my experience.
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!
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.
pngquant is a FOSS tool designed for that.
https://pngquant.org/
Since printers do this, I always wondered if there's a good way to undo dithering (at the cost of resolution) for scans. Would it just be scaling down the image?
This might be an interesting application in some early medical devices for blind people.
What if it's binary but has a better resolution and they would see like that?
Really enjoyable article, reminds me of being at school where the first scanner I encountered only output dithered black and white.
Fascinating read!
Almost makes me miss the days of getting to the graphics lab late and getting stuck with one of the old Mac SEs.
Almost.
it's also possible to get a little better results by cheating a little bit with the error distribution, Ulichneys ξ1 and ξ2 as in "Simple gradient-based error-diffusion method" Journal of Electronic Imaging jul/aug 2016.
This is amazing. Is there any work using ML for "optimal" dithering?
I learned something new today! Nice work, and well-explained.
TLDR use floyd-steinberg dithering with gamma correction.
Thought the blue noise looked the best.
Does anyone else get errors on their HDMI monitors when viewing these images? Mine red shifts the entire screen and I'm not sure why.
The article brings back my ZX-Spectrum memories
n