Path: utzoo!attcan!utgpu!utstat!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!bloom-beacon!usc!venera.isi.edu!raveling
From: raveling@venera.isi.edu (Paul Raveling)
Newsgroups: comp.graphics
Subject: Re: Color Quantization (was Re: Discussion of Computer Pornography)
Message-ID: <8478@venera.isi.edu>
Date: 24 May 89 16:56:12 GMT
References: <4706@uoregon.uoregon.edu> <310@celit.UUCP>
Reply-To: raveling@venera.isi.edu (Paul Raveling)
Organization: Information Sciences Institute, Univ. of So. California
Lines: 52

In article <310@celit.UUCP> billd@celerity (Bill Davidson) writes:
>
>...  If a color is way out away from all the other colors, it will
>get sucked into the other colors.  This resulted in very purple sky ...
>	[+ discussion of median cut alternatives]

	This is why the version of my tree-based quantization algorithm
	that a number of people have picked up recently has a weighting
	function.  Briefly, the algorithm classifies pixels into an
	octree, reduces the tree until it represents the desired number
	of colors, and assigns final colors by reclassifying pixels
	in the reduced tree.

	The weighting is in reduction, where it uses a combination
	of frequency and depth in the tree to decide which nodes to
	eliminate.  The effect is to retain breadth near in the tree
	at relatively shallow levels.  The result is better retention
	of colors than with median cut -- i.e., if the original image
	has n colors at k-bit resolution (k=3 seems to be a meaningful
	resolution), and the output image has m colors at this resolution,
	this algorithm produce images with a higher value of m/n than
	median cut does.

	The result is substantially better images than with median cut
	in some cases, but using an octree produces trouble in the form
	of visible banding on others.  The conceptually biggest problem
	is that it enforces a fixed cubic partitioning of RGB space, and
	the tree structure sometimes isolates neighboring sets of colors
	in branches that reduction doesn't recognize as neighbors.

	So, in spare time (images are no longer part of my job) I'm
	experimenting with variations to get around this and other
	problems.  Recently I've tried binary trees & different ways
	to build somewhat octree-like non-octrees.  Many of these
	variants perform better in different ways, but I haven't
	yet gotten one to perform better in ALL ways.


	Another technique that appears to work well is to weight
	selection based on pixel intensity.  I found that some
	images, such as Lenna, were producing a large number of
	colors that were too dark to distinguish.  Adding a crude
	adjustment for intensity makes it possible to maximize
	resolution for lighter colors, where humans perceive more
	detail.  This is a correction that would improve perceived
	image quality but would produce "more quantization error"
	according to the usual mean squared error measure.


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