[Image-SIG] New fast quantizer for PIL

[Oliver Tonnhofer]

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 at python.org
> http://mail.python.org/mailman/listinfo/image-sig