New fast quantizer for PIL

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

New fast quantizer for PIL

Oliver Tonnhofer-4
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  -  [hidden email]
http://mail.python.org/mailman/listinfo/image-sig
Reply | Threaded
Open this post in threaded view
|

Re: New fast quantizer for PIL

Oliver Tonnhofer-4
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  -  [hidden email]
> http://mail.python.org/mailman/listinfo/image-sig

_______________________________________________
Image-SIG maillist  -  [hidden email]
http://mail.python.org/mailman/listinfo/image-sig
Reply | Threaded
Open this post in threaded view
|

PNG8 with full transparency (Was: New fast quantizer for PIL)

Oliver Tonnhofer-4
Hi all,

I improved the new color quantizer a bit more and it now supports quantizing of RGBA images. I modified the PNGImagePlugin to store the full transparency information of paletted images. It works really great and there is no performance loss compared to RGB quantization.

I've updated the test images at http://bogosoft.com/misc/pil-octree-tests/

Again, the code is available at http://bitbucket.org/olt/pil-117-octree
There is a fork that also contains my other patch 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-a2.tar.gz

The usage:

>>> img = Image.open('transparent.png')
>>> img = img.quantize(256, Image.FASTOCTREE)
>>> img.save('transparent8.png', transparency='full')

Regards,
Oliver

On 02.07.2010, at 14:54, Oliver Tonnhofer wrote:

> 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  -  [hidden email]
>> http://mail.python.org/mailman/listinfo/image-sig
>
> _______________________________________________
> Image-SIG maillist  -  [hidden email]
> http://mail.python.org/mailman/listinfo/image-sig

_______________________________________________
Image-SIG maillist  -  [hidden email]
http://mail.python.org/mailman/listinfo/image-sig