Spatial color quantization is a novel technique for decreasing the color depth of an image, first described in the paper "On Spatial Quantization of Color Images" by Jan Puzicha, Markus Held, Jens Ketterer, Joachim M. Buhmann, and Dieter Fellner, researchers at the University of Bonn in Germany. It combines palette selection and dithering with a simple perceptual model of human vision to produce superior results for many types of images.
Although first published in 1998, and accompanied by a sample image page that has earned many compliments, the algorithm has never been widely adopted due to the lack of available implementations. The authors' implementation was never made publically available, and the algorithm is relatively complex, discouraging others from implementing it.
scolorq, standing for "spatial color quantization", is
a faithful implementation of the highest-quality algorithm described
in the paper. Its results have richer colors and often better detail
than the widely-used median cut and octree algorithms supplied in
bitmap editors like Adobe Photoshop, Paint Shop Pro, and the GIMP,
particularly when reducing to very low color depths, like 4, 8, or 16
colors, as the sample images below demonstrate.
One of the most obvious uses the tool can be applied to is creating images to use on web pages. By decreasing the number of colors in a PNG or GIF file, you can drastically cut the filesize with little apparent visual degradation. This is most useful for small graphics with many colors, such as thumbnails of photos or fancy navigation and layout elements.
The algorithm produces its best results relative to existing
methods at small numbers of colors like 4 and 8, and produces its best
filesizes relative to the original image file for images with a fair
amount of detail. Also, existing algorithms perform very poorly on certain
types of images such as images that have already been dithered; by the design
of its cost function, scolorq is more tolerant of these, and
can even be used for increasing the number of colors and quality
in an already-reduced image.
First, don't use scolorq for large photographs and other
large continuous-tone (smooth) images. Use JPEGs for these —
they'll be smaller and look better. The large photos in the sample images
are for demonstration purposes only.
Also, don't use scolorq for reducing to a large number
of colors, such as 256. The algorithm is extremely slow for large
numbers of colors and will not noticably outperform standard
algorithms available in your bitmap editor. Right now the most it can
comfortably handle is about 32, or 64 for small images.
Finally, be careful using scolorq on large images
— although it can handle them, it may run for a very long
time. We strive to continue to improve the tool's performance to
enable conversion of larger images in a reasonable time. Check the
sample images below to see what typical times are.
Finally, due to its current slow speed, this algorithm is best used for offline processing of images, not on-demand or real-time processing such as performed by windowing systems.
All the below images were created with the default settings for
scolorq (except for the 2/4-color gradient, which used a
filter size of 5, and baboon_small which used a higher dithering
level) and, in Photoshop, the "Local (Perceptual)" palette and 75%
Diffusion dithering. Times given are for scolorq only and
were taken on a 2.8 GhZ Pentium 4 machine. Photoshop's times are all
less than one second. File sizes are shown below each image; all
images (including originals) were reduced in filesize using pngcrush
with the "-brute" option, but this was not included in the time.
Insofar as I have any copyright rights to these images, I release such rights. However, a number of the original images such as Lena are copyright their respective holders — reuse at your own risk.
| Name | Size | Colors | Time | Original | scolorq | Photoshop |
| peppers_small | 100×100 | 4 | 1/2 sec |  21,871 bytes |  2,122 bytes |  2,783 bytes |
| peppers_small | 100×100 | 8 | 1 sec | 21,871 bytes |  3,003 bytes |  3,559 bytes |
| peppers_small | 100×100 | 16 | 2 sec | 21,871 bytes |  3,797 bytes |  4,314 bytes |
| lena_small | 100×100 | 4 | 1/2 sec |  21,499 bytes |  2,051 bytes |  2,879 bytes |
| lena_small | 100×100 | 8 | 1 sec | 21,499 bytes |  2,964 bytes |  3,836 bytes |
| lena_small | 100×100 | 16 | 2 sec | 21,499 bytes |  3,669 bytes |  4,481 bytes |
| gradient | 135×135 | 2 | 3 sec |  390 bytes |  1,951 bytes |  1,967 bytes |
| gradient | 135×135 | 4 | 13 sec | 390 bytes |  2,352 bytes |  2,483 bytes |
| gradient | 135×135 | 8 | 1 sec | 390 bytes |  2,723 bytes |  2,274 bytes |
| gradient | 135×135 | 16 | 3 sec | 390 bytes |  2,287 bytes |  1,918 bytes |
| wiki-en | 135×155 | 2 | 1/2 sec |  12,122 bytes |  2,638 bytes |  3,023 bytes |
| wiki-en | 135×155 | 4 | 3/4 sec | 12,122 bytes |  3,671 bytes |  4,222 bytes |
| wiki-en | 135×155 | 8 | 2 sec | 12,122 bytes |  5,458 bytes |  5,458 bytes |
| Name | Size | Colors | Time | Original | scolorq | Photoshop |
| pool | 491×369 | 4 | 5 sec |  37,671 bytes |  7,755 bytes |  7,640 bytes |
| pool | 491×369 | 8 | 11 sec | 37,571 bytes |  15,540 bytes |  15,664 bytes |
| pool | 491×369 | 16 | 23 sec | 37,571 bytes |  24,275 bytes |  20,873 bytes |
| baboon | 512×512 | 4 | 11 sec |  625,782 bytes (click for PNG) |  49,030 bytes |  44,358 bytes |
| baboon | 512×512 | 8 | 19 sec | 625,782 bytes (click for PNG) |  75,234 bytes |  66,242 bytes |
| baboon | 512×512 | 16 | 42 sec | 625,782 bytes (click for PNG) |  98,615 bytes |  89,188 bytes |
| lena | 512×512 | 4 | 12 sec |  474,332 bytes (click for PNG) |  49,531 bytes |  35,899 bytes |
| lena | 512×512 | 8 | 20 sec | 474,332 bytes (click for PNG) |  63,082 bytes |  53,846 bytes |
| lena | 512×512 | 16 | 37 sec | 474,332 bytes (click for PNG) |  77,428 bytes |  68,430 bytes |
| rainbow | 256×256 | 4 | 3 sec |  6,627 bytes |  11,935 bytes |  7,226 bytes |
| rainbow | 256×256 | 8 | 4 sec | 6,627 bytes |  14,693 bytes |  9,697 bytes |
| rainbow | 256×256 | 16 | 8 sec | 6,627 bytes |  16,628 bytes |  12,030 bytes |
| rainbow | 256×256 | 32 | 18 sec | 6,627 bytes |  17,934 bytes |  14,037 bytes |
| rainbow | 256×256 | 64 | 61 sec | 6,627 bytes |  19,925 |  16,444 bytes |
Announcement: As of February 2009, I'm happy to announce that scolorq has been incorporated by Blas Rodriguez Somoza into a Photoshop plug-in called Ximagic Quantizer, also compatible with the GIMP.
All scolorq source code is released under the
non-copyleft MIT free software license, permitting it to be
reused by anyone.
Under Linux, you will need to install ImageMagick, since
scolorq depends on its convert utility.
If you're aiming to create small PNG files, it's a good idea to
also install pngcrush, which scolorq will
use to postprocess its output.
If you downloaded the source package, just type "make" to
build the binary spatial_color_quant using gcc. Then,
you can run the scolorq script on a file of virtually
any format like this:
./scolorq <input file name> <width> <height> <desired palette size> <output file name>
For example:
./scolorq lena.png 512 512 8 lena_8.png
You can add an additional parameter specifying the dithering level. The default depends on image resolution and the desired number of colors and ranges from about 0.5 to 1.5. Larger values will produce pictures with more high frequency noise but less visible error. You can also, after that, specify a filter size; the default is 3. A filter size of 1 is much faster but essentially eliminates dithering; a filter size of 5 helps to correctly dither some smooth gradients but greatly increases runtime.
You can also now use scolorq interactively by installing the GIMP and installing Blas Rodriguez Somoza's Photoshop plug-in Ximagic Quantizer.
Update: As of February 2009, scolorq has been incorporated by Blas Rodriguez Somoza into a Photoshop plug-in called Ximagic Quantizer, which I recommend using with Photoshop or the GIMP on Windows.
Currently, this utility is a bit cumbersome to use under Windows, but if you have Photoshop, it is possible. First, either download the binary above or download the Windows source package and build it in Visual Studio (or your compiler of choice). Next, open the file you want in Photoshop and perform the following steps:
scolorq.exe binary as follows:
scolorq.exe <input file name.raw> <width> <height> <desired palette size> <output file name.raw>
See notes in the Linux section above on additional optional parameters.
pngcrush for the Win32 console. You can use this with the "-brute" switch to further shrink a PNG file saved out by Photoshop, sometimes by as much as 50%.I apologise for the difficulty and hope to add native support for PNG and GIF files under Windows in a future release.
If you have any feedback on scolorq, positive or
negative, please feel free to mail me.