home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / netpbma.zip / ppm / ppmqvga.c < prev    next >
C/C++ Source or Header  |  1993-10-14  |  14KB  |  530 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.  *  changed options parsing to PBM standards - Ingo Wilken 13/Oct/93
  8. */
  9.  
  10. #define DUMPCOLORS 0
  11. #define DUMPERRORS 0
  12.  
  13. #include <stdio.h>
  14. #include <math.h>
  15. #include "ppm.h"
  16. #if 0   /* this is definded by pbmplus.h (brought in by ppm.h) */
  17. #ifdef SYSV
  18. #include <string.h>
  19. #define srandom srand
  20. #define random rand
  21. #else /*SYSV*/
  22. #include <strings.h>
  23. #define strchr index
  24. #define strrchr rindex
  25. #endif /*SYSV*/
  26. #endif
  27.  
  28. #define min(a,b) ((a) < (b) ? (a) : (b))
  29. #define max(a,b) ((a) > (b) ? (a) : (b))
  30.  
  31. #define RED_BITS   5
  32. #define GREEN_BITS 6
  33. #define BLUE_BITS  5
  34.  
  35. #define MAX_RED    (1 << RED_BITS)
  36. #define MAX_GREEN  (1 << GREEN_BITS)
  37. #define MAX_BLUE   (1 << BLUE_BITS)
  38.  
  39. #define MAXWEIGHT  128
  40. #define STDWEIGHT_DIV  (2 << 8)
  41. #define STDWEIGHT_MUL  (2 << 10)
  42. #define COLORS     256
  43. #define GAIN       4
  44.  
  45. #define BARGRAPH     "__________\b\b\b\b\b\b\b\b\b\b"
  46. #define BARGRAPHLEN  10
  47.  
  48.  
  49. typedef int fs_err_array[2][3];
  50.  
  51. /* prototypes */
  52. void diffuse ARGS((void));
  53. int nearest_color ARGS((register pixel *pP));
  54. void fs_diffuse ARGS((fs_err_array *fs_err, int line, int color, int err));
  55.  
  56.  
  57. int color_cube[MAX_RED][MAX_GREEN][MAX_BLUE];
  58.  
  59. unsigned char clut[COLORS][4];
  60. int erropt[COLORS][4];
  61. enum { red, green, blue, count };
  62. int clutx;
  63.  
  64. int weight_convert[MAXWEIGHT];
  65. int total_weight, cum_weight[MAX_GREEN];
  66. int rep_weight, rep_threshold;
  67. int r, g, b, dr, dg, db;
  68. int dither = 0, verbose = 0;
  69.  
  70. pixval maxval;
  71.  
  72. /*
  73. ** 3-D error diffusion dither routine for points in the color cube; used to
  74. ** select the representative colors.
  75. */
  76. void diffuse()
  77. {
  78.   int _7_32nds, _3_32nds, _1_16th;
  79.  
  80.   if (clutx < COLORS) {
  81.     if (color_cube[r][g][b] > rep_threshold) {
  82.  
  83.       clut[clutx][red]   = ((2 * r + 1) * (maxval + 1)) / (2 * MAX_RED);
  84.       clut[clutx][green] = ((2 * g + 1) * (maxval + 1)) / (2 * MAX_GREEN);
  85.       clut[clutx][blue]  = ((2 * b + 1) * (maxval + 1)) / (2 * MAX_BLUE);
  86. #if DUMPCOLORS
  87.       if (verbose > 2) {
  88.         /* Dump new color */
  89.         if ((clutx & 3) == 0) {
  90.           fprintf(stderr, "\n  %3d (%2d): ", clutx, rep_threshold);
  91.         }
  92.         fprintf(stderr,
  93.           " (%03d,%03d,%03d)", clut[clutx][red],
  94.           clut[clutx][green], clut[clutx][blue]
  95.         );
  96.       }
  97. #endif
  98.       ++clutx;
  99.       color_cube[r][g][b] -= rep_weight;
  100.     }
  101.     _7_32nds = (7 * color_cube[r][g][b]) / 32;
  102.     _3_32nds = (3 * color_cube[r][g][b]) / 32;
  103.     _1_16th = color_cube[r][g][b] - 3 * (_7_32nds + _3_32nds);
  104.     color_cube[ r  ][ g  ][ b  ]  = 0;
  105.     /* spread error evenly in color space. */
  106.     color_cube[ r  ][ g  ][b+db] += _7_32nds;
  107.     color_cube[ r  ][g+dg][ b  ] += _7_32nds;
  108.     color_cube[r+dr][ g  ][ b  ] += _7_32nds;
  109.     color_cube[ r  ][g+dg][b+db] += _3_32nds;
  110.     color_cube[r+dr][ g  ][b+db] += _3_32nds;
  111.     color_cube[r+dr][g+dg][ b  ] += _3_32nds;
  112.     color_cube[r+dr][g+dg][b+db] += _1_16th;
  113.     /* Conserve the error at edges if possible (which it is, except the last pixel) */
  114.     if (color_cube[r][g][b] != 0) {
  115.       if      (dg != 0)   color_cube[r][g+dg][b] += color_cube[r][g][b];
  116.       else if (dr != 0)   color_cube[r+dr][g][b] += color_cube[r][g][b];
  117.       else if (db != 0)   color_cube[r][g][b+db] += color_cube[r][g][b];
  118.       else fprintf(stderr, "\nlost error term\n");
  119.     }
  120.   }
  121.   color_cube[r][g][b] = -1;
  122. }
  123.  
  124. /*
  125. ** Find representative color nearest to requested color.  Check color cube
  126. ** for a cached color index.  If not cached, compute nearest and cache result.
  127. */
  128. int nearest_color(pP)
  129.   register pixel *pP;
  130. {
  131.   register unsigned char *test;
  132.   register unsigned i;
  133.   unsigned long min_dist_sqd, dist_sqd;
  134.   int nearest;
  135.   int *cache;
  136.   int r, g, b;
  137.  
  138.   r = ((int)(PPM_GETR(*pP)));
  139.   g = ((int)(PPM_GETG(*pP)));
  140.   b = ((int)(PPM_GETB(*pP)));
  141.   if ((i = maxval + 1) == 256) {
  142.     cache = &(color_cube[r>>(8-RED_BITS)][g>>(8-GREEN_BITS)][b>>(8-BLUE_BITS)]);
  143.   }
  144.   else {
  145.     cache = &(color_cube[(r<<RED_BITS)/i][(g<<GREEN_BITS)/i][(b<<BLUE_BITS)/i]);
  146.   }
  147.   if (*cache >= 0) return *cache;
  148.   min_dist_sqd = ~0;
  149.   for (i = 0; i < COLORS; ++i) {
  150.     test = clut[i];
  151.     dist_sqd = 3 * (r - test[red])   * (r - test[red])
  152.              + 4 * (g - test[green]) * (g - test[green])
  153.              + 2 * (b - test[blue])  * (b - test[blue]);
  154.     if (dist_sqd < min_dist_sqd) {
  155.       nearest = i;
  156.       min_dist_sqd = dist_sqd;
  157.     }
  158.   }
  159.   return (*cache = nearest);
  160. }
  161.  
  162.  
  163. /* Errors are carried at FS_SCALE times actual size for accuracy */
  164. #define _7x16ths(x)   ((7 * (x)) / 16)
  165. #define _5x16ths(x)   ((5 * (x)) / 16)
  166. #define _3x16ths(x)   ((3 * (x)) / 16)
  167. #define _1x16th(x)    ((x) / 16)
  168. #define NEXT(line)    (!(line))
  169. #define FS_SCALE      1024
  170.  
  171.  
  172. void fs_diffuse (fs_err, line, color, err)
  173.   fs_err_array *fs_err;
  174.   int line, color;
  175.   int err;
  176. {
  177.   fs_err[1] [line]       [color] += _7x16ths(err);
  178.   fs_err[-1][NEXT(line)] [color] += _3x16ths(err);
  179.   fs_err[0] [NEXT(line)] [color] += _5x16ths(err);
  180.   fs_err[1] [NEXT(line)] [color]  = _1x16th(err); /* straight assignment */
  181. }
  182.  
  183. int
  184. main(argc, argv)
  185.   int argc;
  186.   char *argv[];
  187. {
  188.   FILE *ifd;
  189.   pixel **pixels;
  190.   register pixel *pP;
  191.   int rows, cols, row;
  192.   register int col;
  193.   int limitcol;
  194.   int i, j, k;
  195.   char *ccP;
  196.   int *errP;
  197.   unsigned char *clutP;
  198.   int nearest;
  199.   fs_err_array *fs_err_lines, *fs_err;
  200.   int fs_line = 0;
  201.   char *usage = "[-dither] [-verbose] [ppmfile]";
  202.   char *pm_progname;
  203.   int argn;
  204.  
  205.   ppm_init( &argc, argv );
  206.  
  207.   /* option parsing */
  208.   argn = 1;
  209.   while( argn < argc && argv[argn][0] == '-' && argv[argn][1] != '\0' ) {
  210.     if( pm_keymatch(argv[argn], "-dither", 2) ) {
  211.       dither = 1;
  212.     }
  213.     else
  214.     if( pm_keymatch(argv[argn], "-verbose", 2) ) {
  215.       ++verbose;
  216.     }
  217.     /* no quiet option - 'quiet' is now default.  Any -quiet option is
  218.      * swallowed by p?m_init() to silence pm_message().
  219.      * TODO: Change fprintf(stderr,...) calls to pm_message() or pm_error()
  220.      */
  221.     else
  222.       pm_usage(usage);
  223.     ++argn;
  224.   }
  225.  
  226.   if( argn < argc ) {
  227.     ifd = pm_openr( argv[argn] );
  228.     argn++;
  229.   }
  230.   else
  231.     ifd = stdin;
  232.  
  233.   if( argn != argc )
  234.     pm_usage(usage);
  235.  
  236.   if ((pm_progname = strrchr(argv[0], '/')) != NULL) ++pm_progname;
  237.   else pm_progname = argv[0];
  238.  
  239.   /*
  240.   ** Step 0: read in the image.
  241.   */
  242.   pixels = ppm_readppm( ifd, &cols, &rows, &maxval );
  243.   pm_close( ifd );
  244.  
  245.   /*
  246.   ** Step 1: catalog the colors into a color cube.
  247.   */
  248.   if (verbose) {
  249.     fprintf( stderr, "%s: building color tables %s", pm_progname, BARGRAPH);
  250.     j = (i = rows / BARGRAPHLEN) / 2;
  251.   }
  252.  
  253.   /* Count all occurances of each color */
  254.   for (row = 0; row < rows; ++row) {
  255.  
  256.     if (verbose) {
  257.       if (row > j) {
  258.         putc('*', stderr);
  259.         j += i;
  260.       }
  261.     }
  262.  
  263.     if (maxval == 255) {
  264.       for (col = 0, pP = pixels[row]; col < cols; ++col, ++pP) {
  265.         ++(color_cube[PPM_GETR(*pP) / (256 / MAX_RED)]
  266.                      [PPM_GETG(*pP) / (256 / MAX_GREEN)]
  267.                      [PPM_GETB(*pP) / (256 / MAX_BLUE)]
  268.         );
  269.       }
  270.     }
  271.     else {
  272.       for (col = 0, pP = pixels[row]; col < cols; ++col, ++pP) {
  273.         r = (PPM_GETR(*pP) * MAX_RED)  / (maxval + 1);
  274.         g = (PPM_GETG(*pP) * MAX_GREEN)/ (maxval + 1);
  275.         b = (PPM_GETB(*pP) * MAX_BLUE) / (maxval + 1);
  276.         ++(color_cube[r][g][b]);
  277.       }
  278.     }
  279.   }
  280.  
  281.   /*
  282.   ** Step 2: Determine weight of each color and the weight of a representative color.
  283.   */
  284.   /* Initialize logarithmic weighing table */
  285.   for (i = 2; i < MAXWEIGHT; ++i) {
  286.     weight_convert[i] = (int) (100.0 * log((double)(i)));
  287.   }
  288.  
  289.   k = rows * cols;
  290.   if ((k /= STDWEIGHT_DIV) == 0) k = 1;
  291.   total_weight = i = 0;
  292.   for (g = 0; g < MAX_GREEN; ++g) {
  293.     for (r = 0; r < MAX_RED; ++r) {
  294.       for (b = 0; b < MAX_BLUE; ++b) {
  295.         register int weight;
  296.         /* Normalize the weights, independent of picture size. */
  297.         weight = color_cube[r][g][b] * STDWEIGHT_MUL;
  298.         weight /= k;
  299.         if (weight) ++i;
  300.         if (weight >= MAXWEIGHT) weight = MAXWEIGHT - 1;
  301.         total_weight += (color_cube[r][g][b] = weight_convert[weight]);
  302.       }
  303.     }
  304.     cum_weight[g] = total_weight;
  305.   }
  306.   rep_weight = total_weight / COLORS;
  307.  
  308.   if (verbose) {
  309.     putc('\n', stderr);
  310.     if (verbose > 1) {
  311.       fprintf(stderr, "  found %d colors with total weight %d\n",
  312.         i, total_weight);
  313.       fprintf(stderr, "  avg weight for colors used  = %7.2f\n",
  314.         (float)total_weight/i);
  315.       fprintf(stderr, "  avg weight for all colors   = %7.2f\n",
  316.         (float)total_weight/(MAX_RED * MAX_GREEN * MAX_BLUE));
  317.       fprintf(stderr, "  avg weight for final colors = %4d\n", rep_weight);
  318.     }
  319.     fprintf( stderr, "%s: selecting new colors...", pm_progname);
  320.   }
  321.  
  322.   /* Magic foo-foo dust here.  What IS the correct way to select threshold? */
  323.   rep_threshold = total_weight * (28 + 110000/i) / 95000;
  324.  
  325.   /*
  326.   ** Step 3: Do a 3-D error diffusion dither on the data in the color cube
  327.   ** to select the representative colors.  Do the dither back and forth in
  328.   ** such a manner that all the error is conserved (none lost at the edges).
  329.   */
  330. #if !DUMPCOLORS
  331.   if (verbose > 2) {
  332.     fprintf(stderr, "\nrep_threshold: %d", rep_threshold);
  333.   }
  334. #endif
  335.   dg = 1;
  336.   for (g = 0; g < MAX_GREEN; ++g) {
  337.     dr = 1;
  338.     for (r = 0; r < MAX_RED; ++r) {
  339.       db = 1;
  340.       for (b = 0; b < MAX_BLUE - 1; ++b) diffuse();
  341.       db = 0;
  342.       diffuse();
  343.       ++b;
  344.       if (++r == MAX_RED - 1) dr = 0;
  345.       db = -1;
  346.       while (--b > 0) diffuse();
  347.       db = 0;
  348.       diffuse();
  349.     }
  350.     /* Modify threshold to keep rep points proportionally distribited */
  351.     if ((j = clutx - (COLORS * cum_weight[g]) / total_weight) != 0) {
  352.       rep_threshold += j * GAIN;
  353. #if !DUMPCOLORS
  354.       if (verbose > 2) {
  355.         fprintf(stderr, " %d", rep_threshold);
  356.       }
  357. #endif
  358.     }
  359.     if (++g == MAX_GREEN - 1) dg = 0;
  360.     dr = -1;
  361.     while (r-- > 0) {
  362.       db = 1;
  363.       for (b = 0; b < MAX_BLUE - 1; ++b) diffuse();
  364.       db = 0;
  365.       diffuse();
  366.       ++b;
  367.       if (--r == 0) dr = 0;
  368.       db = -1;
  369.       while (--b > 0) diffuse();
  370.       db = 0;
  371.       diffuse();
  372.     }
  373.     /* Modify threshold to keep rep points proportionally distribited */
  374.     if ((j = clutx - (COLORS * cum_weight[g]) / total_weight) != 0) {
  375.       rep_threshold += j * GAIN;
  376. #if !DUMPCOLORS
  377.       if (verbose > 2) {
  378.         fprintf(stderr, " %d", rep_threshold);
  379.       }
  380. #endif
  381.     }
  382.   }
  383.  
  384.   /*
  385.   ** Step 4: check the error associted with the use of each color, and
  386.   ** change the value of the color to minimize the error.
  387.   */
  388.   if (verbose) {
  389.     fprintf( stderr, "\n%s: Reducing errors in the color map %s",
  390.       pm_progname, BARGRAPH);
  391.     j = (i = rows / BARGRAPHLEN) / 2;
  392.   }
  393.   for (row = 0; row < rows; ++row) {
  394.  
  395.     if (verbose) {
  396.       if (row > j) {
  397.         putc('*', stderr);
  398.         j += i;
  399.       }
  400.     }
  401.  
  402.     pP = pixels[row];
  403.     for (col = 0; col < cols; ++col) {
  404.       nearest = nearest_color(pP);
  405.       errP = erropt[nearest]; clutP = clut[nearest];
  406.       errP[red]   += PPM_GETR(*pP) - clutP[red];
  407.       errP[green] += PPM_GETG(*pP) - clutP[green];
  408.       errP[blue]  += PPM_GETB(*pP) - clutP[blue];
  409.       ++errP[count];
  410.       ++pP;
  411.     }
  412.   }
  413. #if DUMPERRORS
  414.     if (verbose) {
  415.       fprintf( stderr, "\n  Color    Red Err  Green Err   Blue Err  Count");
  416.     }
  417. #endif
  418.   for (i = 0; i < COLORS; ++i) {
  419.     clutP = clut[i]; errP = erropt[i];
  420.     j = errP[count];
  421.     if (j > 0) {
  422.       j *= 4;
  423. #if DUMPERRORS
  424.       if (verbose) {
  425.         fprintf( stderr, "\n   %4d %10d %10d %10d %6d",
  426.           i, errP[red]/j, errP[green]/j, errP[blue]/j, j);
  427.       }
  428. #endif
  429.       clutP[red]   += (errP[red]   / j) * 4;
  430.       clutP[green] += (errP[green] / j) * 4;
  431.       clutP[blue]  += (errP[blue]  / j) * 4;
  432.     }
  433.   }
  434.   /* Reset the color cache. */
  435.   for (r = 0; r < MAX_RED; ++r)
  436.     for (g = 0; g < MAX_GREEN; ++g)
  437.       for (b = 0; b < MAX_BLUE; ++b)
  438.         color_cube[r][g][b] = -1;
  439.  
  440.  
  441.   /*
  442.   ** Step 5: map the colors in the image to their closest match in the
  443.   ** new colormap, and write 'em out.
  444.   */
  445.   if (verbose) {
  446.     fprintf( stderr, "\n%s: Mapping image to new colors %s",
  447.       pm_progname, BARGRAPH);
  448.     j = (i = rows / BARGRAPHLEN) / 2;
  449.   }
  450.   ppm_writeppminit( stdout, cols, rows, maxval, 0 );
  451.  
  452.   if (dither) {
  453.     fs_err_lines = (fs_err_array *) calloc((cols + 2), sizeof(fs_err_array));
  454.  
  455.     if (fs_err_lines == NULL) {
  456.       fprintf(stderr, "\n%s: can't allocate Floyd-Steinberg error array.\n",
  457.         pm_progname);
  458.       exit(1);
  459.     }
  460.   }
  461.  
  462.   for (row = 0; row < rows; ++row) {
  463.  
  464.     if (verbose) {
  465.       if (row > j) {
  466.         putc('*', stderr);
  467.         j += i;
  468.       }
  469.     }
  470.  
  471.     if (dither) {
  472.       fs_err = fs_err_lines + 1;
  473.       fs_err[0][NEXT(fs_line)][red]   = 0;
  474.       fs_err[0][NEXT(fs_line)][green] = 0;
  475.       fs_err[0][NEXT(fs_line)][blue]  = 0;
  476.     }
  477.  
  478.     pP = pixels[row];
  479.     for (col = 0; col < cols; ++col) {
  480.  
  481.       if (dither) {
  482.         r = FS_SCALE * (int)(PPM_GETR(*pP)) + fs_err[0][fs_line][red];
  483.         if (r > FS_SCALE * (int)maxval) r = FS_SCALE * (int)maxval;
  484.         if (r < 0) r = 0;
  485.         g = FS_SCALE * (int)(PPM_GETG(*pP)) + fs_err[0][fs_line][green];
  486.         if (g > FS_SCALE * (int)maxval) g = FS_SCALE * (int)maxval;
  487.         if (g < 0) g = 0;
  488.         b = FS_SCALE * (int)(PPM_GETB(*pP)) + fs_err[0][fs_line][blue];
  489.         if (b > FS_SCALE * (int)maxval) b = FS_SCALE * (int)maxval;
  490.         if (b < 0) b = 0;
  491.  
  492.         PPM_ASSIGN(
  493.           *pP, (pixval)(r/FS_SCALE), (pixval)(g/FS_SCALE),
  494.           (pixval)(b/FS_SCALE)
  495.         );
  496.       }
  497.       nearest = nearest_color(pP);
  498.       if (nearest < 0 || nearest > COLORS - 1) {
  499.         fprintf(stderr, "  nearest = %d; out of range\n", nearest);
  500.         exit(1);
  501.       }
  502.       clutP = clut[nearest];
  503.  
  504.       if (dither) {
  505.         r -= FS_SCALE * (int)clutP[red];
  506.         g -= FS_SCALE * (int)clutP[green];
  507.         b -= FS_SCALE * (int)clutP[blue];
  508.  
  509.         fs_diffuse(fs_err, fs_line, red,   r);
  510.         fs_diffuse(fs_err, fs_line, green, g);
  511.         fs_diffuse(fs_err, fs_line, blue,  b);
  512.       }
  513.  
  514.       PPM_ASSIGN( *pP, clutP[red], clutP[green], clutP[blue]);
  515.  
  516.       if (dither) ++fs_err;
  517.       ++pP;
  518.     }
  519.  
  520.     ppm_writeppmrow( stdout, pixels[row], cols, maxval, 0 );
  521.  
  522.     fs_line = NEXT(fs_line);
  523.   }
  524.   if (verbose) {
  525.     fprintf( stderr, "\n%s: done.\n", pm_progname);
  526.   }
  527.  
  528.   exit(0);
  529. }
  530.