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
