Path: utzoo!attcan!uunet!nih-csl!lhc!ncifcrf!haven!purdue!bu.edu!rpi!zaphod.mps.ohio-state.edu!sdd.hp.com!ucsd!nosc!lobster!gag
From: gag@lobster.NOSC.Mil (Gary A. Gilbreath)
Newsgroups: comp.graphics
Subject: Octree vs. Median Cut Color Quantization
Keywords: quantization, octree, median cut
Message-ID: <579@lobster.NOSC.Mil>
Date: 24 Oct 90 17:20:11 GMT
Organization: Naval Ocean Systems Center, San Diego
Lines: 24


Has anybody else out there implemented the octree quantization algorithm
described in _Graphics Gems_, "A Simple Method for Color Quantization: Octree
Quantization", by Gervautz and Purgathofer?  It's advantages over Heckbert's
median cut are that it takes up less memory, runs faster and has about the
same image quality.  My experience is that it runs slower and the image
quality is slightly poorer than median cut.  It seems to assign more
weight to those pixels encountered first in the image than those found later.
This makes the top of the image look pretty good, but tends to posterize the
bottom.  Median cut seems to quantize evenly over the whole image.  As far
as speed goes, the octree method seems to be about 2 to 4 times slower than
median cut (depending on which method is chosen for reducing the octree).
Maybe this is just my particular implementation.  Also, the color table
typically has a few empty entries, perhaps not unexpected considering the
nature of the algorithm.

Has anybody else out there had similar/different experiences?  Is there
some way to spread the posterization evenly or speed the algorithm up?

Thanks,

Gary Gilbreath, Naval Ocean Systems Center, San Diego, CA
Internet: gag@manta.nosc.mil
uucp: {ihnp4,akgua,decvax,dcdwest,ucbvax}!sdcsvax!nosc!gag