Dithering: good, bad, and ugly

Attention Macintosh users!

The software available from this page is now obsolete. The folks at Furbo Filters have incorporated the WebScrub algorithm (described below) into their "Web Scrubber" shareware filter, and added a number of nifty enhancements. I recommend that you download the "Webmaster Series" plug-ins. They're working on a Windows version. This is actually what I hoped would happen.

This piece discusses dithering in the context of Web graphics, and introduces the WebScrub image optimization algorithm developed by Todd Fahrner at Verso, realized as freely-downloadable Photoshop plug-ins for Mac and Windows, as well as scripts for the image-processing program DeBabelizer (MacOS only at present). Sample images show the benefits of the process.

Indexed image optimization for the Web

People preparing graphics for the Web must cope with the fact that many users have their displays set to 8-bit (256) color mode, either out of necessity, ignorance, or apathy. 256 colors are generally insufficient for representing rich graphics, unless the palette is customized very carefully for each image or set of similar images. To assure some level of cross-platform color consistency, however, Netscape and Microsoft have settled on a fixed 216-color palette which applies forcibly to all images viewed in 8-bit color. This palette, known as "the color cube," "the Netscape palette," or "the Browser-Safe palette" is familiar to all seasoned Web designers and graphics production specialists:

The Color Cube
The Color Cube.

One means of extending the usefulness of this limited palette is dithering. Dithering refers to the interpolation of unavailable colors by mixing pixels of (usually two) available colors in certain patterns and ratios. When the dither pattern is very tight, with available colors in nearly equal quantities, the resulting appearance can be very good, sometimes nearly indistinguishable from a nondithered image (demonstrated in the DitherBox plug-in promo materials). Dithering becomes objectionable when the pattern is diffuse, and when the palette used is obviously alien to the original image. The color cube's hot, bright, mathematical unnaturalness makes it alien to a great many images.

Note that images may be dithered either at the time they are created (pre-dithering) or on-the-fly as they are viewed, based on the limits of the display. So there are three kinds of dithering:

  1. Pre-dithering to the cube is Bad (with special-case exceptions).
  2. On-the-fly dithering is Good (or at least often the least of evils).
  3. Diffuse dithering, either pre- or on-the-fly, is Ugly (pretty much always).

The Bad and the Ugly
"Bad" is pre-dithered to the cube. It looks Bad no matter the quality of your display. "Ugly" will dither on-the-fly to a sickly measled appearance when viewed in 8-bit color. (Reload if necessary.)

Many designers leap from the frying pan of the Ugly into the fire of the Bad, forcing their images at publish time to the "worst case" 216-color palette. This is unfortunate on two counts:

  1. Image quality suffers, particularly in color-sensitive areas like anti-aliasing, gradients, and in natural-object representation. Those with higher-quality displays see nothing better than those at the low end. While it is good practice to select major color areas from the cube when creating an image, it is a different matter entirely to banish all other colors from the palette when preparing it for the Web. Only the very simplest of line-art graphics tolerate being forced to the cube without significant degradation.
  2. If pre-dithered to mitigate the banding and violence to the colors that would otherwise occur, the images take longer to download and display, because dithering interferes with most image compression methods. (Note: some kinds of dithering compress better than others. Very regular dither patterns tend to compress better than random dither patterns, and can look good for solid fill areas, as DitherBox demonstrates)

Assuming the image in question is destined for GIF or PNG format, a better way is not to force images to an arbitrary foreign palette like the cube, but to reduce colors in the native palette to the least acceptable number, dithering only in exceptional cases as a last resort. This will assure that the images will look as good as possible under all viewing conditions, dithering only if necessary in 8-bit browsing situations. Undithered images will also be more highly compressible than pre-dithered ones.

The most common tool for this operation is Adobe Photoshop, whose adaptive palette reduction unfortunately shifts the colors ever so slightly, causing even colors originally specified from the "safe" cube colors to dither when viewed in a browser at 8-bit. Because the color shift is slight, this dithering is diffuse and Ugly: measles.

Equilibrium's DeBabelizer is superior to Photoshop in this regard: it does not shift colors when reducing the palette. Even with DeBabelizer, however, there is no assurance that colors remaining in the image will not produce Ugly dithering when viewed in 8-bit.

The only way out of this dilemma has been to hand-edit the palette, adjusting colors that might dither objectionably one-at-a-time. This is extremely tedious work. The ideal dithering solution would permit the Good, shun the Bad, and avoid the Ugly, all without tedious manual intervention. We've done it.

The Photoshop Fix

Programmer Philip Gwyn, a gentleman and scholar, has donated his time and skills to turn the original WebScrub DeBabelizer scripts (offered below) into Photoshop plug-ins, for both Mac and Windows. In a nutshell, the plug-in "biases" images toward the web palette by degrees, rather than simply slamming them to it, all or none. Download the goodies:

How to evaluate and use the plug-in

  1. Unstuff/zip the archives and install as you would any other Photoshop plug-in. The filter will appear in a "Xynthetic" sub-menu from Photoshop's Filter menu.
  2. Finish a test image in RGB mode. Try a tough image containing some photographic or other rich color areas as well as type and spot color from the web palette colors.
  3. Save a GIF by whatever means you normally would today for reference. Do your best to balance high visual quality and small file size.
  4. If necessary, revert to the image as it was in step 2. Index to the least acceptable number of colors using the "adaptive" or "custom" method, with no dithering. Do not map to the "Web palette."
  5. Save another GIF for reference. Note that the colors have shifted somewhat from their original RGB values, including the original "Web-safe" colors. This will cause Ugly dithering in flat-color areas when viewed at 8-bit in a browser.
  6. View the indexed image in RGB mode.
  7. Select a postage-stamp sized area, containing the greatest range of colors in the image - anti-aliased areas, gradients, or other transitions. Open WebScrub.
  8. Nudge the slider upwards, as high as possible before image quality suffers unacceptably. Most images can stand a setting of 10-15 before degrading. Settings beyond 50 (Windows version) are not meaningful except as "art."
  9. Apply the filter at the setting from the previous step to the entire image. Note that spot colors originally specified from the web palette have been restored, without sacrificing more subtle color transitions.
  10. Index using "exact" mode.
  11. Save a GIF.
  12. Compare all the GIFs you've saved. Note file sizes and visual quality in a browser at 8-bit and higher color depths. The last will be best all around.

The DeBabelizer Fix

Got DeBabelizer for MacOS? The scripts offered below will apply the WebScrub algorithm to as many images as you like. It's less flexible than the Photoshop plug-in, but requires no manual intervention for batch processing.

  1. Reduce (index) your full-color image to the least acceptable number of colors, without forcing to a generic (Web or system) palette, and avoiding dithering, either in DeBabelizer, Photoshop, or another program.
  2. Open the indexed image in DeBabelizer. Save a copy in a lossless Web image format (GIF or PNG) for reference. The first column of this image table provides examples.
  3. Run the DeBabelizer script "10-grit WebScrub", available here in MacOS binary, plain-text AppleScript, and AppleScript application format. Binary is fastest and best for integrating with other scripts. (After unstuffing, go to DeBabelizer's "Misc: Scripts-Palettes-etc: Import..." menu to import the scripts.)
  4. Save a copy in the format you chose in 2.
  5. Inspect in Web browser(s) at 8-bit and higher color depths, noting any dithering or banding. Compare with the "prescrubbed" reference version you saved in step 2. The scrubbed version should contain little or no Ugly dithering, equal amounts of the Good, and none of the Bad. The second column of the image table shows typical results.
  6. Note the file size compared to the reference version you saved in step 2. Depending on the image, the scrubbed version should be between a few bytes and several kilobytes smaller than the reference version, sometimes up to 20%.
  7. If the image looks good and is smaller than the reference version, you're done. If banding or colorshifts are evident and objectionable, proceed to 8.
  8. Run the DeBabelizer script "5-grit WebScrub", on the original indexed image, available, again, in MacOS binary, plain-text AppleScript, and AppleScript application format.
  9. Repeat steps 4-6. If this procedure does not produce excellent results (smallish, good visual quality when viewed at all depths) then the image should probably be prepared as JPEG, which has compromises of its own....

How the WebScrub algorithm works

The scrubbing operation alters colors that could produce Ugly dithering, while preserving those that can dither satisfactorily (Good dithering). It looks for colors whose red, green, and blue values are within n units of an equimultiple of 51 in 0-255 RGB space. There are 216 steps, corresponding to the 216 cube colors. "Close" values get snapped to the cube; any others are left alone, to dither only as necessary in 8-bit surfing environments. As a bonus, scrubbing tends to regularize images, boosting the effectiveness of lossless compression schemes like GIF.

If the algorithm fails to produce good results for GIFs, your image should probably be a JPEG or higher-depth PNG. The algorithm can help minimize the Ugly in these formats, too: run one of the processes on the full-color (unreduced) image, perform a mild Gaussian blur to take the edge off any banding, and save.

If you have a PhD in psycho-optics, you could optimize the, uh, "grit curves" to match the eye's sensitivity to color shifts through the spectrum. With 10-grit, for instance, sometimes the collapsed spectral range is quite noticeable, while other times the range could be larger. By varying the curve, you'd further optimize visual quality and compressibility. Finally, it might be worth looking at the 216 values that are exactly in-between adjacent cube values. Anything within n units of those would get locked to exact inter-cube values, where they would dither on-the-fly cleanly to a 50% dither (like DitherBox). Similarly, the values at exactly 1/3 the cube-cube span: these would get locked on, to produce clean 3:1 dithers.... So long as you permit enough off-cube intermediates to avoid the chunky cartoon look, you come out ahead.

If you'd like to improve, extend, or prepare other realizations of this stuff, and make your work publicly available, please contact the author Todd Fahrner at Verso.

Disclaimer: Verso does not provide technical support, nor will it assume any liability for problems related to the use of these scripts. Verso places the scripts and underlying algorithms into the public domain.