Path: utzoo!attcan!uunet!mcsun!hafro!isgate!krafla!pierre
From: pierre@rhi.hi.is (Kjartan Pierre Emilsson)
Newsgroups: comp.graphics
Subject: Re: How to map 24-bit RGB to 256 co
Message-ID: <1109@krafla.rhi.hi.is>
Date: 1 Sep 89 10:55:39 GMT
References: <7772@cbmvax.UUCP>
Organization: University of Iceland
Lines: 45

A year ago or so, there was a similar discussion and there a method originally
devised by Paul Heckbert was introduced, called Color Cube Compression. 
I don't have the original posting but the method went something like that:

         1.  Determine the bounding box of the picture in RGB space.
		 
		 2.  Divide the box in two along the longest axis, such that
			 approximately half the pixels lie on the left of the 
			 division, and half on the right.
			
		 3.  Repeat the procedure with each sub-box, always dividing
			 along the longest axis of each sub-box, such that half 
			 of the pixels in the box lie to the right and half to
			 the left.
			 
		 4.  When you have obtained 256 boxes, take the average of colours
			 inside each box, so you get one average colour per box.
			 
         5.  Read in the picture and check for each pixel, which box it
			 belongs to, and then assign to that pixel the corresponding
			 colour.

          _____________             _______________
         |        .   :|           |        . |   :| 
		 | .   .    ...|           | .  .     |... |
		 |.  .       . | ------->  |. .       | .  | 
		 |_____________|           |__________|____|

	When I tried implementing this method, I got into trouble when a lot of
	pixels were concentrated on a single colour, because then the subdivision
	was actually trying to split a single colour cell.  One way out of this
	is to make a histogram of the picture, and single out the sharpest peaks
	and allocating them specially.  The reast of the picture can then be
	treated with the CCC algorithm.

									 -Kjartan
									 
P.S: I hope I got this method right.

---------------------------------------------------------------------
Kjartan Pierre Emilsson
Science Institute of the University of Iceland
Dunhaga 3
Reykjavik
Iceland      Net: pierre@krafla.rhi.hi.is