It is currently Fri Dec 15, 2017 2:47 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 8 posts ] 
Author Message
PostPosted: Mon Apr 11, 2016 10:53 am 
Offline

Joined: Sun Mar 27, 2011 10:49 am
Posts: 219
Location: NYC
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?


Top
 Profile  
 
PostPosted: Mon Apr 11, 2016 11:38 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19348
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Mon Apr 11, 2016 11:44 am 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10164
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
PostPosted: Mon Apr 11, 2016 1:58 pm 
Offline

Joined: Sun Mar 27, 2011 10:49 am
Posts: 219
Location: NYC
tepples wrote:
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...

tokumaru wrote:
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 :(

Image

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


Top
 Profile  
 
PostPosted: Mon Apr 11, 2016 3:32 pm 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10164
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
PostPosted: Mon Apr 11, 2016 4:42 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19348
Location: NE Indiana, USA (NTSC)
That or use sprites or layer 2 to cover the transitions between palettes.


Top
 Profile  
 
PostPosted: Mon Apr 11, 2016 6:15 pm 
Offline

Joined: Sun Mar 19, 2006 9:44 pm
Posts: 924
Location: Japan
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:
Image

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

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.

_________________
http://www.chrismcovell.com


Top
 Profile  
 
PostPosted: Tue Apr 12, 2016 10:42 am 
Offline

Joined: Thu Aug 12, 2010 3:43 am
Posts: 1589
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).


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group