color reduction tool

by **rcp** » Dec 11, 2005 @ 9:21am

StephC's code on the previous page didn't work for me. In some situations it would dither, in others it didn't. It took some time, but I finally noticed that my MS compiler was reading the code differently than was I. The 'bug' for me was the order in the evaulation. if(dither < Red&15). The compiler saw this as if((dither < Red)&15) while it was meant to be if(dither < (Red&15)). I am not sure what compiler StephC was using, but the MS compilers don't like this. I modified the code and made another adjustment in the dither value for 12 bit cases.

Code: Select all

1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
31 
32 
33 
34 
35 
36 
37 
38 
39 
u32 dither4[4][4] = { {0, 4, 1, 5}, {6, 2, 7, 3}, {1, 5, 0, 4}, {7, 3, 6, 2} };

u16 Dither16(u32 x, u32 y, u32 Red, u32 Green, u32 Blue)
{
    u32 dither;
    u32 pRed, pGreen, pBlue;

    dither = (dither4[y&3][x&3]+0);

    pRed = Red >>3;
    pGreen = Green>>2;
    pBlue = Blue >>3;

    if((dither < (Red&7)) && pRed < 31) { pRed = pRed++; }
    if((dither < (Green&3)) && (pGreen < 63)) { pGreen = pGreen++; }
    if((dither < (Blue&7)) && pBlue < 31) { pBlue = pBlue++; }

    return (pBlue << 11) | (pGreen << 5) | (pRed );
}

u16 Dither12(u32 x, u32 y, u32 Red, u32 Green, u32 Blue)
{
    u32 dither;
    u32 pRed, pGreen, pBlue;


    dither = 2*(dither4[y&3][x&3]+1);

    pRed = Red >>4;
    pGreen = Green>>4;
    pBlue = Blue >>4;

    if((dither < (Red&15)) && pRed < 15) { pRed = pRed++; }
    if((dither < (Green&15)) && (pGreen < 15)) { pGreen = pGreen++; }
    if((dither < (Blue&15)) && pBlue < 15) { pBlue = pBlue++; }

    return (pBlue << 12) | (pGreen << 7) | (pRed<<1 );
}

39 lines; 8 keywds; 48 nums; 236 ops; 0 strs; 0 coms    Syntactic Coloring v0.4 - Dan East

Here is a frame from our movie. "NoDither.jpg" is in 12 bits with no dither, and "Dither.jpg" is using StephC's algorithm. The results are more than good enough for a movie and the performance hit is minimal. Nice job StephC!

by **StephC** » Dec 11, 2005 @ 1:28pm

Hi !

Nice to see my code used..

You can improve it a bit (speed) by storing the dither table in two 32bits constants and access it with shifts and mask instead of memory access.

If you need realtime performance it is also possible to unroll the loop and not use any dither table at all.

by **torus** » Dec 16, 2005 @ 3:38pm

Just in case someone is interested:

I calculated some highres (16*16) ditherkernels some years ago. They don't create the ugly aliasing artifacts that you get when you scale an image that was dithered with a 4*4 or 2*2 ordered dither kernel.

There's a seperate table for each color-channel which improves the visual quality for monocromatic and almost desaturated images quite a lot.

Imho the results of these tables are excellent. It's almost plug and play to replace a 4x4 matrix with these tables. Just change the mask and scale the entries to your bitdepth.

Code: Select all

1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
31 
32 
33 
34 
35 
36 
37 
38 
39 
40 
41 
42 
43 
44 
45 
46 
47 
48 
49 
50 
51 
52 
53 
54 
55 
56 
static unsigned char dithertab_r[16][16] =
{{192, 11,183,125, 26,145, 44,244,  8,168,139, 38,174, 27,141, 43},
 {115,211,150, 68,194, 88,177,131, 61,222, 87,238, 74,224,100,235},
 { 59, 33, 96,239, 51,232, 16,210,117, 32,187,  1,157,121, 14,165},
 {248,128,217,  2,163,105,154, 81,247,149, 97,205, 52,182,209, 84},
 { 20,172, 80,140,202, 41,185, 55, 24,197, 65,129,252, 35, 70,147},
 {201, 63,189, 28, 90,254,116,219,137,107,231, 17,144,119,228,109},
 { 46,245,103,229,134, 13, 67,162,  6,170, 47,178, 76,193,  4,167},
 {133,  9,159, 54,175,124,225, 93,242, 79,214, 99,241, 56,221, 92},
 {186,218, 78,208, 37,196, 25,188, 42,142, 29,158, 21,130,156, 40},
 {102, 31,148,111,234, 85,151,120,207,113,255, 86,184,212, 69,236},
 {176, 73,253,  0,138, 58,249, 71, 10,173, 62,200, 50,114, 12,123},
 { 23,204,118,191, 91,181, 19,164,216,101,233,  3,135,169,246,152},
 {223, 60,143, 48,240, 34,220, 82,132, 36,146,106,227, 30, 95, 49},
 { 83,166, 18,199, 98,155,122, 53,237,179, 57,190, 77,195,127,180},
 {230,108,215, 64,171,  5,206,161, 22, 94,251, 15,153, 45,243,  7},
 { 72,136, 39,250,104,226, 75,112,198,126, 66,213,110,203, 89,160}};


static unsigned char dithertab_g[16][16] =
{{184, 63,169, 99,204, 70,111,179, 62,231,101,206,132, 85,237,109},
 {125,226, 27,246, 42,163, 31,251,140, 21,174, 35,223, 43,143,  8},
 {200, 40,113,137,191, 86,198,124, 79,215,105,151, 93,192,168, 75},
 { 90,149,182, 69, 11,238, 58,  4,167, 50,242, 12,253, 59, 24,232},
 { 54,248, 16,220,157, 96,130,227, 88,186,126, 73,162,118,216,138},
 {175,102,205,117, 47,209,172, 37,202, 18,146,211, 32,194, 82,  7},
 {131, 38, 78,144,254, 25, 71,150,114,236, 64,107,228, 49,156,240},
 {197,110,187,  1,161,106,180,247, 92, 44,183,  2,127,177, 95, 28},
 { 67,234, 56,218, 83,229, 52, 14,139,222, 81,160,249, 61,208,123},
 {152, 19,165,128, 30,135,195,116,171, 23,201,100, 34,141, 15,244},
 { 46,224, 72,207, 98,243, 66,214, 57,255, 68,190,119,217,166, 89},
 {136,115,178,  9,189, 36,158,  6,103,148,129, 10,233, 41, 74,185},
 {230, 33, 94,252,142,122, 76,239,181, 29,219, 87,153,112,203,  5},
 {104,196,154, 60, 48,212,164, 45,108,199, 53,170, 26,250, 55,145},
 {241, 22, 84,221,173, 20, 91,225,134, 80,245,121,188, 97,176, 77},
 { 51,210,133,  3,120,235,147, 13,193, 39,155,  0, 65,213, 17,159}};


static unsigned char dithertab_b[16][16] =
{{ 23,233,121,159, 89,149, 46, 82,157,122, 24,150, 52,226, 61,143},
 {170, 49,205, 32,215, 20,248,169, 37,232, 98,245,128, 33,182,102},
 {200,131, 93,176,109,183,132, 14,197, 66,190,  5,209, 79,238, 13},
 { 69,250,  7, 71,229, 53, 96,237,116,145, 87,165, 44,141,120,160},
 { 38,114,189,153, 29,139,191, 76, 31,224, 55,254,104,204, 28,223},
 {138,231, 60,208, 84,253,  2,162,211,123,179, 17,152, 67,174, 97},
 { 78, 19,167,126,103, 47,203,108, 62, 10,134,218, 81,241,  1,213},
 {196,148,246, 12,220,173, 73,155,243,185,100, 50,194,110,156, 56},
 {119, 88, 43,112,144, 34,234, 22, 91, 36,249,140, 21,228, 40,181},
 { 26,217,127,236, 59,201,135,117,193,124,166, 63,177, 74,133,251},
 {161, 51,186,  4,178, 94, 15,225, 48,214,  6,235, 95,206,  8, 86},
 { 99,199, 68,151, 80,255,164, 70,147, 85,158,107, 30,146,221,171},
 {227, 16,242,115,210, 39,105,188, 27,202, 58,180,240,118, 35, 64},
 {106,154, 41,175, 25,142,239, 65,230,130,252, 42,136, 72,192,129},
 { 45,212,137, 75,195,101,  0,172,113, 11, 92,168, 18,216,  3,247},
 {187, 83,  9,244, 57,222,125,207, 54,219,184, 77,198,111,163, 90}};

56 lines; 9 keywds; 774 nums; 885 ops; 0 strs; 0 coms    Syntactic Coloring v0.4 - Dan East

by **Phantom** » Dec 16, 2005 @ 4:44pm

Is there a reason for not using PocketHAL? It does dithering on the fly, if I'm correct, and fixes a lot of other hardware dependencies for you.

by **torus** » Dec 16, 2005 @ 5:06pm

Don't know. I haven't ever checked PocketHAL.

Maybe you want to process your assets before you use them? or you can't use PocketHAL for a reason Different/multiple platform maybe?.

by **torus** » Dec 16, 2005 @ 5:09pm

Uh. did I already mentioned that ordered dithering sucks when you do do multiple additive blending passes?

by **StephC** » Dec 16, 2005 @ 9:15pm

I tried your 16*16 dither kernel and the results are quite good

But IMHO they are not much better than a simpler 4*4 kernel (for static images).

I've attached a comparison image.

by **torus** » Dec 16, 2005 @ 10:44pm

You've tried how it looks after minification? The real difference becomes visible when you rotatate/scale/animate the image.

by **rcp** » Dec 17, 2005 @ 9:36pm

Hmm... very good point. Thanks for posting this comparision (and your 16x16 constants).

by **torus** » Feb 6, 2006 @ 11:26pm

Sorry for raising the old thread from the dead, but I wrote dithering today, and I'm a bit confused. My dithering algorithm looks different, and the results are also different (imho a bit better).

Here's the significant code. I use the dithertables I've posted earlier in this thread.

If you examine the different results (yours and mine) you can see banding in your version that is dithered in mine.

Now I wonder which version is more correct. I'm totally unsure..

Code: Select all

1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
31 
32 
33 
34 
35 
unsigned char temp[240*320*3];

int main (void)
{
  FILE *f = fopen ("c:/dithertest.raw","rb");
  fread (temp, 320*240*3,1,f);
  fclose (f);

  int a=0;
  for (int y=0; y<320; y++)
  for (int x=0; x<240; x++,a++)
  {

    int r = temp[a*3+0] + (rtab[y&15][x&15]>>4);
    int g = temp[a*3+1] + (gtab[y&15][x&15]>>4);
    int b = temp[a*3+2] + (btab[y&15][x&15]>>4);

    if (r >=255) r = 0xf0; else r = r & 0xf0;
    if (g >=255) g = 0xf0; else g = g & 0xf0;
    if (b >=255) b = 0xf0; else b = b & 0xf0;

    // convert back to 888 (bit replication)
    r = r | (r>>4);
    g = g | (g>>4);
    b = b | (b>>4);

    temp[a*3+0] = r;
    temp[a*3+1] = g;
    temp[a*3+2] = b;
  }

  f = fopen ("c:/dithertest2.raw","wb");
  fwrite (temp, 320*240*3,1,f);
  fclose (f);
 }
35 lines; 19 keywds; 49 nums; 182 ops; 4 strs; 1 coms    Syntactic Coloring v0.4 - Dan East

by **torus** » Feb 6, 2006 @ 11:43pm

Nevermind, folks.

The first dithering was in 565. That's the reason why I saw banding.

Here's my innerloop code for 565 case. Just in case someone is still interested (who knows)

Code: Select all

1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
 int r = temp[a*3+0] + (rtab[y&15][x&15]>>5);
 int g = temp[a*3+1] + (gtab[y&15][x&15]>>6);
 int b = temp[a*3+2] + (btab[y&15][x&15]>>5);

 if (r >=255) r = 0xf8; else r = r & 0xf8;
 if (g >=255) g = 0xfc; else g = g & 0xfc;
 if (b >=255) b = 0xf8; else b = b & 0xf8;

  // convert back to 888 (bit replication)
  r = r | (r>>5);
  g = g | (g>>6);
  b = b | (b>>5);
12 lines; 9 keywds; 27 nums; 99 ops; 0 strs; 1 coms    Syntactic Coloring v0.4 - Dan East

by **yeetoo** » Apr 25, 2006 @ 2:13am

Would you tell me the code editor's name which one is your using? it's looks very beautiful.

StephC wrote:So, I've made an implementation of ordered dithering for 16 and 12bits :

This may be useful to generate smooth gradients etc..

Enjoy

Code: Select all
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 Uint32 dither4[4][4] = { {0, 4, 1, 5}, {6, 2, 7, 3}, {1, 5, 0, 4}, {7, 3, 6, 2} }; PIXEL Dither16(Uint32 x, Uint32 y, Uint32 Red, Uint32 Green, Uint32 Blue) { Uint32 dither; Uint32 pRed, pGreen, pBlue; dither = dither4[y&3][x&3]; pRed = Red >>3; pGreen = Green>>2; pBlue = Blue >>3; if((dither < Red&7) && pRed < 31) { pRed = pRed++; } if((dither < Green&3) && pGreen < 63) { pGreen = pGreen++; } if((dither < Blue&7) && pBlue < 31) { pBlue = pBlue++; } return (pRed << 11) | (pGreen << 5) | (pBlue ); } ///////////////////////////////////////////////////////////////////////////////// PIXEL Dither12(Uint32 x, Uint32 y, Uint32 Red, Uint32 Green, Uint32 Blue) { Uint32 dither; Uint32 pRed, pGreen, pBlue; dithy = y & 0x3; dithx = x & 0x3; dither = 2*dither4[y&3][x&3]; pRed = Red >>4; pGreen = Green>>4; pBlue = Blue >>4; if((dither < Red&15) && pRed < 15) { pRed = pRed++; } if((dither < Green&15) && pGreen < 15) { pGreen = pGreen++; } if((dither < Blue&15) && pBlue < 15) { pBlue = pBlue++; } return (pRed << 12) | (pGreen << 7) | (pBlue<<1 ); } 43 lines; 8 keywds; 48 nums; 220 ops; 0 strs; 1 coms Syntactic Coloring v0.4 - Dan East

PS : isn't "code" section buggy ? (I use Opera)

by **ET3D** » Oct 19, 2010 @ 12:15pm

I came across this old post looking for some simple dithering code, and just figured that I'll correct two things in StephC's code (rcp's version). The first is that a single dither value is used to compare to all components, but they are different size for the 565 version, so green will be dithered incorrectly. The second is just to point out that "pRed++" means "add 1 to pRed", so there's no need to assign the result to pRed.

So the code for the 565 version is:

Code: Select all

1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
u32 dither4[4][4] = { {0, 4, 1, 5}, {6, 2, 7, 3}, {1, 5, 0, 4}, {7, 3, 6, 2} };

u16 Dither16(u32 x, u32 y, u32 Red, u32 Green, u32 Blue)
{
    u32 dither;
    u32 pRed, pGreen, pBlue;

    dither = dither4[y&3][x&3];

    pRed = Red >>3;
    pGreen = Green>>2;
    pBlue = Blue >>3;

    if((dither < (Red&7)) && pRed < 31) { pRed++; }
    if(((dither>>1) < (Green&3)) && (pGreen < 63)) { pGreen++; }
    if((dither < (Blue&7)) && pBlue < 31) { pBlue++; }

    return (pBlue << 11) | (pGreen << 5) | (pRed );
}
19 lines; 4 keywds; 32 nums; 130 ops; 0 strs; 0 coms    Syntactic Coloring v0.4 - Dan East

by **Dan East** » Oct 19, 2010 @ 10:37pm

In that case dither should be shifted left, not right.

color reduction tool

Re: color reduction tool

Re: color reduction tool

Sort

Forum Description

Moderators:

Forum permissions

`1 2 3 4 5 6 7 8 9 10 11 12`	`int r = temp[a3+0] + (rtab[y&15][x&15]>>5); int g = temp[a3+1] + (gtab[y&15][x&15]>>6); int b = temp[a*3+2] + (btab[y&15][x&15]>>5); if (r >=255) r = 0xf8; else r = r & 0xf8; if (g >=255) g = 0xfc; else g = g & 0xfc; if (b >=255) b = 0xf8; else b = b & 0xf8; // convert back to 888 (bit replication) r = r \| (r>>5); g = g \| (g>>6); b = b \| (b>>5);`
	12 lines; 9 keywds; 27 nums; 99 ops; 0 strs; 1 coms Syntactic Coloring v0.4 - Dan East