Error Diffusion Dithering - Computerphile

The smarter way to dither. Dr Bagley takes us through the Floyd-Steinberg error diffusion dithering technique.
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

[@pseudo_goose]

Aw man, you had to put in a teaser for audio dithering at the end. I hope that's in a video soon!

[@azyfloof]

It was probably in the audio of _this_ video :P

[@ChristopherMeadors]

I'm definitely here for the audio dithering. There's an excellent Xiph video called Digital Show and Tell, that goes into what dither does for audio. But other than providing a sample code download, it doesn't really go into the how it's implemented.

[@kaitlyn__L]

Me too!

[@sixft7in]

I love how Dr. Bagley wears that shirt for the dithering videos.

[@totlyepic]

...I think it's more likely that the two videos were just recorded on the same day.

[@sixft7in]

@@totlyepic True, but the fact that he wore that shirt for both or each is still funny.

[@sixft7in]

@Zero Cool Oh, I know. Either way it's funny to me, accidental or intentional.

[@TimTam69420]

I very much hope you asked how they do it for audio. its actually pretty straightforward and would make for an interesting video

[@veggiet2009]

It's interesting that I've seen these different styles of dithering, and I've recognized them as different, but I've never considered what made them different.... These videos are fascinating. I'd like more detail about how the algorithms translate to color and to higher bit depths.

[@jursamaj]

In color, you'd simply dither each of the color channels (red, green, & blue) separately. For higher bits depths, you just pick values for each pixel value. So instead of black (0) and white (255) for 1-bit, you'd have 0, 85, 170, & 255 for 2-bit. You'd use the same error diffusion after picking the nearest value. Technically, your values don't have to be equally spaced, and the formulae really should account for things like display gamma.

[@DreadKyller]

even with how many colors we have today on most modern devices dithering is still used even with 8-bit colors, if you have a smooth gradient there are points where it moves from being solid 80 for example down to solid 79, and while that's not really noticeable, you can still dither that change to blend the colors together to simulate even more colors in between. Because when zoomed in even 256 options per color channel can still have banding issues, dithering as it zooms in helps remove such banding artifacts.

[@user-zz6fk8bc8u]

Dithering is still used in generated color images to reduce banding.

[@silkwesir1444]

What a great idea, why didn't I think of that. Thanks.

[@lazycrypt6893]

KZbin compression sure didn't like the dithering.

[@jerrywatson1958]

Wow you earned a new sub today! Finally after all these years of seeing this kind of dithering in my (then) Amiga photo creation software and graphics it clicked! How the computer calculates each pixel on the screen. The math is calculated and displayed SO fast it puts me in awe of what designers have done. This helps me in what I am trying to learn to do in Blender and understand lighting.

[@tungstikum]

"Error diffusion dithering" is how I walk home from the pub.

[@haulin]

It's also my relationship strategy. I don't return to the one I've already done.

[@JaccovanSchaik]

Wonder what dithering algorithm the shirt uses.

[@haulin]

Must be a crappy one. I can't work out what was the original image.

[@FyberOptic]

These videos were so interesting that after the last one I started playing with implementing a color dithering script, just to experiment with it. Dithering is always something I took for granted in programs like Paint Shop Pro over the last few decades, but never really considered how it worked.

[@mrsvcd]

Thank you for explaining Floyd-Steinberg dithering and now I can understand the notation for it as well.

[@mspysu79]

Another good video, and a teaser for what Sony used to call "Super BitMapping" using a 20 bit ADC and dithering down to 16 bit for recording on a CD.

[@roderik1990]

Notes that you likely want to add some noise before going through the whole floyd-steinberg process. (of the proper PDF) To prevent noise modulation from being too noticeable. Error diffusion dithering like Floyd-Steinberg, is analogous to noise shaping in audio dithering.

[@10100rsn]

What about half-tone algorithms where there is lpi and angle?

[@piteoswaldo]

What's the name of the dither technique that simply sums a white noise to the original image before thresholding?

[@user-vn7ce5ig1z]

5:00 - That's how PWM works.

[@stanrogers5613]

...or PCM (pulse code modulation), where the on/off edges are fixed, which can make some parts of the circuitry easier to manage, but the pattern of pulses is varied (basically a single-bit synchronous encoding of a number). That was how single-bit oversampling worked on many of the early "hifi" CD players, for instance, to move the quantization noise far enough out of the audio frequency range to make filtering easy using lower-order filters (which don't hurt teeth nearly as badly as "brick wall" high-order filter phase shifts).

[@KX36]

or PFM

[@NullPointer]

It's also used today in Deferred Rendered engines to acchieve screen door transparency

[@misterhat5823]

Dithering down (or reducing bit width) is a different process. A random noise (or triangle wave to cheat) is added to the signal and then it's truncated. This is done instead of rounding or simple truncation.

[@matt4193]

Nice dithered shirt, Dr. Bagley.

[@Rocket_Try]

Great, thank you so much. Got it working with your explanation on an ESP32 Cam.

[@NoHandleToSpeakOf]

Animated GIF is limited to 256 colors and they use dithering too.

[@superscatboy]

If keeping the size of a gif to a minimum is a major concern, dithering is your worst enemy :P

[@NoHandleToSpeakOf]

@@superscatboy True. Multi-meg gifs are rarely problematic these days though

[@pattywu9301]

Thanks for the video really helpful

[@alexxxcanz]

I’d like a video on Intel Management Engine. About what is it, how does it work and how to disabled it. That would be great!

[@Sth0r]

Hey love the stuff you guys and girls make on this channel. what happnes if you do this to the red, the green and the blue layers and rekomebine them?

[@decece]

There's a nice example at: caca.zoy.org/study/part6.html

[@arsnakehert]

_Excellent_ choice of shirt

[@f4614n]

At 4:01 it really shows that video compression was not designed to cope with dithered signals.

[@misterhat5823]

Very true. It's adding high frequency noise and most compression methods attempt to throw out high frequency signals.

[@nsputnik]

How did you create the dithering example at 4:04? I have been wanting to do this in VDMX. I can do it with still images by bringing a .jpg into Classic Mac OS Photoshop and switching to graysacale and then halftone.

[@TheAnarchoX_]

We use it to dither lens molds, these lens printer heads have a resolution of a few microns and are rather fault sensitive by applying dithering to the 3d mapping we can eliminate the error of broken printer heads so that we always get a smooth result

[@roar779]

Can someone please tell me what the last sentence was after the big pause? at 5:52

[@forthrightgambitia1032]

A video on line/circle drawing algorithms would be nice.

[@benjamimapancake6429]

Seconded or rather, seventhed

[@renemunkthalund3581]

I would like to have seen dithering in time exemplified on Dr. Bagley. I know it would take some coding, since it's not readily available like Floyd-Steinberg.

[@themusicicreate]

I'd love to learn about audio dithering like he alluded to at the end!

[@juschu85]

The export dialog in my music software also gives me a dithering option. So this is probably also dithering over time since you can only hear a single sample at a time. So in that case, the error is just carried over to the next sample, right?

[@groszak1]

nope, that leads to high frequencies, in audio dithering they randomize whether to round up or down so that the error is uniformly a noise

[@WacKEDmaN]

i wanna know about audio dithering!

[@karlkastor]

Isn't 'dithering in time' just Pulse-width modulation?

[@misterhat5823]

Never thought of that, but essentially yes.

[@danieljensen2626]

Sounds like it yeah, but for each pixel in an image.

[@n00dle_king]

Such a cool algorithm. Makes me miss school.

[@solemnwaltz]

Nice! Your shirt matches your topic. :D

[@noestreet760]

If these values are based on quadrants, why is the maximum 255, not 256?

[@raydleemsc]

So is Floyd-Steinberg used in audio dithering?

[@misterhat5823]

No.

[@groszak1]

humans perceive audio differently than images so Floyd-Steinberg isn't the best choice for audio dithering, randomizing whether to round up or down gives better results for audio

[@OrangeC7]

Me in the previous video: Awww what they didn't show off the dithering on that image! Me in this video: Oh, that's why they didn't show it off

[@BlankBrain]

5:52 Please discuss dithering in audio.

[@JamesBrown-oz5bl]

of course you'd first multiply and only then divide and you'd want gamma correction in your error values...

[@3dlabs99]

That shirt is perfect for the video :)

[@dreammfyre]

Double surnames always makes me think of some dystopian mega-corporation. Maas-Chen Holdings etc.

[@simonmultiverse6349]

Was your shirt created by a dithering algorithm?

[@victorx4648]

A funny thing - just yesterday I was wondering how those dithering algorithms are working. :)

[@AlphaFoxDelta]

Always a pleasure, even if this isnt not my error of expertise, heh

[@sogerc1]

I remember so-so many years ago, when color was a problem for videocards I used to love dithering. Except when looking at pictures of naked chicks ;-)

[@TheRumpletiltskin]

PLS DO AUDIO DITHERING!

[@NVRMTmotion]

Just wrote a python program for cropping and printing photos on thermal printers, dithering required, still relevant and fascinating!

[@someone-br9ur]

notch's tweet

[@KOrbyPoulpe]

Recently, Dithering have also been heavily used in the game "Return of the Obra Dinn" released in october 2018

[@cacheman]

Lucas Pope (the author) did some additional work to make the dithering more stable under movment. He wrote about the technical details in a post on tigsource, which can be easily found through google by searching for something like "lucas pope dithering" #bayermatrix #bluenoise

[@rev_lunar]

Dithering in time seems like it would be the best solution for static images as it wouldn't compromise image quality, but would require more resources.

[@misterhat5823]

There's a limited frame rate most display devices can use, so the benefits are less than you might expect.

[@KuraIthys]

Floyd-Steinberg is a better method on paper, but personally I've always found it to be one of the uglier methods to perform dithering. Guess there's always compromises with stuff like this...

[@hillwin10]

Oh -- we are getting "fancy." Lol.

[@cipherxen2]

His shirt can be dithered

[@danfg7215]

black then white then black then white then black then white then black then white then black then white then black then white then black then white then black then white then black then white then...

[@preferredimage]

Cool minecraft shirt bro! ;)

[@michaelcharlesthearchangel]

Hm. The moment a voxel-deep hologram shade appears and then fills in. I see some kind of holodithering occurring until less than 2 percent error is maintained. Quantum computers/hyperservers will help us speed up the resolution-- error correction of a quantumFlashplayer playing a holovideo.

[@hrnekbezucha]

Printers are black and white. A colour printer is four printers in one package, each doing one colour.

[@vitalnutrients744]

130th!

[@Eternal_23]

Blue noise is answer for everything

[@blazbole3342]

nice teeth

[@blazbole3342]

space for train

[@blazbole3342]

sry bro. ly

[@fredericchopin2947]

Philip Seymour Hoffman

[@schatjepatatje767]

uwu

[@Muzkaw]

It's pixel level ASCII art!

[@SeamusCampbell89]

First

[@misterhat5823]

First down vote.

[@superscatboy]

This is extremely interesting.

[@VIVAFPV]

boring