# Tiled Image Palettization Algorithm?

In most cases today, image palettization consists of reducing the overall number of colors in an image to some fixed number globally. This is typically solved as a straightforward but computationally difficult clustering problem.

A more difficult version of this problem involves older graphics hardware where the palette is broken down into N subpalettes (e.g. of 4 colors each) and the image is broken down into XxY-pixel tiles where each tile can only use colors from a single subpalette and N << the number of tiles. Here both the exact colors, the arrangement of colors into subpalettes, and the subpalette for each tile of the image are all unknowns that must be solved together.

How could this more difficult problem be solved, algorithmically?

• Right. It was originally done by hand by artists who designed the images around the palette constraints. I'm asking about an algorithm to do it. – Justin Olbrantz Feb 28 '19 at 4:14
• Ah, I see. Sorry for my confusion! – user1118321 Feb 28 '19 at 4:14

An interesting problem. I've done a bit of work in texture compression and this sounds something like a generalisation of Campbell et al's "Color Cell Compression". It's also a little like a feature we were asked to include in the Dreamcast VQ compressor so that sub-palettes could be swapped to create different colour schemes on textures.

I was thus thinking that maybe you could adapt a standard VQ algorithm, applied in stages, to the problem.

You say that

"the exact colors, the arrangement of colors into subpalettes, and the subpalette for each tile of the image are all unknowns"

but can we assume the X*Y tile size is predetermined?

Assuming that is the case, perhaps the following might be worth trying:

1) Guess an initial palette size for the entire image, perhaps, $$Psize=(M * SizeOfEachSubpalette)$$ where $$1 < M < N$$.

Use standard VQ quantisation to generate this palette and map the pixels to it.

2) Now consider each $$X*Y$$ tile to be a "super pixel" with $$Psize$$ channels. Set each channel value in the tile's "super pixel" to the number of pixels that mapped to the corresponding colour in our initial palette.

For example, if in our initial palette, entry $$j$$ is [0x11,0x21,0x31] and 5 pixels in the tile mapped to that colour, set the $$j'th$$ component in the tile's superpixel to 5.

Run a second VQ operation on the set of all "super pixels" using '$$Psize$$-dimensional space' to generate $$N$$ "palette" entries. (Actually, you don't need the 'palette' values - the VQ process is just meant as a means of partitioning the tiles into $$N$$ sets)

Hopefully, this will now identify which tiles should share the same sub-palette.

3) For each tile set, collect all the pixels in the tiles, and apply a 3rd VQ operation to identify the $$SizeOfEachSubpalette$$ colours needed for all tiles in that set.

I would think some sort of clever GLA/k-means process might be needed for step 2 to juggle the assignments of tiles to sub-palettes. The choice of M might also be interesting.

• If I understand the proposal, this sounds like something I was considering initially, but I wasn't sure how to do VQ on aggregate vectors as the aggregate vectors could have many permutations of the same set of colors (which would prevent finding the proper centroids). E.g. for two color aggregates (11, 21, 31, 41, 51, 61) would be the same as (41, 51, 61, 11, 21, 31). – Justin Olbrantz Feb 28 '19 at 10:24
• That's why I thought assigning the count to the "tile pixel" would get around the ordering problem. Of course, having lots of "similar" colours in the original palette might work against this hence the uncertainty on the initial choice for M – Simon F Feb 28 '19 at 10:37
• That's definitely a way of imposing a definite order. Though the fact that the distance between two points in the x-D index vector space will not necessarily be proportionate to the actual different between the colors for the two subpalettes means you could potentially end up with a centroid that has wildly different colors that the points away from the centroid. – Justin Olbrantz Feb 28 '19 at 10:57
• Actually, that might not be true since we're just using the counts of each palette entry, and the actual colors for each subpalette could be recomputed once similar blocks are found. – Justin Olbrantz Feb 28 '19 at 11:06