![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
xiphmontMy current round of web wanking has led me to the minor image conundrums no doubt many other CSS wankers face. I have a layout design using images that are heavily but not completely photographic. I make heavy use of alpha channel along with CSS to do highlight tricks that don't require Javascript, multiple image loads or nastiness in the HTML itself. But I kept finding myself thinking things along the lines of:
"Gee, I wish JPEG had an alpha channel. Oh, well, I'll just suck it up and use really huge PNGs."
"Gee, I wish JPEG didn't make hard edges look like a bowl of legos floating in oatmeal. I guess I'll suck it up and use really huge PNGs."
"Gee, I wish Gimp could convert to indexed mode without making every image look like a schizophrenic Lite-Brite. I guess I have no choice but to suck it up and just keep using the really huge PNGs."
...and in the end the page looks *great*! And requires a few meg download per view! Ow! Ow, ow, ow. Oh, the poor users. Oh the poor uplink.
So how do we get the best of both worlds? The small size of a JPEG with the alpha and line-art deliciousness of PNG?
Step one:
We've all realized at this point that optipng and pngcrush are no longer useful in the modern world. Nothing writes PNGs with suboptimal compression these days. I haven't yet found a PNG in the wild that optipng or pngcrush could further reduce in size.
Step two:
Reducing color depth in a PNG yields big big savings even if the depth is not reduced fully from one native encoding depth to another (say, 8 bits per channel to 4). Reducing from 8 bits per channel to 6 or 5 still dramatically reduces the symbol space of the LZW dictionary. However, reducing color depth has an obvious problem; the example below reduces color depth to an extreme (3 bits per channel) to make the effects of depth reduction immediately obvious.
But there's an easy trick to pull here to mostly or entirely eliminate the banding artifacts caused by the reduction of color depth: ordered dither.
There are two reasons to use an ordered dither, not a random dither like Floyd-Steinberg. First, because the dither is a regular every-other-pixel dither, the low-pass nature of the human visual system renders the regular pattern invisible even down as low as 4 bits per channel on a 75dpi display (and most displays these days are pushing or exceeding 100dpi). Second, the fact that the dither is following an always-every-other-pixel pattern in each color plane means that LZW compresses the ordered dither far more efficiently than a random dither.
Again, the illustration below is a lower extreme (3 bits per channel), well below the point where any technique looks good. The point is that ordered dither at the same bit depth is clearly an improvement over naieve bit depth truncation.
I've only found one tool that hands me an ordered dither ready to go (and by 'ready to go' I mean 'it actually works'. I'm talking to you pngquant, you vile tease). The ppmdither util in NetPBM, used along with pngtopnm and pnmtopng, seems to be the lone util with working ordered dither. But that's fine-- it's fully scriptable and the source is easy to hack. That's good, because we need to make a modification.
Step three:
Download the last image above, zoom in, and look at the edges:
(For the record, the image in the zoom appears to only have a one bit alpha because it's a colormapped image, and Gimp assumes all colormapped images have a one bit alpha. Bad Gimp!)
The dither goes all the way to the edges-- and damages how the image blends into and fits into the images around it in the layout. The dither can result in seams and color shifts that cause background-colored borders to no longer be perfectly background colored.
ppmdither was originally intended to dither images for output to printers or display devices with very low output color depth. Obviously, we're not actually restricted to a very low color depth, we just want to reduce the color depth where possible to reduce encoding size. The solution to our border problem is easy: flood-fill the border back in from the original image after dither. I've added this to ppmdither as -borderpreserve (patches below).
Step four:
Almost there. Although it seems like the dither is alot of 'noise' for the compression to handle, the regular and entirely predictable pattern compresses efficiently. However, real, random high-frequency noise in the original does reduce compression efficiency. The next step is to implement a noise filter, in this case, a new util named ppmfilter. ppmfilter performs soft thresholding on a double-density dual-tree complex 2D wavelet transform of the original and is frighteningly good at removing noise (and optionally textures) while leaving edges completely untouched. Like wirth ppmdither, I've implemented a -borderpreserve option to eliminate any possibility of slight alterations to the edges of the image.
The filter setting has a useful range of approximately 0.5 == unnoticable to 10 == airbrush city. For my website, I'm using a setting of 2. Like with JPEG, the more you're willing to lose, the smaller the file gets.
In conclusion:
# reduce alpha channel to 3 bits, but keep the range 0,255 pngtopnm -alpha random.png | pnmdepthquant 7 | pnmdepthquant 255 > alpha.pnm # apply light filtering to image, preserve the border pngtopnm random.png | ppmfilter -filter 1 -border > filtered.pnm # dither with weighted colorspace resolution, preserve the border ppmdither -border -dim 1 -red 8 -green 10 -blue 6 filtered.pnm > dithered.pnm # merge alpha and dithered image back into a PNG pnmtopng -compression 9 -alpha alpha.pnm dithered.pnm > random-reduced.png
Original PNG: 180454 bytes
Again, this example is extreme and operating well below the 'sweet spot'. In practice, a colordepth reduction to approximately 4.5 to 5 bits (-red 24 -green 32 -blue 16) and a filter setting of 1.0 produces results nearly indistinguishable when the nose is mere inches from the screen, and yields PNGs about 1/3 the size of the original.
Note that you can, eg in GIMP, simply convert a PNG to an indexed/colormapped mode, which similarly reduces the color space and image size. However, it will also reduce the alpha channel to single-bit and is very limited in the colormaps it will allow if it allows any colormap control at all. Here's another example that illustrates the problem (a larger colorcube than 'shades of beige' drives the point home):
Original image:
Converted to 'indexed' in The Gimp using 'Web optimized palette':
Depth reduction / filtering by the technique described here:
Not only does the technique described here look better, the file is smaller than the one produced by the Gimp.
Reduced PNG: 23399 bytes
...or 1/8th the size.
Whither the Gimp?
Patches
As promised,
here are the patches to add -borderpreserve and the ppmfilter util
to the current stable version of netpbm (10.26.52).
Huh, a NetPBM bug in 'stable' 10.26.52
Date: 2008-09-10 09:12 am (UTC)Huh, I just noticed in that last image (machines-reduced.png) that Firefox is displaying the alpha as one bit. It isn't. The image is using a transparent tRNS palette (ImageMagick and netpbm confirm it's there). It's working properly in the other images... I wonder what the bug is...
Update: Apparently there was a straight up logic bug in this version of pnmtopng. Newer netpbm releases (and newer releases of the original pnm2png, from which the netpbm version was forked) all work properly. I'll get that added to the patch file i'm offering above.
BTW, Gimp can't see it because Gimp can't support more than one bit alpha in *any* colormapped image.
Re: Huh, a NetPBM bug in 'stable' 10.26.52
Date: 2008-09-10 11:44 am (UTC)no subject
Date: 2008-09-10 02:48 pm (UTC)I found this fascinating, and have bookmarked it to look at again next time I do web stuff. But I was a little frustrated by the absence of side-by-side comparisons — enough so that I made my own. As I say there, if I encountered the compressed image in the wild I might be a little put off by the bobbins seeming a tad out of focus. Or I might not notice, and just enjoy it as a picture of a couple of bobbins. I also note there that the original image raises a question in my mind that the compressed image would not: whether the background might be someone's skin. Whether losing that ambiguity is a good thing or a bad thing is of course an artistic decision.
(Also, the code as you presented it seems to either be missing a step or you made a copy/paste mistake. In step 1, the input is
random.pngand the output isalpha.pnm; in step 2 the input is againrandom.png, making it look like step 1 was dropped on the floor.)no subject
Date: 2008-09-10 10:20 pm (UTC)The bobbins aren't out of focus as much as using natural lighting, high ISO and a wide aperture, so the focal plane is thin.
There's no copy-paste mistake. netpbm works with 'pnm' images, which don't have an alpha channel. You need to peel out the alpha and handle it seperately, which is what step 1 is doing. In this particular case, that's not the liability it seems like, as for my purposes I only want to quantize the alpha, not dither it.
(Newer unstable versions of netpbm have added the 'pam' format variant which has alpha. These newer unstable versions do not even compile on my machine, so I'm not even going to bother considering them)
no subject
Date: 2008-09-10 03:42 pm (UTC)no subject
Date: 2008-09-11 03:57 am (UTC)Floyd-Steinberg is also kind of a crappy dither. Sort of amazing Gimp doesn't have Stucki or similar.
no subject
Date: 2008-09-11 04:17 am (UTC)Also, you have to compare size for size here... it's not fair to say the self optimized looks better when it results in an image twice as big. Keep removing colors until you get a comparable size and it looks even worse than web optimized.
...and part of the point is that Floyd Steinberg is the 'bubble sort' of dithers. It's almost never a good choice and it sure isn't here. It's amazing Gimp is so thoroughly limited in general. Gimp can't even correctly *load* some of these images (it strips the alpha channel down to one bit).
Oh, and Gimp can only do colormapping up to 255 colors. In a real application of all this stuff, you want a much finer colorcube than that (even if you don't end up using it all). My preferred cube is using 12,000 colors.
So how come you aren't using Film-Gimp, then?
Date: 2008-09-21 10:50 pm (UTC)eh?
( I don't know that it supports these things,
but it is rigged for Pro use,
unlike The GIMP )
Re: So how come you aren't using Film-Gimp, then?
Date: 2008-09-23 10:11 pm (UTC)[I'm wary of forked projects. When the fork is clearly superior, it tends to replace the parent. If I haven't heard of Film-Gimp, then it must a) have been around a while and isn't actually much of an improvement, b) hasn't been around long and so doesn't yet have a track record or c) it's better but the social aspects of the project are dysfunctional enough it's not viable in the long run...] Any thoughts as to which of a) b) c) or d) (none of the above)? :-)
Re: So how come you aren't using Film-Gimp, then?
Date: 2008-10-27 03:21 am (UTC)Re: So how come you aren't using Film-Gimp, then?
Date: 2008-11-17 06:24 pm (UTC)From the sounds of the FAQ, Film GIMP kinda got lost when GIMP announced GEGL. Then Linux Journal did an article on it, and interest peaked again, and it's now maintained again.
no subject
Date: 2008-09-16 02:10 pm (UTC)About self-optimising palettes, I suspect a good way of improving them is to minimize error^4 instead of the standard MMSE (error^2). That being said, it's probably a lot more computationally intensive.
Still not perfect
Date: 2008-09-20 11:10 pm (UTC)For example, see:
http://img89.imageshack.us/img89/434/randomreducedyp0.png
and
http://img152.imageshack.us/img152/3646/machinesreducedxq1.png
Re: Still not perfect
Date: 2008-09-21 01:28 am (UTC)All the supposedly 'high end' PNG tools that try every possible compression strategy by brute force did not amange to make the files any smaller from what they were as posted.
Re: Still not perfect
Date: 2008-09-21 01:29 am (UTC)Well, look at that!
Date: 2008-09-21 02:51 am (UTC)Neither is producing results identical to the two image you provided above-- as good but different. None of the tools I've tried have gotten the 'same answer', are you using a win32 tool?
Thanks for the tip/spurring me to look again. Another 5-10% for no downside at all is much appreciated.
Re: Well, look at that!
Date: 2008-09-21 03:09 pm (UTC)Re: Well, look at that!
Date: 2008-09-21 06:50 pm (UTC)Another angle
Date: 2008-09-23 09:29 am (UTC)Indexed, 32 colors. Quantized using http://exoticorn.de/exoquant.zip (actually by a slightly improved version, I guess I should publish the latest version somewhere sometime).
The image has less noise overall, but loses some saturation, which probably could be improved in the quantizer.
Re: Another angle
Date: 2008-09-23 10:06 pm (UTC)These are precisely the artifacts I'm using the fixed cube to escape. It doesn't matter if 90% of the image looks a little better, attention is always drawn to that 10% (or 5% or 2%) where the image has obviously fallen apart.
Re: Another angle
Date: 2008-09-23 10:21 pm (UTC)Hrm, looking again and again, perhaps this is still just something tuning can solve... perhaps enforcing a maximum distance between color cells? One extra blue and one extra red would have gone a long way to the optimized palette being a real improvement instead of just a compromise (eg, the grays, etc, obviously look great...)
The real question though is how the two behave in comparison with a few more colors to work with. My technique is unnoticably good starting at about -red 24 -green 32 -blue 16; if optimization can improve on that without cases where it slips up and slags some small color area badly, I'd love to see it.
Re: Another angle
Date: 2008-09-24 07:24 am (UTC)The quantizer was the best I could come up with 4 Years ago and it was better than any other I compared it to back then, but the good thing is that your post has motivated to put some more work into this subject.
I'll probably post some images with more colors later and I'll also update this if I come up with an improvement for the quantizer.
Re: Another angle
Date: 2008-09-24 11:39 am (UTC)This uses 64 instead of 32 colors, but uses the average error instead of the total error of a node to decide which node to split next. It certainly improves the colors in the smaller details, but it doesn't scale that well when increasing the number of colors.
Re: Another angle
Date: 2008-09-24 10:06 pm (UTC)http://img521.imageshack.us/my.php?image=machines48gx8.png
I think there is still some room for improvement in the dithering code, though. Ordered dithering is much easier in a rigid color cube than in a free palette...
I have also uploaded the code to my launchpad account: https://code.launchpad.net/~exoticorn/+junk/exoquant
It includes a small command-line tool to convert any PNG to an indexed PNG, including correctly handled alpha.
(Just ignore the high-quality option the quantizer offers. It just takes *much* longer and the result looks worse... ;)