How can I split an 8-bit color value into two 4-bit color values?

So I wrote a program that reads in a bitmap and prints into the console using windows.h.

Windows (in the console) allows me to have two colors for each character space - a foreground color, and a background color.

I am limited to the 4 bit palette for these colors :

http://www.infotart.com/blog/wp-content/uploads/2008/06/windows_4bit_color_swatches.png

My program works fine for 16 colors, but I'm having trouble getting 256 figured out. (or figuring out if it's even possible)

I need to take an indexed color's RGB value (from the 256 8bit colors, something like 224, 64, 0) and display it as two of the 16 available colors, with one of them dithered.

The foreground character is going to be one of the ASCII dither characters (176, 177, 178 i think).

So I figure each of the background needs to have R, G, B values of 0, 128, 255, etc and the foreground can be 0, 32, 64, 96, 128, 160, 192, 224, or 255

So if I had the number 开发者_如何学GoRGB = 192,0,0 I could set the background to RGB = 128,0,0 and have the foreground be RGB = 255,0,0 with ASCII character 176 (25% dither)

It seems like this would be pretty simple if I had a separate dither character available for red green and blue individually, but sadly I do not.

I know that the console is an awful choice, but I have to try and do this without the help of the windows gdi.

I'm completely stumped trying to figure out the algorithm for this, and having trouble even seeing if my logic is making any sense.

Anybody able to shed some light on this? all help appreciated, I've hit a wall.

Although this may not be a direct answer about going from a RGB to colored ASCII representation, the 8088 Corruption program may be a good reference to get an idea of approaches that one can take to go from a bitmap image to a CGA screen.

The 8088 Corruption program was designed to run full-motion video with sound on an original IBM PC (Google Video link).

In an explanation of how the video codec was designed (presentation available at archive.org), the creator tried several techniques, one of which was to use the the "ASCII dither characters", but wasn't satisfied with the final quality of the "picture".

So he went on to try a method where he would map multiple pixels into a ASCII character. For example, if there were two lines overlapping perpendicularly, the ASCII character X would be drawn on the screen.

I haven't actually taken a look at the source code (which I believe is written in x86 assembly), but from the descriptions of the techniques used that I've read, it may be something that may be worth taking a look at.

Well, generally, you have to "invent" a mapping from any RGB to your specific subset of colored characters.

Since the exact formula is hard to compute, I would probably stick to a huge precomputed lookup table. Table have to be 3-dimensional (one dimension for R,G,B) and [0..255] in each dimension. Each cell of the table should contain three pieces of information (packed in 2 bytes): the representing character, the foreground color, the background color.

The table should be precomputed in a following manner: for each character that you want to use as output, select each foreground and background color, then compute the resulting RGB mixture of that character displayed with that colors. Then, cell with the given RGB mixture coordinates should be updated with the info of that character and colors.

There will be empty cells, of course, as we have at most only 256*16*16 variations of colored characters for 256^3 colors, so we have to update empty colors with some kind of best nearest filled cells.

Then, for any input pixel we just lookup that table, retrieve the character and the colors, and put them in output.

It's possible to work in an opposite way - compute 256x16x16 table with resulting RGB mixtures, then search it to find a mixture that fits best for the input RGB.

I would suggest reading ImageMagick (Apache 2.0 license) quantization (Color Reduction) document as a starting place. Then you can look at color quantization, of which I believe the most popular two methods used are a median cut method, or using octrees.

You may also prefer to work in a non-RGB color space, such as Lab color space as it has some nice properties, Euclidean distance is more consistent with perceptual difference (Src: Wikipedia).

There are several kinds of dithering, ordered pattern dithering, random dithering, and error-correcting dithering, in this case I believe you want the error-correcting to reduce the apparent color error.

The 4 bit swatches have RGB values, when you mix two of these with a dither character, the RGB values would be a weighted average of each of the separate RGB elements. The weight would depend on the dither pattern used, so for the chequer-board pattern each RGB value would have equal weight, so red+green becomes:

[255,0,0] + [0,128, 0] = [(255+0)/2, (0+128)/2, (0+0)/2] = [127, 64, 0] (a shade of brown)

The weightings for the other patterns would be determined by the proportion of foreground pixels vs background pixels.

Using that to efficiently find a nearest colour is probably the hard part! With three characters, 16 colours and two foreground/background options, there is a large number of combinations, though I imagine there might be large gaps in the gamut. If you only need to translate from a 256 colour palette to one of these combinations rather then from full RGB, then a simple solution would be to write a program to perhaps exhaustively search for a best fit combination of foreground, background, and dither for each of the 256 colours and generate a look-up table that can then be used in the final application to produce a direct lookup.

Of course this fixed look-up table approach would only work is the 256 colour palette is also fixed (which is not necessarily the case). If it is not, then you may need to determine a more efficient method of finding the best match colour. I am sure that it is possible to be smarter than a mere exhaustive search.

As the other answers have already pointed out, the technique to use ASCII shade characters to generate more colors from the 16 base colors is called dithering. Dithering comes at the cost of some image resolution. Also see the legendary 8088 Corruption / 8088 Domination programs.

I'd like to provide you some code on how to find the color pair and dithering shade character algorithmically. The below approach works both in the Windows/linux consoles as well as over SSH and in the Linux Subsystem for Windows.

The general procedure is:

1. scale the source image down to the console resolution
2. map the color of each pixel to the console color that matches best
3. draw block/shade characters with the selected color

As a test image, I use a HSV color map:

At first, here is 16 colors at double vertical resolution. With the block character (char)223 (▀), you can double the vertical resolution by using text/background color to draw the upper and lower half of every character independently. For matching the color, I use the distance vector between the target and the probe color rgb components and brute force test all of the 16 different colors. The function sq(x) returns the square x*x.

int get_console_color(const int color) {
    const int r=(color>>16)&255, g=(color>>8)&255, b=color&255;
    const int matches[16] = {
        sq(r-  0)+sq(g-  0)+sq(b-  0), // color_black      0   0   0   0
        sq(r-  0)+sq(g- 55)+sq(b-218), // color_dark_blue  1   0  55 218
        sq(r- 19)+sq(g-161)+sq(b- 14), // color_dark_green 2  19 161  14
        sq(r- 58)+sq(g-150)+sq(b-221), // color_light_blue 3  58 150 221
        sq(r-197)+sq(g- 15)+sq(b- 31), // color_dark_red   4 197  15  31
        sq(r-136)+sq(g- 23)+sq(b-152), // color_magenta    5 136  23 152
        sq(r-193)+sq(g-156)+sq(b-  0), // color_orange     6 193 156   0
        sq(r-204)+sq(g-204)+sq(b-204), // color_light_gray 7 204 204 204
        sq(r-118)+sq(g-118)+sq(b-118), // color_gray       8 118 118 118
        sq(r- 59)+sq(g-120)+sq(b-255), // color_blue       9  59 120 255
        sq(r- 22)+sq(g-198)+sq(b- 12), // color_green     10  22 198  12
        sq(r- 97)+sq(g-214)+sq(b-214), // color_cyan      11  97 214 214
        sq(r-231)+sq(g- 72)+sq(b- 86), // color_red       12 231  72  86
        sq(r-180)+sq(g-  0)+sq(b-158), // color_pink      13 180   0 158
        sq(r-249)+sq(g-241)+sq(b-165), // color_yellow    14 249 241 165
        sq(r-242)+sq(g-242)+sq(b-242)  // color_white     15 242 242 242
    };
    int m=195075, k=0;
    for(int i=0; i<16; i++) if(matches[i]<m) m = matches[k=i];
    return k;
}

The 16 colors are quite a limitation. So the workaround is dithering, mixing two colors to get better colors at the cost of image resolution. I use the shade characters (char)176/(char)177/(char)178 (Windows) or \u2588/\u2584/\u2580 (Linux); these are represented as (░/▒/▓). In the 12x7 font size that I use, the color mix ratios are 1:6, 2:5 and 1:2 respectively. To find the mixing ratios for your font setting, print the three shade characters in the console, take a screenshot, zoom in and count the pixels.

The three different shade ratios turn the 16 base colors into a whopping 616 colors, not counting duplicates. For matching the closest color, I first mix the colors with the shade character ratios, then compute the distance vector of target to probe rgb color components and brute force this for all probe color combinations. To encode which shade character is used and which two colors are foreground and background colors, I use bit shifting to get it all into one int return value.

int get_console_color_dither(const int color) {
    const int r=(color>>16)&255, g=(color>>8)&255, b=color&255;
    const int red  [16] = {  0,  0, 19, 58,197,136,193,204,118, 59, 22, 97,231,180,249,242};
    const int green[16] = {  0, 55,161,150, 15, 23,156,204,118,120,198,214, 72,  0,241,242};
    const int blue [16] = {  0,218, 14,221, 31,152,  0,204,118,255, 12,214, 86,158,165,242};
    int m=195075, k=0;
    for(int i=0; i<16; i++) {
        for(int j=0; j<16; j++) {
            const int mixred=(red[i]+6*red[j])/7, mixgreen=(green[i]+6*green[j])/7, mixblue=(blue[i]+6*blue[j])/7; // (char)176: pixel ratio 1:6
            const int match = sq(r-mixred)+sq(g-mixgreen)+sq(b-mixblue);
            if(match<m) {
                m = match;
                k = i<<4|j;
            }
        }
    }
    for(int i=0; i<16; i++) {
        for(int j=0; j<16; j++) {
            const int mixred=(2*red[i]+5*red[j])/7, mixgreen=(2*green[i]+5*green[j])/7, mixblue=(2*blue[i]+5*blue[j])/7; // (char)177: pixel ratio 2:5
            const int match = sq(r-mixred)+sq(g-mixgreen)+sq(b-mixblue);
            if(match<m) {
                m = match;
                k = 1<<8|i<<4|j;
            }
        }
    }
    for(int i=0; i<16; i++) {
        for(int j=0; j<i; j++) {
            const int mixred=(red[i]+red[j])/2, mixgreen=(green[i]+green[j])/2, mixblue=(blue[i]+blue[j])/2; // (char)178: pixel ratio 1:2
            const int match = sq(r-mixred)+sq(g-mixgreen)+sq(b-mixblue);
            if(match<m) {
                m = match;
                k = 2<<8|i<<4|j;
            }
        }
    }
    return k;
}

Finally, you extract the shade character and the two colors by bit shifting and bit masking:

const int dither = get_console_color_dither(rgb_color);
const int textcolor=(dither>>4)&0xF, backgroundcolor=dither&0xF;
const int shade = dither>>8;
string character = ""
switch(shade) {
#if defined(_WIN32)
    case 0: character += (char)176; break;
    case 1: character += (char)177; break;
    case 2: character += (char)178; break;
#elif defined(__linux__)
    case 0: character += "\u2591"; break;
    case 1: character += "\u2592"; break;
    case 2: character += "\u2593"; break;
#endif // Windows/Linux
}
print(character, textcolor, backgroundcolor);

The print(...) function is provided here. The resulting image looks like this:

Finally, no asciiart post is complete without the Lenna test image. This shows you what to expect from dithering.