Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!uunet!munnari.oz.au!bruce!labtam!graeme
From: graeme@labtam.labtam.oz (Graeme Gill)
Newsgroups: comp.graphics
Subject: Re: Color quantization ideas: To histogram or not to histogram, comments?
Keywords: graphics quantization
Message-ID: <10480@labtam.labtam.oz>
Date: 2 May 91 02:54:59 GMT
References: <606@lysator.liu.se>
Distribution: comp
Organization: Labtam Australia Pty. Ltd., Melbourne, Australia
Lines: 51

In article <606@lysator.liu.se>, zap@lysator.liu.se (Zap Andersson) writes:
> I have always, always, always wondered one thing:
> 
> * Is there ANY sane reason whatsoever, when trying to quantize a 24 bit
>   image to an 8 bit image, to make a histogram?
> 
> As I see it, the fact that a certain color is used MORE OFTEN than another,
> has NOTHING whatsoever to do with if it should be found in the palette or
> not.


	Unfortunately it is difficult to make a computer program see a picture
the way a human sees it. It is only a human judgment that a spaceship on a
background is the most important object in a scene. Not having the ability
to program an "AI" module into a 24 to 8 bit quantizer, it is necessary to
fall back on other means of assessing the importance of objects in a scene - 
like their relative popularity. Sometimes this produces poor results.
	The suggestion I have is that if you want to be able to get good
results on all scenes, then you need a means of telling the quantizer what parts
of a picture are of high interest, and what areas are of low interest. - ie.
put a human in the loop to asses the importance of objects within a picture
(after all, the desired result is to please someone looking at the picture).
	This feature could be added to something like  rlequan (The variance
based 24 to 8 bit quantiser in the URT toolkit) by making it understand comments
inserted into the source file of the form:

area_of_interest=x,y,w,h,m
	
where x and y are the integer co-ordinates of the bottom left corner of the
area of interest, w and h are the width and height of the rectangular
area of interest, and m is the floating point multiplier. (Note that
the URT toolkit uses a co-ordinate system with 0,0 being at the bottom
left). Comments can be added and deleted with rleaddcom, and examined with
rlehdr. rlequant would need to be hacked to recognize the comments and
scale the stats. of the pixels falling within the area by the multiplier m.
This way you could force the quantizer to allocate more colour maps to the
area of interest, and "fine tune" the result to your taste. The advantage
of having this info as comments in the source file is that the 8 bit file
can be re-created automatically. I haven't got around to trying this idea
out yet.

	The main reason that most quantizer pre-quantize the 24 bit image to
15 bits is so that they can build the histogram in a 2^15 table. One can keep
full 24 bit precision by using a different data structure (ie. a linked list),
but this can use a lot of memory, and can be rather slow in accumulating the
statistics on input and in locating the nearest colours on output. I have
written a quantizer that maintains full 24 bit precision throughout, and it
does not add a great deal to the picture quality. 

	Graeme Gill
	Labtam Australia