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.
The period needs to be sufficiently long such that it won’t show up as visible artifacts. I would think something like PRBS23 would do the trick and be trivial to implement.
That’s the cheapest choice. Better whiteness could come with some added complexity.
For less visual artifacts it is recommended to use PRBS with 50% of the taps 0, 50% of the primitive polynomial tap 1. Same period (2^n-1), but less short-term correlations.
The great thing ("great") was we did the lower end laser printer niche for HP. We were able to make ASICs cheaper than HP could make them for themselves. So we had the (cough) less impressive hardware (scan sensors, laser engines, motors) to work with. So image quality was so-so at even the best of times.
We were able to bury a lot of bodies under the sensor noise and engine output. But we made a super reliable, super cheap laser printer -- VW Bug of Laser Printers, if I may brag a bit. Twelve years later, the M1005 is still selling like hotcakes I hear.
The standard PRBS23 polynomial is X^23 + X^18 + 1. Most of the factors are zero. Only the factors for exp 23,18,1 are 1. This causes poor bit mixing - ie the output sequence will have strong correlation every 23 bits.
Choosing a "fat" primitive polynomial, ie a polynomial not from this list[0] but rather a polynomial with 50% of the taps are 1 (but it still must be primitive[1]), increases the avalanche effect[2] to the optimal 50% probability, ie 50% of the state bits affect the output at each step, instead of just 2 or 3 taps out of 23.
Note: the LFSR sequence length will remain the same, 2^23-1 in either case. It's just that the short-term correlation between bits will be lower.
I'll be honest, that is a bit terse for a lay-person like me, but the links hopefully give enough pointers to properly grok what you said with a bit of reading. Thank you!
Note: in the software world, the equivalent construction to the LFSR with "fat" polynomial is the xorshift PRNG. For more details, see the book: Numerical Recipes, 3rd edition (not 2nd ed!), Chapter 7 random numbers, section 7.1 uniform RNG - history.
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).
To be safe: There is some more graphic violence, but due to the dithering it’s not very offensive imo. However, pretty much the entire crew does die rather brutal deaths (and that’s what the plot of the game is centered around).
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.
Huh, to be honest I feel like I've only ever seen halftoning when printing onto paper -- I've never associated dithering with printing at all.
And the "linear dithering" you're describing, when I think of images in certain banknotes and passports or quality seals that I'd call "engraved", I've always assumed were hand-drawn by an artist.
But I like what you're describing and linking to, as a way to achieve that hand-drawn effect algorithmically, to include a directional texture element! Thanks for sharing.
> Huh, to be honest I feel like I've only ever seen halftoning when printing onto paper -- I've never associated dithering with printing at all.
Yep, sorry about my sloppy terminology. I always use "halftoning" and "dithering" interchangeably. Yet, notice that today's printers are often matrix-based, i.e., like a high-resolution binary screen, with a bit of ink smearing depending on the type of paper/plastic.
> I've always assumed were hand-drawn by an artist.
Maybe some are still drawn by hand, but most printed stuff is at some point dithered automatically (and a lot of critical information can be embedded on the dithering patterns).
Without it (left), a photo remains "accurate" in terms of brightness levels.
But with it (right), it becomes far more high-contrast to feel closer to an illustration or painting. Which certainly makes it clearer. But while it brings out details in middle levels, it totally blows out shadows and highlights.
E.g. the texture of his mask, shirt, and her hand are much clearer. But on the other hand, their hair (and a background object) just turn solid black and lose all detail. But certainly, the vastly higher contrast makes for a much more compelling image IMO.
Black and white images need more contrast to be pleasing. I think that's most of the effect you see here.
Maybe you'd want to start with a decent black and white photograph to get a better comparison.
No matter what you do you probably also don't want to end up with large patches of solid white or black in your source image (unless it's the background). The hair already feels like drowning in black. But to take care of that you need to use photoshop and be careful with the gradient curves :)
I agree; the filtered image (right) is more aesthetically pleasing; but it feels much less accurate. It would depend on the intent of the image I think. If you're creating art, and using photographs in the creation, it's not a problem. If you're reporting on the world and just want to reduce the data size (or use a monochrome output medium), I wouldn't do it like this.
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 have no issue with lossy compression; but things like 4:2:0 aren't really typical lossy compression. It's like calling resizing an image to half its resolution "compression".
Also lossless compression can reduce plenty of "wasted" bits already (see: png vs bmp).
But they are ! Like other lossy forms of compression, chroma subsampling takes advantage of the human visual system's lower acuity for color differences than for luminance.
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.
I misunderstood what you mean. Please ignore. On a side note, by colorspace I mainly meant that we can just stick with one with ultra-wide gamut. There are indeed other reasons to have different color spaces.
(Below is my original comment for transparency.)
-------------
Gamma isn't really about CRT; or I should say, they're two different things. The fact CRT has a somewhat physical "gamma" (light intensity varies nonlinearly with the voltage) is likely just a coincidence with the gamma we're talking here.
The reason gamma is used in sRGB is because human eyes are more sensitive to changes in darker area, i.e. if the light intensity changes linearly, it feels more "jumpy" in darker end (which causes perceptible bandings). This is especially an issue with lower color depth. To solve this, we invented gamma space to give darker end more bits/intensity intervals to smooth the perceptive brightness.
>it's not needed to understand the difference between linear and non-linear colorspaces
It absolutely should, since any gamma space would have problem with "averaging", as explained by the GP. Actually, it's so bad that almost all the image editing/representing tasks we have today are doing it wrong (resizing, blurring, mixing..).
This topic has been discussed extensively on Internet, so I'm not going to go into detail too much. A good start point is [1][2].
(With some changes for a less accurate, but more visually pleasing/exciting replication of brightness levels ?)
Now, with many modern, digital screens (LCD, LED, e-ink?), as far as I've understood the electro-optical hardware response is actually linear, so the hardware actually has to do a non-linear conversion ?
I'm still somewhat confused about this, as I expected to have to do gamma correction when making a gradient recently, but in the end it looked like I didn't have to (or maybe it's because I didn't do it properly : didn't do it two-way?).
Note that the blog author might be confused there too, as just after he says :
> With these conversions in place, dithering produces (more) accurate results:
– you can clearly see that the new dithered gradient doesn't correspond to the undithered one ! (Both undithered gradients seem to be the same.)
sRGB gamma is often approximated to 2.2 [1], but the actual function has a linear section near 0, and a non-linear section with gamma of 2.4, possibly to avoid numerical difficulties near 0.
The document you cite claims that CRT gamma is typically between 2.35 and 2.55.
Human eye gamma can probably be approximated with cieLAB, that is designed to be a perceptually uniform colorspace, which seemingly has a gamma of 3 [2], although it also has a linear section, so maybe slightly lower overall gamma. ciaLAB is not state of the art though in perceptually uniform colorspaces.
What I don't like about this whole CRT/gamma topic:
1. It brings in perceptually uniform colorspaces to the discussion, while it's completely unnecessary. Perceptually uniform colorspaces are mostly unsuitable for arithmetic on colors like any other non-linear colorspace.
2. While the sRGB colorspace and a colorspace defined by a CRT monitor's transfer function are closer to perceptually uniform than a linear colorspace, they are still pretty damn far from it. sRGB still does a decent job to prevent banding in dark areas.
3. The sRGB colorspace is not identical to a colorspace defined by a CRT monitor's transfer function.
4. "gamma" is a crude approximation for transfer functions, assuming they follow a power function on all of their domain.
5. This whole thing about CRTs and gamma doesn't matter if you just want to understand that if you want to do arithmetic on color components, then you most probably want it represented in a linear colorspace (didn't even talk about it yet), and most color values you encounter is actually encoded in sRGB, so you want to convert that to linear first, then convert the result back, depending on what your output requires. This is the most widespread bug in computer color and you don't need the history of CRTs to do that, and in fact this has nothing to do with perceptually uniform colorspaces.
> ciaLAB is not state of the art though in perceptually uniform colorspaces.
Which are state of the art ?
> 1. It brings in perceptually uniform colorspaces to the discussion, while it's completely unnecessary. Perceptually uniform colorspaces are mostly unsuitable for arithmetic on colors like any other non-linear colorspace.
I don't get what you mean, linearity (dL'star') being defined wrt perceptual uniformity, isn't CIELAB 76 linear by definition (to an approximation) ?? And color arithmetic pretty much by definition implies dealing with distances and angles in a perceptually uniform color space, doesn't it ??
(I would really like to know, since it actually is the very topic of 'practical work' that we have to do for mid-January. We were told to do the transformations to CIELAB 76 and, after the modifications, back to sRGB, using the D65 illuminant.)
Otherwise, I didn't mention the finer details about CRT transfer functions because it didn't seem to be relevant enough.
> This is the most widespread bug in computer color and you don't need the history of CRTs to do that, and in fact this has nothing to do with perceptually uniform colorspaces.
Yeah, I know, and while just doing this kind of transformation might be just good enough for the most common color arithmetic, is it really good enough for all use cases ?
To take an example from our practical work, seeing this kind of effect :
You know what, I think I'm going to try and do this practical work in two versions, one using just linear sRGB (and back). I'll see if I get noticeable differences. But that will have to wait a week or so, I'm too busy searching for internships right now (and have already spent too much time in this discussion...)
> I don't get what you mean, linearity (dL'star') being defined wrt perceptual uniformity, isn't CIELAB 76 linear by definition (to an approximation) ?? And color arithmetic pretty much by definition implies dealing with distances and angles in a perceptually uniform color space, doesn't it ??
No. Linearity is about physical light intensities relating to perceived color. Imagine having two light sources on the same spot that you can turn on or off separately. If you turn the first one on you perceive a certain color, if you turn the other on you perceive an other color and if you turn both on you perceive a third one. It turns out the perceivable colors (under normal viewing conditions) are representable in a three dimensional vector-space (for most people) so that the first two colors add up to the third color for every possible two light sources. Such a linear colorspace is XYZ for example [1].
This has nothing to do with perceptual uniformity. Perceptual uniformity is about the capability of distinguishing near colors. This defines a distance between colors, and there are three dimensional colorspace representations where the Euclidean distance approximate this perceptual distance well. cieLAB is such a colorspace, but AFAIK there are better state of the art colorspaces for the same purpose. I'm not very well versed in this, I learned from them from this video [2].
edit: gimp 2.10 now defaults to use a linear colorspace (not perceptually uniform!) for most if not all of its functionalities. This affects alpha-blending layers, the paintbrush, resizing, blur, and pretty much everything that involves adding/averaging colors. There is still a "legacy" option on these tools to turn back to the probably wrong sRGB methods, probably for compatibility with old gimp files. There is a dramatic difference when you use a soft green brush on a red background for example, it's worth to try out.
Ok, my bad, I should have re-read our lesson more carefully : we're actually supposed to do sRGB => XYZ > CIELAB (and later back).
And it looks like that you can either have an Euclidean vector (linear) space (linear sRGB, XYZ), or a perceptually uniform one (CIELAB), but not both !?
(I guess that I should have figured that out myself, sigh… this is why it isn't CIELAB that is used for monitor calibration, but CIELU'V' ?
EDIT : Nope :
"[CIELUV is] a simple-to-compute transformation of the 1931 CIE XYZ color space, but which attempted perceptual uniformity. It is extensively used for applications such as computer graphics which deal with colored lights. Although additive mixtures of different colored lights will fall on a line in CIELUV's uniform chromaticity diagram (dubbed the CIE 1976 UCS), such additive mixtures will not, contrary to popular belief, fall along a line in the CIELUV color space unless the mixtures are constant in lightness. ")
So you have to pick the best color space for the job, in the case of doing color averages that would be one of the linear ones (linear sRGB, XYZ), while if you are trying to design a perceptually uniform gradient for data visualization, you would better pick a perceptually uniform space (CIELAB, CIELUV) ?
See the recent Oklab post[0] for guidance on choosing a perceptually uniform color space for gradients. It's better than CIELab and CIELuv, both of which I would consider inferior to newer alternatives. In particular CIELab has particularly bad hue shifts in the blue range.
I'm also working on a blog post on this topic (there's an issue open in the repo for my blog, for the curious).
> I expected to have to do gamma correction when making a gradient recently, but in the end it looked like I didn't have to
If you don't explicitly specify the color space you're working in, then you're using some implicitly defined color space in which case you basically need to know what that is (at least roughly).
So traditionally in Windows, way back, when you created a bitmap, wrote some data to it and then drew it, there was no explicit mention of a color space. Instead it was implicit, and it was de-facto non-linear.
These days you can specify[1][2] the color space you're working in, and Windows will then transform the colors into the specified device color space. So then you can specify if you want to work in linear RGB space or say non-linear sRGB.
Unity has something similar[3], which affects how you write shaders, how your textures should be saved etc.
Yes, and in almost all of these discussions, the implicit color space is (non-linear) sRGB. (IIRC Macs might have used a different default color space one-two decades ago ?)
Also, I'm on Linux, and doing picture manipulation with Octave, but thank you for the links anyway !
Yeah I was just using Windows because that's what I was familiar with. I guess on Linux is can vary a lot more on the setup.
So yeah for Octave you need to know what Octave does with the data afterwards. If it's saving a matrix to a PNG say, it could assume the matrix is linear and convert to sRGB which would be a good choice if it also supported say OpenEXR files. However it could also just take the values raw, assuming you'd convert the data to sRGB before saving. Or even allow you to specify the color space in the iCCP chunk, which would give you more power.
Again, what it actually does is something that needs to be looked up.
Yeah, since we're learning, we're not doing anything fancy on that side (at least yet), so (so far) working with sRGB bmp/png/jpg input and sRGB bmp output.
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.
I'm not sure what you mean by "physically accurate" ?
No color reproduction is going to be physically accurate, except by accident, since color is an (average) human qualia, not a physical observable.
And especially because whatever the way that the colors are going to be reproduced, there's no guarantee that they will correspond to the same light spectrum than the original, since there's an infinity of spectra corresponding to the same impression for a specific color.
And if you want to do perceptually accurate averaging, you're going to have to work in a perceptually uniform color space ! Which (even linear) sRGB isn't.
All that said, it's perfectly possible that linear sRGB is just good enough for most use cases of averaging, even despite not being perceptually uniform. Especially in OP's example with just 2 shades : black and white.
Yes, color is a human concept for certain stimuli, no recording or reproduction is 100% accurate and even the model is not perfect (different people have shifted color sensitivities, some are even tetrachromats and we are ignoring rods vs. cones altogether).
However, the stimuli is predominantly light, which can be quantified and certain operations with light are well studied. Not all, but most noticeable ones are and that is what is used when doing photorealistic rendering etc.
If you do a 2x downscale, you need to average 4 pixels together. Linear RGB should (by theory and definition) give you a (theoretically) physically accurate result, as if you did a physical 2x downscale by putting it further away in a uniformly lit room or whatever. You can't reproduce that precisely, but neither can you reproduce 1l + 1l of milk = 2l of milk.
This is in stark contrast to downsizing, blur or whatever "performed" in sRGB, where images get curiously darker and slightly off-color (or is it lighter?).
I'm not sure what is perceptual average of colors, but if you mix pixels in 1:1 ratio and apply blur / look from far away, there is only one correct result, and linear RGB average (is one way that) gives you the single correct result. (ignoring screen color reproduction deviations from what they are supposed to be)
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.
One thing I've found (admittedly with audio) is that you can usually get away with less dither power than is needed to completely linearize the error, at the cost of some harmonics for pathological signals which still ends up being less noticeable than the higher power dither noise.
Right, I think that’s what’s going on in my image example.
I think this is a key lesson to people who apply these types of mathematical techniques to the lossy compression of data meant to be experienced by humans. Random noise is not always preferable to non-linear error, i.e. reducing non-linear error is not necessarily the equivalent of improving the perceived quality of the data in question. It can be but the function that determines what “looks good” or what “sounds good” to humans is probably a bit more complex.
This is something I’ve run into with image compression techniques but it applies here too (quantization being a form of compression). E.g. JPEG compresses images in 8x8 blocks because doing the whole image at once would look horrible. Figuring out the redundant information that can be thrown away with the least impact to image quality is still fundamentally an art.
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.
He's not entirely correct, either. I haven't played it, but I did see video of it, and I was impressed by the stability of the dithering. It takes work to avoid it looking like https://www.youtube.com/watch?v=2AKtp3XHn38 or something.
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.
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.