dclaar@hpcupt1.HP.COM (Doug Claar) (09/30/89)
I have seen articles discussing the ability of a black and white device to simulate shades of gray via dithering, but nothing about color dithering. I have a 1024x768 6 plane display, upon which it seems I could display a picture of 512x384 with a greater number of apparent colors by some sort of 2x2 dithering. Can anyone give me a reference on this, or advice, clues, something-already-written-in-c? Thanks, Doug Claar HP Computer Systems Division UUCP: mcvax!decvax!hplabs!hpda!dclaar -or- ucbvax!hpda!dclaar ARPA: dclaar%hpda@hplabs.HP.COM
jchristy@hpspcoi.HP.COM (Jim Christy) (10/02/89)
Color dithering is a simple extension of mono dithering. You simply dither each color component separately before combining them to create your final pixel value (index into your color lookup table [LUT]). In other words, treat each color channel as you would a gray-scale. Then dither using any favorite dithering technique. Foley and Van Dam discuss this in some detail in Fundamentals of Interactive Computer Graphics. It helps if you divide your color LUT uniformly among all three primaries. Then your pixel value (LUT index) encodes what color you will actually get. In your case, divide your 6-bit pixels into 2 bits of red, 2 bits of green, and 2 bits of blue. Now program your color LUT based on this ordering. After dithering each color component, you get a value between 0 and 3 for each of red, green and blue. Now form your final pixel value by shifting these numbers the appropriate number of places and ORing them together. jhc
stephens@cell.mot.COM (Kurt Stephens) (10/11/89)
In article <6350007@hpcupt1.HP.COM>, dclaar@hpcupt1.HP.COM (Doug Claar) writes: > I have seen articles discussing the ability of a black and white device > to simulate shades of gray via dithering, but nothing about color dithering. > > I have a 1024x768 6 plane display, upon which it seems I could display a > picture of 512x384 with a greater number of apparent colors by some sort of > 2x2 dithering. Can anyone give me a reference on this, or advice, clues, > something-already-written-in-c? > > Thanks, > > Doug Claar > HP Computer Systems Division > UUCP: mcvax!decvax!hplabs!hpda!dclaar -or- ucbvax!hpda!dclaar > ARPA: dclaar%hpda@hplabs.HP.COM I wrote some thing for a Sun cgone frame buffer, which can take 24-bit RGB color values and ordered dithers them into LUT indexes. The cgone uses a 8-bit LUT which maps into a 24-bit RGB value. I partitioned the 8-bit pixel (LUT) into three parts: bit: 7 6 5 4 3 2 1 0 tuple: RED | GREEN | BLUE Therefore, RED gets 3-bits of dynamic range, GREEN gets 3-bits, BLUE gets 2-bits in the LUT. An LUT is constructed so each LUT index corresponds to this encoding. e.x. The red tuple is partitioned into 8 ranges. Each range gets ~ 85 units of LUT red channel ( 255 / ((2 ^ 3-bits) - 1)) =~ 85 Bit field 2-bit 3-bit value range ------------------------------- 0 0 0 1 85 36 2 170 72 3 255 109 4 145 5 182 6 218 7 255 LUTindex R G B binary ---------------------------------- 00000000 0 0 0 00100101 36 36 85 10010010 145 145 170 11111111 255 255 255 Since an ordered dither will only toggle between two intensities, Each input RGB tuple had to partitioned into 7 ranges for a 3-bit bit field (red and green), or 3 ranges for 2-bit bit field. This will allow dithering between two LUT index values rather then two intensities. E.x.: the blue tuple mapping Input 2-bit Tuple LUT choices ----------------------- 0 - 84 0 - 1 85 - 169 1 - 2 170 - 255 2 - 3 Each tuples dithered LUT index is bitwise OR'ed together, to return a color dithered image. Since color "spikes" occured at some points in the dithering of a pixel where the dithering matricies coinsided, each RGB tuple uses a different offset when computing which dither matrix entry to use. A more straight forward method could use random dithering and floating-point RGB tuple values, but I chose the ordered dither for its speed. The ordered dither matrices were "grown" from : [ 0 3 ] [ 2 1 ] From the foley & dam book. (They do not provide the algorithm for "growing" the matrices, so I developed the C source for that too) The 4x4 matrix max value (31) didn't fit the red and greeen partition size (35). When I grew the 8x8 matrix, its maximum value was 63! (8 ^ 2 - 1) So I scaled it down to 35 to fit the red and green partition sizes. Same for the blue (85) 16x16 matrix. (16 ^ 2 - 1 = 255) You will have to modify the code and matrices for a 6-bit LUT. Actually you didn't specify if your display used an LUT. If it doesn't, just partition the tuples and dither. Otherwise, 1. Grow an 8x8 matrix (63 = (8 ^ 2 - 1)), 2. partition each tuple into 3 partitions (2-bits per tuple) 3. modify the dithering code accordingly. I've ported this code to MSDOS for use with a Vega VRAM VGA 800x600x256 It works well at high resolution, but very grainy at 320x200x256 VGA mode. If you want to transform a 24-bit RGB image to a best-fit 8-bit LUT, I also have a C implementation of the Color Cube Compression (subdivision) algorithm, but this requires (n log n) passes through a complete image (n = length of LUT), therefore not suitable for on-the-fly processing of RGB images. Good Luck... Kurt Stephens !uunet!motcid!stephens P.S. - Could someone email me, via uunet, a working verson, ported to Sun and/or MSDOS, of the DBW_Render package and associated stuff. PLEASE? I have no ftp. I would really appreciate it. ------------------------------------------------------------------- Here is the C sourec code to setup the LUT and to dither a 24-bit RGB color into 8-bit LUT Feel free to use this code any way you want, but "give credit where credit is due." ---------------------------------------------------------------------- /* 24-bit RGB to dithered 8-bit LUT Kurt A. Stephens 320 Old Sutton Rd Barrington Hills, Il 60010 89.10.10 */ int rgb_to_dithered_lut( x, y, r, g, b) int x, y, r, g, b; { /* matricies for ordered dithering */ /* 3-bit dither matrix: 0 - 35 */ static int d8[8][8] = { { 0, 17, 4, 22, 1, 18, 5, 23}, { 26, 8, 31, 13, 27, 10, 32, 14}, { 6, 24, 2, 20, 7, 25, 3, 21}, { 33, 15, 28, 11, 34, 16, 30, 12}, { 1, 19, 6, 23, 0, 18, 5, 22}, { 28, 10, 32, 15, 27, 9, 31, 13}, { 8, 26, 3, 21, 7, 25, 2, 20}, { 35, 17, 30, 12, 33, 16, 29, 11} }; /* 2-bit dither matrix: 0 to 84 */ static int d16[16][16] = { { 0, 42, 10, 52, 2, 44, 13, 55, 0, 42, 11, 53, 3, 45, 13, 56}, { 63, 21, 73, 31, 65, 23, 76, 34, 63, 21, 74, 32, 66, 24, 77, 34}, { 15, 57, 5, 47, 18, 60, 7, 50, 16, 58, 5, 48, 19, 61, 8, 50}, { 79, 36, 68, 26, 81, 39, 71, 28, 79, 37, 69, 27, 82, 40, 71, 29}, { 3, 46, 14, 56, 1, 43, 11, 54, 4, 46, 15, 57, 1, 44, 12, 54}, { 67, 25, 77, 35, 64, 22, 75, 32, 67, 25, 78, 36, 65, 23, 75, 33}, { 19, 61, 9, 51, 17, 59, 6, 48, 20, 62, 9, 52, 17, 59, 7, 49}, { 83, 40, 72, 30, 80, 38, 69, 27, 83, 41, 73, 30, 81, 38, 70, 28}, { 0, 43, 11, 53, 3, 45, 14, 56, 0, 42, 10, 53, 2, 45, 13, 55}, { 64, 22, 74, 32, 66, 24, 77, 35, 63, 21, 74, 31, 66, 24, 76, 34}, { 16, 58, 6, 48, 19, 61, 8, 51, 16, 58, 5, 47, 18, 60, 8, 50}, { 80, 37, 69, 27, 82, 40, 72, 29, 79, 37, 68, 26, 82, 39, 71, 29}, { 4, 47, 15, 57, 2, 44, 12, 55, 4, 46, 14, 56, 1, 43, 12, 54}, { 68, 26, 78, 36, 65, 23, 76, 33, 67, 25, 78, 35, 64, 22, 75, 33}, { 20, 62, 10, 52, 18, 60, 7, 49, 20, 62, 9, 51, 17, 59, 6, 49}, { 84, 41, 73, 31, 81, 39, 70, 28, 83, 41, 72, 30, 80, 38, 70, 28} }; int i, j, index, r0, r1; int threshold; /* clamp red if > 255 */ if (r >= 255) index = 7 << 5; else { /* chose matrix entry */ i = (x + 1) & 7; j = y & 7; /* partition red tuple into 7 ranges */ for ( i = 7; i ; i-- ) { threshold = 255 * i / 7; if ( r >= threshold ) { r0 = i << 5; r1 = (i - 1) << 5; r -= threshold; /* stop loop */ i = 0; } } /* use dither matrix to chose r0 or r1 */ if (r <= d8[i][j] ) index = r0; else i index = r1; } /* clamp green if > 255 */ if (g >= 255) index |= 7 << 2; else { i = x & 7; j = (y+1) & 7; /* partition green tuple into 7 ranges */ for ( i = 7; i ; i-- ) { threshold = 255 * i / 7; if ( g >= threshold ) { r0 = i << 2; r1 = (i - 1) << 2; g -= threshold; /* stop loop */ i = 0; } } /* use dither matrix to chose r0 or r1 */ if (g <= d8[i][j] ) index |= r0; else index |= r1; } if (b >= 255) index |= 3; else { i = x & 15; j = y & 15; /* partition green tuple into 3 ranges */ for ( i = 3; i ; i-- ) { threshold = 255 * i / 3; if ( b >= threshold ) { r0 = i; r1 = (i - 1); b -= threshold; /* stop loop */ i = 0; } } /* use dither matrix to chose r0 or r1 */ if (b <= d16[i][j]) index |= r0; else index |= r1; } return (index); } init_rgb_dither_lut( red, green, blue) int red[], green[], blue[]; { int i, r, g, b; /* set up a color map with ramps assigned to the following bits bits 7 6 5 4 3 2 1 0 tuple r r r g g g b b */ for ( i = 0; i < 256; i++ ) { /* split i into red, green and blue bit-fields */ r =(i >> 5) & 7; g =(i >> 2) & 7; b = i & 3; /* assign the lut entry to a ramp from 0 - 255 for each bit-field value */ red[i] = 255 * r / 7; green[i] = 255 * g / 7; blue[i] = 255 * b / 3; } } ------------------------------------------------------------- C source for "growing" ordered dither matrices ------------------------------------------------------------- /* shows how to grow ordered dither matrices I'm not sure how this works. I just fiddled with different algorithms! But it produces the examples in the Foley & Van Dam book! Kurt A. Stephens 320 Old Sutton Rd Barrington Hills, Il 60010 89.10.10 */ static int d[2][32][32]; main() { int in,ni,nj; int i,j; int out,nn,i2,j2,k,l; /* inital parent matrix cute isn't it? */ d[0][0][0] = 0; d[0][1][0] = 2; d[0][0][1] = 3; d[0][1][1] = 1; ni = 2;nj = 2; in = 0; /* print matrix */ while (ni <= 16) { printf("static int D%d_%d[%d][%d] = {", ni, nj, ni, nj); for (j=0;j<nj;j++) { printf( "{"); for (i=0;i<ni;i++) { /* scale 8x8 matrix */ if (ni == 8) printf(" %3d",d[in][i][j] * 35 / 63); else printf(" %3d",d[in][i][j]); if ( i < ni - 1) printf( ", "); } printf("}" ); if ( j < nj - 1) printf( ", "); printf("\n"); } printf("}\n\n"); /* grow the matrix: NxN --> N^2xN^2 */ if ((ni < 32) && (nj < 32)) { out = 1 - in; nn = ni * ni; for (i=0;i<ni;i++) { i2 = i + i; for (j=0;j<nj;j++) { j2 = j + j; for (k=0;k<=1;k++) { for (l=0;l<=1;l++) { d[out][i2+k][j2+l] = nn * d[in][k*(ni/2)][l*(nj/2)] + d[in][i][j]; } } } } ni = ni + ni; nj = nj + nj; in = out; } } }
hascall@atanasoff.cs.iastate.edu (John Hascall) (10/11/89)
In article <216@olive11.UUCP> stephens@cell.mot.COM (Kurt Stephens) writes: }In article <6350007@hpcupt1.HP.COM>, dclaar@hpcupt1.HP.COM (Doug Claar) writes: }> }> I have a 1024x768 6 plane display, upon which it seems I could display a }> picture of 512x384 with a greater number of apparent colors by some sort of }> 2x2 dithering. Can anyone give me a reference on this, or advice, clues, }> something-already-written-in-c? }> What I have used is the following. Decide which colors you are going to use. I usually use a "color cube". Since I have an 8-plane system (256 colors) I use a 6x6x6 cube (216 colors), you can use a 4x4x4 cube. idx = 0; for (r=0; r<cubesize; r++) for (g=0; g<cubesize; g++) for (b=0; b<cubesize; b++) { /* set color "idx" to the color <r/cubesize, g/cubesize, b/cubesize> */ idx++; } Then, for each color you want to display, determine the 2 colors in the cube which are closest to the desired color. (a 1-dimension example) ... ---------+-----------+-----------+--------- ... x ^ y z | desired color (colors x & y are the closest colors) Next, determine the distance from the desired color to color x and to color y and use this to determine which dithering pattern to use. x x y x y x y y y y <-- dither patterns x x x x x y x y y y | | | | -----+-----+-----+-----+----- 0.2 0.4 0.6 0.8 <-- ratio of distances John Hascall Iowa State U hascall@atanasoff.cs.iastate.edu