Web Wanking Workshop: CSS and reducing the size of PNGs

[xiphmont]

My 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
Reduced PNG: 23399 bytes
...or 1/8th the size.

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.

Whither the Gimp?

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.

Patches

As promised, here are the patches to add -borderpreserve and the ppmfilter util to the current stable version of netpbm (10.26.52).

Comments

Re: Another angle

[exoticorn.myopenid.com (from livejournal.com)]

Ok, some early tweaking produces this: http://img162.imageshack.us/img162/7593/machines64avgerrornr3.png

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.