Hi all,
I want to give you an update on my new color quantizer.
- I renamed some functions/structs and I've added comments that
describes the algorithm step by step.
- I've added MEDIANCUT, MAXCOVERAGE and FASTOCTREE constants to
Image.py, so you can call img.quantize(256, Image.FASTOCTREE). I used
FASTOCTREE as the name because it is an optimized version and not a
full implementation of the octree algorithm. But I'm open for other
names.
- I fixed a small bug and it now works with all numbers of colors,
from 1 to 256.
- I've added a little test.
- I tested it on Mac OS X 10.5/10.6, Debian 5.0 and Ubuntu 9.10. A
load test showed constant memory usage (so I assume that there is no
leak).
The code is available at http://bitbucket.org/olt/pil-117-octree
There is a new fork that also contains my other path for different ZIP
compress types: http://bitbucket.org/olt/pil-117-fastpng
You can get a source package here:
http://bitbucket.org/olt/pil-117-fastpng/downloads/PIL-1.1.7-fastpng-a1.tar.gz
Regards,
Oliver
On 23.06.2010, at 19:15, Oliver Tonnhofer wrote:
Hi everyone,
I tried to improve the performance of the existing PIL image
quantizer, but the best improvements I got were only 10%. While
investigating how the median cut algorithm works, I came across the
octree color quantization algorithm. I've implemented a variation of
this algorithm and the results are very impressive.
It shows up-to-10x improvements. The algorithm shows good image
quality for rasterized vector images like maps; gradients do not
look as good as with the median cut algorithm.
For our use case[0], serving maps, we get an overall performance
boots of ~x3.5.
Here are some times in ms, best of 5 runs.
rgb adaptive octree octree+rle jpeg
baboon.jpg 122.42 403.77 34.76 20.71 16.35
gradient.png 1.45 6.60 1.01 1.21 0.95
lena.jpg 167.83 325.08 35.53 19.26 13.11
map.png 194.42 305.59 89.83 37.78 34.59
rainbow.png 11.84 229.73 3.83 3.74 3.13
wiki-en.png 7.27 12.45 2.78 1.65 1.81
All times include a convert/quantize and save call.
- rgb is a plain save
- adaptive is `convert('P', palette=ADAPTIVE)`
- octree the new algorithm
- octree+rle the new algorithm with RLE encoding enabled with my
compress_type patch[1]
The images are online [2], and there is also a .tar.gz with all
images to download.
The new quantizer is available at bitbucket[3]. You can use the new
algorithm with `img.convert(256, 2)`.
I'd love to see that in the next PIL release. I will add some more
comments and will clean up the code a bit more, then I'm up for a
code review. Comments are welcomed already, though.
[0] http://osm.omniscale.de/ http://mapproxy.org
[1] http://bitbucket.org/olt/pil-117/changeset/8d4661695edd
[2] http://bogosoft.com/misc/pil-octree-tests/
[3] http://bitbucket.org/olt/pil-117-octree
Regards,
Oliver
_______________________________________________
Image-SIG maillist - Image-SIG@python.org
http://mail.python.org/mailman/listinfo/image-sig
_______________________________________________
Image-SIG maillist - Image-SIG@python.org
http://mail.python.org/mailman/listinfo/image-sig
