9 ms·

Atkinson Dithering (2021)

236 points by jdblair 2y ago

NelsonMinar 2y ago
These days dithering is a lost technique other than as an arty effect. It's a shame, digital video playback would really benefit from it as a way to eliminate posterization.
- 01HNNWZ0MV43FF 2y ago
  I assume those 10 and 12 bit codecs do it on playback, it's just that free video services bit-starve the encoders
  - adgjlsfhk1 2y ago
    Especially with AV1, 10 bit color can lead to a cleaner image with fewer bits than 8 bit. The quantization tables mean that you don't have to store the 10 bit info for the high frequency parts, but just having it available makes things like I frames work better (because randomly shifting blocky output is a worse predictor than the underlying smooth signal).
- zamadatix 2y ago
  Dithering is usually applied as pre or post processing step to encoding/decoding because accurately encoding dither itself actually takes more bits than just encoding without banding would in the first place. Nowadays the easiest way to sidestep banding is to use >8 bit encoding and a codec with good psycho-visual enhancements & perceptual quantization.
  - Sharlin 2y ago
    Of course as post-processing step, yes. Dithering is not uncommon in games to avoid posterization of gradients (which can happen even with 24-bit colors without any extra quantization) so it would be pretty natural for media players to do it as well. And doing it in the player would mean older videos without fancy 10-bit PQ stuff would benefit as well.
    - tempoponet 2y ago
      I'd be curious to know more about how this is done in games. I have noticed that if you get up close to the surface of a car in a lot of modern racing games it has a very noisy/sparkly shader. I know some paint does look like this, but I always suspected this was to prevent banding by creating sub-pixel noise.
- SaberTail 2y ago
  Also e-ink displays. For most of the ebooks I've read recently, the images end up posterized to the point of near illegibility.
  - ddingus 2y ago
    Definitely! The better ones have really high resolution, which compliments this dither technique perfectly.
- doublesocket 2y ago
  We've very recently been testing multiple dithering techniques for graphics we send as bitmaps to a TIJ printer that's used as a dynamic labeller.
- semireg 2y ago
  It’s still used every day in low-DPI label printing where dithering and pixel alignment are very important.
  - Tommix11 2y ago
    Also in the retro computer demo scene is dithering very important. I've seen some outrageously great dithering on C64 demo art.
    - makapuf 2y ago
      Also everywhere you want smooth gradients on any application. Go search gradient rendering without banding by example. Dithering will almost certainly be mentioned.
- dahart 2y ago
  No, not entirely! Dithering is still very important for print media and for displays. I’m talking about dithering from 16 or 32 bits per channel, e.g. floating point and/or HDR, down to 8 bits per channel. The dithering techniques like Floyd Steinberg and Atkinson taking 8 or 4 bits per channel down to 1 bit per channel are definitely anachronistic, but not dithering where the goal is 8 bits per channel. I’ve made very expensive mistakes printing poster-sized art without using dithering, and you can end up with visible color-banding in gradients in the print that aren’t visible on a display. This is why we still need and still have dithering. This is the reason that Photoshop quietly dithers by default when you convert from 16 or 32 bits per channel down to 8 bits per channel.
  - btbuildem 2y ago
    I've definitely seen color banding on video playback across multiple streaming services. Dithering would've been super helpful in resolving that.
    - quietbritishjim 2y ago
      If there wasn't the bandwidth to include full colour depth information then there definitely wasn't the bandwidth for the high-frequency pixel data for dithering.
      - dahart 2y ago
        Lossy compression is definitely anti-dither, that’s true. I think a lot of the banding you see in streaming is actually bad color handing and/or miscalibrated devices… very dark colors are especially prone to banding and it’s often due to TVs being turned up brighter than they should be, and sometimes due to compression algorithms ignoring color space & gamma.
        adgjlsfhk1 2y ago
        what you generally want is rather than lossy compression on top of dithering, to instead use lossy compression of higher bit depth data, and then the decoder can add the dithering to represent the extra bits.
- highlaif 2y ago
  [dead]
- prewett 2y ago
  Well, it's more niche, but it's still necessary. For instance, if you write a printer driver you'll need a good dithering algorithm, since you only get pigment on/off (even in CMYK). In fact, for multi-channel dither you do not want a normal error-diffusion algorithm, since it does not give good results for low values of a channel (for instance, rgb(255, 255, 2)). There appears to be active research on new dithering techniques. I ran across libdither [1] which implements more dithering algorithms that you can imagine. [1] https://github.com/robertkist/libdither https://github.com/robertkist/libdither
- dvh 2y ago
  Chrome uses dithering for canvas gradients, or any other operations really. Firefox looks much worse without it.
- SomeoneFromCA 2y ago
  dwm_lut, widely used tool uses dithering
- Etherlord87 2y ago
  In Blender, dithering is enabled by default. First of all, it's not exactly true, that 8 bits per channel make it so banding is unnoticeable - but it's very hard to notice; will depend on the area of colors (darker/brigher, redish/bluish...), but also if you dither your gradient in the image, and the image is further processed, the dither will help avoid banding after processing. Of course if you want to process an image, don't save it in just 8 bits per channel, but sometimes you don't know the image will be processed, or choosing the format is not up to you.
JKCalhoun 2y ago
I fell in love with the original Macintosh display. It was so crisp, the black and white pixels so beautiful (especially if you had come off the typical computer hooked up to a TV). Combine that with the beautiful dithering and I almost shunned color when it came along. (I believe I've read that Atkinson's dithering didn't come about until scanner software was needed for the Macintosh and so he wrote his own dithering code.)
- kccqzy 2y ago
  I fell in love with the display of Playdate (https://play.date/ https://play.date/), a handheld gaming device that very much inherits the ethos of the original Macintosh display. I'm not even a gamer and I hardly play games and yet I love that screen.
- marssaxman 2y ago
  I have fond memories of the charming pixelated art featured in the classic Macintosh game "Glider", written by someone with an oddly familiar name... That 512x342 monochrome world was really kind of special. I used to spend hours carefully tweaking every pixel in my little 32x32 program icons, trying to make them fit the overall aesthetic.
  - jrussino 2y ago
    Wow I had totally forgotten about this game! Glider (I think I may have played "Glider PRO") was so much fun. I found this youtube video of the game and the title screen music just gave me a wave of nostalgia: https://www.youtube.com/watch?v=V4QP76Om7sQ https://www.youtube.com/watch?v=V4QP76Om7sQ
  - JKCalhoun 2y ago
    Thanks, and yeah, pixels mattered then. When I made Glider in color for the first commercial release, I used only the 16 colors of the Macintosh palette - I guess to keep the performance up, memory footprint down. There was a good deal of experimenting with hand-dithering to get more muted colors — like maybe a checkerboard pattern of brown & grey to get a mustier-looking wood.
kibwen 2y ago
Dithering can still be a striking aesthetic choice. Low Tech Magazine is my go-to example: https://solar.lowtechmagazine.com/ https://solar.lowtechmagazine.com/ From their About page: "Thus, instead of using full-colour high-resolution images, we chose to convert all images to black and white, with four levels of grey in-between. These black-and-white images are then coloured according to the pertaining content category via the browser’s native image manipulation capacities. Compressed through this dithering plugin, images featured in the articles add much less load to the content: compared to the old website, the images are roughly ten times less resource-intensive."
- flobosg 2y ago
  See also the video game Return of the Obra Dinn (https://en.wikipedia.org/wiki/Return_of_the_Obra_Dinn https://en.wikipedia.org/wiki/Return_of_the_Obra_Dinn) as well as the developer log entry about dithering (https://forums.tigsource.com/index.php?topic=40832.msg1363742#msg1363742 https://forums.tigsource.com/index.php?topic=40832.msg136374...).
  - magicalhippo 2y ago
    Was about to mention this game. Found it through HN and loved it. The dithering is used very well in the game and fits very well with the overall gameplay. An interesting aspect about the game is how it required making the dithering stable to changing viewpoints, not something typical dithering algorithms care about.
- Rygian 2y ago
  > compared to the old website, the images are roughly ten times less resource-intensive. Does that account for the repeated post processing done by every client?
  - blacksmith_tb 2y ago
    My sense is they're trying to reduce request size/processing/reading from disk for their solar-powered server, more than reduce the whole world's energy use.
moribvndvs 2y ago
I never really paid attention to the grid-like artifacts[0] that FSD and some other dithering algorithms cause when a dithered image is scaled way down (as is the case of the thumbnails in this article). [0] https://en.m.wikipedia.org/wiki/Moir%C3%A9_pattern https://en.m.wikipedia.org/wiki/Moir%C3%A9_pattern
antirez 2y ago
Floyd-Steinberg looks a lot better IMHO.
- KerrAvon 2y ago
  Results will vary by image; I'm not sure the single comparison in TFA is the best possible source for comparison.
londons_explore 2y ago
I would like to see the ideas of dithering applied to voting systems. Ie. Imagine a country with hundreds of elected officials, each of which represents a town or city. Each official is part of a party. A dithering-like system could be used during the vote so that the country as a whole is fairly represented, and most towns also are represented by who the majority of their population wants. It would work by, during an election, whenever a candidate is chosen for a location, any votes for other parties get transferred to neighbouring towns and cities. That is done repeatedly until every towns seat is filled, and nearly every voters vote has an impact (if not in their local town, then it gets to help a candidate of the same party nearbyish)
- garaetjjte 2y ago
  Just sum party votes and calculate amount of seats for each party on national level, then assign seats for each party based on regional results.
  - pacaro 2y ago
    Or cut to the chase and use sortition, which will provide statistically correct representation with out even needing a vote
- dahart 2y ago
  This is what (for example) congress and congressional districts are supposed to help with, but gerrymandering prevents it from working as intended. I’m kinda guessing that adding a dithering algorithm might only change the gerrymandering without fixing the problem, but I’m certainly curious as to what that might look like and whether there are ways to prevent gerrymandering, with or without vote dithering. I’m guessing it would be extremely difficult to get anything with randomness in it passed as law. First we need to get “one person, one vote” to be the actual goal (https://en.wikipedia.org/wiki/One_man,_one_vote https://en.wikipedia.org/wiki/One_man,_one_vote). In the US, the electoral college was specifically designed to not have one person, one vote as the primary goal, and we haven’t been able to change it yet. For presidential elections, we don’t really need dithering so much as simple majority winner, plus run-off vote counting. Maybe run-off voting already is a type of vote dithering?
bryanthompson 2y ago
One really nice use case for dithering that I've found is for building graphics for 8-bit (Pico-8 and Picotron) games and toys. I made a ruby script that can take a graphic and scale it to whatever size, then it uses a closest color match to substitute colors for the _very_ limited Pico* palette and applies dithering to make it look attractive. I like Stenberg the most, but have played with Atkinson and am still feeling around a bit.
AceJohnny2 2y ago
Why is the Floyd-Steinberg error diffusion kernel so uneven? What's the output like if the error is distributed equally among the bottom-right pixels? And this is a naive question, but could one construct a kernel that diffuses the error across all surrounding pixels, not just the bottom+right? I get that this will cause recursion difficulties as error bounces back-and-forth between neighboring pixels, but is that resolvable?
- chowells 2y ago
  Bottom+right is purely a performance optimization, when processing top-to-bottom, left-to-right. You only ever push the error terms to pixels you haven't processed yet, so the whole algorithm remains a single linear pass. That was the standard approach for handling images at the time. Everything was stored as lines of raster data, rather than the blocks modern compressed formats prefer, and there wasn't parallel processing available to speed things up in ways that make linear data dependency awkward.
  - nullc 2y ago
    It doesn't just prevent you from having to make two passes, it prevents you from having to make potentially infinite passes!
- DonHopkins 2y ago
  Instead of top/bottom left/right scan, you can perform a serpentine scan that goes top/bottom, but alternates left/and right/left each row, zig zagging as it goes down the page. That way the errors get spread out more evenly, and you don't get 45 degree diagonal flowing artifacts down and to the right. The In-Laws (1979): Getting off the plane in Tijuara: https://www.youtube.com/watch?v=A2_w-QCWpS0 https://www.youtube.com/watch?v=A2_w-QCWpS0 "Serpentine! Serpentine!!!"
feverzsj 2y ago
Error diffusions are hard to be parallelized. They're also not stable, meaning moving pixel may look different in different frame. But they usually give best result for static images.
garaetjjte 2y ago
More on dithering: https://surma.dev/things/ditherpunk/ https://surma.dev/things/ditherpunk/
- m12k 2y ago
  Also, here's an example of another 3D dithering technique, inspired by Obra Dinn: https://mastodon.gamedev.place/@runevision/110508837173343595 https://mastodon.gamedev.place/@runevision/11050883717334359...
- DonHopkins 2y ago
  Here's an example of iterative error diffusion dithering, procedural circuit bending, mis-using Micropolis (Open Source SimCity) tiles to render cellular automata (dithered heat diffusion, and Eco (Anneal + Life + Brian's Brain): Micropolis Web Space Inventory Cellular Automata Music 1 https://youtu.be/BBVyCpmVQew?t=291 https://youtu.be/BBVyCpmVQew?t=291 Micropolis Web is the browser based version of Micropolis (open source SimCity), that uses WebAssembly, WebGL, and SvelteKit. Based on the original SimCity Classic code, designed by Will Wright, ported by Don Hopkins. This first video has music by Juho Hietala, Blamstrain, and the Space Inventory Cellular Automata is performed by Don Hopkins. https://MicropolisWeb.com https://MicropolisWeb.com (tap the "space" bar a few times, even though it warns you not to) The error diffusion dithering is most noticeable when there's not a lot of heat change in the system (strong enough heating or cooling rotates the tiles towards the extreme, then they wrap around, producing chaotic boiling lava lamp blobs). Without the error diffusion dithering, the heat diffusion produces much more geometric less organic patterns (sharp diagonal triangular crystals that melt away quickly, instead of fuzzy dithered curvy gradients that smoothly organically diffuse and stay around for a long time). Strictly it's not actually a "cellular automata" because of the error diffusion: information travels further than one cell locally each frame -- the leftover energy can "quantum tunnel" in the direction of scanning (serpentine left/right / right/left) into cells downstream arbitrarily far away. So when you draw in one part of the image, the dither fingers in all parts of the image wiggle in response. A true cellular automata has no "action at a distance" and the flow of information respects the "speed of light" (one cell or so per frame, depending on the radius of the neighborhood). https://en.wikipedia.org/wiki/Circuit_bending https://en.wikipedia.org/wiki/Circuit_bending >Circuit bending is the creative, chance-based customization of the circuits within electronic devices such as low-voltage, battery-powered guitar effects, children's toys and digital synthesizers to create new musical or visual instruments and sound generators. >Emphasizing spontaneity and randomness, the techniques of circuit bending have been commonly associated with noise music, though many more conventional contemporary musicians and musical groups have been known to experiment with "bent" instruments. Circuit bending usually involves dismantling the machine and adding components such as switches and potentiometers that alter the circuit.
leni536 2y ago
There is implementation variance on whether you apply the dithering consistently left to right on each row or you alternate. Floyd-Steinberg definitely benefits from the latter approach. Also whether you apply the dithering in a linear colorspace.
nullc 2y ago
This PHD thesis is the best technical coverage of dither science that I've seen: https://uwspace.uwaterloo.ca/bitstream/handle/10012/3867/thesis.pdf;jsessionid=A3B029F6D36E97D7736287A136AB9962?sequence=1 https://uwspace.uwaterloo.ca/bitstream/handle/10012/3867/the... Among the things it covers is the design of a noise shaping filter with a more symmetrical response than the Floyd-Steinberg one.
jd3 2y ago
I remember creating an X-Face[0] using Atkinson Dithering for my SeaMonkey add-on MessageFaces[1]! You can create one online here[2], but it doesn't seem to support Atkinson for whatever reason. [0]: https://en.wikipedia.org/wiki/X-Face https://en.wikipedia.org/wiki/X-Face [1]: https://github.com/JohnDDuncanIII/messagefaces https://github.com/JohnDDuncanIII/messagefaces [2]: https://www.dairiki.org/xface/ https://www.dairiki.org/xface/
WoodenChair 2y ago
This was the article that inspired me to study the MacPaint format. I ended up writing first a Python program that can do Atkinson dithering of a modern image and then save it as a MacPaint file for display on a retro Mac. That code is a chapter in my upcoming book. I then added 9 more 1-bit dithering algorithms and turned it into a Swift/AppKit app so it's easy to use if you want to Atkinson dither your own images and transfer them over to your retro Macs: https://apps.apple.com/us/app/retro-dither-b-w-is-beautiful/id1586423971?mt=12 https://apps.apple.com/us/app/retro-dither-b-w-is-beautiful/...
mungoman2 2y ago
To avoid changing the overall brightness like in the examples it is important to work on linearized values or to adjust the running error accordingly. It's not correct to work on the encoded sRGB values of the image directly. This is a very common mistake in blog articles about diy image filtering.
- virtualritz 2y ago
  Not working in linearized space is a common error in pretty much any new OSS graphics project done by people who's background is not in computer graphics, I came across in the last decade. I think in the old days you got CG know how from a few books or you went to comp.graphics.algrithms where more experienced people would gladly explain stuff to you. Today people watch YT videos and read blog posts produced by people who also lack these basics. It's like an error that get accumulated. But no dithering will help diffusing it. ;)
  - ghusbands 2y ago
    I assure you that people made the same mistake plenty in the old days, too. Most programmers who come across an array of values assume they know what the values mean, and that stands true across time. Many paint packages and other programs still get many transforms/effects wrong due to it, and in fact some people seem to prefer some effects when not linearized.
    - bandrami 2y ago
      > Most programmers who come across an array of values assume they know what the values mean Oh yeah, let me add from the audio synthesis world that this disease is prevalent here too
  - leni536 2y ago
    > Not working in linearized space is a common error in pretty much any new OSS graphics project done by people who's background is not in computer graphics, I came across in the last decade. This still happens in mature software as well, including contemporary web browsers. Just open this image in your favorite browser and zoom out: http://www.ericbrasseur.org/gamma-1.0-or-2.2.png http://www.ericbrasseur.org/gamma-1.0-or-2.2.png
tiffanyh 2y ago
Am I the only person who thinks the Floyd-Steinberg dithering is superior is clarity and detail? The Atkinson dithering makes the image appear overexposed/blown-out (not true to the original image).
- aldto 2y ago
  I agree that area above the nostrils appears blown-out, but I prefer the eyes more in the Atkinson version. So neither algorithm is superior to me.
- pacaro 2y ago
  As another comment mentioned, the differ is being done naively w.r.t. the color space. Handling rgb (or gray) values as linear values is usually wrong
- quietbritishjim 2y ago
  I think Atkinson might have the edge if you were looking at it on a blurry CRT instead of a modern LCD/LED screen.
- crazygringo 2y ago
  Completely agreed. I don't get the appeal of Atkinson dithering at all -- it makes the noise more "clumpy" or "textured" and thereby inherently reduces the amount of detail you can perceive. I don't think that's something subjective. And if you want the "richer contrast" that the article describes Atkinson as providing, then easy -- just increase the contrast of the grayscale image before dithering. Then you actually have control over whatever final contrast you want -- it can be whatever you want! But you won't lose detail the way Atkinson does.
- TapamN 2y ago
  The point of Atkinson is that it's much faster than Floyd-Steinberg on old CPUs. Floyd-Steinberg requires multiplying most source pixel by a small number (3, 5, 7) and doing a right shift by 4. Atkinson is just doing a right shift by 3. On the original Macintosh's Motorola 68000, I could see Atkinson being more than twice as fast.
lukko 2y ago
Thanks for sharing this. I once used Floyd-Steinberg dithering to make 3D voxel prints from brain MRI scans [0]. You just convert the scan to full white and black values to represent different inks, and it means you don't have to do any segmentation and can represent fine structures much more accurately. May be interesting to try with Atkinson dithering too, although the loss of detail may be an issue. [0] https://www.lukehale.com/voxelprinting/ https://www.lukehale.com/voxelprinting/
tiffanyh 2y ago
More example (and algorithms) can be found here: https://brucebcampbell.wordpress.com/wp-content/uploads/2013/04/dithering-methods.pdf https://brucebcampbell.wordpress.com/wp-content/uploads/2013...
OnlyMortal 2y ago
This just reminded me of the “secret” bitmap of the dev team hidden in the OS. I recall using Macsbug to show it.
- joezydeco 2y ago
  G 41D89A (Mac SE)
  - OnlyMortal 2y ago
    I recall opening a Plus and seeing engraved signatures.
deleted 2y ago
[deleted]
GuB-42 2y ago
Just curious, does the website name "Beyond Loom" has anything to do with the video game "Loom" (1990)?

236 points by jdblair 2y ago

These days dithering is a lost technique other than as an arty effect. It's a shame, digital video playback would really benefit from it as a way to eliminate posterization.

01HNNWZ0MV43FF 2y ago
I assume those 10 and 12 bit codecs do it on playback, it's just that free video services bit-starve the encoders
- adgjlsfhk1 2y ago
  Especially with AV1, 10 bit color can lead to a cleaner image with fewer bits than 8 bit. The quantization tables mean that you don't have to store the 10 bit info for the high frequency parts, but just having it available makes things like I frames work better (because randomly shifting blocky output is a worse predictor than the underlying smooth signal).
zamadatix 2y ago
Dithering is usually applied as pre or post processing step to encoding/decoding because accurately encoding dither itself actually takes more bits than just encoding without banding would in the first place. Nowadays the easiest way to sidestep banding is to use >8 bit encoding and a codec with good psycho-visual enhancements & perceptual quantization.
- Sharlin 2y ago
  Of course as post-processing step, yes. Dithering is not uncommon in games to avoid posterization of gradients (which can happen even with 24-bit colors without any extra quantization) so it would be pretty natural for media players to do it as well. And doing it in the player would mean older videos without fancy 10-bit PQ stuff would benefit as well.
  - tempoponet 2y ago
    I'd be curious to know more about how this is done in games. I have noticed that if you get up close to the surface of a car in a lot of modern racing games it has a very noisy/sparkly shader. I know some paint does look like this, but I always suspected this was to prevent banding by creating sub-pixel noise.
SaberTail 2y ago
Also e-ink displays. For most of the ebooks I've read recently, the images end up posterized to the point of near illegibility.
- ddingus 2y ago
  Definitely! The better ones have really high resolution, which compliments this dither technique perfectly.
doublesocket 2y ago
We've very recently been testing multiple dithering techniques for graphics we send as bitmaps to a TIJ printer that's used as a dynamic labeller.
semireg 2y ago
It’s still used every day in low-DPI label printing where dithering and pixel alignment are very important.
- Tommix11 2y ago
  Also in the retro computer demo scene is dithering very important. I've seen some outrageously great dithering on C64 demo art.
  - makapuf 2y ago
    Also everywhere you want smooth gradients on any application. Go search gradient rendering without banding by example. Dithering will almost certainly be mentioned.
dahart 2y ago
No, not entirely! Dithering is still very important for print media and for displays. I’m talking about dithering from 16 or 32 bits per channel, e.g. floating point and/or HDR, down to 8 bits per channel. The dithering techniques like Floyd Steinberg and Atkinson taking 8 or 4 bits per channel down to 1 bit per channel are definitely anachronistic, but not dithering where the goal is 8 bits per channel. I’ve made very expensive mistakes printing poster-sized art without using dithering, and you can end up with visible color-banding in gradients in the print that aren’t visible on a display. This is why we still need and still have dithering. This is the reason that Photoshop quietly dithers by default when you convert from 16 or 32 bits per channel down to 8 bits per channel.
- btbuildem 2y ago
  I've definitely seen color banding on video playback across multiple streaming services. Dithering would've been super helpful in resolving that.
  - quietbritishjim 2y ago
    If there wasn't the bandwidth to include full colour depth information then there definitely wasn't the bandwidth for the high-frequency pixel data for dithering.
    - dahart 2y ago
      Lossy compression is definitely anti-dither, that’s true. I think a lot of the banding you see in streaming is actually bad color handing and/or miscalibrated devices… very dark colors are especially prone to banding and it’s often due to TVs being turned up brighter than they should be, and sometimes due to compression algorithms ignoring color space & gamma.
      - adgjlsfhk1 2y ago
        what you generally want is rather than lossy compression on top of dithering, to instead use lossy compression of higher bit depth data, and then the decoder can add the dithering to represent the extra bits.
highlaif 2y ago
[dead]
prewett 2y ago
Well, it's more niche, but it's still necessary. For instance, if you write a printer driver you'll need a good dithering algorithm, since you only get pigment on/off (even in CMYK). In fact, for multi-channel dither you do not want a normal error-diffusion algorithm, since it does not give good results for low values of a channel (for instance, rgb(255, 255, 2)). There appears to be active research on new dithering techniques. I ran across libdither [1] which implements more dithering algorithms that you can imagine. [1] https://github.com/robertkist/libdither https://github.com/robertkist/libdither
dvh 2y ago
Chrome uses dithering for canvas gradients, or any other operations really. Firefox looks much worse without it.
SomeoneFromCA 2y ago
dwm_lut, widely used tool uses dithering
Etherlord87 2y ago
In Blender, dithering is enabled by default. First of all, it's not exactly true, that 8 bits per channel make it so banding is unnoticeable - but it's very hard to notice; will depend on the area of colors (darker/brigher, redish/bluish...), but also if you dither your gradient in the image, and the image is further processed, the dither will help avoid banding after processing. Of course if you want to process an image, don't save it in just 8 bits per channel, but sometimes you don't know the image will be processed, or choosing the format is not up to you.

JKCalhoun 2y ago

I fell in love with the original Macintosh display. It was so crisp, the black and white pixels so beautiful (especially if you had come off the typical computer hooked up to a TV). Combine that with the beautiful dithering and I almost shunned color when it came along. (I believe I've read that Atkinson's dithering didn't come about until scanner software was needed for the Macintosh and so he wrote his own dithering code.)

kccqzy 2y ago
I fell in love with the display of Playdate (https://play.date/ https://play.date/), a handheld gaming device that very much inherits the ethos of the original Macintosh display. I'm not even a gamer and I hardly play games and yet I love that screen.
marssaxman 2y ago
I have fond memories of the charming pixelated art featured in the classic Macintosh game "Glider", written by someone with an oddly familiar name... That 512x342 monochrome world was really kind of special. I used to spend hours carefully tweaking every pixel in my little 32x32 program icons, trying to make them fit the overall aesthetic.
- jrussino 2y ago
  Wow I had totally forgotten about this game! Glider (I think I may have played "Glider PRO") was so much fun. I found this youtube video of the game and the title screen music just gave me a wave of nostalgia: https://www.youtube.com/watch?v=V4QP76Om7sQ https://www.youtube.com/watch?v=V4QP76Om7sQ
- JKCalhoun 2y ago
  Thanks, and yeah, pixels mattered then. When I made Glider in color for the first commercial release, I used only the 16 colors of the Macintosh palette - I guess to keep the performance up, memory footprint down. There was a good deal of experimenting with hand-dithering to get more muted colors — like maybe a checkerboard pattern of brown & grey to get a mustier-looking wood.

kibwen 2y ago

Dithering can still be a striking aesthetic choice. Low Tech Magazine is my go-to example: https://solar.lowtechmagazine.com/ https://solar.lowtechmagazine.com/ From their About page: "Thus, instead of using full-colour high-resolution images, we chose to convert all images to black and white, with four levels of grey in-between. These black-and-white images are then coloured according to the pertaining content category via the browser’s native image manipulation capacities. Compressed through this dithering plugin, images featured in the articles add much less load to the content: compared to the old website, the images are roughly ten times less resource-intensive."

flobosg 2y ago
See also the video game Return of the Obra Dinn (https://en.wikipedia.org/wiki/Return_of_the_Obra_Dinn https://en.wikipedia.org/wiki/Return_of_the_Obra_Dinn) as well as the developer log entry about dithering (https://forums.tigsource.com/index.php?topic=40832.msg1363742#msg1363742 https://forums.tigsource.com/index.php?topic=40832.msg136374...).
- magicalhippo 2y ago
  Was about to mention this game. Found it through HN and loved it. The dithering is used very well in the game and fits very well with the overall gameplay. An interesting aspect about the game is how it required making the dithering stable to changing viewpoints, not something typical dithering algorithms care about.
Rygian 2y ago
> compared to the old website, the images are roughly ten times less resource-intensive. Does that account for the repeated post processing done by every client?
- blacksmith_tb 2y ago
  My sense is they're trying to reduce request size/processing/reading from disk for their solar-powered server, more than reduce the whole world's energy use.

moribvndvs 2y ago

I never really paid attention to the grid-like artifacts[0] that FSD and some other dithering algorithms cause when a dithered image is scaled way down (as is the case of the thumbnails in this article). [0] https://en.m.wikipedia.org/wiki/Moir%C3%A9_pattern https://en.m.wikipedia.org/wiki/Moir%C3%A9_pattern

antirez 2y ago

Floyd-Steinberg looks a lot better IMHO.

KerrAvon 2y ago
Results will vary by image; I'm not sure the single comparison in TFA is the best possible source for comparison.

londons_explore 2y ago

I would like to see the ideas of dithering applied to voting systems. Ie. Imagine a country with hundreds of elected officials, each of which represents a town or city. Each official is part of a party. A dithering-like system could be used during the vote so that the country as a whole is fairly represented, and most towns also are represented by who the majority of their population wants. It would work by, during an election, whenever a candidate is chosen for a location, any votes for other parties get transferred to neighbouring towns and cities. That is done repeatedly until every towns seat is filled, and nearly every voters vote has an impact (if not in their local town, then it gets to help a candidate of the same party nearbyish)

garaetjjte 2y ago
Just sum party votes and calculate amount of seats for each party on national level, then assign seats for each party based on regional results.
- pacaro 2y ago
  Or cut to the chase and use sortition, which will provide statistically correct representation with out even needing a vote
dahart 2y ago
This is what (for example) congress and congressional districts are supposed to help with, but gerrymandering prevents it from working as intended. I’m kinda guessing that adding a dithering algorithm might only change the gerrymandering without fixing the problem, but I’m certainly curious as to what that might look like and whether there are ways to prevent gerrymandering, with or without vote dithering. I’m guessing it would be extremely difficult to get anything with randomness in it passed as law. First we need to get “one person, one vote” to be the actual goal (https://en.wikipedia.org/wiki/One_man,_one_vote https://en.wikipedia.org/wiki/One_man,_one_vote). In the US, the electoral college was specifically designed to not have one person, one vote as the primary goal, and we haven’t been able to change it yet. For presidential elections, we don’t really need dithering so much as simple majority winner, plus run-off vote counting. Maybe run-off voting already is a type of vote dithering?

bryanthompson 2y ago

One really nice use case for dithering that I've found is for building graphics for 8-bit (Pico-8 and Picotron) games and toys. I made a ruby script that can take a graphic and scale it to whatever size, then it uses a closest color match to substitute colors for the _very_ limited Pico* palette and applies dithering to make it look attractive. I like Stenberg the most, but have played with Atkinson and am still feeling around a bit.

AceJohnny2 2y ago

Why is the Floyd-Steinberg error diffusion kernel so uneven? What's the output like if the error is distributed equally among the bottom-right pixels? And this is a naive question, but could one construct a kernel that diffuses the error across all surrounding pixels, not just the bottom+right? I get that this will cause recursion difficulties as error bounces back-and-forth between neighboring pixels, but is that resolvable?

chowells 2y ago
Bottom+right is purely a performance optimization, when processing top-to-bottom, left-to-right. You only ever push the error terms to pixels you haven't processed yet, so the whole algorithm remains a single linear pass. That was the standard approach for handling images at the time. Everything was stored as lines of raster data, rather than the blocks modern compressed formats prefer, and there wasn't parallel processing available to speed things up in ways that make linear data dependency awkward.
- nullc 2y ago
  It doesn't just prevent you from having to make two passes, it prevents you from having to make potentially infinite passes!
DonHopkins 2y ago
Instead of top/bottom left/right scan, you can perform a serpentine scan that goes top/bottom, but alternates left/and right/left each row, zig zagging as it goes down the page. That way the errors get spread out more evenly, and you don't get 45 degree diagonal flowing artifacts down and to the right. The In-Laws (1979): Getting off the plane in Tijuara: https://www.youtube.com/watch?v=A2_w-QCWpS0 https://www.youtube.com/watch?v=A2_w-QCWpS0 "Serpentine! Serpentine!!!"

feverzsj 2y ago

Error diffusions are hard to be parallelized. They're also not stable, meaning moving pixel may look different in different frame. But they usually give best result for static images.

garaetjjte 2y ago

More on dithering: https://surma.dev/things/ditherpunk/ https://surma.dev/things/ditherpunk/

m12k 2y ago
Also, here's an example of another 3D dithering technique, inspired by Obra Dinn: https://mastodon.gamedev.place/@runevision/110508837173343595 https://mastodon.gamedev.place/@runevision/11050883717334359...
DonHopkins 2y ago
Here's an example of iterative error diffusion dithering, procedural circuit bending, mis-using Micropolis (Open Source SimCity) tiles to render cellular automata (dithered heat diffusion, and Eco (Anneal + Life + Brian's Brain): Micropolis Web Space Inventory Cellular Automata Music 1 https://youtu.be/BBVyCpmVQew?t=291 https://youtu.be/BBVyCpmVQew?t=291 Micropolis Web is the browser based version of Micropolis (open source SimCity), that uses WebAssembly, WebGL, and SvelteKit. Based on the original SimCity Classic code, designed by Will Wright, ported by Don Hopkins. This first video has music by Juho Hietala, Blamstrain, and the Space Inventory Cellular Automata is performed by Don Hopkins. https://MicropolisWeb.com https://MicropolisWeb.com (tap the "space" bar a few times, even though it warns you not to) The error diffusion dithering is most noticeable when there's not a lot of heat change in the system (strong enough heating or cooling rotates the tiles towards the extreme, then they wrap around, producing chaotic boiling lava lamp blobs). Without the error diffusion dithering, the heat diffusion produces much more geometric less organic patterns (sharp diagonal triangular crystals that melt away quickly, instead of fuzzy dithered curvy gradients that smoothly organically diffuse and stay around for a long time). Strictly it's not actually a "cellular automata" because of the error diffusion: information travels further than one cell locally each frame -- the leftover energy can "quantum tunnel" in the direction of scanning (serpentine left/right / right/left) into cells downstream arbitrarily far away. So when you draw in one part of the image, the dither fingers in all parts of the image wiggle in response. A true cellular automata has no "action at a distance" and the flow of information respects the "speed of light" (one cell or so per frame, depending on the radius of the neighborhood). https://en.wikipedia.org/wiki/Circuit_bending https://en.wikipedia.org/wiki/Circuit_bending >Circuit bending is the creative, chance-based customization of the circuits within electronic devices such as low-voltage, battery-powered guitar effects, children's toys and digital synthesizers to create new musical or visual instruments and sound generators. >Emphasizing spontaneity and randomness, the techniques of circuit bending have been commonly associated with noise music, though many more conventional contemporary musicians and musical groups have been known to experiment with "bent" instruments. Circuit bending usually involves dismantling the machine and adding components such as switches and potentiometers that alter the circuit.

leni536 2y ago

There is implementation variance on whether you apply the dithering consistently left to right on each row or you alternate. Floyd-Steinberg definitely benefits from the latter approach. Also whether you apply the dithering in a linear colorspace.

nullc 2y ago

This PHD thesis is the best technical coverage of dither science that I've seen: https://uwspace.uwaterloo.ca/bitstream/handle/10012/3867/thesis.pdf;jsessionid=A3B029F6D36E97D7736287A136AB9962?sequence=1 https://uwspace.uwaterloo.ca/bitstream/handle/10012/3867/the... Among the things it covers is the design of a noise shaping filter with a more symmetrical response than the Floyd-Steinberg one.

jd3 2y ago

I remember creating an X-Face[0] using Atkinson Dithering for my SeaMonkey add-on MessageFaces[1]! You can create one online here[2], but it doesn't seem to support Atkinson for whatever reason. [0]: https://en.wikipedia.org/wiki/X-Face https://en.wikipedia.org/wiki/X-Face [1]: https://github.com/JohnDDuncanIII/messagefaces https://github.com/JohnDDuncanIII/messagefaces [2]: https://www.dairiki.org/xface/ https://www.dairiki.org/xface/

WoodenChair 2y ago

This was the article that inspired me to study the MacPaint format. I ended up writing first a Python program that can do Atkinson dithering of a modern image and then save it as a MacPaint file for display on a retro Mac. That code is a chapter in my upcoming book. I then added 9 more 1-bit dithering algorithms and turned it into a Swift/AppKit app so it's easy to use if you want to Atkinson dither your own images and transfer them over to your retro Macs: https://apps.apple.com/us/app/retro-dither-b-w-is-beautiful/id1586423971?mt=12 https://apps.apple.com/us/app/retro-dither-b-w-is-beautiful/...

mungoman2 2y ago

To avoid changing the overall brightness like in the examples it is important to work on linearized values or to adjust the running error accordingly. It's not correct to work on the encoded sRGB values of the image directly. This is a very common mistake in blog articles about diy image filtering.

virtualritz 2y ago
Not working in linearized space is a common error in pretty much any new OSS graphics project done by people who's background is not in computer graphics, I came across in the last decade. I think in the old days you got CG know how from a few books or you went to comp.graphics.algrithms where more experienced people would gladly explain stuff to you. Today people watch YT videos and read blog posts produced by people who also lack these basics. It's like an error that get accumulated. But no dithering will help diffusing it. ;)
- ghusbands 2y ago
  I assure you that people made the same mistake plenty in the old days, too. Most programmers who come across an array of values assume they know what the values mean, and that stands true across time. Many paint packages and other programs still get many transforms/effects wrong due to it, and in fact some people seem to prefer some effects when not linearized.
  - bandrami 2y ago
    > Most programmers who come across an array of values assume they know what the values mean Oh yeah, let me add from the audio synthesis world that this disease is prevalent here too
- leni536 2y ago
  > Not working in linearized space is a common error in pretty much any new OSS graphics project done by people who's background is not in computer graphics, I came across in the last decade. This still happens in mature software as well, including contemporary web browsers. Just open this image in your favorite browser and zoom out: http://www.ericbrasseur.org/gamma-1.0-or-2.2.png http://www.ericbrasseur.org/gamma-1.0-or-2.2.png

tiffanyh 2y ago

Am I the only person who thinks the Floyd-Steinberg dithering is superior is clarity and detail? The Atkinson dithering makes the image appear overexposed/blown-out (not true to the original image).

aldto 2y ago
I agree that area above the nostrils appears blown-out, but I prefer the eyes more in the Atkinson version. So neither algorithm is superior to me.
pacaro 2y ago
As another comment mentioned, the differ is being done naively w.r.t. the color space. Handling rgb (or gray) values as linear values is usually wrong
quietbritishjim 2y ago
I think Atkinson might have the edge if you were looking at it on a blurry CRT instead of a modern LCD/LED screen.
crazygringo 2y ago
Completely agreed. I don't get the appeal of Atkinson dithering at all -- it makes the noise more "clumpy" or "textured" and thereby inherently reduces the amount of detail you can perceive. I don't think that's something subjective. And if you want the "richer contrast" that the article describes Atkinson as providing, then easy -- just increase the contrast of the grayscale image before dithering. Then you actually have control over whatever final contrast you want -- it can be whatever you want! But you won't lose detail the way Atkinson does.
TapamN 2y ago
The point of Atkinson is that it's much faster than Floyd-Steinberg on old CPUs. Floyd-Steinberg requires multiplying most source pixel by a small number (3, 5, 7) and doing a right shift by 4. Atkinson is just doing a right shift by 3. On the original Macintosh's Motorola 68000, I could see Atkinson being more than twice as fast.

lukko 2y ago

Thanks for sharing this. I once used Floyd-Steinberg dithering to make 3D voxel prints from brain MRI scans [0]. You just convert the scan to full white and black values to represent different inks, and it means you don't have to do any segmentation and can represent fine structures much more accurately. May be interesting to try with Atkinson dithering too, although the loss of detail may be an issue. [0] https://www.lukehale.com/voxelprinting/ https://www.lukehale.com/voxelprinting/

tiffanyh 2y ago

More example (and algorithms) can be found here: https://brucebcampbell.wordpress.com/wp-content/uploads/2013/04/dithering-methods.pdf https://brucebcampbell.wordpress.com/wp-content/uploads/2013...

OnlyMortal 2y ago

This just reminded me of the “secret” bitmap of the dev team hidden in the OS. I recall using Macsbug to show it.

joezydeco 2y ago
G 41D89A (Mac SE)
- OnlyMortal 2y ago
  I recall opening a Plus and seeing engraved signatures.

deleted 2y ago

[deleted]

GuB-42 2y ago

Just curious, does the website name "Beyond Loom" has anything to do with the video game "Loom" (1990)?