madd@world.std.com (jim frost) (11/22/89)
hartung@amos.ling.ucsd.edu (Jeff Hartung) writes: >What I REALLY need is a >reference (or even a fragment of C code) for dithering from 256 to 16 colors I posted an X program called xloadimage in comp.sources.x a short while ago (a few days). One of the functions it has is colormap reduction; given a color image with 'n' colors in its colormap, it can reduce the number of colors to an arbitrary 'k'. It was written specifically to handle displaying 8-bit images on 4-bit displays (although it's a general case) and works pretty well. I won't say it's perfect, it isn't, but it's fast and works well enough for viewing images. The idea behind the algorithm is to find the closest two colors and average them together, resulting in one color. Loop until you have fewer colors than you need. The obvious algorithms are all O(n**2) so I did some stuff to reduce it to virtually O(n) and it works quite well given its speed and simplicity. You may have to do some things to reduce its memory usage (I think it currently uses 128k + 3*n bytes where 'n' is the size of the colormap, but the 128k is a table of precalculated squares which you could eliminate without degrading performance too much). Xloadimage does a lot of other simple manipulations (zooming, dithering, brightening, etc) using a fairly portable library that I wrote. This library is mostly independent of X, so you shouldn't have a very hard time getting it to run although I'm not guaranteeing that. If you're interested and can't get it from comp.sources.x, it's available by anonymous ftp from expo.lcs.mit.edu in the contrib directory, files xloadimage.tar.Z and xloadimage.patch02.Z. You'll need a UNIX machine to unpack either the posted version or the ftp'able version, of course, and you should try to do the patch (although it only affects the zoom code). If this isn't possible, I can email you selected portions of the code which would be apropos (the whole package is about 150k of source). Hope this is helpful, jim frost software tool & die madd@std.com
lynnand@aardvark.austin.ibm.com (/60000;Austin) (11/22/89)
Color Dithering is a complex subject with no single solution. Check technical books on graphics and image processing for various methods and algorithms. The ACM Graphics SIG publications have caried articles as well. I will check my books at home and post some specific references next week.