Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!uakari.primate.wisc.edu!ginosko!uunet!microsoft!kensy
From: kensy@microsoft.UUCP (Ken Sykes)
Newsgroups: comp.graphics
Subject: Re: help with quick color map search
Message-ID: <8134@microsoft.UUCP>
Date: 20 Oct 89 23:00:29 GMT
References: <67563@tut.cis.ohio-state.edu> <8126@microsoft.UUCP>
Reply-To: kensy@microsoft.UUCP (Ken Sykes)
Organization: Microsoft Corp., Redmond WA
Lines: 34

In article <8126@microsoft.UUCP> erichs@microsoft.UUCP (Erich Stehr) writes:
>In article <67563@tut.cis.ohio-state.edu> rosenbl@cis.ohio-state.edu (Robert Rosenblum) writes:
>>My routine
>>performs a linear search through the color map, comparing the
>>"distance" between my rgb value and each color map entry, and the
>>index of the closest color is returned.  However, this technique is
>>very slow.
>
>Are you doing a square root for each iteration?  If you are, that's
>one of your problems.  All you need is the relative "distance" between 
>the colors, and the squares of the distances will have the same relative
>ordering.
>
>Erich Stehr	"The Sorceress' Apprentice"	uunet!microsoft!erichs

The real problem here is searching (I assume) 256 entries for each pixel.
Paul Heckbert used a local search technique in his paper on color
reduction to reduce the list size:

"Color Image Quantization for Frame Buffer Display"
Paul Heckbert
ACM Transactions on Computer Graphics
Vol 16, Number 3 (July 1982)
pp. 297 - 304

Using this technique he was able to reduce the average number of tests 
from 256 to 11 for his test suite of 17 images.  Definitely worth looking
into.

If anyone knows of other methods that are faster or use less memory, please
post!

Sincerely,
   Ken Sykes