Path: utzoo!attcan!uunet!samsung!sol.ctr.columbia.edu!cica!iuvax!rutgers!deejay!gear!cadlab!staff
From: staff@cadlab.sublink.ORG (Alex Martelli)
Newsgroups: comp.graphics
Subject: Re: Nearest Neighbor
Keywords: search color
Message-ID: <299@cadlab.sublink.ORG>
Date: 24 Oct 90 17:41:21 GMT
References: <2866@unccvax.uncc.edu> <1329@mpirbn.mpifr-bonn.mpg.de>
Organization: CAD.LAB, Bologna, Italia
Lines: 32

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).