From steinmetz!sun.uucp!falk Tue Jul 19 23:32:22 1988
Path: beowulf!steinmetz!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!nosc!ucsd!ucbvax!decwrl!sun!falk
From: falk@sun.uucp (Ed Falk)
Newsgroups: comp.graphics
Subject: Re: Yes, it's another STUPID QUESTION...  ALGORITHM POSTING
Summary: you asked for it, you got it.
Message-ID: <60582@sun.uucp>
Date: 20 Jul 88 03:32:22 GMT
References: <60194@sun.uucp> <1098@eos.UUCP>
Distribution: usa
Organization: Sun Microsystems, Inc. - Mtn View, CA
Lines: 1472

In article <1098@eos.UUCP>, jbm@eos.UUCP (Jeffrey Mulligan) writes:
> From article <60194@sun.uucp>, by falk@sun.uucp (Ed Falk):
> < 
> < If you want to bias this according to human perception, you might try
> < 
> < 	test_distance = ((r[i]-R)*.3)**2 +
> < 			((g[i]-G)*.59)**2 +
> < 			((b[i]-B)*.11)**2 
> < 
> < 	Where .3, .59, .11 are the NTSC weights.
> 
> You might try it, but why?  Those weights are used to compute luminance.
> What do they have to do with color discrimination?  There are plenty
> of valid formulae around describing color discrimination; wouldn't
> one of them be better than something made up on the spur of the moment?

I don't know.  I assumed that the luminance weights were a reasonable
indicator of how sensitive the eye is to those colors.  It follows that
those numbers could also be used as an indicator of the relative
"importance" of the three colors.  If you know a better formula, let
me know.

At any rate, this was just hypothetical, I use equal weights in this
implementation.

> Use of the medain cut algorithm does not dictate any particular
> color space or metric.  Although Heckbert probably used RGB space,
> you could easily transform to a more perceptually based space
> prior to doing the clustering.

It's even more general than that.  No reason that median cut needs to
be used for colors (or even graphics) at all, or even for the number of
dimensions to be three.  As an example, you might perform a ray-tracing
and stop when you have the normal vector at every pixel (assume no
anti-aliasing).  You could then feed the normal vectors into the median cut
algorithm and get as your output, a table of the 256 most
representitive normals and an 8-bit image consisting of indices into
your "normal-vector table".  Load the image into your frame buffer, let
your application keep a copy of the normal-vector table internally and
load the color table entries according to your light sources and
shading algorithm.  Now you have dynamic lighting and shading on
an arbitrarily complex scene!  I saw this trick done on a Megatek many
years ago (12-bit frame buffer, no median-cut algorithm needed) and it
was beautiful.


[24 bit to 8 bit image code deleted since it was posted separately later]

-- 
		-ed falk, sun microsystems
		 sun!falk, falk@sun.com
terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO.