dan@rna.UUCP (Dan Ts'o) (04/25/89)
Does anyone have a program to take an image with 24-bit color info and build an 8-bit color map that is "good" (find the 256 color map entries that produce the least error) ? Note that I am not asking for a 24->8 bit dithering program. It would seem that the program I want must internally build a histogram of the occurences of each of the 16M possibilities and then doles each of the 256 available entries according to overall minimum color error (ideally, including psychophysical facts). Would the results be better in HSI space than RGB space ? Whoever builds those nice GIF images (GIF is only 8-bit) must have such a program. Thanks. Cheers, Dan Ts'o 212-570-7671 Dept. Neurobiology dan@rna.rockefeller.edu Rockefeller Univ. ...cmcl2!rna!dan 1230 York Ave. rna!dan@nyu.edu NY, NY 10021 tso@rockefeller.arpa tso@rockvax.bitnet
kirby@bozo.wbst128.xerox.com (Mike Kirby (co-op)) (04/25/89)
> Does anyone have a program to take an image with 24-bit color info >and build an 8-bit color map that is "good" (find the 256 color map entries >that produce the least error) ? > Note that I am not asking for a 24->8 bit dithering program. It would >seem that the program I want must internally build a histogram of the >occurences of each of the 16M possibilities and then doles each of the >256 available entries according to overall minimum color error (ideally, >including psychophysical facts). A program that was supposed to do something like this floated around on the net last year (don't remember who it was from, or what the name of the method was though). Either way, we didn't get very good results from it. The 24->8 conversion tended to leave an enourmous ammount of banding as a result of the loss of the colors. Something like a 24-8 floyd-steinberg error diffusion algorithm, or some other method of dithering or error diffusion would probably have much better results then a histogram derived colormap. If nobody else beats me to it, I'll mail you the program tomorrow night that does what you want. Has anyone else come up with a method of converting 24-8 that provided a steady colormap. This is desired because when doing animation, changing the colormap produces a fair ammount of flicker. At school we experimented with using the colormap generator and that resulted in the problem of banding & flicker. (needless to say we settled on black and white animation only). We never got around to implimenting f/s. Michael Kirby mpk9172@ritvax.bitnet Works... mpk9172%ritcv@cs.rit.ed usually works with a strong tail wind...
raveling@venera.isi.edu (Paul Raveling) (04/25/89)
In article <538@rna.UUCP> dan@rna.UUCP (Dan Ts'o) writes: > > Does anyone have a program to take an image with 24-bit color info >and build an 8-bit color map that is "good" (find the 256 color map entries >that produce the least error) ? There are lots around these days. One is embedded in the imglib library that I just put out for anonymous ftp. If you're looking for good image quality, though, least error doesn't always correlate with best image quality according to human judgement. Another measure with some merit is one I call chromatic retention; it's essentially the ratio of how many colors the output image retains to the number of colors the input image had at some given resolution in RGB space. It appears to correlate best with image quality at about 3-bit resolution per RGB component (i.e., partitioning RGB space into 256 equal cubes). Even though mean squared error and chromatic retention have some relation to perceived quality of quantized images, neither is entirely appropriate. Does anyone know of other promising measures? ---------------- Paul Raveling Raveling@isi.edu
jef@ace.ee.lbl.gov (Jef Poskanzer) (04/26/89)
In message <538@rna.UUCP>, dan@rna.UUCP (Dan Ts'o) wrote: }Does anyone have a program to take an image with 24-bit color info }and build an 8-bit color map that is "good" (find the 256 color map entries }that produce the least error) ? The best algorithm for this that I've seen is Paul Heckbert's "median cut", as described in "Color Image Quantization for Frame Buffer Display", SIGGRAPH '82 Proceedings. An implementation of it is available in the Utah Raster Toolkit, or in my soon-to-be-released color upgrade to PBM. Michael Mauldin's FBM toolkit includes a "modified" version. I am not sure what exactly the modification consists of -- it might just be the slick-ola recursive formulation he used -- but it seems to produce inferior results. (Sorry, Michael, but that's the way it looks to me. If it's just the recursiveness that's different, I strongly recommend you get rid of it. Cute though it is.) }Would the results be better in HSI space than RGB space ? Probably. I haven't gotten around to trying this yet. In message <735@rocksanne.UUCP>, kirby@bozo.UUCP (Mike Kirby (co-op)) wrote: } The 24->8 conversion tended to leave an enourmous ammount }of banding as a result of the loss of the colors. Something like a 24-8 }floyd-steinberg error diffusion algorithm, or some other method of dithering }or error diffusion would probably have much better results then a histogram }derived colormap. Median-cut does produce banding if you use it by itself. This is clear from reading the original paper. And Floyd-Steinberg by itself wouldn't be much good without a good colormap to aim for. What you have to do is construct the colormap with median-cut, and then fit the original image to it using Floyd-Steinberg or the like. All three versions mentioned above do this. }Has anyone else come up with a method of converting 24-8 that provided }a steady colormap. This is desired because when doing animation, }changing the colormap produces a fair ammount of flicker. How about concatenating all your images together into one, doing the 24 to 8 quantization, and then splitting them up again? --- Jef Jef Poskanzer jef@helios.ee.lbl.gov ...well!pokey WCBG: All Elvis, All The Time
phil@ux1.cso.uiuc.edu (04/26/89)
> Whoever builds those nice GIF images (GIF is only 8-bit) must have > such a program. Anyone know why GIF only has up to 8 bits? --phil
mlm@nl.cs.cmu.edu (Michael L. Mauldin) (04/26/89)
In article <735@rocksanne.UUCP>, kirby@bozo.wbst128.xerox.com (Mike Kirby (co-op)) writes: > > Does anyone have a program to take an image with 24-bit color info > >and build an 8-bit color map that is "good" (find the 256 color map entries > >that produce the least error) ? > Something like a 24-8 floyd-steinberg error diffusion algorithm, > or some other method of dithering or error diffusion would probably > have much better results then a histogram derived colormap. The FBM package has an implementation of Heckbert's median cut algorithm to choose colors and Floyd-Steinberg to dither. The routine is called fbquant, and the package is available from: Host: nl.cs.cmu.edu (128.2.222.56) User: anonymous Password: name@site Directory: /usr/mlm/ftp/ Filename: fbm.tar.Z Transfer: 'image' Note: you must 'cd' to /usr/mlm/ftp directly, you cannot access either /usr, or /usr/mlm alone. Don't forget to specify 'image' format transfer. The only 24bit formats it can read are Sun rasterfiles and Amiga Digi-view "raw" files. It can output a variety of formats including Sun, GIF, and Amiga IFF. The software is in the queue for comp.sources.unix, so if you're not in a hurry it'll get to you on its own. Michael L. Mauldin (Fuzzy) School of Computer Science ARPA: Michael.Mauldin@NL.CS.CMU.EDU Carnegie Mellon University Phone: (412) 268-3065 Pittsburgh, PA 15213-3890 --