Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!decwrl!csus.edu!ucdavis!csusac!unify!Unify.com!raveling
From: raveling@Unify.com (Paul Raveling)
Newsgroups: comp.graphics
Subject: Re: Color quantization and histograms
Message-ID: <1991May3.151259@Unify.com>
Date: 3 May 91 22:12:59 GMT
References: <1991May01.144028.19021@ariel.unm.edu>
Sender: news@Unify.Com (news admin)
Reply-To: raveling@Unify.com (Paul Raveling)
Distribution: usa
Organization: Unify Corporation, Sacramento, CA, USA
Lines: 39

In article <1991May01.144028.19021@ariel.unm.edu>,
swilson@natasha.unm.edu (Scott R. Wilson) writes:

	[about color quantization]
> 
> The complaint was primarily about having to use a histogram to obtain
> the color information, and having to truncate the data to 5
bits/pixel/color
> in order to *get* the histogram. The next complaint is that the 5 bit
truncation
> is not enough precision.  Both of these are valid, especially the
5-bit one.
> ...
> 2. Replace the direct indexed histogram step with one that builds a
>    hash-indexed *sparse* histogram data structure out of linked lists,
etc.

	I agree that prequantizing to 5 bits causes modest suffering
	for many images.  In my "new" (1-year-old) algorithm the code
	most nearly equivalent to Heckbert's prequantization & histogram
	building normally uses 6-bit prequantization.  However, a #define
	parameter does allow truncating to 5 bits for the indexed color
	lookup for the sake of anyone with severe memory limits.

	Another variation comes from fact that that the algorithm
	doesn't exactly build a histogram; it builds a frequency-ordered
	queue of colors, and from that builds a threaded tree.  Until
	it has found either all the colors in the image or 256 colors,
	whichever comes first, it keeps some substructure under the
	direct lookup array, plus some duplicate node definitions,
	to completely eliminate prequantization.  If it finds too many
	colors, then it shifts to prequantized lookups only.

	Anyway it seems to work well.


------------------
Paul Raveling
Raveling@Unify.com