From ph@miro.Berkeley.EDU Mon Dec 12 00:49:18 1988
Path: leah!itsgw!nyser!njin!rutgers!gatech!purdue!decwrl!labrea!agate!pasteur!miro.Berkeley.EDU!ph
From: ph@miro.Berkeley.EDU (Paul Heckbert)
Newsgroups: comp.graphics,comp.windows.x
Subject: Re: Luminance from RGB
Message-ID: <8241@pasteur.Berkeley.EDU>
Date: 12 Dec 88 05:49:18 GMT
Sender: news@pasteur.Berkeley.EDU
Reply-To: ph@miro.Berkeley.EDU (Paul Heckbert)
Organization: University of California at Berkeley
Lines: 52

Dale Schumacher (dal@midgard.Midgard.MN.ORG) wrote:
> ...I have only 3-bits per gun (RGB) on the Atari-ST, and want to expand those
> color values to their 8-bit equivalents...  The method I use is to start at
> the MSB of the source and destination values, copy bits from the source
> proceeding toward the LSB, if you reach the end of the source before filling
> the destination, start over at the beginning of the source.
> This works for both imcreasing and decreasing significance (equivalent
> to right-shift for decreasing).  Example: 101 --> 10110110,
> 000->00000000, 111->11111111, etc.  It seems to work for all cases,
> even wierd things like 7-bits -> 13-bits.

Paraphrasing, Dale is convering the 3 bit number abc, where each of a, b,
and c are 0 or 1, into the 8 bit number abcabcab.

This is very close to the "correct" formula, but you've found a somewhat
roundabout way to compute it.  The formula you want will map black (000)
to black (00000000) and white (111) to white (11111111) and map everything
inbetween linearly.  In other words, you want to multiply by 255/7.
Your formula actually multiplies by 255.9375/7.

You can prove this to yourself by thinking of the 3-bit bit string x=abc as
a representation for the binary fraction x'=.abc (e.g. bit string 010
represents the number .010) and 8-bit bit string y=abcabcab is a code for
binary y'=.abcabcab .  But replicating the bits is equivalent to a
multiplication: y'=x'*1.001001001.  Putting our formulas together, we
have x'=x/8, y'=y/256, and 1.001001001=4095/3584,
so y/x = (1/8)*(4095/(512*7))*256 = 4095/(7*16) = 255.9375/7 .

It's good to step back from the low-level bits once in a while and think
about what these pixel values mean in the real world.

----

Dale also asked about algorithms for selecting the 16 colors out of a
palette of 512 that best represent an image.  This is called "color image
quantization".  I wrote about it in a paper:

    Paul S. Heckbert,
    "Color Image Quantization for Frame Buffer Display",
    Computer Graphics (SIGGRAPH '82 Proceedings),
    vol. 16, no. 3, July 1982, pp. 297-307

see also the improved algorithm in:

    S. J. Wan, K. M. Wong, P. Prusinkiewicz,
    "An Algorithm for Multidimensional Data Clustering",
    ACM Trans. on Mathematical Software,
    vol. 14, no. 2, June 1988, 153-162

Paul Heckbert, CS grad student
508-7 Evans Hall, UC Berkeley		UUCP: ucbvax!miro.berkeley.edu!ph
Berkeley, CA 94720			ARPA: ph@miro.berkeley.edu