Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!venera.isi.edu!raveling
From: raveling@isi.edu (Paul Raveling)
Newsgroups: comp.graphics
Subject: New color quantization algorithm
Message-ID: <11258@venera.isi.edu>
Date: 6 Jan 90 00:41:26 GMT
Sender: news@venera.isi.edu
Reply-To: raveling@isi.edu (Paul Raveling)
Organization: USC Information Sciences Institute
Lines: 65


	In answering an email message I just somewhat announced
	a new color quantization algorithm whose prototype first
	worked without bugs a few days ago.  It appears to be
	about an order of magnitude faster than my old algorithm
	and it produces (I think) better perceived image fidelity.

	Here are some notes from the email reply... 

> How does it differ from Paul's algorithm?  	[Paul is Paul Heckbert]

	His algorithm prequantizes pixels to some precision, 5 bits per
	RGB component suggested, and builds a histogram of these prequantized
	colors.  Then he uses a median cut algorithm to partition
	RGB space into boxes (parellelopipeds) containing [ideally] equal
	numbers of colors.

	My new algorithm begins by doing something like Heckbert's
	prequantization, but the array it builds contains pointers to
	structures that will be manipulated in various ways.  First
	they're threaded into a queue in descending order by color
	frequency.  Next, a tree synthesis phase puts them into a
	threaded tree until the number of nodes matches the desired
	number of colors.

	The synthesis algorithm is a key component, and builds the
	tree breadth-first.  To oversimplify a bit, for each original
	color it finds the nearest color in the tree.  That's a relatively
	short process because of the tree structure.  If the subject color
	is within a given "capture radius" of the nearest color, the subject
	color is forwarded to a thread to be reprocessed deeper in the tree.
	The nearest color will become the subject node's parent, so its identity
	is saved immediately.  If the nearest color is outside the current
	capture radius, the subject color becomes a new sibling among its
	parent's offspring.  As each node is added to the tree, it's also
	appended to a thread that enables convenient scanning of the entire
	tree or of any given level.

	Capture radius begins at 255 so that the tree's root node is the
	most frequent color.  Capture radius is divided by 2 for each successively
	deeper level in the tree.  Since nodes are added to each level in
	descending order by frequency, it represents clusters of colors
	at increasing resolution as the tree grows deeper and favors locating
	these clusters at the most frequent colors.  The "capture radius"
	logic assures that low frequency colors can be retained, and serves
	the same sort of function as the median cut's box-splitting while
	(hopefully) getting better association between individual colors
	and clusters.

	Distance computation is important.  It uses a lot of table lookups
	both for speed and for versatility in changing the distance function.
	The best distance function I've tried is NOT purely Euclidean distance
	in RGB space; it's
		sqrt ((|R1**2 - R2**2| + |G1**2 - G2**2| + |B1**2 - B2**2|)/ 3 )
	so that distance is partly dependent on luminance.  Using fixed-point values
	to represent color components in [0,1], this produces relatively small
	distances for bright colors and relatively large distances for dark
	colors.  Combined with a constant capture radius in the tree synthesis
	phase, this produces higher resolution for bright colors and lower
	resolution for dark colors.


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