ISO true color to 256 color algorithm
 

Hello,

I'm trying to transform 24 bit color images into 256 color images.

I have a fixed palette of 255 colors as restriction which cannot be changed (it's for a game and i need to have several different bitmaps on the screen at the same time)

Just in case of anyone interested into the actual color palette, i creat it like that:

It creats a 216 color entry table, with 6 values of red, green and blue, all mixed up.

I add to that a 32 color table with only gray , from white to black), and that's pretty much it.

I have created 2 algorithms to convert 24 bit images into 256 color images using this palette above.
- One normal algorithm that simply chooses the color from the 256 color table that is closest to the actual 24 bit color pixel at it's same place. this doesn't give great results, here is an exemple of the conversion:
Attachment 28388


- One other algorithm that affter choosing the closest color pixel does compute the difference between the color it picked up and the color it actually should have been, and gives that diff passed to the next right and the next botom pixel (each get a half of the value). This gives much better conversion, but not always, here also an exemple with that algorithm:
Attachment 28389


But sometimes with the 2nd algorithm i get some unwanted color particles in the picture that were never there, like that one, with some green pixels into the gray wall:
Attachment 28391

With the first , simplier algorithm, these green pixels aren't there:
Attachment 28390


I tryed to look on the internet for the best algorithm, but always only found some algorithm that computes the palette new, and that i don't want, i need the conversion to be done with my actual choosen palette.

Does anyone have the "right" algorithm that would make the pictures look a lot better ? that would be great, thanks in advance :)


Edit:

Here is another picture showing better the difference of quality of the 2 algorithms.

This with the simple algorithm:
Attachment 28392

and with the advanced algorithm:
Attachment 28393

The green and red are always more pronounced than blue, and typically you want more red shades than blue, and even yet more green shades. You could try with f.ex 32 grays + 7 red * 8 green * 4 blue = 256 colors.

If it's not a problem to select a different fixed palette then you might find a better one quickly by putting all your graphics in one large image and letting f.ex Photoshop dither the image to 256 colors, and trying the resulting palette, and then you could also benefit from Photoshop using a different color model and color space which is more suited for this.

Also, did you try Floyd-Steinberg dithering? It is based around an error diffusion just like your advanced algorithm, but uses a larger kernel:

Am not sure if only 4 "blues" would be better, but will try it. Or why would they not have done about the same with 16 bit 565 (red5, green6, blue5) mode ?


Already tought about this, but this would force me to redoo the palette each time i added a new object or other graphic to the game, also each time all other objects would lose a bit of their "beauty" because they get less colors declined from them.

This is very good info you gave me here, thanks a lot, will try to use these values :)

Just something I have noticed - Photoshop (version 7 and CS2) seem to be absolutely lousy at selecting a good mix of 256 colours, even when you choose Selective, Perceptive etc.

I find that PPaint 7 on the Amiga picks a far better range of colours when reducing an image. I'm not sure what algorithm it uses but I've always been impressed by PPaint due to this!

You don't need to redo the palette every time you add a new image. Just stitch together a large amount of images which you think are 'representative'. Then quantize that down to 256 colors. Then use that palette for all your current and future needs.
That has a chance to look better than your generated palette.

You may need to add 100% black and 100% white (and/or other key colors) though.

Been playing with this a bit and have come up with a pretty ok color quantization algorithm.

Basically for each pixel in the image I find the color in the current palette which has the shortest euclidean distance to the color of the current pixel, and move this palette color and the two adjacent colors slightly towards that of the current pixel. It's similar to the NeuQuant algorithm but much simpler and doesn't give as good results. I haven't tried the oct-tree algorithm but it will probably give better results as well.

The images show some tests with the default palette of 32 grays + 6*6*6 colors compared to an adapted palette.

use this plugin http://www.ximagic.com/q_index.html to create optimal palette - for 256 colors NeuQuant, for lower especially for 16 o 32 colors go for painfully slow however exceptionally good SColorQ

Ok, i see now that an adaptative palette is much better, but still, i don't like the idea that as more different items with different colors i add to the game, as worse will be the palette, imagine i wanted to add 100 of monsters and other items ;)

That's a sucky limitation you've set for yourself there, because there really isn't a palette that suits all possible images in the best way. It's a big limitation of indexed color modes, and you'll always end up with compromises, although a good palette with Floyd Steinberg dithering will still look quite reasonable regardless of the number of different colors, but the palette has to be universal.

Ultimately, you have to ask yourself if there's absolutely no way in which you can use HAM6 or HAM8. If you can somehow render properly and fast in those modes, then you can get rid of that indexed limitation.

Anyway, what is it you want to use this for? There are ways to use HAM modes in 1x1 pixel resolution without having to calculate every pixel, so it may be a serious option.

@Lord Riton
I thought you were already converting to HAM8?

The other solution is too have a base 'level' palette, but leave a section of palette open for your monsters.

Then you could also base your monster graphics around the palette rather than the other way around. You can also load a palette for each level.
You would need specially drawn/rendered monsters for best results. Bringing in random art that does not have your palette in mind will never work all that well.

If you want to free up some colours, put your control panel down the bottom, and do a palette switch when you get to it, that way it won't steal colours from the game graphics.

Things get quite convoluted in a palette based world, if you can avoid it, all the better (although I strangely enjoy it,up to a point).

Did a game on the DS where the characters had a partial shared palette, but hundreds of outfits...bleedin' nightmare!

Really, you'll end up in a world of hurt once you get into colour ramps, and tinted grey substitute colours.

Ham8 is not fast enough for that new game i want to do.
But i'm pretty sure it can look as good as ham8 in 256 colors. The floyd Steinberg gives me rather good results, and this in 320X256. I think it should be even better in 640X256.
I have the idea to try something that might even work better than floyd-Steinberg. Especially in 640X256 i could simply use 2 pixels (in 640X256) that represents one pixel of the 320X256 source image, so the first of these 2 will be the closest color to the source pixel, and the 2nd would be a pixel that with the first together would make an averadge wich is closest to the real 320X256 pixel. It's a sort of floyd Steinberg method, but that only "spreads" the error on the same line, taking adventage of the 640X256 mode.

Sounds really interesting. Not many games running at hires.
Leffmans quantization results look like a good starting point. You won't have to worry so much about all the crap I posted then :)

@Kalms
Are you posting on TheChaosEngine as well as here? The two sites look the same, and i'm getting confused which tab i'm in ;)

I've seen a couple of people from here on TCE... Not so much amiga hacking though :(

Any reason why you're not specifically drawing your graphics to suit the palette restrictions? Colour reduction like that will always look sucky compared to graphics that's manually designed or at least manually adjusted to fit the restrictions.

Exactly what I said, but I guess Lord Riton is not a graphician, so it's probably easier to start off with one decent palette. Until he can get hold of an artist.

@lord Riton
I thought HAM8 and 256 colour were both 8bit, and therefore exactly the same speed to convert? (you'll have to excuse my ignorance, I don't code).

You don't have to convert anything with 256 colors.
Ham8 does only change one of the 3 rgb components each pixel, keeping the other 2 from the previous left pixel. Therefore you have to choose a simple representation where you altern each rgb component affter each pixel, then you don't have to convert anything also. But that method doesn't look great. A better looking method is to look wich one of the 3 rgb components is furthest away from the real color, and then set this one. But this does only work if you don't draw something else over your picture, because with this method you could have several pixels aligned that do not change one of the rgb component, or even that only alters one, so if you write a pixel in between such a serie of pixels, the pixels affter the one you wrote are altered and probably all get the wrong color. You have to "fix " the pixels with this method what can take a lot of cpu time, depending of the amount of pixels that you have to fix.

Is there no ham algorithm that gets around this? I know bill williams had multi scrolling ham games with no fringing (pioneer plague etc), and a set palette. I don't know how he did it though, if it could be figured out, might give you a few more colours to play with.

If there was an easy way to create games in ham8, then i guess we would have seen all AGA games using ham8, why bother with 256 colors if you can have more ? ;)

Best way for good ham8 scrolling is to do like if the screen had only 1/3 of the pixels in X (Horizontal), so one pixel would in fact be 3 pixels together where we change all 3 rgb components at the same time. Thats the way i did it in QON, looks rather ok if using Hires, and rather bad when using Lores. I'm pretty sure it can look as good with 256 colors and Hires mode, that's why i started this thread, to find out :p

You should realize that hires in 8 bits per pixel is very slow. The reason I mentioned HAM is that you can pre-render your graphics in HAM, and then just correct the edges when you write them to the screen. This means that you have to calculate far fewer HAM pixels than normal (where every pixel is calculated).

Seeing how HAM8 can be reasonably well calculated for about 100 cycles per pixel (68030), correcting only the edges may be fast enough.

Again, 256 color hires is very slow, and Floyd Steinberg dithering isn't particularly fast, either, and I'm almost certain that pre-rendered HAM graphics+edge correction will be faster.

I know that ;)


I said this already, (see above).


It's not only the edges, but every bitmap that has transparent pixels need to get a fix too. Maybe it could be fast enough, maybe not..



Not slower than ham8 hires (ham8 lores does not make great pictures).


The floyd Steinberg rendering is not something i would use in real time, it will apply to the bitmap graphics at their creation.