OSDev.org

I have been looking for information about adapting, say, the colors of a 24bpp bitmap to 16 VGA colors, just like in the window manager demo from Alexei Frounze sources.

I have looked for things like

"rgb to vga" algorithm dithering -cable -adapter

in Google but there doesn't seem to be anything useful. So, where or what should I look at? Does the Abrash graphics programming black book have something like this? I didn't seem to find anything in the wiki either.

Things like rotating and OR'ing the bits for color, but I don't know what concepts are being used beyond it has to do with Red Green Blue and (unused) Alpha and adapt them into a VGA color index (right or not?), in the Display/Display.c source file.


Here is that window manager demo which I think is also at Alexei Frounze site, I hope it to be actually downloadable.

http://126.sytes.net/tmp/alexei_winmngrdemo.zip

search for color interpolation

Hi,

~ wrote:I have been looking for information about adapting, say, the colors of a 24bpp bitmap to 16 VGA colors...

It's possibly best to start looking at Floyd-Steinberg dithering.

The basic idea is, for each (24-bit) pixel to find the closest colour (in the 16 colour palette); then find the difference between what you want and what you can have (the error) and then distribute this error to adjacent pixels.

For an example of this, here's my test pattern:



This image was generated from a (calculated) 96-bit per pixel image (32b:32g:32r) and converted to 32-bit per pixel data with Floyd-Steinberg dithering, to be as accurate as possible.

Here's the exact same thing in 4-bits per pixel (standard VGA/CGA 16 colour mode):



Without dithering you get something called "Posterization". For an example of this, here's my test pattern again without any dithering at all:
As you can see it doesn't look like the original test pattern at all, due to the low colour depth used; and even though the dithered image looks "noisy", it looks a lot better.

Also, you can't just combine 2 RGB colours (e.g. anitaliasing, interpolation, etc) and get a correct result, by doing something like "B = B1 + B2; G = G1 + G2; R = R1 + R2;". There's 2 reasons for this. First, RGB has "gamma correction", which means you need to convert the original colour data (with gamma correction) into pure RGB (without gamma correction) then combine the colours, then add the gamma correction to the result.

Secondly, (AFAIK) even if you do take gamma correction into account you can still get colours that don't look right (wrong hue), because the human eye doesn't work in RGB and perceives colours differently. To avoid this I'd convert to CIE XYZ format then combine the colours, then convert back to RGB.

My test pattern code (used to generate the images above) doesn't account for gamma correction or use CIE XYZ, which is probably what is causing those ugly bright greeen dots in the middle of the "green to red" horizontal bar (second horizontal bar from the top) in the "4-bit per pixel dithered" image above.

If you add all of this up, then the correct method would be:

• - convert the original data from RGB with gamma correction to RGB without gamma correction
  - convert the data from RGB without gamma correction to CIE XYZ
  - process the data (including doing Floyd-Steinberg dithering) while it's in CIE XYZ format
  - convert the data from CIE XYZ back to RGB without gamma correction
  - convert the data from RGB without gamma correction to RGB with gamma correction

However, processing time may be a limiting factor here, especially if you're using floating point (or wide fixed point) to avoid precision loss during processing...


Cheers,

Brendan

Brendan wrote:My test pattern code (used to generate the images above) doesn't account for gamma correction or use CIE XYZ, which is probably what is causing those ugly bright greeen dots in the middle of the "green to red" horizontal bar (second horizontal bar from the top) in the "4-bit per pixel dithered" image above.

Could the bright dots be the result of "local overflow / underflow". When distributing the error term during dithering one of the color channels could "get out of synch" with the others since the error terms for each channel can be different. This could maybe explain the bright green dots in the red to green gradient.

The above description is not very clear. I hope you understand what I try to say. Otherwise I could try to make an example with numbers.

To the original poster. If you do not have a fixed palette of colors you should also look at Color quantization and this.

clange

Hi,

clange wrote:

Brendan wrote:My test pattern code (used to generate the images above) doesn't account for gamma correction or use CIE XYZ, which is probably what is causing those ugly bright greeen dots in the middle of the "green to red" horizontal bar (second horizontal bar from the top) in the "4-bit per pixel dithered" image above.

Could the bright dots be the result of "local overflow / underflow". When distributing the error term during dithering one of the color channels could "get out of synch" with the others since the error terms for each channel can be different. This could maybe explain the bright green dots in the red to green gradient.

The above description is not very clear. I hope you understand what I try to say. Otherwise I could try to make an example with numbers.

Oh my...

I know my code checked for overflow (and clamps to 0xFFFFFFFF if overflow occurs), and I assumed it never underflows (thinking that the range of the error would be smaller than the maximum range of a 32-bit integer). I was curious so I looked into it and found that my code is badly messed up. When calculating the error it does underflow, but to make it worse I'm using stuff like "lea esi,[eax*5]" on signed integers to distribute the error to adjacent pixels (which would severely mess things up for any negative number).

I also noticed that for the "no dithering" example I posted there's no dark grey in the left and right grey scales - there should be black, dark grey, light grey and white, but there isn't. That makes me think there's also a problem with the code that tries to find the closest possible colour to the colour I want.

The strange thing is that it looked right to me, especially at higher colour depths.

*sigh*

I'm going to rip it out and rewrite it, and this time I'll add gamma correction to it too...


Thanks,

Brendan

Hi

Just a clarification to my previous post. I have been thinking a bit more about it and can now (hopefully) formulate it better.

Consider the situation where the error for the three channels are like this (min, min, max) where min and max a very small and very large numbers within some range. Stepping along pixel by pixel, this could cause one color channel to change increment (or decrement) in step N and the other color channels in step N+1. With very few bits in each color channel this would be very visible.

I think that the gradients in your test image would make this quite likely to happen - think aliasing. But this is all guesing.

clange

Hi,

clange wrote:I think that the gradients in your test image would make this quite likely to happen - think aliasing. But this is all guesing.

That sounds like what dithering is meant to do...

My problem is that my code was dodgy, which caused the error to be much larger than it should have been. Since then I've converted everything to use signed 32-bit integers for everything, which effectively reduces it to a 93-bit per pixel source image (31r:31b:31g), and replaced my code to find the closest 4-bpp colour with code that loops through each colour to find the colour with the least error (rather than doing a much faster table lookup).

As far as I can tell, my current code is now as perfect as possible. Unfortunately this is the image I get now: The problem now is that for a colour like 100% red, there is no close 4-bpp equivelent, so it chooses light magenta (which looks very ugly), and because that area is meant to be pure red it can't find a pixel with negative blue/green to compensate for the magenta.

I'm guessing that my next step is to use my own palette instead...

Note: I won't be implementing gamma correction - it's very CPU intensive (e.g. "red = pow(red, 2.4); green = pow(green, 2.4); blue = pow(blue, 2.4)") and I'd need some huge (slow) lookup tables to do it with integer maths.


Cheers,

Brendan

Hi,

Brendan wrote:I'm guessing that my next step is to use my own palette instead...

Ok, here's the final result, using 4-bits per pixel and my own ("RGgB") palette:
It looks a lot better to me...


Cheers,

Brendan

Hi again,

I didn't like the grey scale, so I tried a different palette - this time it's a variation of "IRGB" that's similar to the original CGA palette (black, dark grey, light grey and white) but with half saturated and fully saturated colours (e.g. colour 0x01 is 50% blue, while 0x09 is 100% blue without any green or red). Basically I'd call CGA "LRGB" (where the L is lightness, not intensity), while my version is "IRGB" (where I is intensity and not lightness).

Anyway, here it is:
This is probably the best possible test image that can be created with only 16 colours.


Cheers,

Brendan

How easy is it to choose the dithering technique? Post it using the pattern algorithm (I forget the technical name, the one with uniform spacing like #==#==#== instead of =#=#===#=). For gradients I find that sometimes it looks better. Sometimes.

Brendan wrote:Hi again,

I didn't like the grey scale, so I tried a different palette - this time it's a variation of "IRGB" that's similar to the original CGA palette (black, dark grey, light grey and white) but with half saturated and fully saturated colours (e.g. colour 0x01 is 50% blue, while 0x09 is 100% blue without any green or red). Basically I'd call CGA "LRGB" (where the L is lightness, not intensity), while my version is "IRGB" (where I is intensity and not lightness).

Brendan, is your source code at your website or is it something separated, or could you please possibly post it if you think it could be useful to just learn?

By the way, I updated the ZIP archive with a missing file called "Vinca.bmp" that should be in the same directory as WinMngr.exe so that you see how it looks like when converted to 16 colors:

http://126.sytes.net/tmp/alexei_winmngrdemo.zip



It looks something like this when converted, but like 3 times with more dotted green and purple than this (it was saved with Paint, not a screenshot of the actual program):

Hi,

Firestryke31 wrote:How easy is it to choose the dithering technique? Post it using the pattern algorithm (I forget the technical name, the one with uniform spacing like #==#==#== instead of =#=#===#=). For gradients I find that sometimes it looks better. Sometimes.

I took a look at the pictures representing different dithering algorithms on Wikipedia's "Dither" page, and did a little googling, and chose Floyd-Steinberg dithering because it gives good results and is one of the more commonly used algorithms.

~ wrote:Brendan, is your source code at your website or is it something separated, or could you please possibly post it if you think it could be useful to just learn?

The source code is on my web site (here's probably the best starting point), although I wouldn't consider it the cleanest possible implementation - the algorithm is split in half (with a generic half that generates the 96/94-bit per pixel test image and takes care of handling error, and six "colour depth dependent" halves for 4, 8, 15, 16 24 and 32 bpp video modes), was written in a rush (to be honest, it's part of an "interactive boot menu" that I didn't want to write at all), and has since been modified several times...


Cheers,

Brendan

Maybe you could change your dithering functions to be able to choose between different algorithms at runtime. Bayer (ordered, or in Photoshop, pattern) I think tends to work well with smallish GUI images (i.e. the progress bar on the iPod), but it all depends on the colors used and available. I do admit that for actual images like photographs where there aren't many solid or smoothly fading areas that Floyd-Steinberg looks nice. I use Bayer for reducing a 8ARGB PNG to the iPod's 4ARGB format in my iPNG utility. What I should do is make a menu choice so the user can choose whether they want to simply lop off the lower 4 bits of each channel (reasonable for flat colored images), Bayer, or Floyd-Steinberg dithering.

Hi,

Firestryke31 wrote:Maybe you could change your dithering functions to be able to choose between different algorithms at runtime. Bayer (ordered, or in Photoshop, pattern) I think tends to work well with smallish GUI images (i.e. the progress bar on the iPod), but it all depends on the colors used and available. I do admit that for actual images like photographs where there aren't many solid or smoothly fading areas that Floyd-Steinberg looks nice. I use Bayer for reducing a 8ARGB PNG to the iPod's 4ARGB format in my iPNG utility. What I should do is make a menu choice so the user can choose whether they want to simply lop off the lower 4 bits of each channel (reasonable for flat colored images), Bayer, or Floyd-Steinberg dithering.

I haven't seen any images where Floyd-Steinberg dithering hasn't done a good job...

Note: I've spent the last few months building tools, etc for the purpose of converting pictures into (solid and shaded) triangles - if you look closely, all pictures (including photographs) are made up of sold and smoothly fading areas.

The beautiful thing about triangles (as opposed to pixels), is that they're easy to scale, rotate, transform, etc without any loss, and fit well into typical 3D rendering pipelines.

Here's an image that's been converted into triangles, and then converted back into pixels:
Cheers,

Brendan

Brendan, that is amazing. I didn't think it was possible to have such a good image with only 16 colors.

If I turn my eyes slightly out of focus, the image looks exactly like the 32bit one. I'm impressed.