Use pngquant (libimagequant) for quantization to palette

[pornel]

I've refactored pngquant into a library (libimagequant) that can be embedded in other software (BSD-like license). I'd like to propose incorporating this library into ImageMagick.

Quantization algorithm currently used by ImageMagick posterizes images unnecessarily, doesn't support alpha transparency, and is slower than quantizers of comparable quality (like the 15-bit mediancut from libjpeg).

Comparison with pngquant based on this image:

ImageMagick: pngquant:

Both have essentially the same file size, took about the same time to generate (0.6/0.7s), but pngquant version is visibly less posterized and even had lots colors to spare for semitransparencies of the shadow.

Images above are without dithering, because in this particular case ImageMagick produces malformed image when dithering is on. Another comparison:

ImageMagick: pngquant:

Note that the first image is quite noisy (especially in dark areas) and brightest points on the yellow ball are remapped incorrectly.

So overall I think switch to pngquant's quantization and remapping would be a significant quality improvement without loss of speed or file sizes. pngquant also has fast-and-rough speed setting that is 2.5 to 6 times faster than ImageMagick's current algorithm while still mostly winning in quality.

Would you be interested in adopting the library?

It's written in C99, doesn't have any dependencies, less than 60KB compiled. Optionally supports OpenMP and SSE optimizations. It's successfully integrated with LibGD already.

More info/documentation: http://pngquant.org/lib/ and source.

From what I've gathered by looking at ImageMagick's source code is that currently ImageMagick supports generating palette from arbitrary number of images. The library can do that too, but I haven't added public API for it yet. I will if you're interested.

[magick]

We recommend creating a binding to ImageMagick as an image filter. See http://www.imagemagick.org/script/archi ... hp#filters. Image filters are staging areas for experimental code. With an image filter, users can test the quantization algorithm and provide feedback. Once the bugs are resolved and there is a degree of stability and user acceptance, we will consider including it in the main ImageMagick distribution.

[pornel]

bump.

Unfortunately I wasn't able to get filters to compile, but maybe somebody else would like to give it a try?

[Marsu42]

For the record: As a simple user, I would find it great if this would be incorporated into IM.

Sure most of the time you can run a second command line with pngquant after IM, but getting it "all in one" would be preferable because the file size reduction is unheard of with plain IM png8 output.

[snibgo]

I've described the process of building image "-process" filters into IM on my page http://im.snibgo.com/customim.htm . This is with Cygwin on Windows, but I expect the process is the same for any Unix-like environment.

[pornel]

Bump.

Filters cannot do this. As far as I can tell it's not possible for a filter to emit a tRNS chunk.

Would you consider just integrating pngquant directly?

[canavan]

I'd think the theory was that the PNG coder would be able to write the filter output pixel values 1:1 to a correct PNG file, including emitting a tRNS chunk if necessary. I haven't tried a filter, but using convert to create a TIFF file from a pngquant-ed PNG and converting that TIFF back to PNG results in a (slightly larger) PNG file with tRNS and intact alpha channel. Apparently this also works if a TrueColor+Alpha TIFF is used as input. I would conclude that a libimagequant filter should work.

[pornel]

Could you tell me which function call can I use to write tRNS chunk?

The docs point to analyze.c example, but that's read-only filter, so I don't know how to write PNG chunks.

http://www.imagemagick.org/source/analyze.c

[fmw42]

For use in command line see http://www.imagemagick.org/Usage/formats/#png_write

[pornel]

No, I did not mean command line at all, but a C API.

In the beginning of the tread I've been told to use the C filter API to integrate pngquant, but I suspect that's been a misunderstanding, because from what I've seen in the documentation and examples the filters API is technically incapable of providing such integration, because it works with a higher-level pixel-based image abstraction, and I don't see any C function call in the filter API that would allow a filter to define a tRNS chunk for IM to use when writing to a PNG file, which is essential for libimagequant to do useful work.

[glennrp]

I have been considering adding this to the PNG encoder. However, I think the filter solution would be better.

The filter wouldn't have to know anything about the PNG tRNS chunk. ImageMagick's PNG encoder will write an indexed PNG with a tRNS chunk when it receives an image with 256 or fewer colors, including the background color. That doesn't work with the example firefox image presented at the beginning of this thread because it has 256 colors, none of which is the default background color, so there are 257 colors in total and "convert" writes a PNG32.

If you define the background color to be one of the opaque colors present in the image, or use the "-define png:exclude-chunks=bkgd" option, then IM will write an indexed PNG with tRNS chunk.

So a filter would work, so long as it reduced the colors to 255 instead of 256.

[pornel]

The filter wouldn't have to know anything about the PNG tRNS chunk. ImageMagick's PNG encoder will write an indexed PNG with a tRNS chunk when it receives an image with 256 or fewer colors, including the background color.

This is the limitation I would like to avoid. As far as I understand to make ImageMagick write PNG8 I would have to remove alpha semitransparency and make the transparency as primitive as in GIF.

But the key feature of libimagequant is ability to have up to 256 semitransparent colors, not just one transparent and 255 fully opaque.

So a filter would work, so long as it reduced the colors to 255 instead of 256.

Would it be able to write a 255-color image with a shadow with hundred levels of semi-transparency?

[glennrp]

The total RGBA combinations plus 1 for background has to be 256 or fewer, for IM to write an indexed PNG.

The transparency only has to be binary if you call for a "PNG8" which by our definition has GIF-style transparency. There's no special name for an indexed PNG with semitransparency. It's just a "PNG".

[FrontierDK]

Wow, any chance of a stand-alone libimagequant which will Work in classic ASP / VB?