Use pngquant (libimagequant) for quantization to palette

Questions and postings pertaining to the development of ImageMagick, feature enhancements, and ImageMagick internals. ImageMagick source code and algorithms are discussed here. Usage questions which are too arcane for the normal user list should also be posted here.
Post Reply
pornel
Posts: 8
Joined: 2013-05-03T14:13:02-07:00
Authentication code: 6789

Use pngquant (libimagequant) for quantization to palette

Post by 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: Image pngquant: Image

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: Image pngquant: Image

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.
User avatar
magick
Site Admin
Posts: 11064
Joined: 2003-05-31T11:32:55-07:00

Re: Use pngquant (libimagequant) for quantization to palette

Post by 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
Posts: 8
Joined: 2013-05-03T14:13:02-07:00
Authentication code: 6789

Re: Use pngquant (libimagequant) for quantization to palette

Post by pornel »

bump.

Unfortunately I wasn't able to get filters to compile, but maybe somebody else would like to give it a try?
User avatar
Marsu42
Posts: 75
Joined: 2014-06-12T03:17:45-07:00
Authentication code: 6789
Location: Berlin

Re: Use pngquant (libimagequant) for quantization to palette

Post by 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
Posts: 12159
Joined: 2010-01-23T23:01:33-07:00
Authentication code: 1151
Location: England, UK

Re: Use pngquant (libimagequant) for quantization to palette

Post by 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.
snibgo's IM pages: im.snibgo.com
pornel
Posts: 8
Joined: 2013-05-03T14:13:02-07:00
Authentication code: 6789

Re: Use pngquant (libimagequant) for quantization to palette

Post by 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
Posts: 23
Joined: 2013-02-18T10:12:03-07:00
Authentication code: 6789

Re: Use pngquant (libimagequant) for quantization to palette

Post by 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
Posts: 8
Joined: 2013-05-03T14:13:02-07:00
Authentication code: 6789

Re: Use pngquant (libimagequant) for quantization to palette

Post by 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
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: Use pngquant (libimagequant) for quantization to palette

Post by fmw42 »

pornel
Posts: 8
Joined: 2013-05-03T14:13:02-07:00
Authentication code: 6789

Re: Use pngquant (libimagequant) for quantization to palette

Post by 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.
User avatar
glennrp
Posts: 1147
Joined: 2006-04-01T08:16:32-07:00
Location: Maryland 39.26.30N 76.16.01W

Re: Use pngquant (libimagequant) for quantization to palette

Post by 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
Posts: 8
Joined: 2013-05-03T14:13:02-07:00
Authentication code: 6789

Re: Use pngquant (libimagequant) for quantization to palette

Post by 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?
User avatar
glennrp
Posts: 1147
Joined: 2006-04-01T08:16:32-07:00
Location: Maryland 39.26.30N 76.16.01W

Re: Use pngquant (libimagequant) for quantization to palette

Post by 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
Posts: 10
Joined: 2017-05-08T11:12:41-07:00
Authentication code: 1151

Re: Use pngquant (libimagequant) for quantization to palette

Post by FrontierDK »

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