w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

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