Ditherpunk — The article I want I had about monochrome picture dithering — surma.dev

I at all times beloved the visible aesthetic of dithering however by no means knew the way it’s accomplished. So I did some analysis. This text could include traces of nostalgia and none of Lena.

How did I get right here? (You may skip this)

I’m late to the occasion, however I lastly performed “Return of the Obra Dinn”, the latest recreation by Lucas Pope of “Papers Please” fame. Obra Dinn is a narrative puzzler that I can solely suggest, however what piqued my curiosity as a software program engineer is that it’s a 3D recreation (utilizing the Unity game engine) however rendered utilizing solely 2 colours with dithering. Apparently, this has been dubbed “Ditherpunk”, and I really like that.

Dithering, so my unique understanding, was a way to put pixels utilizing solely a few colours from a palette in a intelligent solution to trick your mind into seeing many colours. Like within the image, the place you most likely really feel like there are a number of brightness ranges when in reality there’s solely two: Full brightness and black.

The truth that I’ve by no means seen a 3D recreation with dithering like this most likely stems from the truth that shade palettes are principally a factor of the previous. You could keep in mind working Home windows 95 with 16 colours and enjoying video games like “Monkey Island” on it.

For a very long time now, nonetheless, now we have had 8 bits per channel per pixel, permitting every pixel in your display screen to imagine one in every of 16 million colours. With HDR and broad gamut on the horizon, issues are transferring even additional away to ever requiring any type of dithering. And but Obra Dinn used it anyway and rekindled a protracted forgotten love for me. Understanding a tiny bit about dithering from my work on Squoosh, I used to be particularly impressed with Obra Dinn’s skill to maintain the dithering steady whereas I moved and rotated the digicam by way of 3D house and I wished to know the way it all labored.

Because it seems, Lucas Pope wrote a forum post the place he explains which dithering methods he makes use of and the way he applies them to 3D house. He put in depth work into making the dithering steady when digicam actions happen. Studying that discussion board put up kicked me down the rabbit gap, which this weblog put up tries to summarize.

Dithering

What’s Dithering?

In response to Wikipedia, “Dither is an deliberately utilized type of noise used to randomize quantization error”, and is a way not solely restricted to photographs. It’s truly a way used to at the present time on audio recordings, however that’s yet one more rabbit gap to fall into one other time. Let’s dissect that definition within the context of pictures. First up: Quantization.

Quantization

Quantization is the method of mapping a big set of values to a smaller, normally finite, set of values. For the rest of this text, I’m going to make use of two pictures as examples:

Each black-and-white images use 256 completely different shades of grey. If we wished to make use of fewer colours — for instance simply black and white to attain monochromaticity — now we have to vary each pixel to be both pure black or pure white. On this state of affairs, the colours black and white are known as our “shade palette” and the method of adjusting pixels that don’t use a shade from the palette is named “quantization”. As a result of not all colours from the unique pictures are within the shade palette, it will inevitably introduce an error known as the “quantization error”. The naïve resolution is to quantizer every pixel to the colour within the palette that’s closest to the pixel’s unique shade.

Notice: Defining which colours are “shut to one another” is open to interpretation and is dependent upon the way you measure the gap between two colours. I suppose ideally we’d measure distance in a psycho-visual means, however many of the articles I discovered merely used the euclidian distance within the RGB dice, i.e. $sqrt{Deltatext{purple}^2 + Deltatext{inexperienced}^2 + Deltatext{blue}^2}$

With our palette solely consisting of black and white, we will use the brightness of a pixel to determine which shade to quantize to. A brightness of 0 means black, a brightness of 1 means white, every part else is in-between, ideally correlating with human notion such {that a} brightness of 0.5 is a pleasant mid-gray. To quantize a given shade, we solely have to test if the colour’s brightness is bigger or lower than 0.5 and quantize to white and black respectively. Making use of this quantization to the picture above yields an… unsatisfying consequence.

grayscaleImage.mapSelf(brightness => 
  brightness > 0.5 
    ? 1.0 
    : 0.0
);

Notice: The code samples on this article are actual however constructed on high of a helper class GrayImageF32N0F8 I wrote for the demo of this text. It’s just like the net’s ImageData, however makes use of Float32Array, solely has one shade channel, represents values between 0.0 and 1.0 and has an entire bunch of helper capabilities. The supply code is offered in the lab.

Gamma

I had completed writing this text and simply wished to “rapidly” look what a black-to-white gradient appears to be like like with the completely different dithering algorithms. The outcomes confirmed me that I failed to contemplate the factor that at all times turns into an issue when working with pictures: shade areas. I had written the sentence “ideally correlating with human notion” with out truly following it myself.

My demo is applied utilizing net applied sciences, most notably <canvas> and ImageData, that are — on the time of writing — specified to make use of sRGB. It’s an outdated shade house specification (from 1996) whose value-to-color mapping was modeled to reflect the habits of CRT displays. Whereas barely anybody makes use of CRTs nowadays, it’s nonetheless thought-about the “secure” shade house that will get accurately displayed on each show. As such, it’s the default on the internet platform. Nevertheless, sRGB just isn’t linear, that means that $(0.5, 0.5, 0.5)$

Warning: I set image-rendering: pixelated; on many of the pictures on this article. This lets you zoom in and really see the pixels. Nevertheless, on gadgets with fraction devicePixelRatio, this would possibly introduce artifacts. If doubtful, open the picture separate in a brand new tab.

As this picture reveals, the dithered gradient will get vibrant means too rapidly. If we would like 0.5 be the colour in the course of pure black and white (as perceived by a human), we have to convert from sRGB to linear RGB house, which could be accomplished with a course of known as “gamma correction”. Wikipedia lists the next formulation to transform between sRGB and linear RGB.

$$start{array}{rcl} textual content{srgbToLinear}(b) & = & left{start{array}{ll} frac{b}{12.92} & b le 0.04045 left( frac{b + 0.055}{1.055}proper)^{gamma} & textual content{in any other case} finish{array}proper.$$

textual content{linearToSrgb}(b) & = & left{start{array}{ll} 12.92cdot b & b le 0.0031308 1.055 cdot b^frac{1}{gamma} – 0.055 & textual content{in any other case} finish{array}proper. (gamma = 2.4) finish{array} srgbToLinear(b)linearToSrgb(b)(γ=2.4)​==​{12.92b​(1.055b+0.055​)γ​b≤0.04045in any other case​{12.92⋅b1.055⋅bγ1​−0.055​b≤0.0031308in any other case​​

With these conversions in place, dithering produces (extra) correct outcomes:

Random noise

Again to Wikipedia’s definition of dithering: “Deliberately utilized type of noise used to randomize quantization error”. We acquired the quantization down, and now it says so as to add noise. Deliberately.

As a substitute of quantizing every pixel instantly, we add noise with a price between -0.5 and 0.5 to every pixel. The concept is that some pixels will now be quantized to the “improper” shade, however how typically that occurs is dependent upon the pixel’s unique brightness. Black will at all times stay black, white will at all times stay white, a mid-gray can be dithered to black roughly 50% of the time. Statistically, the general quantization error is lowered and our brains are desperate to do the remainder and make it easier to see the, uh, huge image.

grayscaleImage.mapSelf(brightness =>
  brightness + (Math.random() - 0.5) > 0.5 
    ? 1.0 
    : 0.0
);

I discovered this fairly shocking! It’s on no account good — video video games from the 90s have proven us that we will do higher — however this can be a very low effort and fast solution to get extra element right into a monochrome picture. And if I used to be to take “dithering” actually, I’d finish my article right here. However there’s extra…

Ordered Dithering

As a substitute of speaking about what sort of noise so as to add to a picture earlier than quantizing it, we will additionally change our perspective and speak about adjusting the quantization threshold.

grayscaleImage.mapSelf(brightness =>
  brightness + Math.random() - 0.5 > 0.5 
    ? 1.0 
    : 0.0
);


grayscaleImage.mapSelf(brightness => 
  brightness > Math.random() 
    ? 1.0 
    : 0.0
);

Within the context of monochrome dithering, the place the quantization threshold is 0.5, these two approaches are equal:

$$start{array} {} & mathrm{brightness} + mathrm{rand}() – 0.5 & > & 0.5 Leftrightarrow & mathrm{brightness} & > & 1.0 – mathrm{rand}() Leftrightarrow & mathrm{brightness} &>& mathrm{rand}() finish{array}$$

The upside of this method is that we will speak about a “threshold map”. Threshold maps could be visualized to make it simpler to motive about why a ensuing picture appears to be like the best way it does. They may also be precomputed and reused, which makes the dithering course of deterministic and parallelizable per pixel. Consequently, the dithering can occur on the GPU as a shader. That is what Obra Dinn does! There are a few completely different approaches to producing these threshold maps, however all of them introduce some sort of order to the noise that’s added to the picture, therefore the identify “ordered dithering”.

The brink map for the random dithering above, actually a map filled with random thresholds, can also be known as “white noise”. The identify comes from a time period in sign processing the place each frequency has the identical depth, similar to in white mild.

Bayer Dithering

“Bayer dithering” makes use of a Bayer matrix as the edge map. They’re named after Bryce Bayer, inventor of the Bayer filter, which is in use to at the present time in digital cameras. Every pixel on the sensor can solely detect brightness, however by cleverly arranging coloured filters in entrance of the person pixels, we will reconstruct shade pictures by way of demosaicing. The sample for the filters is similar sample utilized in Bayer dithering.

Bayer matrices are available in numerous sizes which I ended up calling “ranges”. Bayer Stage 0 is $2 instances 2$

$$start{array}{rcl} textual content{Bayer}(0) & = & left( start{array}{cc} 0 & 2 3 & 1 finish{array} proper) finish{array}$$

$$start{array}{c} textual content{Bayer}(n) = left( start{array}{cc} 4 cdot textual content{Bayer}(n-1) + 0 & 4 cdot textual content{Bayer}(n-1) + 2 4 cdot textual content{Bayer}(n-1) + 3 & 4 cdot textual content{Bayer}(n-1) + 1 finish{array} proper) finish{array}$$

A degree $n$ Bayer matrix incorporates the numbers $0$ to $2^{2n+2}$

const bayer = generateBayerLevel(degree);
grayscaleImage.mapSelf((brightness, { x, y }) =>
  brightness > bayer.valueAt(x, y, { wrap: true }) 
    ? 1.0 
    : 0.0
);

One factor to notice: Bayer dithering utilizing matrices as outlined above will render a picture lighter than it initially was. For instance: An space the place each pixel has a brightness of $frac{1}{255} = 0.4$

In our darkish check picture, the sky just isn’t pure black and made considerably brighter when utilizing Bayer Stage 0. Whereas it will get higher with increased ranges, an alternate resolution is to flip the bias and make pictures render darker by inverting the best way we use the Bayer matrix:

const bayer = generateBayerLevel(degree);
grayscaleImage.mapSelf((brightness, { x, y }) =>
  
  brightness > 1 - bayer.valueAt(x, y, { wrap: true }) 
    ? 1.0 
    : 0.0
);

I’ve used the unique Bayer definition for the sunshine picture and the inverted model for the darkish picture. I personally discovered Stage 1 and three essentially the most aesthetically pleasing.

Blue noise

Each white noise and Bayer dithering have drawbacks, in fact. Bayer dithering, for instance, could be very structured and can look fairly repetitive, particularly at decrease ranges. White noise is random, that means that there inevitably can be clusters of vibrant pixels and voids of darker pixels within the threshold map. This may be made extra apparent by squinting or, if that’s an excessive amount of give you the results you want, by way of blurring the edge map algorithmically. These clusters and voids can have an effect on the output of the dithering course of negatively. If darker areas of the picture fall into one of many clusters, particulars will get misplaced within the dithered output (and vice-versa for brighter areas falling into voids).

There’s a variant of noise known as “blue noise”, that addresses this situation. It’s known as blue noise as a result of increased frequencies have increased intensities in comparison with the decrease frequencies, similar to blue mild. By eradicating or dampening the decrease frequencies, cluster and voids turn out to be much less pronounced. Blue noise dithering is simply as quick to use to a picture as white noise dithering — it’s only a threshold map in the long run — however producing blue noise is a bit more durable and costly.

The most typical algorithm to generate blue noise appears to be the “void-and-cluster technique” by Robert Ulichney. Right here is the original whitepaper. I discovered the best way the algorithm is described fairly unintuitive and, now that I’ve applied it, I’m satisfied it’s defined in an unnecessarily summary style. However it’s fairly intelligent!

The algorithm relies on the concept you will discover a pixel that’s a part of cluster or a void by making use of a Gaussian Blur to the picture and discovering the brightest (or darkest) pixel within the blurred picture respectively. After initializing a black picture with a few randomly positioned white pixels, the algorithm proceeds to constantly swap cluster pixels and void pixels to unfold the white pixels out as evenly as doable. Afterwards, each pixel will get a quantity between 0 and n (the place n is the full variety of pixels) in accordance with their significance for forming clusters and voids. For extra particulars, see the paper.

My implementation works nice however just isn’t very quick, as I didn’t spend a lot time optimizing. It takes about 1 minute to generate a 64×64 blue noise texture on my 2018 MacBook, which is adequate for these functions. If one thing quicker is required, a promising optimization could be to use the Gaussian Blur not within the spatial area however within the frequency area as a substitute.

Tour: Of course figuring out this nerd-sniped me into implementing it. The rationale this optimization is so promising is as a result of convolution (which is the underlying operation of a Gaussian blur) has to loop over every area of the Gaussian kernel for every pixel within the picture. Nevertheless, in the event you convert each the picture in addition to the Gaussian kernel to the frequency area (utilizing one of many many Quick Fourier Rework algorithms), convolution turns into an element-wise multiplication. Since my focused blue noise dimension is an influence of two, I might implement the well-explored in-place variant of the Cooley-Tukey FFT algorithm. After some initial hickups, it did find yourself reducing the blue noise era time by 50%. I nonetheless wrote fairly garbage-y code, so there’s much more to room for optimizations.

As blue noise relies on a Gaussian Blur, which is calculated on a torus (a elaborate means of claiming that Gaussian blur wraps round on the edges), blue noise may also tile seamlessly. So we will use the 64×64 blue noise and repeat it to cowl the complete picture. Blue noise dithering has a pleasant, even distribution with out displaying any apparent patterns, balancing rendering of particulars and natural look.

Error diffusion

All of the earlier methods depend on the truth that quantization errors will statistically even out as a result of the thresholds within the threshold maps are uniformly distributed. A unique method to quantization is the idea of error diffusion, which is more than likely what you could have examine you probably have ever researched picture dithering earlier than. On this method we don’t simply quantize and hope that on common the quantization error stays negligible. As a substitute, we measure the quantization error and diffuse the error onto neighboring pixels, influencing how they’ll get quantized. We’re successfully altering the picture we wish to dither as we go alongside. This makes the method inherently sequential.

Foreshadowing: One huge benefit of error diffusion algorithms that we gained’t contact on on this put up is that they will deal with arbitrary shade palettes, whereas ordered dithering requires your shade palette to be evenly spaced. Extra on that one other time.

Virtually all error diffusion ditherings that I’m going to take a look at use a “diffusion matrix”, which defines how the quantization error from the present pixel will get distributed throughout the neighboring pixels. For these matrices it’s typically assumed that the picture’s pixels are traversed top-to-bottom, left-to-right — the identical means us westerners learn textual content. That is vital because the error can solely be subtle to pixels that haven’t been quantized but. If you end up traversing a picture in a special order than the diffusion matrix assumes, flip the matrix accordingly.

“Easy” 2D error diffusion

The naïve method to error diffusion shares the quantization error between the pixel beneath the present one and the one to the suitable, which could be described with the next matrix:

$$left(start{array}{cc} * & 0.5 0.5 & 0 finish{array} proper)$$

The diffusion algorithm visits every pixel within the picture (in the suitable order!), quantizes the present pixel and measures the quantization error. Notice that the quantization error is signed, i.e. it may be damaging if the quantization made the pixel brighter than the unique brightness worth. We then add fractions of the quantization error to neighboring pixels as specified by the matrix. Rinse and repeat.

This animation is meant to visualise the algorithm, however gained’t be capable of present that the dithered consequence resembles the unique. 4×4 pixels are hardly sufficient do diffuse and common out quantization errors. But it surely does present that if a pixel is made brighter throughout quantization, neighboring pixels can be made darker to make up for it (and vice-versa).

Nevertheless, the simplicity of the diffusion matrix is liable to producing patterns, just like the line-like patterns you possibly can see within the check pictures above.

Floyd-Steinberg

Floyd-Steinberg is arguably essentially the most well-known error diffusion algorithm, if not even essentially the most well-known dithering algorithm. It makes use of a extra elaborate diffusion matrix to distribute the quantization error to all instantly neighboring, unvisited pixels. The numbers are fastidiously chosen to stop repeating patterns as a lot as doable.

$$frac{1}{16} cdot left(start{array} {} & * & 7 3 & 5 & 1 finish{array} proper)$$

Floyd-Steinberg is a giant enchancment because it prevents lots of patterns from forming. Nevertheless, bigger areas with little texture can nonetheless find yourself wanting a bit unorganic.

Jarvis-Judice-Ninke

Jarvis, Judice and Ninke take an excellent greater diffusion matrix, distributing the error to extra pixels than simply instantly neighboring ones.

$$frac{1}{48} cdot left(start{array} {} & {} & * & 7 & 5 3 & 5 & 7 & 5 & 3 1 & 3 & 5 & 3 & 1 finish{array} proper)$$

Utilizing this diffusion matrix, patterns are even much less prone to emerge. Whereas the check pictures nonetheless present some line like patterns, they’re much much less distracting now.

Atkinson Dither

Atkinson dithering was developed at Apple by Invoice Atkinson and gained notoriety on on early Macintosh computer systems.

$$frac{1}{8} cdot left(start{array}{} & * & 1 & 1 1 & 1 & 1 & & 1 & & finish{array} proper)$$

It’s price noting that the Atkinson diffusion matrix incorporates six ones, however is normalized utilizing $frac{1}{8}$

Riemersma Dither

To be utterly sincere, the Riemersma dither is one thing I stumbled upon accidentally. I discovered an in-depth article whereas I used to be researching the opposite dithering algorithms. It doesn’t appear to be extensively identified, however I actually like the best way it appears to be like and the idea behind it. As a substitute of traversing the picture row-by-row it traverses the picture with a Hilbert curve. Technically, any space-filling curve would do, however the Hilbert curve got here really useful and is rather easy to implement using generators. Via this it goals to take the perfect of each ordered dithering and error diffusion dithering: Limiting the variety of pixels a single pixel can affect along with the natural look (and small reminiscence footprint).

The Hilbert curve has a “locality” property, that means that the pixels which can be shut collectively on the curve are additionally shut collectively within the image. This fashion we don’t want to make use of an error diffusion matrix however quite a diffusion sequence of size $n$. To quantize the present pixel, the final $n$ quantization errors are added to the present pixel with weights given within the diffusion sequence. Within the article they use an exponential falloff for the weights — the earlier pixel’s quantization error getting a weight of 1, the oldest quantization error within the checklist a small, chosen weight $r$. This leads to the next system for the $i$th weight:

$$textual content{weight}[i] = r^{-frac{i}{n-1}}$$

The article recommends $r = frac{1}{16}$

The dithering appears to be like extraordinarily natural, nearly nearly as good as blue noise dithering. On the identical time it’s simpler to implement than each of the earlier ones. It’s, nonetheless, nonetheless an error diffusion dithering algorithm, that means it’s sequential and never appropriate to run on a GPU.

???? Blue noise, Bayer & Riemersma

As a 3D recreation, Obra Dinn had to make use of ordered dithering to have the ability to run it as a shader. It makes use of each Bayer dithering and blue noise dithering which I additionally suppose are essentially the most aesthetically pleasing decisions. Bayer dithering reveals a bit extra construction whereas blue noise appears to be like very pure and natural. I’m additionally notably keen on the Riemersma dither and I wish to discover the way it holds up when there are a number of colours within the palette.

Obra Dinn makes use of blue noise dithering for many of the atmosphere. Folks and different objects of curiosity are dithered utilizing Bayer, which types a pleasant visible distinction and makes them stand out with out breaking the video games general aesthetic. Once more, extra on his reasoning as nicely his resolution to dealing with digicam motion in his forum post.

If you wish to attempt completely different dithering algorithms on one in every of your individual pictures, check out my demo that I wrote to generate all the pictures on this weblog put up. Remember the fact that these aren’t the quickest. If you happen to determine to throw your 20 megapixel digicam JPEG at this, it can take some time.

Notice: It appears I’m hitting a de-opt in Safari. My blue noise generator takes ~30 second in Chrome, however takes >20 minutes Safari. It’s significantly faster in Safari Tech Preview.

I’m positive this tremendous area of interest, however I loved this rabbit gap. If in case you have any opinions or experiences with dithering, I’d love to listen to them.

Thanks & different sources

Because of Lucas Pope for his video games and the visible inspiration.

Because of Christoph Peters for his glorious article on blue noise generation.