Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!uwm.edu!zaphod.mps.ohio-state.edu!unix.cis.pitt.edu!brutus.cs.uiuc.edu!apple!sun-barr!newstop!sun!falk
From: falk@sun.Eng.Sun.COM (Ed Falk)
Newsgroups: comp.graphics
Subject: Re: Optimal palette selection for dither?
Message-ID: <132001@sun.Eng.Sun.COM>
Date: 18 Feb 90 01:23:45 GMT
References: <10675@primitive.ADS.COM> <9231@pixar.UUCP>
Distribution: na
Organization: Sun Microsystems, Inc. - Mtn View, CA
Lines: 32

In article <9231@pixar.UUCP>, mccoy@pixar.UUCP (Daniel McCoy) writes:
> In article <SPENCER.90Jan30042240@spline.eecs.umich.edu> spencer@eecs.umich.edu (Spencer W. Thomas) writes:
> > ...  We concluded that if you were going to do some sort of
> >error-propagation dither (e.g. Floyd-Steinberg), that you might want
> >to make sure to pick representative colors that spanned the convex
> >hull of your actual colors.  This way your error propagation would
> >never diverge.
> 
> You would have to know the maximum possible propagated error and expand 
> the convex hull by that much to insure that the error never diverges.  
> (You could control it by clamping.)
> Even then there can still be large gaps inside of the convex hull where
> the error can get noticable.
> An "optimal" pallete is hard to define, you remove error from one place
> and it squirts out somewhere else.

Ain't it the truth.

I've toyed with one variation on the median cut algorithm: instead
of assigning one color to represent a color cell, assign one color
for each corner of the cell.  That would handle the problem quite
nicely, but you would only have 1/8 as many cells.

A variation on this is in my own median-cut implementation.  I assign
a 5x5x5 color cube before I start computing cells.  This ensures that
error-propagation will never diverge.

-- 
	-ed falk, sun microsystems, sun!falk, falk@corp.sun.com

  "If you wrapped yourself in the flag like George Bush does, you'd
  be worried about flag-burning too"