# Palette reduction to pre-defined palette

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.

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

• This is just awesome, and the fact you've done that tool... Pure gold. Thanks! Jul 22 '14 at 7:59
• If you can re-visit the code at some point, I'd be glad - I tried it out and I basically get only red, white and black with the sample palette you included. :) Jul 22 '14 at 8:33
• Bleh, sorry for the late reply. What code bit? The shader part might need some work, I've been unable to set something up to test it properly. You could try debugging it by skipping the sampling part to see if the colors are encoded directly. Does the output you get make sense compared to what you're expecting? (i.e. is it random pixels everywhere or do the colors roughly fit)
– Elva
Jul 31 '14 at 12:07
• I fiddled around with it, and got it working almost correctly. Some colors, however, were wrong (light gray was yellow etc). It might be a problem with the palette, though. Jul 31 '14 at 12:21
• Possibly, my tool is also pretty basic simply taking the colors as points in 3d space and taking linear distance, could be improved to take human perception into account. If you want, you could edit my reply to add the tweaks you made to the shader :)
– Elva
Jul 31 '14 at 12:41

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.

• I understand, that this is not that practical and immediately usable answer as Kevin's, so please accept that, if it solves your problem. As a sidenote: his solutions is a special case of the general framework I described. The spatial partitioning structure of the color space is a 16x16x16 grid, the palette is preprocessed to build that spatial partitioning structure, which is encoded in a texture, the texture is transferred to the GPU, and it is used to solve the point location (by texture sampling).
– zogi
Jul 22 '14 at 6:43
• Thanks for your answer. I pretty much need an online solution (fragment shader) because the original assets are affected by shaders and such. I want the end result to be limited to the palette, and it seems Kevin's answer is just what I was looking for. :) Jul 22 '14 at 8:01