Path: utzoo!utgpu!watserv1!watmath!att!mcdchg!laidbak!ism.isc.com!uunet!know!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!uflorida!gatech!mcnc!unccvax!aec
From: aec@unccvax.uncc.edu (Eddie Crocker)
Newsgroups: comp.graphics
Subject: Nearest Neighbor
Keywords: search color
Message-ID: <2866@unccvax.uncc.edu>
Date: 19 Oct 90 15:33:39 GMT
Organization: University of NC at Charlotte
Lines: 27



I am posting this for a friend. Please respond to him directly.
----------------------------------------------------------------------

Earlier, I wrote:

>I am looking for nearest neighbor search methods. Specifically,
>I have 256 color registers and a great many 24 bit colors to match with
>their nearest color register. The best algorithm I've seen so far is
>in Paul Heckbert's Median Cut paper. Only trouble is that it takes a
>long time to set up the data structures. Does anyone know of any
>other methods ?

Unfortunately, I did not state the problem correctly. Here goes again:
I have 256 already quantized color registers. Now I need to map each image
color (pixel) to the nearest existing color register. The most 
straightforward way is to compare the distance from the pixel color to each
color register and save the minimum. A better method is outlined Paul
Heckbert's paper that he calls "Locally Sorted Search". My question is, has
any more efficient methods been used since his 1982 paper ?
 

                Thanks Alot,

                Hal Schwab
                elox!hal@unccvax.uncc.edu