gag@lobster.NOSC.Mil (Gary A. Gilbreath) (10/25/90)
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!gagphils@athena.mit.edu (Philip R. Thompson) (10/25/90)
Paul Raveling has implemented such a an octree scheme for quantizing. You can find it in his "Img" package available on: venera.isi.edu [~ftp/] pub expo.lcs.mit.edu [~ftp/] contrib This algorithm is a little slower, uses more memory but certainly does the best job of quantizing colors that I have seen, in publicly available quantizers. I have never gotten the dithering to work. but that can easily be switched off and in the case of scanned images usually isn't even desired. Additionally, the author has moved and I'm sure many of use would like to know his where abouts. Philip -- vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv > Philip R. Thompson (phils@athena.mit.edu) < > Computer Resource Laboratory < > Department of Architecture and Urban Planning <
jroth@allvax.enet.dec.com (Jim Roth) (10/25/90)
In article <579@lobster.NOSC.Mil>, gag@lobster.NOSC.Mil (Gary A. Gilbreath) writes... > >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? I haven't tried the Octree, but its main advantage would seem to be simplicity and speed. In my experience, a variance based assignment gives the best results of all. I've certainly never seen different performance in different parts of the image! Median or simple midpoint subdivision of bounding boxes does not work as well as variance minimizing subdivision - there is a noticible difference. - Jim
raveling@unify.com (Paul Raveling) (10/26/90)
In article <1990Oct25.140850.29957@athena.mit.edu>, phils@athena.mit.edu (Philip R. Thompson) writes: > > Paul Raveling has implemented such a an octree scheme for quantizing. > You can find it in his "Img" package available on: > venera.isi.edu [~ftp/] pub > expo.lcs.mit.edu [~ftp/] contrib > This algorithm is a little slower, uses more memory but certainly does > the best job of quantizing colors that I have seen, in publicly > available quantizers. Actually quantization in V1.3 of the Img software set is a different algorithm. It works in part by synthesizing a tree (not an octree); earlier versions of the Img software set had my earlier algorithm that did in fact operate by building a potentially huge octree and pruning it. The new algorithm generally seems to produce (IMHO) better image fidelity, uses less memory, and runs faster than the old one. It includes color dithering, and the quantization algorithm tends to be better at producing a set of colors appropriate for a dithered image. If you're still using the old algorithm, it might be worth picking up a fresh copy of img_1.3.tar.Z and trying the new one. I still haven't had time to run a formal evaluation on it or write it up, but will try to make time for that within the next month or 2. ------------------ Paul Raveling Raveling@Unify.com