Path: utzoo!attcan!uunet!ginosko!gem.mps.ohio-state.edu!apple!well!pokey
From: pokey@well.UUCP (Jef Poskanzer)
Newsgroups: comp.graphics
Subject: Re: help with quick color map search + FIX for ppmquant
Message-ID: <14222@well.UUCP>
Date: 22 Oct 89 17:19:42 GMT
References: <67563@tut.cis.ohio-state.edu>
Reply-To: Jef Poskanzer <pokey@well.sf.ca.us>
Organization: Paratheo-Anametamystikhood Of Eris Esoteric, Ada Lovelace Cabal
Lines: 28

In the referenced message, rosenbl@cis.ohio-state.edu (Robert Rosenblum) wrote:
}I'm writing an application which involves taking a given rgb value and
}finding the color in the color map which is closest.  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.

Someone else already mentioned Heckbert's paper - that's a good reference.
In the PBM+ package, I used a different, quite simple technique: a hash
table.  The first time I encounter a given color, I do the linear search
you use, but after that the color is in the hash table and I find the
proper mapping instantly.  The worst-case performance of this method is
somewhat worse than what you're doing now, since in theory every pixel
in the image could have a different value, but the performance on typical
images is quite good.

By the way, for those of you who are trying to use ppmquant, you might
want to increase the hash table size defined in libppm3.c.  Apparently
I made it smaller for testing purposes and forgot to make it large
again before the beta release.  Just switch the commenting on the
two definitions.
---
Jef

    Jef Poskanzer  pokey@well.sf.ca.us  {ucbvax, apple, hplabs}!well!pokey
  "Reality must take precedence over public relations, for nature cannot be
                          fooled." -- R. P. Feynman