aec@unccvax.uncc.edu (Eddie Crocker) (10/19/90)
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
p554mve@mpirbn.mpifr-bonn.mpg.de (Michael van Elst) (10/22/90)
In article <2866@unccvax.uncc.edu> aec@unccvax.uncc.edu (Eddie Crocker) writes: >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. Hello, I'd like to know sth about a related topic. I have a set of (RGB) colors that I want to approximate through a smaller color lookup table. Currently, I use a variation of a 2D closest pair algorithm to find the color pair with the smallest distance. I average this pair, thereby eliminating one color, and loop until the set fits into the lookup table. Is there anything better (maybe a true 3D closest pair algorithm) ? I'm using color distances in RGB space which isn't a good model for visual differences. I'd appreciate any hints for a better model too. Thanx in advance, -- Michael van Elst UUCP: universe!local-cluster!milky-way!sol!earth!uunet!unido!mpirbn!p554mve Internet: p554mve@mpirbn.mpifr-bonn.mpg.de "A potential Snark may lurk in every tree."
staff@cadlab.sublink.ORG (Alex Martelli) (10/25/90)
p554mve@mpirbn.mpifr-bonn.mpg.de (Michael van Elst) writes: ... >I'd like to know sth about a related topic. I have a set of (RGB) colors >that I want to approximate through a smaller color lookup table. >Currently, I use a variation of a 2D closest pair algorithm to find I'm not sure closest-pair is buying you anything much; you have a clustering problem, and (assuming you DO find a good perceptual-distance model) should solve it by a clustering algorithm. A simple one is K-means clustering; given P[1..NP] vectors to approximate with N[1..NN] "vector-prototypes": 1. randomly (...or better...) chose initial guess for N[1..NN]; 2. build for each N[i] the cluster of those vectors in P[] that are closer to N[i] than to any other N[j] for j<>i; 3. now you have NP clusters of vectors from P[]; for each cluster, take its central-estimator (e.g., average) as new prototype; you have thus refined the previous-guess to a new N[1..NN]; 4. iterate from 2. until some measure of convergence is OK (e.g. how many vectors are changing cluster, or how much better some measure such as sum of squares of distance from each vector to its cluster's prototypes is getting, in the last few iterations). The literature on clustering is vast. A useful keyword to search on for this particular problem is "vector quantization", interesting articles will turn up in surprising places (e.g. speech processing!). -- Alex Martelli - CAD.LAB s.p.a., v. Stalingrado 45, Bologna, Italia Email: (work:) staff@cadlab.sublink.org, (home:) alex@am.sublink.org Phone: (work:) ++39 (51) 371099, (home:) ++39 (51) 250434; Fax: ++39 (51) 366964 (work only; any time of day or night).