Thursday, June 19, 2008

Dithering Images for Mobile Devices

I wanted to share some of my experiences creating images on mobile devices. My experience in this respect is specific to Windows Mobile, however this will likely transfer to other types of smarpthones or handheld devices.

First a little background on colors and our ability to perceive them (this is relevant). Scientists believe we're able to distinguish roughly 10 million different colors/shades. So computer scientists have decided that displaying colors from a possible selection of about 16.7 million colors should cover what we can see. This is known as 24 bit color - or TrueColor. In 24 bit color, we use 8 bits of information for Red, 8 for Green and 8 for Blue. 8 Bits gives us a range of values from 0-255. So as you can now work out - we have 256 possible values for each color - and 256x256x256 gives us about 16.7 million.

Now on mobile devices, where memory is limited and screen sizes are small anyways - most modern smartphones use 16 bit color screens instead. On 16 bit devices you get 5 bits for Red, 6 bits for Green and 5 bit for Blue again. So our total number of colors is 32x64x32, which equals 65536. And on a small screen this gives us a pretty good looking image in most cases.

Where you run into trouble is with images that consist mostly or entirely of one color - for example - a gradient that goes from Black to Blue. In this case, we will not be using Red or Green at any point in the image, so we can only differentiate the color by changing the Blue level. With 5 bits we get 32 steps, so if we draw the gradient mentioned above, you will be able to see 32 bands of color and at 16 bit there is no way to get additional shades of Blue.

This is an excellent example of where dithering can be useful. Dithering, simply put, is the act of adding noise or errors. As it relates to images, this noise can be done in such a way that it will fool the eye into thinking there are more colors present.

Now at this point if you'd like further clarification there is a wealth of information online discussing this in further detail: a simple Google search will do nicely.

I would like to focus on the practical aspects. So back to creating mobile software, if you're creating graphics on a desktop machine I would recommend first creating all of your images as 24 bit graphics and then using software to dither to 16 bit. My favourite application for dithering is ACDSee Pro 2.

This will accomplish three things:
1. Your images will be dithered so they will look as good as possible on a 16 bit screen
2. Your images take up less disk space (50% smaller in the case of bitmaps)
3. Your images will load faster as the device isn't required to convert from 24 to 16 bits when displaying (on Windows Mobile devices there is a performance penalty for this)

Now onto the really interesting part, if you create any graphics in code, ie, dynamically generate gradients, controls, etc. You can still dither from 24 bit to 16 bit.
You'll need to create a 24 bit memory buffer, render to the 24 bit buffer using full 24 bit values.

Now you'll create a second 24 bit buffer to copy the dithered version using your algorithm of choice. Once you've copied this over you'll then want to copy the dithered information to a 16 bit buffer. This is easier than it sounds as all of your 24 bit values with be "16 bit friendly".

My favourite dithering algorithm is the standard Floyd-Stienberg and Wikipedia has a great write-up containing pseudo code:
http://en.wikipedia.org/wiki/Floyd-Steinberg_dithering

This code is trivial to convert to C++ but note you'll need to dither each color individually (Red, Green, Blue) and your errors will need to be calculated individually as well.

And of course you'll need to keep an eye on the edges, you can simply indent by one pixel all around when dithering. In "most" cases this won't affect your results.

Please feel free to write if you have any questions or comments.

1 comment:

PsychoMark said...

Thanks for this post! It got me thinking, since I had trouble getting a good looking gradient as well. Instead of trying to write my own dithering routine, I came up with an easy (and free) solution; using the ImageMagick utilities to do most of the dirty work.

I couldn't get it to dither to 16-bits directly, but the 'convert' utility does support applying another image as a color map. I wrote a small utility to output a 256x256 bitmap of all possible color values for 16-bits images (the end result can be found here). Then it's as easy as running:

convert Source.png -remap ColorMap.png Dithered.png

The output is still stored as a 24-bits image (even if you apply this to bitmaps instead of PNGs, ImageMagick will save it as a 24-bits bitmap), but by limiting the actual colors it now looks great on the device.