From jevans@.ucalgary.ca Mon Sep 19 15:15:12 1988
Path: leah!bingvaxu!sunybcs!rutgers!apple!voder!pyramid!prls!philabs!micomvax!ncc!alberta!calgary!!jevans
From: jevans@.ucalgary.ca (David Jevans)
Newsgroups: comp.graphics
Subject: Re: Color Pallet Mapping?
Summary: color cube compression for sun3
Message-ID: <7@cs-spool.calgary.UUCP>
Date: 19 Sep 88 19:15:12 GMT
References: <101880001@hpcvlx.HP.COM> <522@epicb.UUCP>
Sender: news@calgary.UUCP
Lines: 53
Posted: Mon Sep 19 15:15:12 1988

In article <522@epicb.UUCP>, david@epicb.UUCP (David P. Cook) writes:
> 
>   Now, for your RGB to Color Map question...
> 
>   This is more tough, since in the Targa 16, there are 32,768 colors possible.
>   There are many approaches, three of which I will list here:
> 
>   Method #1:  Conversion of the Color Map to a RGB simulation map
>   Methods #2 and #3:  Color selection
>      The drawback to method #1 is that it uses the entire color space. You
>      may, on the other hand, have an image which is primarily one or two
>      tones (ie... perhaps the image is basically reds and tans, with no
>      greens or blues).  In this case, much of your VDA map is wasted.  For
>      this solution, you can COMPRESS the original image.  Two methods exist:
> 
>      Popularity reduction:
> ...
>      Color Cube Compression:
	ref: Proceedings of SIGGRAPH '85
	Used a median cut algorithm to determine "best" colors.
> ...

Another reference for color cube compression is
 Proceedings of Computer Graphics International '88 (Geneva).
I'm not sure of the author 'cuz the ref is in my office and i'm posting
from home.  Anyway, the proceedings are published every year in book format
by Springer-Verlag.  This year one (or both?) of the Thallmanns (sp?) from
Montreal was (were) the editor(s).

Essentially the author of the CGI paper used an octree data-structure which
is allowed to have N root nodes (N = # of entries in your colortable).
As colors are read in from a file they are inserted into the octree.  When
there are more than N colors the deepest nodes are merged into one color
which is their weighted average.  After the image has been read once the
colortable is made (traverse the octree).  The image is then re-read and
each pixel's colortable value is found by indexing into the octree in
the same manner as it was created.  This results is fairly fast display
time once the octree has been built since the colortable doesn't have
to be searched for the nearest color to a given pixel's color.

I implemented this algorithm one afternoon for my 8bit-color sun3/60.  I wanted
to be able to display my 24bit images without having to walk over to the
the graphics lab and using an iris.  If anyone is interested in the
program you can try to email me and I'll send it.  A friend ported it
to an 8bit iris last week, so that is probably available too.

The format that they use is a simple non-run-length-encoded rgb binary
format with the xsize and ysize at the front of the file.  It shouldn't
take anyone more than a few minutes to convert to a different format.

Dave Jevans (jevans@cpsc.UCalgary.CA   <- probably incorrect?!?)

"I've been waiting for a guide to come and take me by the hand."