Back to home page

scolorq: A Spatial Color Quantization Utility

Summary

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.

What's new

Version 0.4

Version 0.3

What is it good for?

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.

What is it not good for?

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.

Sample images

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.

Small images

NameSizeColorsTimeOriginalscolorqPhotoshop
peppers_small100×10041/2 sec
21,871 bytes

2,122 bytes

2,783 bytes
peppers_small100×10081 sec
21,871 bytes

3,003 bytes

3,559 bytes
peppers_small100×100162 sec
21,871 bytes

3,797 bytes

4,314 bytes
lena_small100×10041/2 sec
21,499 bytes

2,051 bytes

2,879 bytes
lena_small100×10081 sec
21,499 bytes

2,964 bytes

3,836 bytes
lena_small100×100162 sec
21,499 bytes

3,669 bytes

4,481 bytes
gradient135×13523 sec
390 bytes

1,951 bytes

1,967 bytes
gradient135×135413 sec
390 bytes

2,352 bytes

2,483 bytes
gradient135×13581 sec
390 bytes

2,723 bytes

2,274 bytes
gradient135×135163 sec
390 bytes

2,287 bytes

1,918 bytes
wiki-en135×15521/2 sec
12,122 bytes

2,638 bytes

3,023 bytes
wiki-en135×15543/4 sec
12,122 bytes

3,671 bytes

4,222 bytes
wiki-en135×15582 sec
12,122 bytes

5,458 bytes

5,458 bytes

Large images

NameSizeColorsTimeOriginalscolorqPhotoshop
pool491×36945 sec
37,671 bytes

7,755 bytes

7,640 bytes
pool491×369811 sec
37,571 bytes

15,540 bytes

15,664 bytes
pool491×3691623 sec
37,571 bytes

24,275 bytes

20,873 bytes
baboon512×512411 sec
625,782 bytes (click for PNG)

49,030 bytes

44,358 bytes
baboon512×512819 sec
625,782 bytes (click for PNG)

75,234 bytes

66,242 bytes
baboon512×5121642 sec
625,782 bytes (click for PNG)

98,615 bytes

89,188 bytes
lena512×512412 sec
474,332 bytes (click for PNG)

49,531 bytes

35,899 bytes
lena512×512820 sec
474,332 bytes (click for PNG)

63,082 bytes

53,846 bytes
lena512×5121637 sec
474,332 bytes (click for PNG)

77,428 bytes

68,430 bytes
rainbow256×25643 sec
6,627 bytes

11,935 bytes

7,226 bytes
rainbow256×25684 sec
6,627 bytes

14,693 bytes

9,697 bytes
rainbow256×256168 sec
6,627 bytes

16,628 bytes

12,030 bytes
rainbow256×2563218 sec
6,627 bytes

17,934 bytes

14,037 bytes
rainbow256×2566461 sec
6,627 bytes

19,925

16,444 bytes

Download

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.

Version 0.4

Version 0.3

Version 0.2

All scolorq source code is released under the non-copyleft MIT free software license, permitting it to be reused by anyone.

Using under Linux

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.

Using under Windows with Photoshop

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:

  1. Make sure the image is in RGB mode
  2. Save the image in the RAW format. Specify a Header size of 0 and make sure "Interleaved Order" is selected. Click OK.
  3. At a command line and in the same directory where you saved the raw image, run the 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.

  4. Open the resulting output file in Photoshop, specifying the same width and height as the original image. Under Channels, specify 3 channels, check the Interleaved box, and choose a Depth of 8 bits. Make sure Header size is 0 and click OK.
  5. Your reduced image will open. If you want to save it out in another format, you will probably first want to reduce it to Indexed Color using the Exact palette mode.
  6. You may want to get pngutils, which includes a version of 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.

Contact information

If you have any feedback on scolorq, positive or negative, please feel free to mail me.

To Do List

Some things I still need to add to scolorq include:

Back to home page