Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!pasteur!helios.ee.lbl.gov!ace.ee.lbl.gov!jef From: jef@ace.ee.lbl.gov (Jef Poskanzer) Newsgroups: comp.graphics Subject: Re: 24-bit RGB color to 8-bit color ? Message-ID: <2485@helios.ee.lbl.gov> Date: 25 Apr 89 19:46:42 GMT References: <538@rna.UUCP> <735@rocksanne.UUCP> Sender: usenet@helios.ee.lbl.gov Reply-To: Jef Poskanzer Organization: Paratheo-Anametamystikhood Of Eris Esoteric, Ada Lovelace Cabal Lines: 45 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