This project was originally created as a component of a larger project. I was developing an online texture editor for an old game that required paletted images. I developed this palette generator by simply playing with the distribution of the image colors. A user of an online forum who viewed this article pointed out that this is not the optimal solution to generate palettes. That person is almost certainly correct, however, this method was "good enough" for my purposes and I chose to document it because it was an interesting solution.
We start by scanning all the pixels of the image. We record each color, and how many times that color appears, which we call "frequency". The collection of colors is then sorted by frequency in highest-to-lowest order.
In our example above, the specified palette size was 256. This means that out of the 83,882 unique colors that are used in the image, we have to choose 256 that will be represent the original image. The example above shows 3 different schemes I tried before obtaining a good result.
The final solution was to take the sorted colors list and calculate a stepping distance. This stepping distance is the number of colors to skip between each selection. The stepping distance is calculated using floor(num_of_colors / palette_size). This allowed us to sample from a wide range of frequencies which gave the best result.
Once the scheme is chosen, we have to loop back through all the pixels replacing them with their palette equivalents. There are 2 cases:
- The current pixel contains a color that is in the palette. In this case we just replace the pixel with its reference to that color within the palette.
- The current pixel contains a color that is not in the palette. So then we loop through the entire palette, searching for the closest color. That pixel is then replaced with a reference to its closest color.
Above we mentioned "finding the closest color", but how do we do this? Think of it this way, colors are made of 3 primary colors. These primary colors are completely independent of one another. For whatever reason, computers don't use the three primary colors but instead use red, blue, and green, but thats okay because the result is the same. Think of our 3D world, how each location is specified as a distance along the x, y, and z axis. Well we can think of red, green, and blue as independent axes in color space. So, finding the distance between colors is the same thing as finding the distance between to points in 3D space. We simply use the distance formula.
Let color1 be made of (r1, g1, b1) and color2 be made of of (r2, g2, b2). Then the distance between the colors is d = sqrt( (r2 - r1)^2 + (g2 - g1)^2 + (b2 - b1)^2)
This method was implemented in javascript for an online palette generator.
You can test it here.Note: The example palette generator is VERY slow for large images
Here is the function at the heart of the algorithm:
function createPalette(size, buffer) {
//Create a frequency list of all colors in the buffer
var colors = [];
// For every pixel
for (var i = 0; i < buffer.length; i += 4) {
// Get the rgb values of the current pixel
var r = buffer[i+0];
var g = buffer[i+1];
var b = buffer[i+2];
var a = buffer[i+3];
// Compare against the already catalogued colors list
var found = false;
for (var j = 0; j < colors.length; j++) {
// If color is already noted, add to its frequency count
if (colors[j].r == r && colors[j].g == g && colors[j].b == b) {
colors[j].frequency++;
found = true;
break;
}
}
// If color not found in the loop, this is a new color, add it
if (!found)
colors.push({r:r, g:g, b:b, frequency:0});
}
// Sort by frequency
colors.sort( function(a, b) {return b.frequency - a.frequency;});
// Get ready to form the palette
var palette = [];
// If the number of colors is <= the palette size, just add all the colors
if (colors.length < size) {
for (var i = 0; i < colors.length; i++)
palette.push(colors[i]);
return palette;
}
// How far to step in between in colors to get the widest possible range of the frequencies
var step = Math.floor(colors.length / size);
// Add the colors to the palette
for (var i = 0, color = 0; i < size; i++, color += step) {
palette.push(colors[color]);
}
return palette;
}