From raveling@vaxb.isi.edu Fri Dec 30 15:12:13 1988
Path: leah!csd4.milw.wisc.edu!mailrus!wasatch!cs.utexas.edu!sm.unisys.com!aero!venera.isi.edu!raveling
From: raveling@vaxb.isi.edu (Paul Raveling)
Newsgroups: comp.graphics
Subject: Re: Palette Optimization
Message-ID: <7170@venera.isi.edu>
Date: 30 Dec 88 20:12:13 GMT
References: <AXco9BF28k-0E78UVK@andrew.cmu.edu> <12745@cup.portal.com> <571@epicb.UUCP> <9871@gryphon.COM> <14231@oberon.USC.EDU>
Sender: news@venera.isi.edu
Reply-To: raveling@vaxb.isi.edu (Paul Raveling)
Organization: USC-Information Sciences Institute
Lines: 55


	We've implemented a color selection algorithm that differs
	a bit from the others I'm familiar with.  I've drafted a
	paper about it, but would frankly prefer to do a
	refined variant of this algorithm before publishing.

	In comparisons with Paul Heckbert's median cut algorithm,
	it produces better results on many images, about the same on a most,
	and does relatively poorly on some.  One virtue is that it's
	tunable -- it's possible to change one key number to change
	its bias toward how to select colors.

	This algorithm operates by classifying an image's colors
	into a tree, much like an octree,  then reducing the tree
	by pruning upward from the leaves, and finally reclassifying
	pixels in the reduced tree.  Classification produces a count
	of the number of pixels which classify into and through each node;
	in fact, each level of the tree can be viewed as a histogram
	at a particular resolution of prequantization (e.g. 1st level
	below root represents colors at 1-bit resolution, 2nd level
	at 2 bits, etc).

	The first cut at reduction chose the least populated nodes
	to prune and averaged their colors into their parent nodes.
	The current rendition uses a weighting factor to bias it
	toward retaining nodes near the top of the tree.  This tends
	to increase the chance that any populated volume of RGB space
	will be represented in the output image, even if only at limited
	resolution.

	If time allows, I hope to do a two-tree variant that would
	let reduction effectively partition RGB space into volumes of
	arbitrary shape (not just cubes or boxes).  It would be slower
	than the current version, but offers hope for better
	color palette optimization.


	One problem with optimizing color palettes is defining what's
	optimal.  In our experience the most useful measure has been
	A/B comparisons by human observers.  This doesn't always correlate
	completely with numerical measures such as mean square distance
	in RGB space.  We tried one experiment with mean square distance
	in a perceptual space, but the results offered no more insight
	than RGB space.  We also defined a "color retention" measure
	that appears to be meaningful but also doesn't fully support
	judgements of human observers.

	If anyone knows of other promising measures of image fidelity
	or image quality (not necessarily identical!), I'd be eager
	to hear of them.


---------------------
Paul Raveling
Raveling@vaxb.isi.edu