Allow to use more than one palette

[haroldo-ok]

Objective

SMS/GG background tiles can use either the background palette or the sprite; it would be interesting if RgbQuant-SMS could support generating two or more palettes for the same image, and automatically assign the best fitting palette for each tile.

How?

I have a general idea on how this could be done, but it would take a while to implement:

1. First of all, the original image would have to be cut into multiple 8x8 non-palettized tiles;
2. A color histogram would be built for each tile, counting how many times each color is used for that tile;
3. The color histograms would then be fed into a clustering algorithm that should generate as many clusters as the desired number of palettes;
4. A separate instance of the color quantizer should be instantiated for each desired palette;
5. Each cluster of tiles will be fed into the corresponding color quantizer, therefore generating palettes that are optimized for them;
6. Then the actual color reduction is performed, each tile being reduced to the corresponding palette, generating the indexed tiles as before, except the map will also receive information saying which palette is being used for that slot;
7. The usual tile normalization and duplicate tile elimination will be then performed, except tiles that use different palettes won't be considered identical, otherwise there will be problems on the next step;
8. The clusterization for tile reduction would be then performed, but taking into consideration the palette that will be in use on each piece ot the map;
9. Then the tiles will be merged as usual,
10. The the merged tiles will be color-reduced with both palettes, and the reduced tiles will be compared to the original ones; the tile will use the palette that causes less difference from the original.