Palette reduction to pre-defined palette

Question

I'm writing a bunch of GLSL effects for fun, but I can't wrap my head around this. Basically, I want to reduce a texture's palette into a pre-defined set of colors. For example, a post-processing shader would take the FBO result texture and a 1D / 2D texture that would contain the reduced palette (say, 64 colors), and the output would then be sampled based on these.

Something like this in its core:

sampler2D source;
sampler2D palette;

vec4 source = texture2D(...); // Source texture to sample
vec4 palette = texture2D(...); // Palette

vec3 result = /* color from the source converted to the closest value available in palette */;

Any ideas how to do this? And to be more precise, I don't mean palette swapping - the source texture is full-colored result, and this shader would ultimately be a post-processing shader, reducing the amount of colors to the ones that are predefined in the palette texture.

Answer 1

Another way to do this is to make a texture that maps each RGB to a colour on the palette, an image like this (from the NES colours):

Then in a post processing shader you can the RGB colour from your regular image in a way like this:

uniform sampler2d paletteMapping;

vec3 mapColor( vec3 realColor ) {
    vec3 mappedColors = floor( realColor * 16 );
    int mappedI = mappedColors.r + mappedColors.g * 16 + mappedColors.b * 16 * 16;

    return texture2D( paletteMapping, floor( vec2( mappedI / 64, mod( mappedI, 64 ) ) );
}

I've not tested the shader as I'm at work, but this should work on a texture that has interpolation disabled (i.e. it uses nearest neighbour sampling).

The map image I created with a little tool I wrote, from the NES palette image on wikipedia

Answer 2

This problem is called Color quantization. Basically for each pixel you want to find a closest color present in the palette. This can be done by partitioning the 3D color space into regions each of which containing exactly one palette color. The partitioning can be performed using e.g. Voronoi diagram, octree or any other spatial partitioning data structure. Then, for each pixel, a point location problem has to be solved, i.e. the region containing the pixel color has to be found. In case of octrees this can be done efficiently in a straightforward way. The unique palette color in the region will replace the original pixel color.

Because this process is computationally intensive, you should perform as many steps offline in a preprocessing step (e.g. in your asset pipeline) as possible.

Performing the entire quantization step on your textures offline is the easiest way. ImageMagick can perform this via the -remap option. ImageMagick can also perform dithering automatically, which improves the visual quality of quantized images.

If you want to apply a palette to your rendered scene while using your original textures, but the palette is fixed, the color space partitioning can still be done offline. E.g. you can build an octree using the palette colors, transfer the tree to the GPU, and use it in the shader to perform the quantization. ImageMagick uses this approach (on the CPU), the algorithm is described in the source code.

If you want to be able to switch between palettes, the partitioning has to be done on-the-fly, but reasonably on the CPU.