Path: utzoo!utgpu!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!rutgers!njin!princeton!notecnirp!cek From: cek@notecnirp.Princeton.EDU (Craig Kolb) Newsgroups: comp.graphics Subject: Re: Palette Optimization Summary: Variance-based Quantization Message-ID: <13962@princeton.Princeton.EDU> Date: 3 Jan 89 16:06:04 GMT References: <12745@cup.portal.com> <571@epicb.UUCP> <9871@gryphon.COM> <14231@oberon.USC.EDU> <7170@venera.isi.edu> Sender: news@princeton.Princeton.EDU Reply-To: cek@princeton.edu (Craig Kolb) Organization: Dept. of Computer Science, Princeton University Lines: 24 A number of people at the University of Regina have written a paper that describes a variant of Heckbert's median-cut algorithm. The key difference is that rather than always cutting along the 'longest edge' of a box, one makes cuts along axes at points which minimize the variance of the resulting set of representative colors with respect to the original image. Since color space is discrete, one can find these optimal cut-points by exhaustive search. In the paper, "Variance-based Color Image Quantization For Frame Buffer Display", the authors (Wan, Prusinkiewicz and Wong) compare the compression of two images using a number of algorithms, and show that their scheme is 'better' than median-cut, at least in terms of total quantization error. The paper has been submitted to Graphics Interface for publication. I've implemented this algorithm and the results are quite nice. Drop me a line if you'd be interested in a copy of the code. The program makes use of the Utah-Raster toolkit and has display routines for both the color Sun and Iris workstations. Craig Kolb Yale U. Math Department cek@princeton.edu or craig@lom1.math.yale.edu