home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 1 / FFMCD01.bin / bbs / graphics / ppmqvga.lha / PPMQVGA / src / extra / ppmqvga.c < prev    next >
C/C++ Source or Header  |  1993-09-01  |  14KB  |  518 lines
  1. /*
  2.  *  ppmqvga.c - quantize the colors in a pixmap down to a VGA
  3.  *    (256 colors, 6 bits per pixel)
  4.  *
  5.  *  original by Lyle Rains (lrains@netcom.com) as ppmq256 and ppmq256fs
  6.  *  combined, commented, and enhanced by Bill Davidsen (davidsen@crd.ge.com)
  7. */
  8.  
  9. #define DUMPCOLORS 0
  10. #define DUMPERRORS 0
  11.  
  12. #include <stdio.h>
  13. #include <math.h>
  14. #include <stdlib.h>
  15. #include "ppm.h"
  16. #ifdef SYSV
  17. #include <string.h>
  18. #define srandom srand
  19. #define random rand
  20. #else /*SYSV*/
  21. #include <strings.h>
  22. #define strchr index
  23. #define strrchr rindex
  24. #endif /*SYSV*/
  25.  
  26. #define min(a,b) ((a) < (b) ? (a) : (b))
  27. #define max(a,b) ((a) > (b) ? (a) : (b))
  28.  
  29. #define RED_BITS   5
  30. #define GREEN_BITS 6
  31. #define BLUE_BITS  5
  32.  
  33. #define MAX_RED    (1 << RED_BITS)
  34. #define MAX_GREEN  (1 << GREEN_BITS)
  35. #define MAX_BLUE   (1 << BLUE_BITS)
  36.  
  37. #define MAXWEIGHT  128
  38. #define STDWEIGHT_DIV  (2 << 8)
  39. #define STDWEIGHT_MUL  (2 << 10)
  40. #define COLORS     256
  41. #define GAIN       4
  42.  
  43. #define BARGRAPH     "__________\b\b\b\b\b\b\b\b\b\b"
  44. #define BARGRAPHLEN  10
  45.  
  46. int color_cube[MAX_RED][MAX_GREEN][MAX_BLUE];
  47.  
  48. unsigned char clut[COLORS][4];
  49. int erropt[COLORS][4];
  50. enum { red, green, blue, count };
  51. int clutx;
  52.  
  53. int weight_convert[MAXWEIGHT];
  54. int total_weight, cum_weight[MAX_GREEN];
  55. int rep_weight, rep_threshold;
  56. int r, g, b, dr, dg, db;
  57. int dither = 0, verbose = 1;
  58.  
  59. pixval maxval;
  60.  
  61. /*
  62. ** 3-D error diffusion dither routine for points in the color cube; used to
  63. ** select the representative colors.
  64. */
  65. diffuse()
  66. {
  67.   int _7_32nds, _3_32nds, _1_16th;
  68.  
  69.   if (clutx < COLORS) {
  70.     if (color_cube[r][g][b] > rep_threshold) {
  71.  
  72.       clut[clutx][red]   = ((2 * r + 1) * (maxval + 1)) / (2 * MAX_RED);
  73.       clut[clutx][green] = ((2 * g + 1) * (maxval + 1)) / (2 * MAX_GREEN);
  74.       clut[clutx][blue]  = ((2 * b + 1) * (maxval + 1)) / (2 * MAX_BLUE);
  75. #if DUMPCOLORS
  76.       if (verbose > 2) {
  77.         /* Dump new color */
  78.         if ((clutx & 3) == 0) {
  79.           fprintf(stderr, "\n  %3d (%2d): ", clutx, rep_threshold);
  80.         }
  81.         fprintf(stderr,
  82.           " (%03d,%03d,%03d)", clut[clutx][red],
  83.           clut[clutx][green], clut[clutx][blue]
  84.         );
  85.       }
  86. #endif
  87.       ++clutx;
  88.       color_cube[r][g][b] -= rep_weight;
  89.     }
  90.     _7_32nds = (7 * color_cube[r][g][b]) / 32;
  91.     _3_32nds = (3 * color_cube[r][g][b]) / 32;
  92.     _1_16th = color_cube[r][g][b] - 3 * (_7_32nds + _3_32nds);
  93.     color_cube[ r  ][ g  ][ b  ]  = 0;
  94.     /* spread error evenly in color space. */
  95.     color_cube[ r  ][ g  ][b+db] += _7_32nds;
  96.     color_cube[ r  ][g+dg][ b  ] += _7_32nds;
  97.     color_cube[r+dr][ g  ][ b  ] += _7_32nds;
  98.     color_cube[ r  ][g+dg][b+db] += _3_32nds;
  99.     color_cube[r+dr][ g  ][b+db] += _3_32nds;
  100.     color_cube[r+dr][g+dg][ b  ] += _3_32nds;
  101.     color_cube[r+dr][g+dg][b+db] += _1_16th;
  102.     /* Conserve the error at edges if possible (which it is, except the last pixel) */
  103.     if (color_cube[r][g][b] != 0) {
  104.       if      (dg != 0)   color_cube[r][g+dg][b] += color_cube[r][g][b];
  105.       else if (dr != 0)   color_cube[r+dr][g][b] += color_cube[r][g][b];
  106.       else if (db != 0)   color_cube[r][g][b+db] += color_cube[r][g][b];
  107.       else fprintf(stderr, "\nlost error term\n");
  108.     }
  109.   }
  110.   color_cube[r][g][b] = -1;
  111. }
  112.  
  113. /*
  114. ** Find representative color nearest to requested color.  Check color cube
  115. ** for a cached color index.  If not cached, compute nearest and cache result.
  116. */
  117. int nearest_color(pP)
  118.   register pixel *pP;
  119. {
  120.   register unsigned char *test;
  121.   register unsigned i;
  122.   unsigned long min_dist_sqd, dist_sqd;
  123.   int nearest;
  124.   int *cache;
  125.   int r, g, b;
  126.  
  127.   r = ((int)(PPM_GETR(*pP)));
  128.   g = ((int)(PPM_GETG(*pP)));
  129.   b = ((int)(PPM_GETB(*pP)));
  130.   if ((i = maxval + 1) == 256) {
  131.     cache = &(color_cube[r>>(8-RED_BITS)][g>>(8-GREEN_BITS)][b>>(8-BLUE_BITS)]);
  132.   }
  133.   else {
  134.     cache = &(color_cube[(r<<RED_BITS)/i][(g<<GREEN_BITS)/i][(b<<BLUE_BITS)/i]);
  135.   }
  136.   if (*cache >= 0) return *cache;
  137.   min_dist_sqd = ~0;
  138.   for (i = 0; i < COLORS; ++i) {
  139.     test = clut[i];
  140.     dist_sqd = 3 * (r - test[red])   * (r - test[red])
  141.              + 4 * (g - test[green]) * (g - test[green])
  142.              + 2 * (b - test[blue])  * (b - test[blue]);
  143.     if (dist_sqd < min_dist_sqd) {
  144.       nearest = i;
  145.       min_dist_sqd = dist_sqd;
  146.     }
  147.   }
  148.   return (*cache = nearest);
  149. }
  150.  
  151.  
  152. /* Errors are carried at FS_SCALE times actual size for accuracy */
  153. #define _7x16ths(x)   ((7 * (x)) / 16)
  154. #define _5x16ths(x)   ((5 * (x)) / 16)
  155. #define _3x16ths(x)   ((3 * (x)) / 16)
  156. #define _1x16th(x)    ((x) / 16)
  157. #define NEXT(line)    (!(line))
  158. #define FS_SCALE      1024
  159.  
  160. typedef int fs_err_array[2][3];
  161.  
  162. void fs_diffuse (fs_err, line, color, err)
  163.   fs_err_array *fs_err;
  164.   int line, color;
  165.   int err;
  166. {
  167.   fs_err[1] [line]       [color] += _7x16ths(err);
  168.   fs_err[-1][NEXT(line)] [color] += _3x16ths(err);
  169.   fs_err[0] [NEXT(line)] [color] += _5x16ths(err);
  170.   fs_err[1] [NEXT(line)] [color]  = _1x16th(err); /* straight assignment */
  171. }
  172.  
  173. main(argc, argv)
  174.   int argc;
  175.   char *argv[];
  176. {
  177.   FILE *ifd;
  178.   pixel **pixels;
  179.   register pixel *pP;
  180.   int rows, cols, row;
  181.   register int col;
  182.   int limitcol;
  183.   int i, j, k;
  184.   char *ccP;
  185.   int *errP;
  186.   unsigned char *clutP;
  187.   int nearest;
  188.   fs_err_array *fs_err_lines, *fs_err;
  189.   int fs_line = 0;
  190.   char *usage = "[-dither] [-verbose] [ppmfile]";
  191.   char *pm_progname;
  192.   int argn;
  193.  
  194.   ppm_init(&argc, argv);
  195.  
  196.   argn = 1;
  197.   /* option parsing */
  198.   while( argn < argc && argv[argn][0] == '-' && argv[argn][1] != '\0' ) {
  199.     if( pm_keymatch(argv[argn], "-dither", 2) )
  200.         dither = 1;
  201.     else
  202.     if( pm_keymatch(argv[argn], "-nodither", 4) )
  203.         dither = 0;
  204.     else
  205.     if( pm_keymatch(argv[argn], "-verbose", 2) )
  206.         verbose = 1;
  207.     if( pm_keymatch(argv[argn], "-noverbose", 4) || pm_keymatch(argv[argn], "-quiet", 2) )
  208.         verbose = 0;
  209.     else
  210.         pm_usage(usage);
  211.     ++argn;
  212.   }
  213.  
  214.   if( argn < argc ) {
  215.     ifd = pm_openr(argv[argn]);
  216.     ++argn;
  217.   }
  218.   else
  219.     ifd = stdin;
  220.  
  221.   if( argn != argc )
  222.     pm_usage(usage);
  223.  
  224.   if ((pm_progname = strrchr(argv[0], '/')) != NULL) ++pm_progname;
  225.   else pm_progname = argv[0];
  226.  
  227.   /*
  228.   ** Step 0: read in the image.
  229.   */
  230.   pixels = ppm_readppm( ifd, &cols, &rows, &maxval );
  231.   pm_close( ifd );
  232.  
  233.   /*
  234.   ** Step 1: catalog the colors into a color cube.
  235.   */
  236.   if (verbose) {
  237.     fprintf( stderr, "%s: building color tables %s", pm_progname, BARGRAPH);
  238.     j = (i = rows / BARGRAPHLEN) / 2;
  239.   }
  240.  
  241.   /* Count all occurances of each color */
  242.   for (row = 0; row < rows; ++row) {
  243.  
  244.     if (verbose) {
  245.       if (row > j) {
  246.         putc('*', stderr);
  247.         j += i;
  248.       }
  249.     }
  250.  
  251.     if (maxval == 255) {
  252.       for (col = 0, pP = pixels[row]; col < cols; ++col, ++pP) {
  253.         ++(color_cube[PPM_GETR(*pP) / (256 / MAX_RED)]
  254.                      [PPM_GETG(*pP) / (256 / MAX_GREEN)]
  255.                      [PPM_GETB(*pP) / (256 / MAX_BLUE)]
  256.         );
  257.       }
  258.     }
  259.     else {
  260.       for (col = 0, pP = pixels[row]; col < cols; ++col, ++pP) {
  261.         r = (PPM_GETR(*pP) * MAX_RED)  / (maxval + 1);
  262.         g = (PPM_GETG(*pP) * MAX_GREEN)/ (maxval + 1);
  263.         b = (PPM_GETB(*pP) * MAX_BLUE) / (maxval + 1);
  264.         ++(color_cube[r][g][b]);
  265.       }
  266.     }
  267.   }
  268.  
  269.   /*
  270.   ** Step 2: Determine weight of each color and the weight of a representative color.
  271.   */
  272.   /* Initialize logarithmic weighing table */
  273.   for (i = 2; i < MAXWEIGHT; ++i) {
  274.     weight_convert[i] = (int) (100.0 * log((double)(i)));
  275.   }
  276.  
  277.   k = rows * cols;
  278.   if ((k /= STDWEIGHT_DIV) == 0) k = 1;
  279.   total_weight = i = 0;
  280.   for (g = 0; g < MAX_GREEN; ++g) {
  281.     for (r = 0; r < MAX_RED; ++r) {
  282.       for (b = 0; b < MAX_BLUE; ++b) {
  283.         register int weight;
  284.         /* Normalize the weights, independent of picture size. */
  285.         weight = color_cube[r][g][b] * STDWEIGHT_MUL;
  286.         weight /= k;
  287.         if (weight) ++i;
  288.         if (weight >= MAXWEIGHT) weight = MAXWEIGHT - 1;
  289.         total_weight += (color_cube[r][g][b] = weight_convert[weight]);
  290.       }
  291.     }
  292.     cum_weight[g] = total_weight;
  293.   }
  294.   rep_weight = total_weight / COLORS;
  295.  
  296.   if (verbose) {
  297.     putc('\n', stderr);
  298.     if (verbose > 1) {
  299.       fprintf(stderr, "  found %d colors with total weight %d\n",
  300.         i, total_weight);
  301.       fprintf(stderr, "  avg weight for colors used  = %7.2f\n",
  302.         (float)total_weight/i);