<p>An interesting problem. I've done a bit of work in texture compression and this sounds something like a generalisation of <a href="https://en.wikipedia.org/wiki/Color_Cell_Compression" rel="nofollow noreferrer">Campbell et al's "Color Cell Compression"</a>.  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. </p>

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

<p>You say that </p>

<blockquote>
  <p><em>"the exact colors, the arrangement of colors into subpalettes, and the subpalette for each tile of the image are all unknowns"</em></p>
</blockquote>

<p>but can we assume the X*Y tile size <em>is</em> predetermined?</p>

<p>Assuming that is the case, perhaps the following might be worth trying:</p>

<p>1) Guess an initial palette size for the entire image, perhaps, 
 <span class="math-container">$$Psize=(M * SizeOfEachSubpalette)$$</span>
where <span class="math-container">$1 &lt; M &lt; N$</span>.</p>

<p>Use standard VQ quantisation to generate this palette and map the pixels to it.</p>

<p>2) Now consider each <span class="math-container">$X*Y$</span> tile to be a "super pixel" with <span class="math-container">$Psize$</span> 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.</p>

<p>For example, if in our initial palette, entry <span class="math-container">$j$</span> is [0x11,0x21,0x31] and 5 pixels in the tile mapped to that colour, set the <span class="math-container">$j'th$</span> component in the tile's superpixel to 5.</p>

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

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

<p>3) For each tile set, collect all the pixels in the tiles, and apply a 3rd VQ operation to identify the <span class="math-container">$SizeOfEachSubpalette$</span> colours needed for all tiles in that set.</p>

<p>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.</p>

CC BY-SA 4.0
2019-02-28T10:24:09.110Z
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
CC BY-SA 4.0
2019-02-28T10:37:15.557Z
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
CC BY-SA 4.0
2019-02-28T10:57:04.293Z
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
CC BY-SA 4.0
2019-02-28T11:06:43.637Z
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
CC BY-SA 4.0
2019-02-28T09:47:12.897Z
2019-02-28T09:53:12.243Z
2019-02-28T09:53:12.243Z
Simon F
<p>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.</p>

<p>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 &lt;&lt; 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.</p>

<p>How could this more difficult problem be solved, algorithmically?</p>

CC BY-SA 4.0
2019-02-28T04:14:12.583Z
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
CC BY-SA 4.0
2019-02-28T04:14:56.473Z
Ah, I see. Sorry for my confusion!
user1118321
<algorithm><image-processing><color>
Tiled Image Palettization Algorithm?
Justin Olbrantz
# Tiled Image Palettization Algorithm?

(Asked by: username_0 on 2019-02-28)

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?

**Tags:** algorithm, image-processing, color

> **Comments:**
> **username_0**: 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.  
> **username_1**: Ah, I see. Sorry for my confusion!  

---

## 1 answers

### Answer by username_2 on 2019-02-28. Score: 2

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"](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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).  
> **username_2**: 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*  
> **username_0**: 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.  
> **username_0**: 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.  

---

