English Amiga Board


Go Back   English Amiga Board > Coders > Coders. General

 
 
Thread Tools
Old 12 April 2011, 02:10   #1
Lord Riton
Registered User
Lord Riton's Avatar
 
Join Date: Jan 2011
Location: France
Age: 45
Posts: 490
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:

Code:
creatColorTable
            move.l    #1,d0      ; color counter
            move.l    #21,d1     ; Red counter
cct02       move.l    #21,d2     ; Green counter
cct03       move.l    #21,d3     ; Blue counter
cct04       PALETTE    vp4,d0,d1,d2,d3,CM
            add.l    #1,d0
    
            add.l    #42,d3
            cmp.l    #255,d3
            bmi.b    cct04
    
            add.l    #42,d2
            cmp.l    #255,d2
            bmi.b    cct03
    
            add.l    #42,d1
            cmp.l    #255,d1
            bmi.b    cct02
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:
Click image for larger version

Name:	023.png
Views:	624
Size:	58.6 KB
ID:	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:
Click image for larger version

Name:	024.png
Views:	453
Size:	76.0 KB
ID:	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:
Click image for larger version

Name:	026.png
Views:	427
Size:	55.2 KB
ID:	28391

With the first , simplier algorithm, these green pixels aren't there:
Click image for larger version

Name:	025.png
Views:	414
Size:	45.2 KB
ID:	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:
Click image for larger version

Name:	027.png
Views:	462
Size:	68.9 KB
ID:	28392

and with the advanced algorithm:
Click image for larger version

Name:	028.png
Views:	487
Size:	86.7 KB
ID:	28393

Last edited by Lord Riton; 12 April 2011 at 02:40.
Lord Riton is offline  
AdSense AdSense  
Old 12 April 2011, 03:08   #2
Leffmann

 
Join Date: Jul 2008
Location: Sweden
Posts: 2,029
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:

Code:
advanced algorithm      Floyd-Steinberg

      0 0 0                  0 0 0

      0 0 1                  0 0 7

      0 1 0                  3 5 1
Leffmann is offline  
Old 12 April 2011, 05:15   #3
Lord Riton
Registered User
Lord Riton's Avatar
 
Join Date: Jan 2011
Location: France
Age: 45
Posts: 490
Quote:
Originally Posted by Leffmann View Post
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.
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 ?


Quote:
Originally Posted by Leffmann View Post
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...
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.

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

Code:
advanced algorithm      Floyd-Steinberg

      0 0 0                  0 0 0

      0 0 1                  0 0 7

      0 1 0                  3 5 1
This is very good info you gave me here, thanks a lot, will try to use these values
Lord Riton is offline  
Old 12 April 2011, 06:50   #4
Codetapper
2 contact me: email only!

Codetapper's Avatar
 
Join Date: May 2001
Location: Auckland / New Zealand
Posts: 3,135
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!
Codetapper is offline  
Old 12 April 2011, 12:46   #5
Kalms
Registered User
 
Join Date: Nov 2006
Location: Stockholm, Sweden
Posts: 165
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.
Kalms is offline  
Old 14 April 2011, 06:28   #6
Leffmann

 
Join Date: Jul 2008
Location: Sweden
Posts: 2,029
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.
Attached Thumbnails
Click image for larger version

Name:	adaptive_nearest.png
Views:	594
Size:	108.2 KB
ID:	28432   Click image for larger version

Name:	default_50-50.png
Views:	371
Size:	83.3 KB
ID:	28434   Click image for larger version

Name:	adaptive.png
Views:	409
Size:	361.3 KB
ID:	28435   Click image for larger version

Name:	default.png
Views:	379
Size:	228.3 KB
ID:	28436   Click image for larger version

Name:	rgb.png
Views:	441
Size:	157.9 KB
ID:	28437  

Leffmann is offline  
Old 14 April 2011, 18:44   #7
pandy71
Registered User
 
Join Date: Jun 2010
Location: PL
Posts: 1,546
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
pandy71 is offline  
Old 14 April 2011, 19:07   #8
Lord Riton
Registered User
Lord Riton's Avatar
 
Join Date: Jan 2011
Location: France
Age: 45
Posts: 490
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
Lord Riton is offline  
Old 14 April 2011, 20:03   #9
Thorham
Computer Nerd

Thorham's Avatar
 
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 41
Posts: 2,972
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.
Thorham is offline  
Old 14 April 2011, 20:23   #10
khph_re
Registered User
 
Join Date: Feb 2008
Location: Northampton/UK
Posts: 245
@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.
khph_re is offline  
Old 15 April 2011, 02:56   #11
Lord Riton
Registered User
Lord Riton's Avatar
 
Join Date: Jan 2011
Location: France
Age: 45
Posts: 490
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.
Lord Riton is offline  
Old 15 April 2011, 13:52   #12
khph_re
Registered User
 
Join Date: Feb 2008
Location: Northampton/UK
Posts: 245
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
khph_re is offline  
Old 15 April 2011, 14:20   #13
korruptor
TDI
korruptor's Avatar
 
Join Date: Feb 2007
Location: DUNDEE
Posts: 122
I've seen a couple of people from here on TCE... Not so much amiga hacking though
korruptor is offline  
Old 15 April 2011, 14:40   #14
vidarh
Registered User
 
Join Date: Sep 2010
Location: Croydon, UK
Posts: 46
Quote:
Originally Posted by Lord Riton View Post
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
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.
vidarh is offline  
Old 15 April 2011, 15:16   #15
khph_re
Registered User
 
Join Date: Feb 2008
Location: Northampton/UK
Posts: 245
Quote:
Originally Posted by vidarh View Post
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).
khph_re is offline  
Old 15 April 2011, 16:50   #16
Lord Riton
Registered User
Lord Riton's Avatar
 
Join Date: Jan 2011
Location: France
Age: 45
Posts: 490
Quote:
Originally Posted by khph_re View Post
@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.
Lord Riton is offline  
Old 15 April 2011, 17:04   #17
khph_re
Registered User
 
Join Date: Feb 2008
Location: Northampton/UK
Posts: 245
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.
khph_re is offline  
Old 15 April 2011, 17:24   #18
Lord Riton
Registered User
Lord Riton's Avatar
 
Join Date: Jan 2011
Location: France
Age: 45
Posts: 490
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
Lord Riton is offline  
Old 15 April 2011, 18:25   #19
Thorham
Computer Nerd

Thorham's Avatar
 
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 41
Posts: 2,972
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.
Thorham is offline  
Old 15 April 2011, 18:49   #20
Lord Riton
Registered User
Lord Riton's Avatar
 
Join Date: Jan 2011
Location: France
Age: 45
Posts: 490
Quote:
Originally Posted by Thorham View Post
You should realize that hires in 8 bits per pixel is very slow.
I know that


Quote:
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).
I said this already, (see above).


Quote:
Seeing how HAM8 can be reasonably well calculated for about 100 cycles per pixel (68030), correcting only the edges may be fast enough.
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..



Quote:
Again, 256 color hires is very slow,
Not slower than ham8 hires (ham8 lores does not make great pictures).


Quote:
and Floyd Steinberg dithering isn't particularly fast, either, and I'm almost certain that pre-rendered HAM graphics+edge correction will be faster.
The floyd Steinberg rendering is not something i would use in real time, it will apply to the bitmap graphics at their creation.
Lord Riton is offline  
AdSense AdSense  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Color Saturation and Color Tint/Hue Retro-Nerd support.WinUAE 19 28 August 2017 10:06
Printing in color with WinUAE on color laser source support.Apps 7 14 April 2013 01:32
Color difference Leandro Jardim support.WinUAE 3 16 November 2012 09:51
shapeshifter - 8bit(256 color mode) pbareges support.Apps 1 07 October 2006 21:41
New 256 color backgrounds in the Zone ! DoomMaster support.Apps 0 09 October 2004 11:35

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 10:58.


Powered by vBulletin® Version 3.8.8 Beta 1
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Page generated in 0.24104 seconds with 13 queries