Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!dali.cs.montana.edu!ogicse!pdxgate!qiclab!nosun!tessi!bobl
From: bobl@tessi.UUCP (Bob Lewis)
Newsgroups: comp.graphics
Subject: Re: Color quantization ideas: To histogram or not to histogram, comments?
Keywords: graphics quantization
Message-ID: <708@ghidrah.tessi.UUCP>
Date: 10 May 91 16:40:18 GMT
References: <606@lysator.liu.se>
Distribution: comp
Organization: Test Systems Strategies, Beaverton, Oregon
Lines: 34

In article <606@lysator.liu.se> zap@lysator.liu.se (Zap Andersson) writes:
...
>However, the RESULT of my renderer is MUCH better 8 bit images than using
>any 'standard' algorithm. And the main bottleneck (I think) is the histo-
>gram they (all?) use. To create one, you need to pre-quantize to a
>manageable number of colors, most often 5 bits per channel, yielding
>15 bits (32768 colors). BUT 5 BITS PER COLOR IS NOT ENOUGH! If you
>forget the pre-quantization stage, and forget that stupid histogram (that
>only decreases image quality) the result is much better.
>
>What I like to "know" is:
>
>Q: Any comments on the above?

As you suggest, the pre-quantization isn't really necessary.  It's still
possible to use a histogram, though, if you treat the it as a sparse array
with hashed indices derived from the 24-bit (or whatever) RGB values.  This
is, of course, a big virtual memory consumer if the input image has distinct
values in every pixel, but it seems to perform adequately on typical (SPD,
for example) images, which typically only have a few thousand distinct
values.

Your "tiny spaceship and big rainbow" example is a good one.  Median cut
(the way I do it, at least) does ignore spatial coherence.  Perhaps the
algorithm could be enhanced to give additional weight to values of pixels
surrounded by pixels with similar values.  The more similar, the greater the
weight.

>Q: When are these STUPID 8 bit displays gonna disappear for good :-) ?

Probably about the time we can get the 24-bit wall units.  Ah, progress!  B-)

	- Bob Lewis
	  ...!sun!nosun!tessi!bobl