Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!usc!snorkelwacker!bloom-beacon!eru!luth!sunic!mcsun!unido!konech!pest
From: pest@konech.UUCP (Wolfgang Pest)
Newsgroups: comp.graphics
Subject: Re: Converting color values to color indices
Summary: References to this problem
Keywords: color index inverse table algorithm request
Message-ID: <973@konech.UUCP>
Date: 1 Dec 89 08:52:23 GMT
References: <248@dlogics.UUCP>
Organization: Develop. Dept. Kontron Eching, Germany
Lines: 22

In article <248@dlogics.UUCP>, kam@dlogics.UUCP (Kevin Mitchell) writes:
> 
> Right now, I'm comparing each color position in the inverse table to
> each color in the color lookup table to find the index I want. Since I'm
> using the Pythagorean Theorem to find the distance, I'm executing thousands
> of multiplications and it takes a long time (Macintosh Plus; 68000 at 8Mhz).
> 
> 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 am not very experienced in computer graphics, but your problem is
mentionned briefly in the latest issue of a German computer journal,
called "c't" (issue 12/89 pp. 166-178) and I hope I have understood that
article. 
There the author describes the method you are using in detail and mentions
that it could be made more efficient by "pre-sorting the color lookup table
in sub-cubes of the RGB space and determining the nearest neighbours".
(Instead of comparing with _each_ entry of the color index table, he means
obviously).

As a reference, he gives "Heckbert, P.: Color Image Quantization for Frame
Buffer Display, SIGRAPH 1982 Proceedings, pp. 297-307"


Brought to you by Super Global Mega Corp .com