[HN Gopher] Atkinson Dithering (2021)
___________________________________________________________________
Atkinson Dithering (2021)
Author : jdblair
Score : 171 points
Date : 2024-06-20 15:18 UTC (7 hours ago)
(HTM) web link (beyondloom.com)
(TXT) w3m dump (beyondloom.com)
| NelsonMinar wrote:
| 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 wrote:
| I assume those 10 and 12 bit codecs do it on playback, it's
| just that free video services bit-starve the encoders
| zamadatix wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| Definitely! The better ones have really high resolution,
| which compliments this dither technique perfectly.
| doublesocket wrote:
| 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 wrote:
| It's still used every day in low-DPI label printing where
| dithering and pixel alignment are very important.
| Tommix11 wrote:
| Also in the retro computer demo scene is dithering very
| important. I've seen some outrageously great dithering on C64
| demo art.
| makapuf wrote:
| Also everywhere you want smooth gradients on any
| application. Go search gradient rendering without banding
| by example. Dithering will almost certainly be mentioned.
| dahart wrote:
| 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 wrote:
| I've definitely seen color banding on video playback across
| multiple streaming services. Dithering would've been super
| helpful in resolving that.
| quietbritishjim wrote:
| 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 wrote:
| 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.
| Sesse__ wrote:
| You can dither the decoded data to the output display,
| though (assuming you either are in a float codec, or a
| 10-bit or higher). It won't solve all problems, but it's
| not completely unheard of either (e.g. I believe JPEG-XL
| does it on encode).
| prewett wrote:
| 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
| dvh wrote:
| Chrome uses dithering for canvas gradients, or any other
| operations really. Firefox looks much worse without it.
| JKCalhoun wrote:
| 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 wrote:
| I fell in love with the display of Playdate
| (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 wrote:
| 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 wrote:
| 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
| JKCalhoun wrote:
| 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.
| LocalH wrote:
| I remember the original splash screen ;)
| kibwen wrote:
| Dithering can still be a striking aesthetic choice. Low Tech
| Magazine is my go-to example: 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 wrote:
| See also the video game _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.tigs
| ource.com/index.php?topic=40832.msg136374...).
| magicalhippo wrote:
| 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 wrote:
| > 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 wrote:
| 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.
| thih9 wrote:
| Their core goal is, paraphrasing, helping design a
| sustainable society[1]. Reducing the whole world's energy
| use is aligned with that - more than reducing load on a
| single server.
|
| That being said, I doubt the post processing adds much in
| this case.
|
| [1]: "Low-tech Magazine questions the belief in
| technological progress and highlights the potential of past
| knowledge and technologies when it comes to designing a
| sustainable society" -
| https://www.patreon.com/lowtechmagazine/about
| makapuf wrote:
| Decoding a black and white compressed image using a two color
| palette is essentially free. You have to paint a bit to a
| color, might as well choose #ff00ff instead of #111111 for
| "black"
| calebm wrote:
| Lichtenstein would agree.
| xattt wrote:
| Dithered content stands out because it's an outlier in a world
| of smooth gradients. We'd be clamouring for the opposite if
| everything was dithered.
| omoikane wrote:
| Unfortunately, if the browser window were not at the right
| size, some of those dithered images will be scaled with visible
| moire patterns. If they wanted a dithered look that works at
| different resolutions, it might have been better to serve
| grayscale images and filter them on the client side.
| mjcohen wrote:
| Thanks. Low Tech Magazine is fascinating.
| moribvndvs wrote:
| 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
| antirez wrote:
| Floyd-Steinberg looks a lot better IMHO.
| KerrAvon wrote:
| Results will vary by image; I'm not sure the single comparison
| in TFA is the best possible source for comparison.
| londons_explore wrote:
| 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 wrote:
| 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 wrote:
| Or cut to the chase and use sortition, which will provide
| statistically correct representation with out even needing a
| vote
| dahart wrote:
| 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). 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?
| crazygringo wrote:
| That's basically proportional representation with added steps:
|
| https://en.wikipedia.org/wiki/Proportional_representation
|
| It's extremely common in Europe, and there are a lot of
| different precise methods for it. But the point is exactly what
| you're describing -- every vote has an impact.
|
| I've always been baffled that not only has the idea never taken
| off in the US, virtually nobody except political scientists
| seems to be even aware of it.
| bryanthompson wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| It doesn't just prevent you from having to make two passes,
| it prevents you from having to make potentially infinite
| passes!
| DonHopkins wrote:
| 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
|
| "Serpentine! Serpentine!!!"
| feverzsj wrote:
| 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 wrote:
| More on dithering: https://surma.dev/things/ditherpunk/
| m12k wrote:
| Also, here's an example of another 3D dithering technique,
| inspired by Obra Dinn:
| https://mastodon.gamedev.place/@runevision/11050883717334359...
| DonHopkins wrote:
| 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
|
| 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 (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
|
| >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.
| rikroots wrote:
| I still have that Ditherpunk article bookmarked! I leaned on
| its insights heavily when I was building the dither (reduce
| palette) filter[1] for my canvas library.
|
| "Return of the Obra Dinn" looks fantastic. I keep meaning to
| purchase/play that game but the intention keeps slipping down
| my ToDo list while I'm distracted.
|
| [1] Demo on CodePen (will ask to use your device's camera) -
| https://codepen.io/kaliedarik/pen/OJOaOZz
| leni536 wrote:
| 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 wrote:
| This PHD thesis is the best technical coverage of dither science
| that I've seen:
|
| 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 wrote:
| 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
|
| [1]: https://github.com/JohnDDuncanIII/messagefaces
|
| [2]: https://www.dairiki.org/xface/
| WoodenChair wrote:
| 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/...
| mungoman2 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| leni536 wrote:
| > 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
| crazygringo wrote:
| In my experience it's been the exact opposite -- back in the
| "old days" most programmers simply didn't know about
| linearized space, which is why even Adobe Photoshop does
| plenty of incorrect calculations that way. And because there
| wasn't any internet, there was nobody to tell you otherwise.
|
| These days you can at least find references to it when you
| look things up.
| pornel wrote:
| With a caveat that when dithering in color, you need both:
| linear RGB for diffusion/color blending, and a perceptual color
| space for palette search. Distance in sRGB is more closely
| aligned with perception of color than linearized RGB.
| tiffanyh wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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), adding them
| together, and doing a right shift by 4. Atkinson is just adding
| without multiplication, then doing a right shift by 3. On the
| original Macintosh's Motorola 68000, I could see Atkinson being
| more than twice as fast.
| lukko wrote:
| 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/
| tiffanyh wrote:
| More example (and algorithms) can be found here:
|
| https://brucebcampbell.wordpress.com/wp-content/uploads/2013...
| OnlyMortal wrote:
| This just reminded me of the "secret" bitmap of the dev team
| hidden in the OS.
|
| I recall using Macsbug to show it.
| joezydeco wrote:
| G 41D89A (Mac SE)
___________________________________________________________________
(page generated 2024-06-20 23:00 UTC)