Color quantization tests

Original image
This was the original image. It originates from Animegalleries.
Tests of reducing a sample picture into 16 colours using Imagemagick, Neuquant, Scolorq and Gifsicle.

View this page in 4 colours / 8 colours / 16 colours

Table of contents:

Tests

Imagemagick

The results of Imagemagick's color quantization depend greatly on which colorspace it is performed in; therefore this table lists the quantization results for various colorspaces.

Imagemagick's color reduction algorithm is explained here.

Dithering vs non-dithering in various colorspaces

Colorspace No dithering Dithered (Hilbert-Peano) Original
RGB
XYZ
Grayscale
YCC
YIQ
YUV
LAB
HSL

Ordered dithering methods

RGB and YCC produce very similar results, and one might argue that YCC produces better results than RGB. For this reason, this table includes the results when quantized and dithered using the YCC colorspace. The grayscale colorspace is also shown, because it is interesting to note the differences between the effects of the dithering in different colorspaces.

The first row of the table shows a non-ordered dithering method, Hilbert-Peano, for comparison.
Dithering method Grayscale YCC Original
Hilbert-Peano dithering
o2x2 dithering
o3x3 dithering
o4x4 dithering
o8x8 dithering
h4x4a dithering
h6x6a dithering
h6x6o dithering
checks dithering

Kohonen neural network quantization (Neuquant)

Wikipedia describes Neuquant as follows:
The high quality but slow NeuQuant algorithm reduces images to 256 colors by training a Kohonen neural network "which self-organises through learning to match the distribution of colours in an input image. Taking the position in RGB-space of each neuron gives a high-quality colour map in which adjacent colours are similar." It is particularly advantageous for images with gradients.

Neuquant does not do dithering by itself, but I added a Hilbert-Peano dithering to it by copying the algorithm from Imagemagick. The algorithm is a close variant of the Riemersma dithering algorithm. Also, it is stated that Neuquant is not optimized for working with a small number of colors.
Sampling factor No dithering Dithered (Hilbert-Peano) Original
1
4
7
10
13
16
19
22
25
28
30
It is difficult to find any correlation between the sampling factor and the quality. In 8-color test, the sampling factor 1 seemed to produce the best result. In this test, sampling factor 30 seems to produce the greatest opportunity for smooth dithers and least loss in color fidelity.
Neuquant seems to have an unexplained bias towards brown colors.

Spatial color quantization (scolorq)

Wikipedia describes scolorq as follows:
One of the most promising new methods is spatial color quantization, conceived by Puzicha, Held, Ketterer, Buhmann, and Fellner of the University of Bonn, which combines dithering with palette generation and a simplified model of human perception to produce visually impressive results even for very small numbers of colors. It does not treat palette selection strictly as a clustering problem, in that the colors of nearby pixels in the original image also affect the color of a pixel.

For some reason, filter size 1 resulted always in broken images, so it is excluded from this test.
Dithering level Filter size = 3 Filter size = 5 Original
0.2
0.4
0.5
0.6
0.7
0.8
0.9
1.0
1.1
1.2
1.5
2
5
10

Gifsicle

Gifsicle is an animated GIF creation/optimization tool-kit for unix-type systems.

Because Gifsicle does not support reading of truecolor images, or actually any other images than GIF, I first reduced the image to 256 colors using Neuquant, and then converted it to GIF and gave it to Gifsicle for working. The result was converted to PNG.
Method No dithering Dithering (floyd-steinberg) Original
Median-cut, aka. Heckbert algorithm
Diversity
Blend-diversity

Conclusion

It is the author's opinion that the best tool to quantize this particular image was Scolorq, at these settings:

Scolorq, Filter 3, dither level 1.0
Tests performed by Joel Yliluoma, december 21 2007

Test tools

This script was used to generate all the images: 
# Gifsicle tests:
scolorq original.jpg neuquant-256c-q30.png -q30 -c256
mogrify -format gif neuquant-256c-q30.png

gifsicle -o gifsicle-16c-mc-dith.gif -f -k16 --color-method median-cut \
	neuquant-256c-q30.gif
gifsicle -o gifsicle-16c-di-dith.gif -f -k16 --color-method diversity \
	neuquant-256c-q30.gif
gifsicle -o gifsicle-16c-bd-dith.gif -f -k16 --color-method blend-diversity \
	neuquant-256c-q30.gif
gifsicle -o gifsicle-16c-mc-nodith.gif -k16 --color-method median-cut \
	neuquant-256c-q30.gif
gifsicle -o gifsicle-16c-di-nodith.gif -k16 --color-method diversity \
	neuquant-256c-q30.gif
gifsicle -o gifsicle-16c-bd-nodith.gif -k16 --color-method blend-diversity \
	neuquant-256c-q30.gif

mogrify -format png gifsicle-16c-{mc,di,bd}-{nodith,dith}.gif

# Scolorq tests:
for f in 1 3 5;do \
for d in 0.2 0.4 0.5 0.6 0.7 0.8 0.85 0.9 1.0 1.1 1.2 1.5 2 3 5 10 20 30 50;do \
scolorq original.jpg scolorq-16c-f"$f"-d"$d".png -f$f -d$d -c16;done;done

# Neuquant tests:
for s  in `seq 0 30`;do \
scolorq original.jpg neuquant-16c-q$s.png -q$s -c16;done

# Imagemagick tests:
for s in rgb yuv ycc xyz yiq hsl lab gray;do \
convert original.jpg -quantize $s -depth 8 \
+dither -colors 16 imagemagick-16c-$s-nodith.png;done

for s in rgb yuv ycc xyz yiq hsl lab gray;do \
convert original.jpg -quantize $s -depth 8 \
 -colors 16 imagemagick-16c-$s-dith.png;done
 
for d in o2x2 o3x3 o4x4 o8x8 h4x4a h6x6a h8x8a h4x4o h6x6o h8x8o h16x16o checks;do
for s in rgb yuv ycc xyz yiq hsl lab gray;do \
convert original.jpg -quantize $s -depth 8 \
-ordered-dither $d -colors 16 imagemagick-16c-$s-$d.png;done
done

The package containing my custom version of scolorq that also includes the neuquant algorithm, can be downloaded here: http://bisqwit.iki.fi/src/arch/scolorq_and_neuquant-1.0.0.tar.bz2. It requires libGD.

The images produced by the tests were optimized losslessly for small size using AdvanceCOMP and PNGOUT.

The version of Imagemagick used was 6.3.5. Note that version 6.2.4 does not support the -quantize and -ordered-dither parameters in the way used by this script.