]> git.saurik.com Git - wxWidgets.git/blob - src/tiff/tools/tiffmedian.c
projects / wxWidgets.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Remove all lines containing cvs/svn "$Id$" keyword.
[wxWidgets.git] / src / tiff / tools / tiffmedian.c
1
2 /*
3 * Apply median cut on an image.
4 *
5 * tiffmedian [-c n] [-f] input output
6 * -C n - set colortable size. Default is 256.
7 * -f - use Floyd-Steinberg dithering.
8 * -c lzw - compress output with LZW
9 * -c none - use no compression on output
10 * -c packbits - use packbits compression on output
11 * -r n - create output with n rows/strip of data
12 * (by default the compression scheme and rows/strip are taken
13 * from the input file)
14 *
15 * Notes:
16 *
17 * [1] Floyd-Steinberg dither:
18 * I should point out that the actual fractions we used were, assuming
19 * you are at X, moving left to right:
20 *
21 * X 7/16
22 * 3/16 5/16 1/16
23 *
24 * Note that the error goes to four neighbors, not three. I think this
25 * will probably do better (at least for black and white) than the
26 * 3/8-3/8-1/4 distribution, at the cost of greater processing. I have
27 * seen the 3/8-3/8-1/4 distribution described as "our" algorithm before,
28 * but I have no idea who the credit really belongs to.
29
30 * Also, I should add that if you do zig-zag scanning (see my immediately
31 * previous message), it is sufficient (but not quite as good) to send
32 * half the error one pixel ahead (e.g. to the right on lines you scan
33 * left to right), and half one pixel straight down. Again, this is for
34 * black and white; I've not tried it with color.
35 * --
36 * Lou Steinberg
37 *
38 * [2] Color Image Quantization for Frame Buffer Display, Paul Heckbert,
39 * Siggraph '82 proceedings, pp. 297-307
40 */
41
42 #include "tif_config.h"
43
44 #include <stdio.h>
45 #include <stdlib.h>
46 #include <string.h>
47
48 #ifdef HAVE_UNISTD_H
49 # include <unistd.h>
50 #endif
51
52 #ifdef NEED_LIBPORT
53 # include "libport.h"
54 #endif
55
56 #include "tiffio.h"
57
58 #define MAX_CMAP_SIZE 256
59
60 #define streq(a,b) (strcmp(a,b) == 0)
61 #define strneq(a,b,n) (strncmp(a,b,n) == 0)
62
63 #define COLOR_DEPTH 8
64 #define MAX_COLOR 256
65
66 #define B_DEPTH 5 /* # bits/pixel to use */
67 #define B_LEN (1L<<B_DEPTH)
68
69 #define C_DEPTH 2
70 #define C_LEN (1L<<C_DEPTH) /* # cells/color to use */
71
72 #define COLOR_SHIFT (COLOR_DEPTH-B_DEPTH)
73
74 typedef struct colorbox {
75 struct colorbox *next, *prev;
76 int rmin, rmax;
77 int gmin, gmax;
78 int bmin, bmax;
79 uint32 total;
80 } Colorbox;
81
82 typedef struct {
83 int num_ents;
84 int entries[MAX_CMAP_SIZE][2];
85 } C_cell;
86
87 uint16 rm[MAX_CMAP_SIZE], gm[MAX_CMAP_SIZE], bm[MAX_CMAP_SIZE];
88 int num_colors;
89 uint32 histogram[B_LEN][B_LEN][B_LEN];
90 Colorbox *freeboxes;
91 Colorbox *usedboxes;
92 C_cell **ColorCells;
93 TIFF *in, *out;
94 uint32 rowsperstrip = (uint32) -1;
95 uint16 compression = (uint16) -1;
96 uint16 bitspersample = 1;
97 uint16 samplesperpixel;
98 uint32 imagewidth;
99 uint32 imagelength;
100 uint16 predictor = 0;
101
102 static void get_histogram(TIFF*, Colorbox*);
103 static void splitbox(Colorbox*);
104 static void shrinkbox(Colorbox*);
105 static void map_colortable(void);
106 static void quant(TIFF*, TIFF*);
107 static void quant_fsdither(TIFF*, TIFF*);
108 static Colorbox* largest_box(void);
109
110 static void usage(void);
111 static int processCompressOptions(char*);
112
113 #define CopyField(tag, v) \
114 if (TIFFGetField(in, tag, &v)) TIFFSetField(out, tag, v)
115
116 int
117 main(int argc, char* argv[])
118 {
119 int i, dither = 0;
120 uint16 shortv, config, photometric;
121 Colorbox *box_list, *ptr;
122 float floatv;
123 uint32 longv;
124 int c;
125 extern int optind;
126 extern char* optarg;
127
128 num_colors = MAX_CMAP_SIZE;
129 while ((c = getopt(argc, argv, "c:C:r:f")) != -1)
130 switch (c) {
131 case 'c': /* compression scheme */
132 if (!processCompressOptions(optarg))
133 usage();
134 break;
135 case 'C': /* set colormap size */
136 num_colors = atoi(optarg);
137 if (num_colors > MAX_CMAP_SIZE) {
138 fprintf(stderr,
139 "-c: colormap too big, max %d\n",
140 MAX_CMAP_SIZE);
141 usage();
142 }
143 break;
144 case 'f': /* dither */
145 dither = 1;
146 break;
147 case 'r': /* rows/strip */
148 rowsperstrip = atoi(optarg);
149 break;
150 case '?':
151 usage();
152 /*NOTREACHED*/
153 }
154 if (argc - optind != 2)
155 usage();
156 in = TIFFOpen(argv[optind], "r");
157 if (in == NULL)
158 return (-1);
159 TIFFGetField(in, TIFFTAG_IMAGEWIDTH, &imagewidth);
160 TIFFGetField(in, TIFFTAG_IMAGELENGTH, &imagelength);
161 TIFFGetField(in, TIFFTAG_BITSPERSAMPLE, &bitspersample);
162 TIFFGetField(in, TIFFTAG_SAMPLESPERPIXEL, &samplesperpixel);
163 if (bitspersample != 8 && bitspersample != 16) {
164 fprintf(stderr, "%s: Image must have at least 8-bits/sample\n",
165 argv[optind]);
166 return (-3);
167 }
168 if (!TIFFGetField(in, TIFFTAG_PHOTOMETRIC, &photometric) ||
169 photometric != PHOTOMETRIC_RGB || samplesperpixel < 3) {
170 fprintf(stderr, "%s: Image must have RGB data\n", argv[optind]);
171 return (-4);
172 }
173 TIFFGetField(in, TIFFTAG_PLANARCONFIG, &config);
174 if (config != PLANARCONFIG_CONTIG) {
175 fprintf(stderr, "%s: Can only handle contiguous data packing\n",
176 argv[optind]);
177 return (-5);
178 }
179
180 /*
181 * STEP 1: create empty boxes
182 */
183 usedboxes = NULL;
184 box_list = freeboxes = (Colorbox *)_TIFFmalloc(num_colors*sizeof (Colorbox));
185 freeboxes[0].next = &freeboxes[1];
186 freeboxes[0].prev = NULL;
187 for (i = 1; i < num_colors-1; ++i) {
188 freeboxes[i].next = &freeboxes[i+1];
189 freeboxes[i].prev = &freeboxes[i-1];
190 }
191 freeboxes[num_colors-1].next = NULL;
192 freeboxes[num_colors-1].prev = &freeboxes[num_colors-2];
193
194 /*
195 * STEP 2: get histogram, initialize first box
196 */
197 ptr = freeboxes;
198 freeboxes = ptr->next;
199 if (freeboxes)
200 freeboxes->prev = NULL;
201 ptr->next = usedboxes;
202 usedboxes = ptr;
203 if (ptr->next)
204 ptr->next->prev = ptr;
205 get_histogram(in, ptr);
206
207 /*
208 * STEP 3: continually subdivide boxes until no more free
209 * boxes remain or until all colors assigned.
210 */
211 while (freeboxes != NULL) {
212 ptr = largest_box();
213 if (ptr != NULL)
214 splitbox(ptr);
215 else
216 freeboxes = NULL;
217 }
218
219 /*
220 * STEP 4: assign colors to all boxes
221 */
222 for (i = 0, ptr = usedboxes; ptr != NULL; ++i, ptr = ptr->next) {
223 rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2;
224 gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2;
225 bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2;
226 }
227
228 /* We're done with the boxes now */
229 _TIFFfree(box_list);
230 freeboxes = usedboxes = NULL;
231
232 /*
233 * STEP 5: scan histogram and map all values to closest color
234 */
235 /* 5a: create cell list as described in Heckbert[2] */
236 ColorCells = (C_cell **)_TIFFmalloc(C_LEN*C_LEN*C_LEN*sizeof (C_cell*));
237 _TIFFmemset(ColorCells, 0, C_LEN*C_LEN*C_LEN*sizeof (C_cell*));
238 /* 5b: create mapping from truncated pixel space to color
239 table entries */
240 map_colortable();
241
242 /*
243 * STEP 6: scan image, match input values to table entries
244 */
245 out = TIFFOpen(argv[optind+1], "w");
246 if (out == NULL)
247 return (-2);
248
249 CopyField(TIFFTAG_SUBFILETYPE, longv);
250 CopyField(TIFFTAG_IMAGEWIDTH, longv);
251 TIFFSetField(out, TIFFTAG_BITSPERSAMPLE, (short)COLOR_DEPTH);
252 if (compression != (uint16)-1) {
253 TIFFSetField(out, TIFFTAG_COMPRESSION, compression);
254 switch (compression) {
255 case COMPRESSION_LZW:
256 case COMPRESSION_DEFLATE:
257 if (predictor != 0)
258 TIFFSetField(out, TIFFTAG_PREDICTOR, predictor);
259 break;
260 }
261 } else
262 CopyField(TIFFTAG_COMPRESSION, compression);
263 TIFFSetField(out, TIFFTAG_PHOTOMETRIC, (short)PHOTOMETRIC_PALETTE);
264 CopyField(TIFFTAG_ORIENTATION, shortv);
265 TIFFSetField(out, TIFFTAG_SAMPLESPERPIXEL, (short)1);
266 CopyField(TIFFTAG_PLANARCONFIG, shortv);
267 TIFFSetField(out, TIFFTAG_ROWSPERSTRIP,
268 TIFFDefaultStripSize(out, rowsperstrip));
269 CopyField(TIFFTAG_MINSAMPLEVALUE, shortv);
270 CopyField(TIFFTAG_MAXSAMPLEVALUE, shortv);
271 CopyField(TIFFTAG_RESOLUTIONUNIT, shortv);
272 CopyField(TIFFTAG_XRESOLUTION, floatv);
273 CopyField(TIFFTAG_YRESOLUTION, floatv);
274 CopyField(TIFFTAG_XPOSITION, floatv);
275 CopyField(TIFFTAG_YPOSITION, floatv);
276
277 if (dither)
278 quant_fsdither(in, out);
279 else
280 quant(in, out);
281 /*
282 * Scale colormap to TIFF-required 16-bit values.
283 */
284 #define SCALE(x) (((x)*((1L<<16)-1))/255)
285 for (i = 0; i < MAX_CMAP_SIZE; ++i) {
286 rm[i] = SCALE(rm[i]);
287 gm[i] = SCALE(gm[i]);
288 bm[i] = SCALE(bm[i]);
289 }
290 TIFFSetField(out, TIFFTAG_COLORMAP, rm, gm, bm);
291 (void) TIFFClose(out);
292 return (0);
293 }
294
295 static int
296 processCompressOptions(char* opt)
297 {
298 if (streq(opt, "none"))
299 compression = COMPRESSION_NONE;
300 else if (streq(opt, "packbits"))
301 compression = COMPRESSION_PACKBITS;
302 else if (strneq(opt, "lzw", 3)) {
303 char* cp = strchr(opt, ':');
304 if (cp)
305 predictor = atoi(cp+1);
306 compression = COMPRESSION_LZW;
307 } else if (strneq(opt, "zip", 3)) {
308 char* cp = strchr(opt, ':');
309 if (cp)
310 predictor = atoi(cp+1);
311 compression = COMPRESSION_DEFLATE;
312 } else
313 return (0);
314 return (1);
315 }
316
317 char* stuff[] = {
318 "usage: tiffmedian [options] input.tif output.tif",
319 "where options are:",
320 " -r # make each strip have no more than # rows",
321 " -C # create a colormap with # entries",
322 " -f use Floyd-Steinberg dithering",
323 " -c lzw[:opts] compress output with Lempel-Ziv & Welch encoding",
324 " -c zip[:opts] compress output with deflate encoding",
325 " -c packbits compress output with packbits encoding",
326 " -c none use no compression algorithm on output",
327 "",
328 "LZW and deflate options:",
329 " # set predictor value",
330 "For example, -c lzw:2 to get LZW-encoded data with horizontal differencing",
331 NULL
332 };
333
334 static void
335 usage(void)
336 {
337 char buf[BUFSIZ];
338 int i;
339
340 setbuf(stderr, buf);
341 fprintf(stderr, "%s\n\n", TIFFGetVersion());
342 for (i = 0; stuff[i] != NULL; i++)
343 fprintf(stderr, "%s\n", stuff[i]);
344 exit(-1);
345 }
346
347 static void
348 get_histogram(TIFF* in, Colorbox* box)
349 {
350 register unsigned char *inptr;
351 register int red, green, blue;
352 register uint32 j, i;
353 unsigned char *inputline;
354
355 inputline = (unsigned char *)_TIFFmalloc(TIFFScanlineSize(in));
356 if (inputline == NULL) {
357 fprintf(stderr, "No space for scanline buffer\n");
358 exit(-1);
359 }
360 box->rmin = box->gmin = box->bmin = 999;
361 box->rmax = box->gmax = box->bmax = -1;
362 box->total = imagewidth * imagelength;
363
364 { register uint32 *ptr = &histogram[0][0][0];
365 for (i = B_LEN*B_LEN*B_LEN; i-- > 0;)
366 *ptr++ = 0;
367 }
368 for (i = 0; i < imagelength; i++) {
369 if (TIFFReadScanline(in, inputline, i, 0) <= 0)
370 break;
371 inptr = inputline;
372 for (j = imagewidth; j-- > 0;) {
373 red = *inptr++ >> COLOR_SHIFT;
374 green = *inptr++ >> COLOR_SHIFT;
375 blue = *inptr++ >> COLOR_SHIFT;
376 if (red < box->rmin)
377 box->rmin = red;
378 if (red > box->rmax)
379 box->rmax = red;
380 if (green < box->gmin)
381 box->gmin = green;
382 if (green > box->gmax)
383 box->gmax = green;
384 if (blue < box->bmin)
385 box->bmin = blue;
386 if (blue > box->bmax)
387 box->bmax = blue;
388 histogram[red][green][blue]++;
389 }
390 }
391 _TIFFfree(inputline);
392 }
393
394 static Colorbox *
395 largest_box(void)
396 {
397 register Colorbox *p, *b;
398 register uint32 size;
399
400 b = NULL;
401 size = 0;
402 for (p = usedboxes; p != NULL; p = p->next)
403 if ((p->rmax > p->rmin || p->gmax > p->gmin ||
404 p->bmax > p->bmin) && p->total > size)
405 size = (b = p)->total;
406 return (b);
407 }
408
409 static void
410 splitbox(Colorbox* ptr)
411 {
412 uint32 hist2[B_LEN];
413 int first=0, last=0;
414 register Colorbox *new;
415 register uint32 *iptr, *histp;
416 register int i, j;
417 register int ir,ig,ib;
418 register uint32 sum, sum1, sum2;
419 enum { RED, GREEN, BLUE } axis;
420
421 /*
422 * See which axis is the largest, do a histogram along that
423 * axis. Split at median point. Contract both new boxes to
424 * fit points and return
425 */
426 i = ptr->rmax - ptr->rmin;
427 if (i >= ptr->gmax - ptr->gmin && i >= ptr->bmax - ptr->bmin)
428 axis = RED;
429 else if (ptr->gmax - ptr->gmin >= ptr->bmax - ptr->bmin)
430 axis = GREEN;
431 else
432 axis = BLUE;
433 /* get histogram along longest axis */
434 switch (axis) {
435 case RED:
436 histp = &hist2[ptr->rmin];
437 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
438 *histp = 0;
439 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
440 iptr = &histogram[ir][ig][ptr->bmin];
441 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
442 *histp += *iptr++;
443 }
444 histp++;
445 }
446 first = ptr->rmin;
447 last = ptr->rmax;
448 break;
449 case GREEN:
450 histp = &hist2[ptr->gmin];
451 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
452 *histp = 0;
453 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
454 iptr = &histogram[ir][ig][ptr->bmin];
455 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
456 *histp += *iptr++;
457 }
458 histp++;
459 }
460 first = ptr->gmin;
461 last = ptr->gmax;
462 break;
463 case BLUE:
464 histp = &hist2[ptr->bmin];
465 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) {
466 *histp = 0;
467 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
468 iptr = &histogram[ir][ptr->gmin][ib];
469 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
470 *histp += *iptr;
471 iptr += B_LEN;
472 }
473 }
474 histp++;
475 }
476 first = ptr->bmin;
477 last = ptr->bmax;
478 break;
479 }
480 /* find median point */
481 sum2 = ptr->total / 2;
482 histp = &hist2[first];
483 sum = 0;
484 for (i = first; i <= last && (sum += *histp++) < sum2; ++i)
485 ;
486 if (i == first)
487 i++;
488
489 /* Create new box, re-allocate points */
490 new = freeboxes;
491 freeboxes = new->next;
492 if (freeboxes)
493 freeboxes->prev = NULL;
494 if (usedboxes)
495 usedboxes->prev = new;
496 new->next = usedboxes;
497 usedboxes = new;
498
499 histp = &hist2[first];
500 for (sum1 = 0, j = first; j < i; j++)
501 sum1 += *histp++;
502 for (sum2 = 0, j = i; j <= last; j++)
503 sum2 += *histp++;
504 new->total = sum1;
505 ptr->total = sum2;
506
507 new->rmin = ptr->rmin;
508 new->rmax = ptr->rmax;
509 new->gmin = ptr->gmin;
510 new->gmax = ptr->gmax;
511 new->bmin = ptr->bmin;
512 new->bmax = ptr->bmax;
513 switch (axis) {
514 case RED:
515 new->rmax = i-1;
516 ptr->rmin = i;
517 break;
518 case GREEN:
519 new->gmax = i-1;
520 ptr->gmin = i;
521 break;
522 case BLUE:
523 new->bmax = i-1;
524 ptr->bmin = i;
525 break;
526 }
527 shrinkbox(new);
528 shrinkbox(ptr);
529 }
530
531 static void
532 shrinkbox(Colorbox* box)
533 {
534 register uint32 *histp;
535 register int ir, ig, ib;
536
537 if (box->rmax > box->rmin) {
538 for (ir = box->rmin; ir <= box->rmax; ++ir)
539 for (ig = box->gmin; ig <= box->gmax; ++ig) {
540 histp = &histogram[ir][ig][box->bmin];
541 for (ib = box->bmin; ib <= box->bmax; ++ib)
542 if (*histp++ != 0) {
543 box->rmin = ir;
544 goto have_rmin;
545 }
546 }
547 have_rmin:
548 if (box->rmax > box->rmin)
549 for (ir = box->rmax; ir >= box->rmin; --ir)
550 for (ig = box->gmin; ig <= box->gmax; ++ig) {
551 histp = &histogram[ir][ig][box->bmin];
552 ib = box->bmin;
553 for (; ib <= box->bmax; ++ib)
554 if (*histp++ != 0) {
555 box->rmax = ir;
556 goto have_rmax;
557 }
558 }
559 }
560 have_rmax:
561 if (box->gmax > box->gmin) {
562 for (ig = box->gmin; ig <= box->gmax; ++ig)
563 for (ir = box->rmin; ir <= box->rmax; ++ir) {
564 histp = &histogram[ir][ig][box->bmin];
565 for (ib = box->bmin; ib <= box->bmax; ++ib)
566 if (*histp++ != 0) {
567 box->gmin = ig;
568 goto have_gmin;
569 }
570 }
571 have_gmin:
572 if (box->gmax > box->gmin)
573 for (ig = box->gmax; ig >= box->gmin; --ig)
574 for (ir = box->rmin; ir <= box->rmax; ++ir) {
575 histp = &histogram[ir][ig][box->bmin];
576 ib = box->bmin;
577 for (; ib <= box->bmax; ++ib)
578 if (*histp++ != 0) {
579 box->gmax = ig;
580 goto have_gmax;
581 }
582 }
583 }
584 have_gmax:
585 if (box->bmax > box->bmin) {
586 for (ib = box->bmin; ib <= box->bmax; ++ib)
587 for (ir = box->rmin; ir <= box->rmax; ++ir) {
588 histp = &histogram[ir][box->gmin][ib];
589 for (ig = box->gmin; ig <= box->gmax; ++ig) {
590 if (*histp != 0) {
591 box->bmin = ib;
592 goto have_bmin;
593 }
594 histp += B_LEN;
595 }
596 }
597 have_bmin:
598 if (box->bmax > box->bmin)
599 for (ib = box->bmax; ib >= box->bmin; --ib)
600 for (ir = box->rmin; ir <= box->rmax; ++ir) {
601 histp = &histogram[ir][box->gmin][ib];
602 ig = box->gmin;
603 for (; ig <= box->gmax; ++ig) {
604 if (*histp != 0) {
605 box->bmax = ib;
606 goto have_bmax;
607 }
608 histp += B_LEN;
609 }
610 }
611 }
612 have_bmax:
613 ;
614 }
615
616 static C_cell *
617 create_colorcell(int red, int green, int blue)
618 {
619 register int ir, ig, ib, i;
620 register C_cell *ptr;
621 int mindist, next_n;
622 register int tmp, dist, n;
623
624 ir = red >> (COLOR_DEPTH-C_DEPTH);
625 ig = green >> (COLOR_DEPTH-C_DEPTH);
626 ib = blue >> (COLOR_DEPTH-C_DEPTH);
627 ptr = (C_cell *)_TIFFmalloc(sizeof (C_cell));
628 *(ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib) = ptr;
629 ptr->num_ents = 0;
630
631 /*
632 * Step 1: find all colors inside this cell, while we're at
633 * it, find distance of centermost point to furthest corner
634 */
635 mindist = 99999999;
636 for (i = 0; i < num_colors; ++i) {
637 if (rm[i]>>(COLOR_DEPTH-C_DEPTH) != ir ||
638 gm[i]>>(COLOR_DEPTH-C_DEPTH) != ig ||
639 bm[i]>>(COLOR_DEPTH-C_DEPTH) != ib)
640 continue;
641 ptr->entries[ptr->num_ents][0] = i;
642 ptr->entries[ptr->num_ents][1] = 0;
643 ++ptr->num_ents;
644 tmp = rm[i] - red;
645 if (tmp < (MAX_COLOR/C_LEN/2))
646 tmp = MAX_COLOR/C_LEN-1 - tmp;
647 dist = tmp*tmp;
648 tmp = gm[i] - green;
649 if (tmp < (MAX_COLOR/C_LEN/2))
650 tmp = MAX_COLOR/C_LEN-1 - tmp;
651 dist += tmp*tmp;
652 tmp = bm[i] - blue;
653 if (tmp < (MAX_COLOR/C_LEN/2))
654 tmp = MAX_COLOR/C_LEN-1 - tmp;
655 dist += tmp*tmp;
656 if (dist < mindist)
657 mindist = dist;
658 }
659
660 /*
661 * Step 3: find all points within that distance to cell.
662 */
663 for (i = 0; i < num_colors; ++i) {
664 if (rm[i] >> (COLOR_DEPTH-C_DEPTH) == ir &&
665 gm[i] >> (COLOR_DEPTH-C_DEPTH) == ig &&
666 bm[i] >> (COLOR_DEPTH-C_DEPTH) == ib)
667 continue;
668 dist = 0;
669 if ((tmp = red - rm[i]) > 0 ||
670 (tmp = rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 )
671 dist += tmp*tmp;
672 if ((tmp = green - gm[i]) > 0 ||
673 (tmp = gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 )
674 dist += tmp*tmp;
675 if ((tmp = blue - bm[i]) > 0 ||
676 (tmp = bm[i] - (blue + MAX_COLOR/C_LEN-1)) > 0 )
677 dist += tmp*tmp;
678 if (dist < mindist) {
679 ptr->entries[ptr->num_ents][0] = i;
680 ptr->entries[ptr->num_ents][1] = dist;
681 ++ptr->num_ents;
682 }
683 }
684
685 /*
686 * Sort color cells by distance, use cheap exchange sort
687 */
688 for (n = ptr->num_ents - 1; n > 0; n = next_n) {
689 next_n = 0;
690 for (i = 0; i < n; ++i)
691 if (ptr->entries[i][1] > ptr->entries[i+1][1]) {
692 tmp = ptr->entries[i][0];
693 ptr->entries[i][0] = ptr->entries[i+1][0];
694 ptr->entries[i+1][0] = tmp;
695 tmp = ptr->entries[i][1];
696 ptr->entries[i][1] = ptr->entries[i+1][1];
697 ptr->entries[i+1][1] = tmp;
698 next_n = i;
699 }
700 }
701 return (ptr);
702 }
703
704 static void
705 map_colortable(void)
706 {
707 register uint32 *histp = &histogram[0][0][0];
708 register C_cell *cell;
709 register int j, tmp, d2, dist;
710 int ir, ig, ib, i;
711
712 for (ir = 0; ir < B_LEN; ++ir)
713 for (ig = 0; ig < B_LEN; ++ig)
714 for (ib = 0; ib < B_LEN; ++ib, histp++) {
715 if (*histp == 0) {
716 *histp = -1;
717 continue;
718 }
719 cell = *(ColorCells +
720 (((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) +
721 ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH) +
722 (ib>>(B_DEPTH-C_DEPTH))));
723 if (cell == NULL )
724 cell = create_colorcell(
725 ir << COLOR_SHIFT,
726 ig << COLOR_SHIFT,
727 ib << COLOR_SHIFT);
728 dist = 9999999;
729 for (i = 0; i < cell->num_ents &&
730 dist > cell->entries[i][1]; ++i) {
731 j = cell->entries[i][0];
732 d2 = rm[j] - (ir << COLOR_SHIFT);
733 d2 *= d2;
734 tmp = gm[j] - (ig << COLOR_SHIFT);
735 d2 += tmp*tmp;
736 tmp = bm[j] - (ib << COLOR_SHIFT);
737 d2 += tmp*tmp;
738 if (d2 < dist) {
739 dist = d2;
740 *histp = j;
741 }
742 }
743 }
744 }
745
746 /*
747 * straight quantization. Each pixel is mapped to the colors
748 * closest to it. Color values are rounded to the nearest color
749 * table entry.
750 */
751 static void
752 quant(TIFF* in, TIFF* out)
753 {
754 unsigned char *outline, *inputline;
755 register unsigned char *outptr, *inptr;
756 register uint32 i, j;
757 register int red, green, blue;
758
759 inputline = (unsigned char *)_TIFFmalloc(TIFFScanlineSize(in));
760 outline = (unsigned char *)_TIFFmalloc(imagewidth);
761 for (i = 0; i < imagelength; i++) {
762 if (TIFFReadScanline(in, inputline, i, 0) <= 0)
763 break;
764 inptr = inputline;
765 outptr = outline;
766 for (j = 0; j < imagewidth; j++) {
767 red = *inptr++ >> COLOR_SHIFT;
768 green = *inptr++ >> COLOR_SHIFT;
769 blue = *inptr++ >> COLOR_SHIFT;
770 *outptr++ = (unsigned char)histogram[red][green][blue];
771 }
772 if (TIFFWriteScanline(out, outline, i, 0) < 0)
773 break;
774 }
775 _TIFFfree(inputline);
776 _TIFFfree(outline);
777 }
778
779 #define SWAP(type,a,b) { type p; p = a; a = b; b = p; }
780
781 #define GetInputLine(tif, row, bad) \
782 if (TIFFReadScanline(tif, inputline, row, 0) <= 0) \
783 bad; \
784 inptr = inputline; \
785 nextptr = nextline; \
786 for (j = 0; j < imagewidth; ++j) { \
787 *nextptr++ = *inptr++; \
788 *nextptr++ = *inptr++; \
789 *nextptr++ = *inptr++; \
790 }
791 #define GetComponent(raw, cshift, c) \
792 cshift = raw; \
793 if (cshift < 0) \
794 cshift = 0; \
795 else if (cshift >= MAX_COLOR) \
796 cshift = MAX_COLOR-1; \
797 c = cshift; \
798 cshift >>= COLOR_SHIFT;
799
800 static void
801 quant_fsdither(TIFF* in, TIFF* out)
802 {
803 unsigned char *outline, *inputline, *inptr;
804 short *thisline, *nextline;
805 register unsigned char *outptr;
806 register short *thisptr, *nextptr;
807 register uint32 i, j;
808 uint32 imax, jmax;
809 int lastline, lastpixel;
810
811 imax = imagelength - 1;
812 jmax = imagewidth - 1;
813 inputline = (unsigned char *)_TIFFmalloc(TIFFScanlineSize(in));
814 thisline = (short *)_TIFFmalloc(imagewidth * 3 * sizeof (short));
815 nextline = (short *)_TIFFmalloc(imagewidth * 3 * sizeof (short));
816 outline = (unsigned char *) _TIFFmalloc(TIFFScanlineSize(out));
817
818 GetInputLine(in, 0, goto bad); /* get first line */
819 for (i = 1; i <= imagelength; ++i) {
820 SWAP(short *, thisline, nextline);
821 lastline = (i >= imax);
822 if (i <= imax)
823 GetInputLine(in, i, break);
824 thisptr = thisline;
825 nextptr = nextline;
826 outptr = outline;
827 for (j = 0; j < imagewidth; ++j) {
828 int red, green, blue;
829 register int oval, r2, g2, b2;
830
831 lastpixel = (j == jmax);
832 GetComponent(*thisptr++, r2, red);
833 GetComponent(*thisptr++, g2, green);
834 GetComponent(*thisptr++, b2, blue);
835 oval = histogram[r2][g2][b2];
836 if (oval == -1) {
837 int ci;
838 register int cj, tmp, d2, dist;
839 register C_cell *cell;
840
841 cell = *(ColorCells +
842 (((r2>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) +
843 ((g2>>(B_DEPTH-C_DEPTH)) << C_DEPTH ) +
844 (b2>>(B_DEPTH-C_DEPTH))));
845 if (cell == NULL)
846 cell = create_colorcell(red,
847 green, blue);
848 dist = 9999999;
849 for (ci = 0; ci < cell->num_ents && dist > cell->entries[ci][1]; ++ci) {
850 cj = cell->entries[ci][0];
851 d2 = (rm[cj] >> COLOR_SHIFT) - r2;
852 d2 *= d2;
853 tmp = (gm[cj] >> COLOR_SHIFT) - g2;
854 d2 += tmp*tmp;
855 tmp = (bm[cj] >> COLOR_SHIFT) - b2;
856 d2 += tmp*tmp;
857 if (d2 < dist) {
858 dist = d2;
859 oval = cj;
860 }
861 }
862 histogram[r2][g2][b2] = oval;
863 }
864 *outptr++ = oval;
865 red -= rm[oval];
866 green -= gm[oval];
867 blue -= bm[oval];
868 if (!lastpixel) {
869 thisptr[0] += blue * 7 / 16;
870 thisptr[1] += green * 7 / 16;
871 thisptr[2] += red * 7 / 16;
872 }
873 if (!lastline) {
874 if (j != 0) {
875 nextptr[-3] += blue * 3 / 16;
876 nextptr[-2] += green * 3 / 16;
877 nextptr[-1] += red * 3 / 16;
878 }
879 nextptr[0] += blue * 5 / 16;
880 nextptr[1] += green * 5 / 16;
881 nextptr[2] += red * 5 / 16;
882 if (!lastpixel) {
883 nextptr[3] += blue / 16;
884 nextptr[4] += green / 16;
885 nextptr[5] += red / 16;
886 }
887 nextptr += 3;
888 }
889 }
890 if (TIFFWriteScanline(out, outline, i-1, 0) < 0)
891 break;
892 }
893 bad:
894 _TIFFfree(inputline);
895 _TIFFfree(thisline);
896 _TIFFfree(nextline);
897 _TIFFfree(outline);
898 }
899 /*
900 * Local Variables:
901 * mode: c
902 * c-basic-offset: 8
903 * fill-column: 78
904 * End:
905 */
wxWidgets (Impactor)