pokey@well.UUCP (Jef Poskanzer) (10/23/89)
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
poe@hpfcdq.HP.COM (Daryl Poe) (10/26/89)
> Is there is a more efficient way to find the closest color in a color > map? Any help would be greatly appreciated. Take a look at "An Algorithm for Finding Nearest Neighbors" by Friedman, Baskett, and Shushtek, IEEE Transactions on Computers, October, 1975, p. 1000. The algorithm they suggest is to sort the points along one of the dimensions. Given a target point, search outward from that target along your sorted dimension (say, blue) until the distance along that dimension is greater than the distance (in all three dimensions) to the nearest color found so far. Obviously, any colors further away from your target in that dimension are also going to be further away when all three dimensions are considered, so you can end your search at that point. The overhead of this algorithm is fairly small and it works well with small data sets (like the 16-4096 entries in a typical colormap). Daryl Poe Hewlett-Packard, Graphics Technology Division