Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!sun-barr!cs.utexas.edu!uunet!cbmvax!mitchell
From: mitchell@cbmvax.UUCP (Fred Mitchell - QA)
Newsgroups: comp.graphics
Subject: Re: How to map 24-bit RGB to 256 co
Message-ID: <7772@cbmvax.UUCP>
Date: 29 Aug 89 04:34:53 GMT
References: <2009@uceng.UC.EDU> <5300026@ux1.cso.uiuc.edu>
Reply-To: mitchell@cbmvax.UUCP (Fred Mitchell - QA)
Organization: Commodore Technology, West Chester, PA
Lines: 66

In article <5300026@ux1.cso.uiuc.edu> phil@ux1.cso.uiuc.edu writes:
>
>> 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')
>
>or more!
>
>> Problem 2: is Euclidian distance (at least in RGB color space) a good
>> 	measure of closeness of color ?
>
>I would think so.  Also, two very close colors, with high frequency of
>occurence, could be represented by the SAME color out.  You should examine
>the number of colors clustering around an area (in rgb color space) to see
>if it is tonal information that can be dithered instead, input quantization
>noise, or other legitimate occurences that need to be retained.  I have no
>idea how to do this.

It would also help to know what the source image is. In my case, the source
was a 24-bit ray-traced image. If you are digitizing an actual scene, then
the color quantization problem become alot more acute if one is to
maintain realism. But one can do only so much to make up for the lost
information. Dithering reduces the effective resolution, for example.

>> 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 ...)
>
>When dealing with scanned input images, the number of bins actually used can
>be quite large, and most having only a small frequency.  What out the bin
>bin "way out yonder" (in rgb color space) with a count of 1?  What if there
>are a lot of the WOY bits?

It would seem, when one first thinks of it, that there may be some 
'all-important' color in the scene SOMEWHERE that, even though it may not 
be one of the most used, the scene would 'fall-apart' without it. At first
I thought that might be a possibility, but no, for the following reasons:

1) The loss of the really pertinent information is so great, that that one
   little-used 'key color' would fall by the way-side. Of course, someone might
   be able to diliberatly manufacture an exception, but in most cases, this
   would not be a common occurance.

2) If the source image has such 'gross color variations' that causes the
   destination pallette to fill up early, then again, this little-used
   'key color' would be drowned in all the commotion. 

In any case, to round this up, in doing color quantization from a very large
pallette to a very small one, one must consider the destination colors
one has, how much dithering it would require to match the original and at 
what expense of resolution, what information is really worth keeping, and
whether a theoritically-correct color transformation is really worth the
extra overhead, especially if it will make little difference in the
destination image. As well as what type of source image you are working
with in the first place (e.g. real vs. synthetic) and how important it would
be to preserve the color variation to maintain realism and to what expense in
terms of CPU time and loss of resolution, etc.
-- 

                                   |*******************************************|
	-Compliments of	       /// |* All thoughts and comments are soley     *|
	 Fred Mitchell	   \\\///  |* thoses of The Author and has nothing to *|
			    \XX/   |* do with Commodore-Amiga.		      *|
   Software QA - Commodore-Amiga   |*******************************************|