Path: utzoo!utgpu!watmath!iuvax!uceng!mfinegan
From: mfinegan@uceng.UC.EDU (michael k finegan)
Newsgroups: comp.graphics
Subject: Re: How to map 24-bit RGB to 256 color palette?
Keywords: RGB EGA VGA color requantization
Message-ID: <2009@uceng.UC.EDU>
Date: 25 Aug 89 18:24:15 GMT
References: <3129@cbnewsm.ATT.COM> <7743@cbmvax.UUCP>
Distribution: na
Organization: Univ. of Cincinnati, College of Engg.
Lines: 46

mitchell@cbmvax.UUCP (Fred Mitchell - QA) writes:

>In article <3129@cbnewsm.ATT.COM> schapira@cbnewsm.ATT.COM (alexander.d.schapira) writes:
>>Can anyone shed some *light* on algorithms for mapping 24-bit RGB
>>pixel data (such as found in some image files) into the "best"
>>EGA or VGA palette?

>One way that you can do it is this (...) :

>NOTE: in all of this, treat all your colors as a R-G-B 'vector'.

>Determine your target color range in terms of the 24-bit pallette- that is,
>come up with a color-equivalency table for your target colors (all of them)
>that matches the 24-bit colors as closely as possible.

  ? There are 2^24 possible colors, which 256 will match that range?
  Isn't this a restatement of the problem?
  Are you suggesting starting with a linear requantization ? You could
  use 8 red values, 8 green values, and 4 blue values (8 bits).
  A linear LUT, as above, yields false contouring (depending on image)
  that is objectionable.

>Next, set up a weighted color-range-substitution table that will basically
>map the 24-bit colors onto your target palette. Normally, this will simply
>be the nearest-color match in terms of the RGB representation of your source
>pixel and target color range. Then determine the relative frequency of
>the colors for each color range. Take the highest of these and use them
>for your color palette.

i.e. Calculate the 3-D histogram and use the 256 values with highest frequency.
     Then map original image, pixel by pixel - using closest entry in 256 color
     palette, into the displayable image.

Problem 1: the histogram will be large (up to 262144 'bins')
Problem 2: is Euclidian distance (at least in RGB color space) a good
	measure of closeness of color ?
Problem 3: are the highest frequency colors in the histogram necessarily
        the best to use? (Maybe there should be a minimum distance between
	bins used - (dithering?) image dependent ...)

I am sure all these problems are solved by the fbm package routine 'fbquant()'.
Could others toss out pieces of the algorithms that have been successfully used?


					- Mike Finegan
					  mfinegan@uceng.UC.EDU