pngquant

pngquant uses modified version of Median Cut quantization algorithm and additional techniques to mitigate deficiencies of Median Cut.

Instead of splitting boxes with largest volume or number of colors, boxes are selected to minimize variance from their median value.

Histogram is built with addition of a basic perception model, which gives less weight to noisy areas of the image.

To improve color further, histogram is adjusted in a process similar to gradient descent (Median Cut is repeated many times with more weight on poorly represented colors).

Finally, colors are corrected using Voronoi iteration (K-means), which guarantees locally optimal palette.

pngquant works in premultiplied alpha color space to give less weight to transparent colors.

When remapping, error diffusion is applied only to areas where several neighboring pixels quantize to the same value, and which are not edges. This avoids adding noise to areas which have high visual quality without dithering.