]> git.saurik.com Git - wxWidgets.git/blob - src/tiff/tools/tiffmedian.c
projects / wxWidgets.git / blob
? search:


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