Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.csd.uwm.edu!gem.mps.ohio-state.edu!ginosko!brutus.cs.uiuc.edu!usc!bloom-beacon!athena.mit.edu!tuna
From: tuna@athena.mit.edu (Kirk 'UhOh' Johnson)
Newsgroups: comp.graphics
Subject: Re: How to map 24-bit RGB to best EGA/VGA palette?
Keywords: RGB EGA VGA color
Message-ID: <14131@bloom-beacon.MIT.EDU>
Date: 7 Sep 89 20:09:43 GMT
References: <4379@cps3xx.UUCP> <126@vsserv.scri.fsu.edu> <3129@cbnewsm.ATT.COM> <7743@cbmvax.UUCP> <13319@well.UUCP> <586@celit.com> <4862@eos.UUCP> <13381@well.UUCP> <9464@venera.isi.edu> <9473@venera.isi.edu> <71733@yale-celray.yale.UUCP> <4503@cps3xx.UUCP>
Sender: daemon@bloom-beacon.MIT.EDU
Reply-To: tuna@athena.mit.edu (Kirk 'UhOh' Johnson)
Organization: Massachusetts Institute of Technology
Lines: 29

In article <4503@cps3xx.UUCP> flynn@pixel.cps.msu.edu (Patrick J. Flynn) writes:
%
% Here's one possible application of clustering, used as a
% postprocessing step for a poor-quality color quantizer.  I probably
% won't get around to implementing it anytime soon (gotta finish that
% PhD), but maybe someone with spare time would be interested.
%
% Suppose you have a true-color image, and one quick&dirty color
% quantization routine, which produces only tolerable output.  View
% each of the 256 color bins as a cluster center for a 256-cluster
% partitioning of the color space occupied by the image.  Construct a
% (stratified?) sample from the original image by picking up a subset
% of the true-color pixels falling into each bin (so you have a few
% 3-vectors from each of the bins). Then cluster those babies.  See if
% the resultant clustering is an improvement.  If it is, publish it in
% SIGGRAPH and make big bucks. 

although your description is not extremely detailed, it sounds like
you're describing a standard vector-quantization (VQ) algorithm
("Lloyd-Max Quantization", or something like that). _Digital Coding of
Waveforms_ by Jayant and Noll (Prentice Hall) provides a reasonable
description of the algorithm. it is a mechanism for iteratively
improving the "quality" (based on some error criterion) of a
particular quantization (or what you folks are calling "clustering").
it could certainly be applied to the problem at hand; i've used it in
other application domains (speech compression) and had pretty good
luck.

kirk