CrystalSpace

Public API Reference

csColorQuantizer Class Reference
[Graphics]

Color quantizer. More...

#include <csgfx/quantize.h>

List of all members.

Public Member Functions

void Begin ()
 Begin quantization.
void Bias (csRGBpixel *colors, int count, int weight)
 Bias the color histogram towards given colors (weight = 0..100).
void Count (csRGBpixel *image, int pixels, csRGBpixel *transp=0)
 Count the colors in a image and update the color histogram.
 csColorQuantizer ()
 Construct a new quantizer object.
void DoRGB (csRGBpixel *image, int pixels, int pixperline, uint8 *&outimage, csRGBpixel *&outpalette, int &maxcolors, bool dither)
 Quantize a RGB image into a paletted image.
void End ()
 Finish quantization.
void Palette (csRGBpixel *&outpalette, int &maxcolors, csRGBpixel *transp=0)
 Compute the optimal palette for all images passed to QuantizeCount().
void Remap (csRGBpixel *image, int pixels, uint8 *&outimage, csRGBpixel *transp=0)
 Remap a image to the palette computed by Palette().
void RemapDither (csRGBpixel *image, int pixels, int pixperline, csRGBpixel *palette, int colors, uint8 *&outimage, csRGBpixel *transp=0)
 Same but apply Floyd-Steinberg dithering for nicer (but slower) results.
 ~csColorQuantizer ()
 Destruct and cleanup.

Friends

struct csColorBox


Detailed Description

Color quantizer.

The algorithm presented here is a variation of well-known and widely-used Heckbert quantization algorithm. It works in the following way: first, we build a 3-D histogram that describes which colors and how many times the corresponding colors were used. Since we deal with RGB images, all possible colors counts to 256^3 = 16777216 colors, too much to keep in memory. Because of this, we ignore several lowest bits from each color component, taking into consideration human eye's sensivity to different color components we take 5 bits for R, 6 bits for G and 4 bits for B. This summary reduces to 32*64*16 = 32768 histogram cells, which is a reasonable size for an dynamically-allocated array.

Next, we take the entire color box and split it into subboxes. The split happens along the longest of R,G,B axis into half (and taking again into account eye sensivity). After which we take again the biggest box, and split it again and so on until we have that much boxes how much colors we want. Then we assign to each box a color index, and compute the median RGB value for each box.

To keep memory requirements in reasonable bounds, we scale down R/G/B components to 5/6/4 bits respectively. This produces results that are different from those we'll get with, say, 6/7/6 resolution but its a quite suitable solution, for a quality vs speed choice. I've tried 5/6/5 as well as 6/6/4 and its really hard to say they are better - the results are definitely different but it's hard to say they are really better.

WARNING: If the sum of R+G+B bits exceeds 16, you will a need special case for big endian machines for the INDEX_B macro (see below). With big-endian machines the B component starts at bit 8, thus the right shift counter becomes negative. Probably the best solution is to add an #if B_BIT + 8 - HIST_B_BITS - HIST_G_BITS - HIST_R_BITS < 0.

Quantizing
The following routines can be used to split the quantization process into small steps. First, you should call Begin(). This will allocate some memory for color histogram and also do some other maintenance work. Then you call Count () as much times as you want, to count the frequencies of colors. This is a quite fast operation, thus you can use it, for example, to compute a optimal palette for a large number of images (for example, software 3D renderer uses it for computing the optimal palette in paletted modes, by passing every texture to Count()).

When you're finished with images, call Palette(). This will compute the optimal palette. If you need just that, you can call End() and you're done. If you need to remap all those textures to the optimal palette, you can call Remap() as much times as you wish. Finally you anyway should call End() to free all the memory used by quantizer.

Now, a typical quantization sequence could look like this:

 Begin ();

    Count (image, pixels);
   Count (...);
   ...

   int maxcolors = 256;
   Palette (outpalette, maxcolors);
   // now maxcolors contains the actual number of palette entries

   Remap (image, pixels, outimage);
   Remap (...);
   ...

 End ();
The quantizer itself keeps track of its current state, and will silently ignore invalid calls. For example, if you call Remap() right after calling Begin() nothing will happen. You still can call Palette() right after Begin(), and you will get the expected black (or let's call it `empty') palette.

The Bias routine can be used to introduce a bias inside the currently open color histogram towards given colors. The "weight" parameter shows how important those colors are (0 - not at all, 100 - very). This can be used to bias the resulting palette towards some hard-coded values, for example you may want to use it to create a relatively uniform palette that is somewhat biased towards the colors contained in some picture(s).

Some routines accept an additional parameter (csRGBpixel *transp). If it is 0, nothing special is performed. If it is non-0, it should point to an valid csRGBpixel object; the color of that pixel will be treated in a special way: Count() will ignore pixels of that color, Palette() will allocate color index 0 for that color, and Remap will map all such pixel values to index 0.

Definition at line 129 of file quantize.h.


Constructor & Destructor Documentation

csColorQuantizer::csColorQuantizer (  ) 

Construct a new quantizer object.

csColorQuantizer::~csColorQuantizer (  ) 

Destruct and cleanup.


Member Function Documentation

void csColorQuantizer::Begin (  ) 

Begin quantization.

void csColorQuantizer::Bias ( csRGBpixel colors,
int  count,
int  weight 
)

Bias the color histogram towards given colors (weight = 0..100).

void csColorQuantizer::Count ( csRGBpixel image,
int  pixels,
csRGBpixel transp = 0 
)

Count the colors in a image and update the color histogram.

void csColorQuantizer::DoRGB ( csRGBpixel image,
int  pixels,
int  pixperline,
uint8 *&  outimage,
csRGBpixel *&  outpalette,
int &  maxcolors,
bool  dither 
)

Quantize a RGB image into a paletted image.

This is a relatively expensive operation, in both CPU and memory resources terms. It is pretty fast though (more than 3.200.000 pixels/sec on a relatively weak P5/166) for what it does. It uses a variation of well-known Heckbert quantization algorithm. The side bonus after quantization is that the palette is ordered in most-used-first fashion. If outimage is 0, it is allocated. If outpalette is 0, it is allocated as well. If it is non-0, the routine supposes that the storage the pointers point to has enough size to store resulting image and palette (the size of resulting image is exactly "pixels" bytes, the size of resulting palette is palsize colors).

Parameters:
image input image
pixels number of pixels in input image
pixperline number of pixels in one line
outimage output image (allocated if 0)
outpalette output palette (allocated if 0)
maxcolors maximal number of colors in output palette (actual number of colors on return)
dither Use/do not use Floyd-Steinberg dithering

void csColorQuantizer::End (  ) 

Finish quantization.

void csColorQuantizer::Palette ( csRGBpixel *&  outpalette,
int &  maxcolors,
csRGBpixel transp = 0 
)

Compute the optimal palette for all images passed to QuantizeCount().

void csColorQuantizer::Remap ( csRGBpixel image,
int  pixels,
uint8 *&  outimage,
csRGBpixel transp = 0 
)

Remap a image to the palette computed by Palette().

void csColorQuantizer::RemapDither ( csRGBpixel image,
int  pixels,
int  pixperline,
csRGBpixel palette,
int  colors,
uint8 *&  outimage,
csRGBpixel transp = 0 
)

Same but apply Floyd-Steinberg dithering for nicer (but slower) results.


The documentation for this class was generated from the following file:
Generated for Crystal Space by doxygen 1.4.7