How do I quantize an image into an arbitrary bitdepth with dithering?

In the games I make, sometimes I need to balance the quality of the images I show with the amount of memory they consume. This is especially true for smartphones and other devices with very tight memory constraints.

Most of the time, images are saved in 24 or 32 bit formats, depending on whether or not there is an alpha channel, and graphic programs make use of the full 32 bits.

In order to reduce the memory used by some images, some times I have to reduce the memory they consume by loading them for example in 16 bits: 5 for red, 6 for green and 5 for blue. However, this process creates banding and other nasty artifacts, as the downsampling process is performed by fitting each pixel separately to the reduced palette.

I'm looking for a process to quantize an image to an arbitrary bitdepth, with dithering. In fact, I am a great fan of pngquant, which palettizes an image down to 256 colors, and applies dithering very intelligently to achieve some very impressive results. The problem is that the quantized colors are still 32 bits, and while this may reduce the size of the file, it won't reduce the amount of memory consumed once the image is loaded.

The tool I'm looking for should optimize on the decompressed size of the image, based on an arbitrary texture format, by reducing the amount of bits used by each pixel, and dithering where necessary to minimize the perceived detail and color loss. It doesn't really matter if the image is actually saved with 32 bits per pixel, as long as when it is loaded as a lower depth image, no further truncations occur. Optimally, this tool would also palettize the image, and minimize both file and uncompressed size.

In other words, how do I turn this image:

into, for example, this dithered R1G1B1 image?

Of course, I want to set the bitdepth myself. Notice that this is irrespective of the file format.

Texture compression is the standard way of doing this; for mobile you'd typically use something like PVRTC, for desktop you'd use DXT/S3TC.

These will give smaller sizes for both the image file on disk and in GPU memory; for example, DXT1 compression (typically used where there is no alpha channel) will be one-eighth the size of the original. GPU hardware is able to sample directly from such a compressed texture, so there's no decompression step required in your program.

Modern versions of OpenGL and GL ES support an additional for of compression via the GL_KHR_texture_compression_astc_hdr and GL_KHR_texture_compression_astc_ldr extensions which allow you to use the same assets for mobile as you use for desktop, but of course you're limiting the target hardware if you use them.

• I'm not asking how to compress an image. I want to know how to intelligently quantize it to a lower bit depth. Actual encoding of the image is outside of the scope of this question. In fact, I'm using a platform that only supports a proprietary file format. Nov 19 '13 at 11:33
• Maybe that should be added to the question to provide the full context then? Nov 19 '13 at 11:44
• No, because it's irrelevant. I'm not talking about encoding or file formats, I'm talking about quantizing and dithering, which applies to all image formats. Nov 19 '13 at 12:09

Basically, the idea is to spread out the error to adjacent pixels. Let's take a grayscale image for simplicity (for RGB you'd just do the same thing for each channel), and say you had an 8-bit pixel value (255 max) of 116 that you want to scale to 4-bits. The closest 4-bit color (15 max) would be 116*15/255, which rounds to 7. This, expanded back to 8-bits would be 7*255/15, or 119. Therefore, your quantized pixel will be slightly brighter than the original by 3 units. To compensate, you spread 3 units out to adjacent pixels (there are several schemes for how the error gets distributed) and subtract them in before the quantization step on those pixels.

Let's take a really simple scheme -- one you'd never use in real life, but is simple enough for now -- and subtract those 3 units to the next pixel to the right. Say that pixel has a value of 67. You'd subtract 3 from 67 to get 64. 64*15/255 rounds to 4, 4*255/15=68, and now you've got an error of 4, which gets subtracted from the next pixel to the right, and so on.

The error accumulation above is a good reason why you usually spread the error to more than one pixel. Floyd–Steinberg dithering adds 7/16 of the error to the pixel to the right, 5/16 of it to the pixel below, 3/16 to the one below and to the left, and 1/16 to the one below and to the right:

     (pixel) 7/16
3/16   5/16  1/16


The general procedure, though, is the same.