home *** CD-ROM | disk | FTP | other *** search
/ Encyclopedia of Graphics File Formats Companion / GFF_CD.ISO / software / unix / saoimage / sao1_07.tar / defs / dither.def < prev    next >
Text File  |  1989-11-09  |  13KB  |  314 lines
  1. #ifndef lint
  2. static char SccsDitherId[] = "%W%  %G%";
  3. #endif
  4.  
  5. /* Module:    Dither.def
  6.  * Purpose:    Declare and initialize dither weight matrices and
  7.  *        random error vals (includes sample of code to generate it)
  8.  * Modified:    {0} Michael VanHilst    initial version        31 December 1987
  9.  *        {n} <who> -- <does what> -- <when>
  10.  */
  11.  
  12. /* FATTING DITHER PATTERN WEIGHT MATRIX - AS USED BY UTAH RLE LIBRARY */
  13. short dotmatrix1 [16][16] = {
  14.   {  0,222, 48,206, 14,236, 62,220,  3,225, 51,209, 13,235, 61,219},
  15.   {175, 79,127, 95,189, 93,141,109,178, 82,130, 98,188, 92,140,108},
  16.   {191, 32,238, 16,204, 46,252, 30,193, 35,241, 19,203, 45,251, 29},
  17.   {111,143, 64,159,125,157, 77,173,114,146, 66,162,124,156, 76,172},
  18.   { 11,233, 59,217,  5,227, 53,211,  8,230, 56,214,  6,228, 54,212},
  19.   {186, 90,138,106,180, 84,132,100,183, 87,135,103,181, 85,133,101},
  20.   {201, 43,249, 27,195, 37,243, 21,198, 40,246, 24,196, 38,244, 22},
  21.   {122,154, 74,170,116,148, 68,164,119,151, 71,167,117,149, 69,165},
  22.   { 12,234, 60,218,  2,224, 50,208, 15,237, 63,221,  1,223, 49,207},
  23.   {187, 91,139,107,177, 81,129, 97,190, 94,142,110,176, 80,128, 96},
  24.   {202, 44,250, 28,192, 34,240, 18,205, 47,253, 31,191, 33,239, 17},
  25.   {123,155, 75,171,113,145, 65,161,126,158, 78,174,112,144, 64,160},
  26.   {  7,229, 55,213,  9,231, 57,215,  4,226, 52,210, 10,232, 58,216},
  27.   {182, 86,134,102,184, 88,136,104,179, 83,131, 99,185, 89,137,105},
  28.   {197, 39,245, 23,199, 41,247, 25,194, 36,242, 20,200, 42,248, 26},
  29.   {118,150, 70,166,120,152, 72,168,115,147, 67,163,121,153, 73,169}};
  30.  
  31. /* MINIMUM CLUMPING WEIGHT MATRIX - BASED ON MAXIMUM GEOMETRIC SYMMETRY */
  32. short dotmatrix2 [16][16] = {
  33.   {  0,192, 48,240, 12,204, 60,252,  3,195, 51,243, 15,207, 63,254},
  34.   {128, 64,176,112,140, 76,188,124,131, 67,179,115,143, 79,191,127},
  35.   { 32,224, 16,208, 44,236, 28,220, 35,227, 19,211, 47,239, 31,223},
  36.   {160, 96,144, 80,172,108,156, 92,163, 99,147, 83,175,111,159, 95},
  37.   {  8,200, 56,248,  4,196, 52,244, 11,203, 59,251,  7,199, 55,247},
  38.   {136, 72,184,120,132, 68,180,116,139, 75,187,123,135, 71,183,119},
  39.   { 40,232, 24,216, 36,228, 20,212, 43,235, 27,219, 39,231, 23,215},
  40.   {168,104,152, 88,164,100,148, 84,171,107,155, 91,167,103,151, 87},
  41.   {  2,194, 50,242, 14,206, 62,254,  1,193, 49,241, 13,205, 61,253},
  42.   {130, 66,178,114,142, 78,190,126,129, 65,177,113,141, 77,189,125},
  43.   { 34,226, 18,210, 46,238, 30,222, 33,225, 17,209, 45,237, 29,221},
  44.   {162, 98,146, 82,174,110,158, 94,161, 97,145, 81,173,109,157, 93},
  45.   { 10,202, 58,250,  6,198, 54,246,  9,201, 57,249,  5,197, 53,245},
  46.   {138, 74,186,122,134, 70,182,118,137, 73,185,121,133, 69,181,117},
  47.   { 42,234, 26,218, 38,230, 22,214, 41,233, 25,217, 37,229, 21,213},
  48.   {170,106,154, 90,166,102,150, 86,169,105,153, 89,165,101,149, 85}};
  49.  
  50. #define ERRBUFSZ 1202    /* longest bitmap line plus 2 */
  51. /* RANDOM VALUES TO INITIALIZE THE ERROR DIFFUSION BUFFER */
  52. short errbuf [ERRBUFSZ] = {
  53.   247, 17,122,232, 90,238,167,  5,131, 51,240, 52, 96,203, 73, 68, 91, 32,
  54.   180,188,205,234,130,195,116,120, 76,156, 18,127, 56, 10,144,178,243,234,
  55.   161,154,240, 36,206,224, 88, 47,171,162,116,  7,195, 40,195,144, 18, 70,
  56.    83,135,191,160, 36,210, 32, 92,220,176, 14,208,155,176,107,139,212, 57,
  57.   108, 45,105, 23,208,221, 30,147,  5,226, 36, 24, 41,120,159,232, 24,195,
  58.   187, 57, 31,151,233, 46,103,133,223,211, 16,179, 13,124,225,118,148,177,
  59.    84,179, 69, 90,150,105,114,191,225, 17,168,250,213, 99, 51,244,251, 29,
  60.    35, 99,162,  2, 54,179,182, 67, 48,152,186,196, 73, 14,120,142,104, 14,
  61.   248,218,206,217,236,119,212,193,219,  8,182,214, 37,218, 58,200,220,112,
  62.   123,147,180,171, 43,110,112,117,125,233,  4,229,248,252,192,198,214,172,
  63.    62,171,110, 25,179, 36,240,217,254, 42,161,219,155, 29,111, 80,201,155,
  64.   190, 57, 16, 59, 35, 21, 33, 27, 17,225,226,232,142, 32,147,252, 58, 70,
  65.    32, 42, 31, 31, 85,193,251,241,222,106, 65,167,  5,  0,225, 22, 60,  4,
  66.    43, 94, 31, 61, 63,  1, 37,206, 34,184,202, 92,255,235,135, 31, 11,221,
  67.   224,  6,206,191,113, 16,102,118, 17, 71,141, 78, 75,184,172,107,246,236,
  68.   109, 27,186,143,212,133,235,211,112,115,243,123, 80,211,130, 31,146,243,
  69.    48,249,105, 65, 64,247,143,140,176, 59,248,166, 40,101,193,226,244,150,
  70.   103,224,105,216, 83, 93, 84,164, 48,214,196,195,201,244,188, 51, 53,253,
  71.    42,197,138,218,  1,130,129, 41,231, 66, 12,220,217,116,189, 67, 76, 17,
  72.   160,160,181,208,118,122,148, 63,110, 80,114,164, 78,157,105,216,119,107,
  73.    90,248,149, 66, 59,161, 31, 20, 21,220, 87, 98,238,247,  2,164,200,121,
  74.    30, 92,185,140,173, 43, 48,251,201,154,212, 64,  6, 46, 57,155,113,117,
  75.    60,145,138, 82,110,226,180, 92,218,183,  0,163, 48, 30,255,233,171,173,
  76.    21,220,168,222,118,124, 31,125,171, 89, 24, 29,207, 85,174, 89,167, 28,
  77.    60, 91,121, 22, 19,121,185, 67,152,185, 45, 67,102, 67, 31, 15, 33,150,
  78.   140, 65, 19, 56,155, 43, 86,106,128,  5,196, 40, 33,  1,132,155, 23,151,
  79.    20,209,219,172,139,  8,240,242, 75, 15,  2,109,165,143,174,184,199, 74,
  80.   228, 30,181,101, 35,121,141, 69,123, 17,224,147,169,245,100,132,161,240,
  81.   140,146,226,215,161,229, 69, 70,116,244,255, 60, 62,227, 90,243, 72,125,
  82.   109,214,195,232,231,163,123,144,152,224, 21, 58,209,161,204,180,121,109,
  83.   153,190,180, 14,178,180, 74,240,151,165,228,224, 35, 82,182,230, 58,158,
  84.   137,182, 47, 34,151, 68, 93,105,230, 41, 29, 95,151,183, 29, 76,197,207,
  85.     0, 15,192,152,180,165,120,215,247, 47,189, 50,206, 71,232,253,106,128,
  86.    66,199,234, 40,240,  7,135,136,190,165,212,132,117,213,147, 53,109, 72,
  87.   218,230, 32,210, 22,222,  4,228, 37,237,226,143,109, 37, 87, 87, 77, 71,
  88.    95,213,208, 30,123,165,162,240,122, 54, 38,232,127,  1,207,159,211,229,
  89.   125,215,201,163,196,172, 51, 50,209,138,138, 30,210,234,244,162,  8,112,
  90.    71,171, 96,194,226,135,170, 97,136,122,  0, 92, 95,126, 52, 40, 33,248,
  91.   213, 84, 43,166,223,182,197,177,160,186, 83,169, 42,155, 84,138, 93, 55,
  92.    17,  8,152,154,130,153,247,226, 23, 43, 11, 57, 36,224,142, 79,134,109,
  93.     5, 75, 30,166,  6,114, 79, 48, 13,164,186,107,219,204,116,115,103,247,
  94.    12, 94,217, 36,137,228, 94,174,197,236,253, 75, 90,  3,151,120,169,157,
  95.   235,249,205,249,157,136,100,120, 85,217,235,188,209,248, 27,170, 29,165,
  96.   143,123, 83, 84,104, 81,160,194, 85, 55, 59,255,213, 38,248,163, 31,149,
  97.    43,132, 13,128, 94,249, 61, 47,242, 89,218, 16,254,106,139, 82,191,244,
  98.   164, 95,182,249,151,242,249,108, 24,242, 16, 56,135, 59,189,149,188, 27,
  99.   143,250, 75,130, 83, 38,146, 82,144, 30,165, 80, 18, 73,175,201, 67, 71,
  100.   187, 61,180,211, 47,196, 12,183,255,201, 76,188,229,220,183, 49, 94, 11,
  101.    87,240, 93,232, 14,  3, 56, 33, 77,232,234,145, 47,165,206,228,120,253,
  102.   168,133,180,168, 79,  1,100, 52,222, 28,102, 60, 39,190, 45,132,166, 59,
  103.   136,223, 92,213,200, 70,102,248,235, 52,220,100, 50,132,233,231, 44, 56,
  104.   233,145,109,199,173,212,  3,212,146, 48, 89, 57,108,225, 24,201,183,225,
  105.    16, 29,217,252, 82,181, 96,132, 57, 74,108,102,131, 85,248,241, 28,165,
  106.   197, 32,122, 88, 81,211,145,190,181,170,135,108,139,152,137,100,148,220,
  107.    26,245, 96, 84, 64,204,186,196, 33,178,181, 62, 88,123, 94,210,211,176,
  108.   165,101,110, 91, 15,246,199,154,142, 81,255, 35, 45, 25, 25,142,109, 89,
  109.    90, 40, 29,124,219,211,187, 51, 79, 26,  5, 35,202,171,136, 57,  6,151,
  110.    48,206, 50,190, 32, 49,226, 78, 75,251,220,185, 85, 55,226,115,180,189,
  111.    70,111,240,150,137,245,186, 84,161, 66,142,168,218,190,119, 12,125,151,
  112.    62, 95,229,138, 91,194, 68,176,249, 38, 35,173,227,106, 29,211,  0,167,
  113.   201,186,251,107,253,137, 19,215, 72,139,228,197, 34, 35, 36,  8,174,127,
  114.   202,242, 47,196, 24, 83,113,251,189,142,206,189, 54,152,120, 49,  3,118,
  115.   187, 23, 78,  3,162, 50,201,197, 86,237,205,  4,109,152,246,157, 92, 14,
  116.   240,206,  9,173, 92,216,107,147,113,228,196,116, 90,128,139,168,132, 46,
  117.   219, 77,243, 49, 59,192, 54,169, 88, 44, 71,181, 59, 55,131, 68,229,224,
  118.    29, 81,115,142, 54, 56,  3,144,185,143, 57, 61,189, 21,139,176, 71,199,
  119.   113,125,113,202,170,184,127,229,240,  2, 42,213,227, 71};
  120.  
  121.  
  122. #ifdef EXCESS
  123.  
  124. /* ALGORYTHM USED TO GENERATE RLE DITHER PATTERN */
  125. int magic4x4[4][4] =  {
  126.       0, 14,  3, 13,
  127.     11,  5,  8,  6,
  128.     12,  2, 15,  1,
  129.      7,  9,  4, 10
  130. };
  131. /*****************************************************************
  132.  * TAG( make_square )
  133.  * 
  134.  * Build the magic square for a given number of levels.
  135.  * Inputs:
  136.  *     N:        Pixel values per level (255.0 / levels).
  137.  * Outputs:
  138.  *     divN:        Integer value of pixval / N
  139.  *    modN:        Integer remainder between pixval and divN[pixval]*N
  140.  *    magic:        Magic square for dithering to N sublevels.
  141.  * Assumptions:
  142.  *     
  143.  * Algorithm:
  144.  *    divN[pixval] = (int)(pixval / N) maps pixval to its appropriate level.
  145.  *    modN[pixval] = pixval - (int)(N * divN[pixval]) maps pixval to
  146.  *    its sublevel, and is used in the dithering computation.
  147.  *    The magic square is computed as the (modified) outer product of
  148.  *    a 4x4 magic square with itself.
  149.  *    magic[4*k + i][4*l + j] = (magic4x4[i][j] + magic4x4[k][l]/16.0)
  150.  *    multiplied by an appropriate factor to get the correct dithering
  151.  *    range.
  152.  */
  153. make_square( N, divN, modN, magic )
  154. double N;
  155. int divN[256];
  156. int modN[256];
  157. int magic[16][16] ;
  158. {
  159.     register int i, j, k, l;
  160.     double magicfact;
  161.  
  162.     for ( i = 0; i < 256; i++ )
  163.     {
  164.     divN[i] = (int)(i / N);
  165.     modN[i] = i - (int)(N * divN[i]);
  166.     }
  167.  
  168.     /*
  169.      * Expand 4x4 dither pattern to 16x16.  4x4 leaves obvious patterning,
  170.      * and doesn't give us full intensity range (only 17 sublevels,
  171.      * we want at least 51).  Note that 8x8 would be sufficient, but
  172.      * 16x16 is easier to build.
  173.      * 
  174.      * magicfact is (N - 2)/16 so that we get numbers in the matrix from 0 to
  175.      * N - 2: mod N gives numbers in 0 to N - 1, we want some chance that the
  176.      * number is greater than a matrix entry, so the highest matrix
  177.      * entry must be N - 2.
  178.      */
  179.     magicfact = (N - 2) / 16.;
  180.     for ( i = 0; i < 4; i++ )
  181.     for ( j = 0; j < 4; j++ )
  182.         for ( k = 0; k < 4; k++ )
  183.         for ( l = 0; l < 4; l++ )
  184.             magic[4*k+i][4*l+j] =
  185.             (int)(0.5 + magic4x4[i][j] * magicfact +
  186.                   (magic4x4[k][l] / 16.) * magicfact);
  187. }
  188.  
  189.  
  190. /* ALGORITHM FOR 2ND DITHER WEIGHT MATRIX */
  191. /* SATISFIES CONDITION OF MINIMUM CLUMPING AT ALL LEVELS ...
  192.  ... BY MAXIMIZING UNIFORMITY OF PATTERN DISTRIBUTION (PATTERN REGULARITY) */
  193. static int ix[4] = {0,1,0,1}, iy[4] = {0,1,1,0};
  194. makematrix ( matrix )
  195.      short matrix[16][16];
  196. {
  197.   int i,j,k,l;
  198.   int ax,bx,cx,dx;
  199.   int ay,by,cy,dy;
  200.   int indx, indy;
  201.   short val;
  202.  
  203.   val = 0;
  204.   /* ASSIGNMENT PATTERN NESTS CORNERS OF SUCCESSIVELY LARGER SQUARES */
  205.   /* 2x2 SQUARE */
  206.   for (i = 0; i < 4; i++) {
  207.     ax = ix[i];
  208.     ay = iy[i];
  209.     /* SAME PATTERN 4x4 SQUARE */
  210.     for (j = 0; j < 4; j++) {
  211.       bx = ix[j] * 2;
  212.       by = iy[j] * 2;
  213.       /* SAME PATTERN 8x8 SQUARE */
  214.       for (k = 0; k < 4; k++) {
  215.     cx = ix[k] * 4;
  216.     cy = iy[k] * 4;
  217.     /* SAME PATTERN 16x16 SQUARE */
  218.     for (l = 0; l < 4; l++) {
  219.       dx = ix[l] * 8;
  220.       dy = iy[l] * 8;
  221.       indx = ax + bx + cx + dx;
  222.       indy = ay + by + cy + dy;
  223.       matrix[indx][indy] = val++;
  224.     }
  225.       }
  226.     }
  227.   }
  228.   /* TOP VAL (255) CAN'T BE EXCEEDED BY DATA SO REDUCE IT BY ONE */
  229.   --matrix[indx][indy];
  230.   return;
  231. }
  232.  
  233. /* DITHER WEIGHT MATRIX - CONTIGUOUS FROM UPPER LEFT CORNER */
  234. /* SATISFIES CONDITION OF MAXIMUM CLUMPING, HAS ONLY 64 LEVELS */
  235. /* SUITED FOR PRINTERS WHERE BLACK DOTS ARE BIGGER THAN WHITE DOTS */
  236. /*
  237. short dotmatrix3 [16][16] = {
  238.   {  0,  8, 20, 36, 56, 80,108,140,  0,  8, 20, 36, 56, 80,108,140},
  239.   {  4, 16, 32, 52, 76,104,136,168,  4, 16, 32, 52, 76,104,136,168},
  240.   { 12, 28, 48, 72,100,132,164,192, 12, 28, 48, 72,100,132,164,192},
  241.   { 24, 44, 68, 96,128,160,188,212, 24, 44, 68, 96,128,160,188,212},
  242.   { 40, 64, 92,124,156,184,208,228, 40, 64, 92,124,156,184,208,228},
  243.   { 60, 88,120,152,180,204,224,240, 60, 88,120,152,180,204,224,240},
  244.   { 84,116,148,176,200,220,236,248, 84,116,148,176,200,220,236,248},
  245.   {112,144,172,196,216,232,244,252,112,144,172,196,216,232,244,252},
  246.   {  0,  8, 20, 36, 56, 80,108,140,  0,  8, 20, 36, 56, 80,108,140},
  247.   {  4, 16, 32, 52, 76,104,136,168,  4, 16, 32, 52, 76,104,136,168},
  248.   { 12, 28, 48, 72,100,132,164,192, 12, 28, 48, 72,100,132,164,192},
  249.   { 24, 44, 68, 96,128,160,188,212, 24, 44, 68, 96,128,160,188,212},
  250.   { 40, 64, 92,124,156,184,208,228, 40, 64, 92,124,156,184,208,228},
  251.   { 60, 88,120,152,180,204,224,240, 60, 88,120,152,180,204,224,240},
  252.   { 84,116,148,176,200,220,236,248, 84,116,148,176,200,220,236,248},
  253.   {112,144,172,196,216,232,244,252,112,144,172,196,216,232,244,252}};
  254. */
  255.  
  256. /* program to print out a dither matrix for use in array initialization */
  257. main()
  258.   int argc;
  259.   char **argv;
  260. {
  261.   short matrix[16][16];
  262.   int i, j;
  263.  
  264.   makematrix(matrix);
  265.   for( i=0; i<16; i++ ) {
  266.     (void)printf("  {");
  267.     for( j=0; j<15; j++ ) {
  268.       (void)printf("%3d,",matrix[j][i]);
  269.     }
  270.     if( i<15 )
  271.       (void)printf("%3d},\n",matrix[15][i]);
  272.     else
  273.       (void)printf("%3d}};\n",matrix[15][i]);
  274.   }
  275. }
  276.  
  277. /* program to print out random values for error diffusion buffer */
  278. main()
  279. {
  280.   int iscale = 256;
  281.   int errbufsize = 1202;
  282.   int iseed = 5121953;
  283.   float ran_();
  284.   int i, j;
  285.  
  286.   j = 0;
  287.   /* RANDOMLY INITIALIZE ERRORS TO SUPRESS ANY PATTERNS */
  288.   (void)printf("\n  ");
  289.   for (i = 0; i < errbufsize; i++) {
  290.     (void)printf("%3d,",(int)((float)iscale * ran_(&iseed)));
  291.     if( ++j > 17 ) {
  292.       (void)printf("\n  ");
  293.       j = 0;
  294.     }
  295.   }
  296.   (void)printf("\n");
  297. }
  298.  
  299. static int rflag=0;
  300.  
  301. float ran_(seed)
  302. int *seed;
  303. {
  304.   float r;
  305.   if(rflag==0) {
  306.     srandom(1);
  307.     rflag = 1;
  308.   }
  309.   r = (float)random();
  310.   return(r/(float)0x7fffffff);
  311. }
  312.  
  313. #endif
  314.