Genesis Colour Quantization

[adam_smasher]

Suppose you're making a game for the Genesis (or any other old console, but I have my particular interests) and want to use high-colour assets (photos, 3D renderings) for the art. Photoshop or whatever you can easily reduce the number of colours with a standard colour quantization algorithm (octree, median cut), but that doesn't quite get you far enough. The Genesis gives you four 16 colour palettes and each 8x8 tile can use one of those palettes. If you reduce the image to 16 colours, you're missing out on an additional 48 shades; but reducing the image to 64 colours won't necessarily organize the colours into four palettes such that each 8x8 block uses only one.

I thought that maybe you could:

1. Reduce each 8x8 tile down to 16 colours, producing n 16-colour palettes, then
2. Split the n palettes up into four groups based on similarity, then merge the palettes in each group into one

The former is the classic colour quantization problem. But the latter is, at least on the face of it, a little trickier? It seems like it's just a higher dimensional version of the colour problem, so maybe you could adapt an existing algorithm to it, but I'm not sure how, exactly, and Google isn't helping. Does anyone know any commonly accepted solutions for this?

[tepples]

This is for still art, such as a title screen, right? Because in a game, you're going to need to reserve some colors for the sprites.

I seem to remember something called "Quither" from the GBA scene.

[tokumaru]

The same happens on the NES, where you have to assign one of four palettes to each 16x16-pixel area. What I've done so far is resize the image to 1/16 its size (on the Genesis you'd do 1/8) using linear interpolation, in order to get the average color of each 16x16-pixel block, and then reduce that image to 4 colors. In theory, that would tell you which regions use similar colors, and thus should use the same palette.

Scale that image back to the original size (nearest neighbor this time) and use the areas covered by each of the four colors as selection masks to convert different parts of the original image separately, one conversion per palette.

On the NES, results are less than spectacular, because the low color count makes the attribute clashes very evident, so it's usually better to handpick the palettes to make attribute transitions less harsh. On the Genesis though, where the attribute areas are smaller (8x8 pixels) and there are way more colors per palette, I'd expect much better results from this straightforward technique.

[adam_smasher]

This is for still art, such as a title screen, right? Because in a game, you're going to need to reserve some colors for the sprites.

I think the principles are the same either way
For gameplay graphics, you could either only use two or three palettes for the backgrounds (or only one palette, which would make things very simple), or include the sprite graphics in with the background graphics, or...

The same happens on the NES, where you have to assign one of four palettes to each 16x16-pixel area. What I've done so far is resize the image to 1/16 its size (on the Genesis you'd do 1/8) using linear interpolation, in order to get the average color of each 16x16-pixel block, and then reduce that image to 4 colors. In theory, that would tell you which regions use similar colors, and thus should use the same palette.

Scale that image back to the original size (nearest neighbor this time) and use the areas covered by each of the four colors as selection masks to convert different parts of the original image separately, one conversion per palette.

On the NES, results are less than spectacular, because the low color count makes the attribute clashes very evident, so it's usually better to handpick the palettes to make attribute transitions less harsh. On the Genesis though, where the attribute areas are smaller (8x8 pixels) and there are way more colors per palette, I'd expect much better results from this straightforward technique.

This is really clever, and I was really excited to try it out, so I threw together a Python script for it and ran it on the classic Lena image...but to be honest the results weren't so hot



From top to bottom, left to right: the original image, the image reduced to 64 colours (a sort of "ideal" Genesis version), the image reduced to 16 colours, and then finally at the right the "tokumaru-reduced" version. All colour-reduction and dithering was the default as performed by PIL. Even with the smaller tile sizes the attribute clash is extremely unsightly; certain regions look better, but given the choice I'd take the 16-colour, dithered version instead.

It's possible - even likely - that the Lena image is particularly unsuited to this kind of transform - it has lots of curves and fine edges, and probably looks better 16-colour dithered than a lot of other images because it's not very, uh, colourful (it's mostly shades of orange and pink). But I wonder if we can't do better...

[tokumaru]

You can see the benefits of giving similarly colored areas their own palette (less banding, better textures, etc.), but the edges where different palettes meet is indeed atrocious. Maybe what we need is to analyze the tiles where different palettes touch so we can force a few colors from one palette into the other. This would make things significantly more complicated.

[tepples]

That or use sprites or layer 2 to cover the transitions between palettes.

[ccovell]

There might be Genesis-specific programs that can help you with this, but since the Gen & PCE/Turbografx-16 are both 9-bit, perhaps one piece of software can help you with ideas:

http://somanybits.com/i2pce/download.html

Though it's not the easiest-to-use or most bug-free piece of software, it does convert high-colour bitmaps (dumbly) down to a # of palettes. The 2nd-to-last tab will let you limit it to 4 palette banks.

The ideal convertor would let you use shadow/highlight overlays to multiply the # of colours that could be achieved in your pic.

Anyway, some other techniques for smoothing out ugliness would be to dither the image before reduction to indexed colours:


I also made some curves for Photoshop that posterize to 9-bit colour with 2 different biases:


http://www.chrismcovell.com/data/PCE_Re ... Curves.zip

You might want to stick with vertical dithering only, since that works best on the Genesis through composite.

[Sik]

Dithering causes problems no matter the pattern, if the color difference is too high then it'll result in severe artifacts, period.

The biggest problem with checkerboard dithering is its notorious tendency to wreck the silhouettes. Vertical dithering was used in large part to reduce the effects from this, not to reduce the amount of artifacts (if anything, they're made worse).