Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!dewey.soe.berkeley.edu!oster
From: oster@dewey.soe.berkeley.edu (David Phillip Oster)
Newsgroups: comp.graphics
Subject: Re: Converting color values to color indices
Keywords: color index inverse table algorithm request
Message-ID: <32886@ucbvax.BERKELEY.EDU>
Date: 30 Nov 89 05:32:16 GMT
References: <248@dlogics.UUCP>
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: oster@dewey.soe.berkeley.edu.UUCP (David Phillip Oster)
Organization: School of Education, UC-Berkeley
Lines: 31

In article <248@dlogics.UUCP> kam@dlogics.UUCP (Kevin Mitchell) writes:
>I'm using a Floyd-Steinburg dither to reduce the number of colors in
>an image. To find the colors I need quickly, I'm using an inverse table-
>a three-dimensional array indexed by color value yielding the color index
>to put into the image.

>I must be missing something obvious, since I know that there are fast 
>implementations out there; such as in Apple's color QuickDraw software.

I do this in the BarneyScan Mac color scanner driver. There is no need to
do multiplies to compute the pythagorean distance between the color you've
got and the closest color in the color table. Consider:
If you use a color cube that is a power of two on a side, and is uniformly
distributed in color space, you can just use the appropriate number of
high order bits of red, blue, and green to index directly to the closest
color. You can avoid round off by adding an appropriate offset to your
original color before you start. The Floyd-Steinberg dithering algorithm
will propogate the error between the color you want and the color you get,
so the next pixels will pick up the slack.

If your color aren't uniformly distributed, you can still use a uniform
color cube to get you to the head of a list of colors that are close to
the one you've got, then you can binary search the list to find the actual
one.  This is still alot better than binary searching the entire color
cube.

> The mac is a detour in the inevitable march of mediocre computers.
> drs@bnlux0.bnl.gov (David R. Stampf)
--- David Phillip Oster          -master of the ad hoc odd hack. 
Arpa: oster@dewey.soe.berkeley.edu 
Uucp: {uwvax,decvax}!ucbvax!oster%dewey.soe.berkeley.edu 


Brought to you by Super Global Mega Corp .com