a dithering rabbithole explored by the Packbats,
For reasons, we wanted to play with color quantization and dithering, and from friends we found out that ImageMagick, a command line image editor, has color quantization/dither tools. (Thank you, Anthony Thyssen, for the extensive documentation!) Then we came up with a very silly idea: what if we took a given starting image and, using our limited knowledge of dither algorithms and complete lack of knowledge of image size optimization, tried to make the coolest versions we could under 32 KiB? Setting the limit to be filesize and not raster resolution means that every algorithm is going to create some compromise between size and fidelity … so maybe Floyd-Steinberg produces a clearer result at the same resolution, but how much smaller does it have to be to fit in the size limit?
The first thing you should know is that, when you're aiming for 32 KiB, metadata can take up an extremely meaningful amount of space. If you know a good way to wipe metadata without janking up the colors, tell us; we settled for some BS that didn't jank up the colors much.
(Also, there's often private information in that metadata. You don't want to accidentally post your home GPS coordinates or something.)
(Addendum, : Shoutout to Snibgo – we don't know who you are, but you told someone on Github to do magick inputfile -colorspace RGB -colorspace sRGB outputfile and that does erase the ICC profile that we didn't know how to erase. You still have to delete the other metadata somehow, but the colors should be fine.)
The second thing you should know is that dithering doesn't resize very well. You frequently end up getting a Moiré pattern, a checkerboard of lighter and darker regions, which can be a serious impediment to legibility if the original image doesn't have great contrast. This isn't as big an issue if you're making an image for a website, but if you're posting on social media or you're making illustrations for a PDF, it's a consideration.
Third, we meant it about the "complete lack of knowledge of image size optimization". If WebP has some superpower for limited-palette images that we don't know about, then sorry, Google, we don't care. But if you care and know, let us know so people reading this guide have the accurate info. We have a fedi account @Packbat@indiepocalypse.social, a Yahoo! Mail address with the name umpelty, a Dreamwidth account at packbat, and a itch.io account at packbat, and probably some others. Don't … don't message us on Twitter or Facebook, those accounts are dead and we will never see your message.
(Update, : Found the ImageMagick page about WebP - you just insert -define webp:lossless=true into your string. It's usually better than PNG and GIF - about 3-8% for this image, but we tested a different image and it was like 25% better on that one so we have no idea.)
That said, fourth, we're picking the best images to share, and by best I mean largest image resolution at the fixed filesize for the modifications chosen. The formats we tested were GIF, JPEG, PNG, WebP, JPEG XL, and (just because ImageMagick supports it) QOI, and, well, all that testing really just boils down to this:
Finally: for this exercise, we're using a cool photo our dad took that's 5712 by 4284 pixels and almost 9 MiB … but every image we post in this post will be 32 KiB or less. That does mean – spoiler alert – two WebP images; if you can't read those, here's a replacement .png of the color one and here's one of the grayscale one. Being lossless, they are much bigger than 32 KiB, but being lossless, they accurately convey the contents of the WebPs.
Right – let's get started.
magick noexif.png -resize 8.2% full.webp
If what we care about is image quality and filesize, the baseline for comparison will be the high-fidelity option. We're going to be trying a lot of artistic choices here, and for all of them we should wonder, "is this in some way better than just uploading a normal photo?" And as you will see, none of our dithering choices are better in terms of fidelity.
Regarding other file formats: JPEG XL hits the filesize limit at 6.3%, regular old JPEG at 5.0%, GIF at 4% with color banding because its palette maxes out at 256 unique colors and reducing the colorspace saves bytes, and the other lossless formats sit around 2.5%.
Speaking of reducing the colorspace, 256 is nice, but this whole thing is an exercise in color quantization – do we need 256? How about … eight?
magick noexif.png -resize 9.7% -dither None -colors 8 color8-none.gif
Okay, that's muddy, let's boost that a bit.
magick noexif.png -resize 9.7% -dither None -colors 8 -auto-level color8level-none.gif
What I like about this is the way that, when we gave it enough colors, the math in ImageMagick picked out the most notable colors of the image and made them pop. It being un-dithered gives it an almost cel-shaded effect, but there's enough messiness in the image that it's not that, it's its own thing.
Also, just on a personal note, we really enjoy the added contrastiness we get from the auto-level step. Contrasty images are our jam.
Anyway, fun fact: for this source image…
magick noexif.png -resize 10.3% -dither None -colors 7 -auto-level color7level-none.gif
…you can drop the palette to 7 colors, and get a little bit more intense and cartoony a version of this effect. We're not sure which one we like best – probably 8 colors, but they're both pretty good.
magick noexif.png -resize 7.9% -dither FloydSteinberg -colors 8 -auto-level color8level-fs.gif
magick noexif.png -resize 8.2% -dither FloydSteinberg -colors 7 -auto-level color7level-fs.gif
I think these end up as almost a painterly version of the limited palettes – the dithers acting as blending of colors. I think this might actually bumps the 7-color over the 8-color, despite the increase in red-speckling – the more intense shadows are fun, and now the dress details are recovered.
magick noexif.png -resize 9.4% -dither Riemersma -colors 8 -auto-level color8level-ri.gif
magick noexif.png -resize 9.9% -dither Riemersma -colors 7 -auto-level color7level-ri.gif
Yeah, I think the 7-color is our favorite with dithering.
ImageMagick only supports two error-diffusion dither algorithms, which is a shame (check out Ditherpunk — The article I wish I had about monochrome image dithering if you want to see a whole mess of hand-implemented algorithms), but ImageMagick's two error-diffusion dithers are configured to very different results, which is a treat. Where Floyd-Steinberg tries to smooth over differences with a fine mesh of dots, ImageMagick's version of Riemersma here produces big chunky lumps, which look kinda like the no-dither option but messier and capturing more detail (compare the skirts). It's a fun, dramatic look.
(Addendum, : It also avoids the Moiré effect on scaling, which is useful!)
Anyway, though, there's a lot of dithers we can't use on these custom palettes, and that's because there's a lot of dithers that require specific palettes. In ImageMagick, a lot of dithers are inherently 1-bit, on or off – so either a 1-bit black-and-white image (which we'll get to later) or a one-bit-per-channel image in some colorspace. Could be any colorspace, technically – ImageMagick has a bunch of colorspaces – but we're sticking with RGB because it works and we want to finish this ever.
magick noexif.png -resize 12.7% -dither None -posterize 2 colorp2-none.gif
Now that's dramatic. We did say we like contrasty colors and that's contrasty to the limit. Heck yeah.
Okay, dither time.
magick noexif.png -resize 6.4% -dither FloydSteinberg -remap RGB_3bits_palette_color_test_chart.png colorp2-fs.png
…I mean, that's just the full-color version, but smaller and pixel-y. I guess that's what Floyd-Steinberg is for – capturing the original picture on a low-color-resolution display – but … mmm. We'll leave this at "you're not saving space, but if you like Floyd-Steinberg artifacts, go for it."
Also the RGB_3bits_palette_color_test_chart.png we mention in the text of the example ImageMagick command is the 3-bit RGB test image off Wikimedia Commons. If you want Floyd-Steinberg to dither between a specific set of colors you choose, you have to communicate that somehow, and an easy option is to reference an image containing the correct palette.
(Edit : If you are reading this in the future, an even easier way is to just use -posterize 2 again. This was broken in ImageMagick 7.1.1-25, which we used to write this, but a patch was made for ImageMagick 7.1.1-28.)
And yes, this can be any palette. If you wanna load your image on a CGA monitor for some reason, grab a CGA palette image and go to town.
magick noexif.png -resize x200 -dither FloydSteinberg -remap Cga_palette_color_test_chart.png cga-fs.gif
Or what about PICO-8? We still have that reference image from when we made a cart to show contrast ratios between all the colors, we can slot that in!
magick noexif.png -resize x128 -crop 128x128+21+0 -dither FloydSteinberg -remap PICO-8-color_info_default_plus.png P8-fs.png
Or what about … about … sorry, we're realizing that if we continue down this path we'll never finish the post. Gotta back on topic.
magick noexif.png -resize 8.0% -dither Riemersma -remap RGB_3bits_palette_color_test_chart.png colorp2-ri.gif
Okay, that's still smaller than the full-color version, but look at it! What a chaotic image! What a lumpy mess of approximations! This is awesome!
Okay, it doesn't have to be awesome to you if you don't want it to be, but it's undeniably interesting and I think that's worth highlighting.
magick noexif.png -resize 11.5% -ordered-dither o2x2 colorp2-o2.png
Gonna go out on a limb here and say that color 2x2 ordered dithers are wonderful. Everything seems to be just a little bit glossier in our ioho – it's a real classic distinctive look. And PNG absolutely loves ordered dithers – look how big we could make this! Look how big we can make all of these!
magick noexif.png -resize 11.2% -ordered-dither o3x3 colorp2-o3.png
3x3 is an interesting one! The artifacts are a bit less familiar to our eyes – look at all the tiny circles in the pillar – but it's still pretty clean and the color resolution is noticeably better than 2x2. It's pretty cool.
magick noexif.png -resize 11.5% -ordered-dither o4x4 colorp2-o4.png
magick noexif.png -resize 11.5% -ordered-dither o8x8 colorp2-o8.png
The 4x4 and 8x8 dithers always seem a bit similar to our eyes, except the 8x8 is a trifle less tidy. These are the high-fidelity options among the ordered dithers, almost without color banding, but also a little … dustier? Distinctive, but not quite as pretty to our eyes. You might like them, though!
Now, obviously we've left a lot of color options on the table (and there's one in particular we'll come back to, look forward to that), but if we're talking about dithering, we can't not talk about black-and-white dithers. The concept's a little weird with this image, where the striking colors are a lot of the appeal, but let's continue anyhow. What does this look like in monochrome?
To start, a new benchmark.
magick noexif.png -resize 8.6% -colorspace gray gray.webp
WebP's lead is a little less significant without color information, but it still wound up the most efficient by a fair margin.
That said, it will be nowhere as big as the next picture in this post.
magick noexif.png -resize 18.3% -threshold 50% bw-thresh50.png
This is the biggest picture on the list, and it is a dramatic one!
Now, just to defend our honor for a sec: we didn't just type -threshold 50% and call it a day. We checked a bunch of values and made a judgment call, and you'll have to do so as well.
This is the dead simplest form of dithering, which is to pick a threshold (see?), chop everything below that to black, and chop everything above that to white. It will have exactly the details found at that point in the histogram – with a lower threshold, the gradient on the red shoes becomes clearer, with a higher one, the patterning on the toe of the left white shoe becomes clearer. You find the point where it's too dark and the point where it's too bright and you pick your tradeoff between them. But it's sharp, it's dramatic, it's eye-catching, and you can't beat the filesize. Definitely a good tool for your toolkit.
Right, dithery-dithering time.
For the error-correction dithers in black and white, there's two approaches. The first is to let ImageMagick pick what levels to dither between, then blow up the resultant image to black-and-white.
magick noexif.png -resize 13.9% -colorspace gray -dither FloydSteinberg -colors 2 -normalize bw-fs-norm.png
magick noexif.png -resize 17.1% -colorspace gray -dither Riemersma -colors 2 -normalize bw-ri-norm.png
As you can see, both of these wound up way bigger than the WebP – the sharp clean Floyd-Steinberg and the gooey spattery Riemersma. Really good bold and dramatic choices – the automatic color picker chose its dither thresholds in a way that captured a lot of details, but still heightened the contrast.
The other way is to give them a black and a white palette – we just made an image in KolourPaint that's half and half – and have them preserve the original color levels.
magick noexif.png -resize 11.3% -dither FloydSteinberg -remap BW.png bw-fs.png
When constrained like this, the Floyd-Steinberg is very accurate but we don't find it terribly interesting. Mainly it's just grainy. That's us, though.
magick noexif.png -resize 12.8% -dither Riemersma -remap BW.png bw-ri.png
Riemersma ends up messier than at the optimized grayscale levels, due to dithering a lot more middle grays than before. It's interesting, but … well, messy.
Honestly, this really shows off how powerful it is to dither between thresholds, rather than dither the whole range – when some colors are pushed to white and others to black (as happens with the -colors 2 -normalize process), the contrast within the dither is increased, making a clearer image. We're mainly showing these for comparison to the dithers that are locked to black and white: the ordered dithers.
magick noexif.png -resize 16.7% -colorspace gray -ordered-dither o2x2 bw-o2.png
It's still a very organized look, is a 2x2 ordered dither, but I think it doesn't serve this particular grayscale image well, even if it's still a bit dramatic – it doesn't really capture the gradients that are there. This would probably benefit from more preprocessing before the dither (dithering should always be the last or almost-last step), but, again, we need to draw a line or we'll never finish.
(But seriously, stick -contrast-stretch 11x9% before the -ordered-dither step or something – remove some of that information so the dither can work better on the information you want to preserve. Figure out good percentages for the black point and white point halves, make it more vivid.)
magick noexif.png -resize 16.3% -colorspace gray -ordered-dither o3x3 bw-o3.png
Okay, you know what? We really liked the 2x2 ordered gradient in color, but here in black and white, look at how much better the gradients read in the toes of the red shoes! When all you have is black and white, I think the added color resolution of the 3x3 dither pays big dividends, and at this physical scale I think the patterns in the grid are less distracting.
magick noexif.png -resize 16.6% -colorspace gray -ordered-dither o4x4 bw-o4.png
magick noexif.png -resize 17.0% -colorspace gray -ordered-dither o8x8 bw-o8.png
It's confusing that the 8x8 ordered dither compressed better than the 4x4. For both PNG and GIF, actually. Anyway.
Again, I think the larger image resolution really helps these larger threshold maps come into their own. The color banding on the shoe gradient is very subtle at this point – it mostly just feels like a gradient – and details like chain links and shoelaces are quite clear. Again, it would probably benefit from some preprocessing (-contrast-stretch something), but at this scale the 4x4 and 8x8 dithering work. The 8x8 doesn't even feel as chaotic as it sometimes does. Just solid choices, both.
Before we leave the ordered dithers behind, though, there's a style we skipped in the color section of this post: digital halftones.
magick noexif.png -resize 16.6% -colorspace gray -ordered-dither h4x4a bw-h4a.png
Digital halftoning is inspired by physical halftoning - a method where a grayscale photograph is turned into a grid of dots of varying sizes. In digital halftoning, the dots are stuck on the pixel grid and broken up by details in the underlying image, but it's the same principle: instead of a fine pixel mesh of varying density like the diffused-pixel dithers, you have a coarser mesh of larger dots of varying size.
I think it works well on this image. At this particular size, the dots are subtle but organized, and it doesn't look dusty or messy in the smooth color areas.
magick noexif.png -resize 17.1% -colorspace gray -ordered-dither h4x4o bw-h4o.png
magick noexif.png -resize 15.7% -colorspace gray -ordered-dither h6x6a bw-h6a.png
Three things happen as you make the dot pattern larger in a digital halftone dither. First, the effective resolution for details gets coarser. Second, the color resolution improves rapidly. Third … it starts looking like a newspaper or somethng. If you've looked at printed papers and seen the dots, it's that vibe – and while not strictly realistic, the messiness of the dots in the digital halftone adds to the vibe. It's really neat.
You can go farther – stars, ImageMagick ships with a 16x16 orthogonal halftone dither if you want one – but if you're constrained to 32 KiB you lose the details of the actual image you're processing very rapidly, so we're gonna move on to our last demonstration.
So you remember back in the monochrome 1-bit Floyd-Steinberg/Riemersma bit when we said "how powerful it is to dither between thresholds"? There's a kind of dither which gets talked down a lot, but which in ImageMagick defaults to dithering between thresholds you can tune: random dithering.
magick noexif.png -resize 12.0% -colorspace gray -channel All -random-threshold 30x65% bw-rand3065.png
This is not efficient. It spends a ton of filesize on capturing quite literally random noise, and not very much on capturing the source image. If you do this, it's because you think random noise looks cool.
And in your defense:
magick noexif.png -resize 7.8% -random-threshold 35x60% color-rand3560.png
…it looks pretty cool.
Also you could probably make some sick animated GIFs if you wanted to spend six thousand years doing it. ImageMagick does have animation. You'd just need to render every individual frame and then combine them into a single GIF animation afterwards.
Us? We're done. I think we've shown you enough. Let us know if this was helpful or entertaining.
(Addendum : For comparison, almost all pictures scaled up to the size of the largest.)
Late breaking update: We found out we missed some things. Have some extended dithering techniques – they're good.
