Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84 / ST 1.0; site saber.UUCP
Path: utzoo!watmath!clyde!bonnie!akgua!whuxlm!harpo!decvax!decwrl!sun!idi!saber!skinner
From: skinner@saber.UUCP (Robert Skinner)
Newsgroups: net.graphics
Subject: Re: Allocation of color map
Message-ID: <1637@saber.UUCP>
Date: Mon, 10-Jun-85 13:37:01 EDT
Article-I.D.: saber.1637
Posted: Mon Jun 10 13:37:01 1985
Date-Received: Wed, 12-Jun-85 07:55:30 EDT
References: <12800001@umn-cs.UUCP> <218@rti-sel.UUCP> <1974@watcgl.UUCP>
Organization: Saber Technology, San Jose, CA
Lines: 47

*** REPLACE THIS LINE WITH YOUR MESSAGE ***

> This is a hard problem, I think.  What you really want is to find a set
> of 256 points in RGB space such that when the set of all colours present
> in the image are each mapped to their nearest represented colour,
> the sum of the errors are minimized.  And you probably want to weight
> this sum according to the visibility to the eye of each error.
> I think there was a paper presented at SIGGRAPH a year or two ago that
> dealt with the subject; unfortunately my proceedings are still packed
> somewhere.
>

The paper that Dave is refering to is in the 1982 SIGGRAPH proceedings, page
297, "Color Image Quantization for Frame Buffer Display.  What this amounts
to, it seems, is a two dimensional sort of the color space, with a correction
for colors that are poorly represented.  (i.e. if the image has a little 
blue, but mostly red and green, we don't want to exclude blue from the 
color map entirely as a straight sort would imply.)


> What most people do with 8-bit frame buffers is just allocate 3 bits for
> red, 3 bits for green, and 2 bits for blue.  The colour map is easy
> to build, and encoding the pixels is easy.  If you want the image
> to look realistic, don't forget to include gamma correction when
> building the colour map.

The above method of truncation is easy and accurate for 8 bits, but 
it breaks down quickly if the target frame buffer has only 4 or 3 bits 
(color hardcopy).  The last section of the above article describes a good
dithering algoritm that I have used successfully in reducing 24 bit images
down to 3 bits for a color printer.  The paper uses integer fractions, where
I used floats, and I extended the color error in four directions instead of 
three, but the principle is the same.  To me, the dithering algorithm 
resembles Bresenham's line drawing algorithm extended to two dimensions.

Surprisingly, the dithering method works best for high frequency information
(hair), but tends to show contouring for smooth shades.  Preventing the
contouring is something I'd like to spend some time researching in the future.

One of the images I used this algorithm on while at Seiko Instruments was of
a blonde girl holding a cat.  Seiko gives away lots of hardcopies of this
image at Siggraph and NCGA, so its fairly easy to get a look at the results.
I will also be glad to give any more information to those that want it.

Robert Skinner
Saber Technology, Inc.
San Jose, CA