1 /* quant.c - provides general image quantization
2 currently only used by gif.c, but maybe we'll support producing
3 8-bit (or bigger indexed) png files at some point
8 static void makemap_webmap(i_quantize *);
9 static void makemap_addi(i_quantize *, i_img **imgs, int count);
10 static void makemap_mediancut(i_quantize *, i_img **imgs, int count);
11 static void makemap_mono(i_quantize *);
13 static int makemap_palette(i_quantize *, i_img **imgs, int count);
17 setcol(i_color *cl,unsigned char r,unsigned char g,unsigned char b,unsigned char a) {
26 /* make a colour map overwrites mc_existing/mc_count in quant Note
27 that i_makemap will be called once for each image if mc_perimage is
28 set and the format support multiple colour maps per image.
30 This means we don't need any special processing at this level to
31 handle multiple colour maps.
35 =item i_quant_makemap(C<quant>, C<imgs>, C<count>)
37 =category Image quantization
39 Analyzes the C<count> images in C<imgs> according to the rules in
40 C<quant> to build a color map (optimal or not depending on
41 C<< quant->make_colors >>).
47 i_quant_makemap(i_quantize *quant, i_img **imgs, int count) {
49 if (quant->translate == pt_giflib) {
50 /* giflib does it's own color table generation */
51 /* previously we used giflib's quantizer, but it didn't handle multiple
52 images, which made it hard to build a global color map
53 We've implemented our own median cut code so we can ignore
55 makemap_mediancut(quant, imgs, count);
59 switch (quant->make_colors & mc_mask) {
61 /* use user's specified map */
64 makemap_webmap(quant);
68 makemap_mediancut(quant, imgs, count);
77 makemap_addi(quant, imgs, count);
82 static void translate_closest(i_quantize *, i_img *, i_palidx *);
83 static void translate_errdiff(i_quantize *, i_img *, i_palidx *);
84 static void translate_addi(i_quantize *, i_img *, i_palidx *);
87 =item i_quant_translate(C<quant>, C<img>)
89 =category Image quantization
91 Quantize the image given the palette in C<quant>.
93 On success returns a pointer to a memory block of C<< img->xsize *
94 img->ysize >> C<i_palidx> entries.
96 On failure returns NULL.
98 You should call myfree() on the returned block when you're done with
101 This function will fail if the supplied palette contains no colors.
106 i_quant_translate(i_quantize *quant, i_img *img) {
110 mm_log((1, "quant_translate(quant %p, img %p)\n", quant, img));
112 /* there must be at least one color in the paletted (though even that
114 if (quant->mc_count == 0) {
115 i_push_error(0, "no colors available for translation");
119 bytes = img->xsize * img->ysize;
120 if (bytes / img->ysize != img->xsize) {
121 i_push_error(0, "integer overflow calculating memory allocation");
124 result = mymalloc(bytes);
126 switch (quant->translate) {
129 translate_closest(quant, img, result);
133 translate_errdiff(quant, img, result);
138 translate_addi(quant, img, result);
145 static void translate_closest(i_quantize *quant, i_img *img, i_palidx *out) {
147 translate_addi(quant, img, out);
150 #define PWR2(x) ((x)*(x))
152 typedef int (*cmpfunc)(const void*, const void*);
175 static void prescan(i_img **im,int count, int cnum, cvec *clr, i_sample_t *line);
176 static void reorder(pbox prescan[512]);
177 static int pboxcmp(const pbox *a,const pbox *b);
178 static void boxcenter(int box,cvec *cv);
179 static float frandn(void);
180 static void boxrand(int box,cvec *cv);
181 static void bbox(int box,int *r0,int *r1,int *g0,int *g1,int *b0,int *b1);
182 static void cr_hashindex(cvec clr[256],int cnum,hashbox hb[512]);
183 static int mindist(int boxnum,cvec *cv);
184 static int maxdist(int boxnum,cvec *cv);
186 /* Some of the simpler functions are kept here to aid the compiler -
187 maybe some of them will be inlined. */
190 pixbox(i_color *ic) { return ((ic->channel[0] & 224)<<1)+ ((ic->channel[1]&224)>>2) + ((ic->channel[2] &224) >> 5); }
193 pixbox_ch(i_sample_t *chans) { return ((chans[0] & 224)<<1)+ ((chans[1]&224)>>2) + ((chans[2] &224) >> 5); }
197 if (in>255) { return 255; }
198 else if (in>0) return in;
205 return rand()/(RAND_MAX+1.0);
211 eucl_d(cvec* cv,i_color *cl) { return PWR2(cv->r-cl->channel[0])+PWR2(cv->g-cl->channel[1])+PWR2(cv->b-cl->channel[2]); }
216 eucl_d_ch(cvec* cv,i_sample_t *chans) {
217 return PWR2(cv->r - chans[0]) + PWR2(cv->g - chans[1])
218 + PWR2(cv->b - chans[2]);
222 ceucl_d(i_color *c1, i_color *c2) {
223 return PWR2(c1->channel[0]-c2->channel[0])
224 +PWR2(c1->channel[1]-c2->channel[1])
225 +PWR2(c1->channel[2]-c2->channel[2]);
229 gray_samples[] = { 0, 0, 0 };
233 This quantization algorithm and implementation routines are by Arnar
234 M. Hrafnkelson. In case any new ideas are here they are mine since
235 this was written from scratch.
237 The algorithm uses local means in the following way:
239 For each point in the colormap we find which image points
240 have that point as it's closest point. We calculate the mean
241 of those points and in the next iteration it will be the new
242 entry in the colormap.
244 In order to speed this process up (i.e. nearest neighbor problem) We
245 divied the r,g,b space up in equally large 512 boxes. The boxes are
246 numbered from 0 to 511. Their numbering is so that for a given vector
247 it is known that it belongs to the box who is formed by concatenating the
248 3 most significant bits from each component of the RGB triplet.
250 For each box we find the list of points from the colormap who might be
251 closest to any given point within the box. The exact solution
252 involves finding the Voronoi map (or the dual the Delauny
253 triangulation) and has many issues including numerical stability.
255 So we use this approximation:
257 1. Find which point has the shortest maximum distance to the box.
258 2. Find all points that have a shorter minimum distance than that to the box
260 This is a very simple task and is not computationally heavy if one
261 takes into account that the minimum distances from a pixel to a box is
262 always found by checking if it's inside the box or is closest to some
263 side or a corner. Finding the maximum distance is also either a side
266 This approach results 2-3 times more than the actual points needed but
267 is still a good gain over the complete space. Usually when one has a
268 256 Colorcolor map a search over 30 is often obtained.
270 A bit of an enhancement to this approach is to keep a seperate list
271 for each side of the cube, but this will require even more memory.
273 Arnar M. Hrafnkelsson (addi@umich.edu);
277 Extracted from gifquant.c, removed dependencies on gif_lib,
278 and added support for multiple images.
279 starting from 1nov2000 by TonyC <tony@develop-help.com>.
284 makemap_addi(i_quantize *quant, i_img **imgs, int count) {
286 int cnum, i, bst_idx=0, ld, cd, iter, currhb, img_num;
292 i_img_dim maxwidth = 0;
294 const int *sample_indices;
296 mm_log((1, "makemap_addi(quant %p { mc_count=%d, mc_colors=%p }, imgs %p, count %d)\n",
297 quant, quant->mc_count, quant->mc_colors, imgs, count));
299 if (makemap_palette(quant, imgs, count))
304 clr = i_mempool_alloc(&mp, sizeof(cvec) * quant->mc_size);
305 hb = i_mempool_alloc(&mp, sizeof(hashbox) * 512);
306 for (i=0; i < quant->mc_count; ++i) {
307 clr[i].r = quant->mc_colors[i].rgb.r;
308 clr[i].g = quant->mc_colors[i].rgb.g;
309 clr[i].b = quant->mc_colors[i].rgb.b;
313 /* mymalloc doesn't clear memory, so I think we need this */
314 for (; i < quant->mc_size; ++i) {
315 /*clr[i].r = clr[i].g = clr[i].b = 0;*/
322 cnum = quant->mc_size;
325 for (img_num = 0; img_num < count; ++img_num) {
326 if (imgs[img_num]->xsize > maxwidth)
327 maxwidth = imgs[img_num]->xsize;
329 line = i_mempool_alloc(&mp, 3 * maxwidth * sizeof(*line));
331 prescan(imgs, count, cnum, clr, line);
332 cr_hashindex(clr, cnum, hb);
334 for(iter=0;iter<3;iter++) {
337 for (img_num = 0; img_num < count; ++img_num) {
338 i_img *im = imgs[img_num];
339 sample_indices = im->channels >= 3 ? NULL : gray_samples;
340 for(y=0;y<im->ysize;y++) {
341 i_gsamp(im, 0, im->xsize, y, line, sample_indices, 3);
343 for(x=0;x<im->xsize;x++) {
345 /*i_gpix(im,x,y,&val);*/
346 currhb=pixbox_ch(val);
347 /* printf("box = %d \n",currhb); */
348 for(i=0;i<hb[currhb].cnt;i++) {
349 /* printf("comparing: pix (%d,%d,%d) vec (%d,%d,%d)\n",val.channel[0],val.channel[1],val.channel[2],clr[hb[currhb].vec[i]].r,clr[hb[currhb].vec[i]].g,clr[hb[currhb].vec[i]].b); */
351 cd=eucl_d_ch(&clr[hb[currhb].vec[i]],val);
353 ld=cd; /* shortest distance yet */
354 bst_idx=hb[currhb].vec[i]; /* index of closest vector yet */
358 clr[bst_idx].mcount++;
360 clr[bst_idx].dr+=val[0];
361 clr[bst_idx].dg+=val[1];
362 clr[bst_idx].db+=val[2];
364 val += 3; /* next 3 samples (next pixel) */
371 clr[i].dr/=clr[i].mcount;
372 clr[i].dg/=clr[i].mcount;
373 clr[i].db/=clr[i].mcount;
376 /* for(i=0;i<cnum;i++) printf("vec(%d)=(%d,%d,%d) dest=(%d,%d,%d) matchcount=%d\n",
377 i,clr[i].r,clr[i].g,clr[i].b,clr[i].dr,clr[i].dg,clr[i].db,clr[i].mcount); */
379 /* printf("total error: %.2f\n",sqrt(accerr)); */
381 for(i=0;i<cnum;i++) {
382 if (clr[i].fixed) continue; /* skip reserved colors */
386 clr[i].r=clr[i].r*(1-dlt)+dlt*clr[i].dr;
387 clr[i].g=clr[i].g*(1-dlt)+dlt*clr[i].dg;
388 clr[i].b=clr[i].b*(1-dlt)+dlt*clr[i].db;
390 /* let's try something else */
402 cr_hashindex(clr,cnum,hb);
407 for(i=0;i<cnum;i++) {
408 cd=eucl_d(&clr[i],&val);
416 /* if defined, we only include colours with an mcount or that were
417 supplied in the fixed palette, giving us a smaller output palette */
418 #define ONLY_USE_USED
420 /* transfer the colors back */
422 for (i = 0; i < cnum; ++i) {
423 if (clr[i].fixed || clr[i].used) {
424 /*printf("Adding %d (%d,%d,%d)\n", i, clr[i].r, clr[i].g, clr[i].b);*/
425 quant->mc_colors[quant->mc_count].rgb.r = clr[i].r;
426 quant->mc_colors[quant->mc_count].rgb.g = clr[i].g;
427 quant->mc_colors[quant->mc_count].rgb.b = clr[i].b;
432 /* transfer the colors back */
433 for (i = 0; i < cnum; ++i) {
434 quant->mc_colors[i].rgb.r = clr[i].r;
435 quant->mc_colors[i].rgb.g = clr[i].g;
436 quant->mc_colors[i].rgb.b = clr[i].b;
438 quant->mc_count = cnum;
442 mm_log((1, "makemap_addi returns - quant.mc_count = %d\n", quant->mc_count));
443 for (i = 0; i < quant->mc_count; ++i)
444 mm_log((5, " map entry %d: (%d, %d, %d)\n", i, clr[i].r, clr[i].g, clr[i].b));
447 i_mempool_destroy(&mp);
449 mm_log((1, "makemap_addi() - %d colors\n", quant->mc_count));
457 #define MEDIAN_CUT_COLORS 32768
459 #define MED_CUT_INDEX(c) ((((c).rgb.r & 0xF8) << 7) | \
460 (((c).rgb.g & 0xF8) << 2) | (((c).rgb.b & 0xF8) >> 3))
462 #define MED_CUT_GRAY_INDEX(c) ((((c).rgb.r & 0xF8) << 7) | \
463 (((c).rgb.r & 0xF8) << 2) | (((c).rgb.r & 0xF8) >> 3))
465 /* scale these to cover the whole range */
466 #define MED_CUT_RED(index) ((((index) & 0x7C00) >> 10) * 255 / 31)
467 #define MED_CUT_GREEN(index) ((((index) & 0x3E0) >> 5) * 255 / 31)
468 #define MED_CUT_BLUE(index) (((index) & 0x1F) * 255 / 31)
471 i_sample_t min[3]; /* minimum for each channel */
472 i_sample_t max[3]; /* maximum for each channel */
473 i_sample_t width[3]; /* width for each channel */
474 int start, size; /* beginning and size of the partition */
475 i_img_dim pixels; /* number of pixels represented by this partition */
479 =item calc_part(part, colors)
481 Calculates the new color limits for the given partition.
483 Giflib assumes that the limits for the non-split channels stay the
484 same, but this strikes me as incorrect, especially if the colors tend
487 Of course this could be optimized by not recalculating the channel we
488 just sorted on, but it's not worth the effort right now.
492 static void calc_part(medcut_partition *part, quant_color_entry *colors) {
495 for (ch = 0; ch < 3; ++ch) {
499 for (i = part->start; i < part->start + part->size; ++i) {
500 for (ch = 0; ch < 3; ++ch) {
501 if (part->min[ch] > colors[i].rgb[ch])
502 part->min[ch] = colors[i].rgb[ch];
503 if (part->max[ch] < colors[i].rgb[ch])
504 part->max[ch] = colors[i].rgb[ch];
507 for (ch = 0; ch < 3; ++ch) {
508 part->width[ch] = part->max[ch] - part->min[ch];
512 /* simple functions to sort by each channel - we could use a global, but
516 color_sort_red(void const *left, void const *right) {
517 return ((quant_color_entry *)left)->rgb[0] - ((quant_color_entry *)right)->rgb[0];
521 color_sort_green(void const *left, void const *right) {
522 return ((quant_color_entry *)left)->rgb[1] - ((quant_color_entry *)right)->rgb[1];
526 color_sort_blue(void const *left, void const *right) {
527 return ((quant_color_entry *)left)->rgb[2] - ((quant_color_entry *)right)->rgb[2];
530 static int (*sorters[])(void const *, void const *) =
538 makemap_mediancut(i_quantize *quant, i_img **imgs, int count) {
539 quant_color_entry *colors;
542 i_img_dim x, y, max_width;
545 i_img_dim total_pixels;
546 medcut_partition *parts;
549 /* number of channels we search for the best channel to partition
550 this isn't terribly efficient, but it should work */
553 mm_log((1, "makemap_mediancut(quant %p { mc_count=%d, mc_colors=%p }, imgs %p, count %d)\n",
554 quant, quant->mc_count, quant->mc_colors, imgs, count));
556 if (makemap_palette(quant, imgs, count))
561 colors = i_mempool_alloc(&mp, sizeof(*colors) * MEDIAN_CUT_COLORS);
562 for (i = 0; i < MEDIAN_CUT_COLORS; ++i) {
563 colors[i].rgb[0] = MED_CUT_RED(i);
564 colors[i].rgb[1] = MED_CUT_GREEN(i);
565 colors[i].rgb[2] = MED_CUT_BLUE(i);
570 for (imgn = 0; imgn < count; ++imgn) {
571 if (imgs[imgn]->xsize > max_width)
572 max_width = imgs[imgn]->xsize;
574 line = i_mempool_alloc(&mp, sizeof(i_color) * max_width);
576 /* build the stats */
578 chan_count = 1; /* assume we just have grayscale */
579 for (imgn = 0; imgn < count; ++imgn) {
580 total_pixels += imgs[imgn]->xsize * imgs[imgn]->ysize;
581 for (y = 0; y < imgs[imgn]->ysize; ++y) {
582 i_glin(imgs[imgn], 0, imgs[imgn]->xsize, y, line);
583 if (imgs[imgn]->channels > 2) {
585 for (x = 0; x < imgs[imgn]->xsize; ++x) {
586 ++colors[MED_CUT_INDEX(line[x])].count;
590 /* a gray-scale image, just use the first channel */
591 for (x = 0; x < imgs[imgn]->xsize; ++x) {
592 ++colors[MED_CUT_GRAY_INDEX(line[x])].count;
598 /* eliminate the empty colors */
600 for (in = 0; in < MEDIAN_CUT_COLORS; ++in) {
601 if (colors[in].count) {
602 colors[out++] = colors[in];
605 /*printf("out %d\n", out);
607 for (i = 0; i < out; ++i) {
608 if (colors[i].count) {
609 printf("%d: (%d,%d,%d) -> %d\n", i, colors[i].rgb[0], colors[i].rgb[1],
610 colors[i].rgb[2], colors[i].count);
614 if (out < quant->mc_size) {
615 /* just copy them into the color table */
616 for (i = 0; i < out; ++i) {
617 for (ch = 0; ch < 3; ++ch) {
618 quant->mc_colors[i].channel[ch] = colors[i].rgb[ch];
621 quant->mc_count = out;
624 /* build the starting partition */
625 parts = i_mempool_alloc(&mp, sizeof(*parts) * quant->mc_size);
628 parts[0].pixels = total_pixels;
629 calc_part(parts, colors);
632 while (color_count < quant->mc_size) {
633 /* initialized to avoid compiler warnings */
634 int max_index = 0, max_ch = 0; /* index/channel with biggest spread */
636 medcut_partition *workpart;
640 /* find the partition with the most biggest span with more than
643 for (i = 0; i < color_count; ++i) {
644 for (ch = 0; ch < chan_count; ++ch) {
645 if (parts[i].width[ch] > max_size
646 && parts[i].size > 1) {
649 max_size = parts[i].width[ch];
654 /* nothing else we can split */
658 workpart = parts+max_index;
659 /*printf("splitting partition %d (pixels %ld, start %d, size %d)\n", max_index, workpart->pixels, workpart->start, workpart->size);*/
660 qsort(colors + workpart->start, workpart->size, sizeof(*colors),
663 /* find the median or something like it we need to make sure both
664 sides of the split have at least one color in them, so we don't
665 test at the first or last entry */
667 cum_total = colors[i].count;
669 half = workpart->pixels / 2;
670 while (i < workpart->start + workpart->size - 1
671 && cum_total < half) {
672 cum_total += colors[i++].count;
674 /*printf("Split at %d to make %d (half %ld, cumtotal %ld)\n", i, color_count, half, cum_total);*/
676 /* found the spot to split */
677 parts[color_count].start = i;
678 parts[color_count].size = workpart->start + workpart->size - i;
679 workpart->size = i - workpart->start;
680 parts[color_count].pixels = workpart->pixels - cum_total;
681 workpart->pixels = cum_total;
683 /* recalculate the limits */
684 calc_part(workpart, colors);
685 calc_part(parts+color_count, colors);
689 /* fill in the color table - since we could still have partitions
690 that have more than one color, we need to average the colors */
691 for (part_num = 0; part_num < color_count; ++part_num) {
693 medcut_partition *workpart;
695 workpart = parts+part_num;
696 for (ch = 0; ch < 3; ++ch)
699 for (i = workpart->start; i < workpart->start + workpart->size; ++i) {
700 for (ch = 0; ch < 3; ++ch) {
701 sums[ch] += colors[i].rgb[ch] * colors[i].count;
704 for (ch = 0; ch < 3; ++ch) {
705 quant->mc_colors[part_num].channel[ch] = sums[ch] / workpart->pixels;
708 quant->mc_count = color_count;
710 /*printf("out %d colors\n", quant->mc_count);*/
711 i_mempool_destroy(&mp);
713 mm_log((1, "makemap_mediancut() - %d colors\n", quant->mc_count));
717 makemap_mono(i_quantize *quant) {
718 quant->mc_colors[0].rgba.r = 0;
719 quant->mc_colors[0].rgba.g = 0;
720 quant->mc_colors[0].rgba.b = 0;
721 quant->mc_colors[0].rgba.a = 255;
722 quant->mc_colors[1].rgba.r = 255;
723 quant->mc_colors[1].rgba.g = 255;
724 quant->mc_colors[1].rgba.b = 255;
725 quant->mc_colors[1].rgba.a = 255;
730 makemap_webmap(i_quantize *quant) {
734 for (r = 0; r < 256; r+=0x33)
735 for (g = 0; g < 256; g+=0x33)
736 for (b = 0; b < 256; b += 0x33)
737 setcol(quant->mc_colors+i++, r, g, b, 255);
742 in_palette(i_color *c, i_quantize *quant, int size) {
745 for (i = 0; i < size; ++i) {
746 if (c->channel[0] == quant->mc_colors[i].channel[0]
747 && c->channel[1] == quant->mc_colors[i].channel[1]
748 && c->channel[2] == quant->mc_colors[i].channel[2]) {
757 =item makemap_palette(quant, imgs, count)
759 Tests if all the given images are paletted and have a common palette,
760 if they do it builds that palette.
762 A possible improvement might be to eliminate unused colors in the
769 makemap_palette(i_quantize *quant, i_img **imgs, int count) {
770 int size = quant->mc_count;
776 mm_log((1, "makemap_palette(quant %p { mc_count=%d, mc_colors=%p }, imgs %p, count %d)\n",
777 quant, quant->mc_count, quant->mc_colors, imgs, count));
778 /* we try to build a common palette here, if we can manage that, then
779 that's the palette we use */
780 for (imgn = 0; imgn < count; ++imgn) {
781 int eliminate_unused;
782 if (imgs[imgn]->type != i_palette_type) {
783 mm_log((1, "makemap_palette() -> 0 (non-palette image)\n"));
787 if (!i_tags_get_int(&imgs[imgn]->tags, "gif_eliminate_unused", 0,
788 &eliminate_unused)) {
789 eliminate_unused = 1;
792 if (eliminate_unused) {
793 i_palidx *line = mymalloc(sizeof(i_palidx) * imgs[imgn]->xsize);
795 memset(used, 0, sizeof(used));
797 for (y = 0; y < imgs[imgn]->ysize; ++y) {
798 i_gpal(imgs[imgn], 0, imgs[imgn]->xsize, y, line);
799 for (x = 0; x < imgs[imgn]->xsize; ++x)
806 /* assume all are in use */
807 memset(used, 1, sizeof(used));
810 col_count = i_colorcount(imgs[imgn]);
811 for (i = 0; i < col_count; ++i) {
814 i_getcolors(imgs[imgn], i, &c, 1);
816 if (in_palette(&c, quant, size) < 0) {
817 if (size < quant->mc_size) {
818 quant->mc_colors[size++] = c;
821 mm_log((1, "makemap_palette() -> 0 (too many colors)\n"));
829 mm_log((1, "makemap_palette() -> 1 (%d total colors)\n", size));
830 quant->mc_count = size;
837 /* Define one of the following 4 symbols to choose a colour search method
838 The idea is to try these out, including benchmarking, to see which
839 is fastest in a good spread of circumstances.
840 I'd expect IM_CFLINSEARCH to be fastest for very small palettes, and
841 IM_CFHASHBOX for large images with large palettes.
843 Some other possibilities include:
844 - search over entries sorted by luminance
846 Initially I was planning on testing using the macros and then
847 integrating the code directly into each function, but this means if
848 we find a bug at a late stage we will need to update N copies of
849 the same code. Also, keeping the code in the macros means that the
850 code in the translation functions is much more to the point,
851 there's no distracting colour search code to remove attention from
852 what makes _this_ translation function different. It may be
853 advisable to move the setup code into functions at some point, but
854 it should be possible to do this fairly transparently.
856 If IM_CF_COPTS is defined then CFLAGS must have an appropriate
859 Each option needs to define 4 macros:
860 CF_VARS - variables to define in the function
861 CF_SETUP - code to setup for the colour search, eg. allocating and
862 initializing lookup tables
863 CF_FIND - code that looks for the color in val and puts the best
864 matching index in bst_idx
865 CF_CLEANUP - code to clean up, eg. releasing memory
868 /*#define IM_CFLINSEARCH*/
870 /*#define IM_CFSORTCHAN*/
871 /*#define IM_CFRAND2DIST*/
874 /* return true if the color map contains only grays */
876 is_gray_map(const i_quantize *quant) {
879 for (i = 0; i < quant->mc_count; ++i) {
880 if (quant->mc_colors[i].rgb.r != quant->mc_colors[i].rgb.g
881 || quant->mc_colors[i].rgb.r != quant->mc_colors[i].rgb.b) {
882 mm_log((1, " not a gray map\n"));
887 mm_log((1, " is a gray map\n"));
893 /* The original version I wrote for this used the sort.
894 If this is defined then we use a sort to extract the indices for
898 /* assume i is available */
899 #define CF_VARS hashbox *hb = mymalloc(sizeof(hashbox) * 512); \
905 static long *gdists; /* qsort is annoying */
906 /* int might be smaller than long, so we need to do a real compare
907 rather than a subtraction*/
908 static int distcomp(void const *a, void const *b) {
909 long ra = gdists[*(int const *)a];
910 long rb = gdists[*(int const *)b];
921 /* for each hashbox build a list of colours that are in the hb or is closer
923 This is pretty involved. The original gifquant generated the hashbox
924 as part of it's normal processing, but since the map generation is now
925 separated from the translation we need to do this on the spot.
926 Any optimizations, even if they don't produce perfect results would be
929 static void hbsetup(i_quantize *quant, hashbox *hb) {
930 long *dists, mind, maxd;
931 int cr, cb, cg, hbnum, i;
934 int *indices = mymalloc(quant->mc_count * sizeof(int));
937 dists = mymalloc(quant->mc_count * sizeof(long));
938 for (cr = 0; cr < 8; ++cr) {
939 for (cg = 0; cg < 8; ++cg) {
940 for (cb = 0; cb < 8; ++cb) {
941 /* centre of the hashbox */
942 cenc.channel[0] = cr*pboxjump+pboxjump/2;
943 cenc.channel[1] = cg*pboxjump+pboxjump/2;
944 cenc.channel[2] = cb*pboxjump+pboxjump/2;
945 hbnum = pixbox(&cenc);
947 /* order indices in the order of distance from the hashbox */
948 for (i = 0; i < quant->mc_count; ++i) {
952 dists[i] = ceucl_d(&cenc, quant->mc_colors+i);
955 /* it should be possible to do this without a sort
956 but so far I'm too lazy */
958 qsort(indices, quant->mc_count, sizeof(int), distcomp);
959 /* any colors that can match are within mind+diagonal size of
961 mind = dists[indices[0]];
963 maxd = (sqrt(mind)+pboxjump)*(sqrt(mind)+pboxjump);
964 while (i < quant->mc_count && dists[indices[i]] < maxd) {
965 hb[hbnum].vec[hb[hbnum].cnt++] = indices[i++];
968 /* work out the minimum */
970 for (i = 0; i < quant->mc_count; ++i) {
971 if (dists[i] < mind) mind = dists[i];
973 /* transfer any colours that might be closest to a colour in
975 maxd = (sqrt(mind)+pboxjump)*(sqrt(mind)+pboxjump);
976 for (i = 0; i < quant->mc_count; ++i) {
978 hb[hbnum].vec[hb[hbnum].cnt++] = i;
989 #define CF_SETUP hbsetup(quant, hb)
992 currhb = pixbox(&val); \
994 for (i = 0; i < hb[currhb].cnt; ++i) { \
995 cd = ceucl_d(quant->mc_colors+hb[currhb].vec[i], &val); \
996 if (cd < ld) { ld = cd; bst_idx = hb[currhb].vec[i]; } \
999 #define CF_CLEANUP myfree(hb)
1003 #ifdef IM_CFLINSEARCH
1004 /* as simple as it gets */
1005 #define CF_VARS long ld, cd
1006 #define CF_SETUP /* none needed */
1009 for (i = 0; i < quant->mc_count; ++i) { \
1010 cd = ceucl_d(quant->mc_colors+i, &val); \
1011 if (cd < ld) { ld = cd; bst_idx = i; } \
1016 #ifdef IM_CFSORTCHAN
1017 static int gsortchan;
1018 static i_quantize *gquant;
1019 static int chansort(void const *a, void const *b) {
1020 return gquant->mc_colors[*(int const *)a].channel[gsortchan] -
1021 gquant->mc_colors[*(int const *)b].channel[gsortchan];
1023 #define CF_VARS int *indices, sortchan, diff; \
1025 int vindex[256] /* where to find value i of chan */
1027 static void chansetup(i_img *img, i_quantize *quant, int *csortchan,
1028 int *vindex, int **cindices) {
1029 int *indices, sortchan, chan, i, chval;
1030 int chanmins[MAXCHANNELS], chanmaxs[MAXCHANNELS], maxrange;
1032 /* find the channel with the maximum range */
1033 /* the maximum stddev would probably be better */
1034 for (chan = 0; chan < img->channels; ++chan) {
1035 chanmins[chan] = 256; chanmaxs[chan] = 0;
1036 for (i = 0; i < quant->mc_count; ++i) {
1037 if (quant->mc_colors[i].channel[chan] < chanmins[chan])
1038 chanmins[chan] = quant->mc_colors[i].channel[chan];
1039 if (quant->mc_colors[i].channel[chan] > chanmaxs[chan])
1040 chanmaxs[chan] = quant->mc_colors[i].channel[chan];
1044 for (chan = 0; chan < img->channels; ++chan) {
1045 if (chanmaxs[chan]-chanmins[chan] > maxrange) {
1046 maxrange = chanmaxs[chan]-chanmins[chan];
1050 indices = mymalloc(quant->mc_count * sizeof(int)) ;
1051 for (i = 0; i < quant->mc_count; ++i) {
1054 gsortchan = sortchan;
1056 qsort(indices, quant->mc_count, sizeof(int), chansort) ;
1057 /* now a lookup table to find entries faster */
1058 for (chval=0, i=0; i < quant->mc_count; ++i) {
1059 while (chval < 256 &&
1060 chval < quant->mc_colors[indices[i]].channel[sortchan]) {
1061 vindex[chval++] = i;
1064 while (chval < 256) {
1065 vindex[chval++] = quant->mc_count-1;
1067 *csortchan = sortchan;
1068 *cindices = indices;
1072 chansetup(img, quant, &sortchan, vindex, &indices)
1074 int chanfind(i_color val, i_quantize *quant, int *indices, int *vindex,
1076 int i, bst_idx, diff, maxdiff;
1079 i = vindex[val.channel[sortchan]];
1080 bst_idx = indices[i];
1083 maxdiff = quant->mc_count;
1084 while (diff < maxdiff) {
1085 if (i+diff < quant->mc_count) {
1086 cd = ceucl_d(&val, quant->mc_colors+indices[i+diff]);
1088 bst_idx = indices[i+diff];
1094 cd = ceucl_d(&val, quant->mc_colors+indices[i-diff]);
1096 bst_idx = indices[i-diff];
1108 bst_idx = chanfind(val, quant, indices, vindex, sortchan)
1111 #define CF_CLEANUP myfree(indices)
1115 #ifdef IM_CFRAND2DIST
1117 /* This is based on a method described by Addi in the #imager channel
1118 on the 28/2/2001. I was about 1am Sydney time at the time, so I
1119 wasn't at my most cogent. Well, that's my excuse :)
1121 <TonyC> what I have at the moment is: hashboxes, with optimum hash box
1122 filling; simple linear search; and a lookup in the widest channel
1123 (currently the channel with the maximum range)
1124 <Addi> There is one more way that might be simple to implement.
1125 <Addi> You want to hear?
1126 <TonyC> what's that?
1127 <purl> somebody said that was not true
1128 <Addi> For each of the colors in the palette start by creating a
1129 sorted list of the form:
1130 <Addi> [distance, color]
1131 <Addi> Where they are sorted by distance.
1132 <TonyC> distance to where?
1133 <Addi> Where the elements in the lists are the distances and colors of
1134 the other colors in the palette
1136 <Addi> So if you are at color 0
1137 <Addi> ok - now to search for the closest color when you are creating
1138 the final image is done like this:
1139 <Addi> a) pick a random color from the palette
1140 <Addi> b) calculate the distance to it
1141 <Addi> c) only check the vectors that are within double the distance
1142 in the list of the color you picked from the palette.
1143 <Addi> Does that seem logical?
1144 <Addi> Lets imagine that we only have grayscale to make an example:
1145 <Addi> Our palette has 1 4 10 20 as colors.
1146 <Addi> And we want to quantize the color 11
1147 <Addi> lets say we picked 10 randomly
1148 <Addi> the double distance is 2
1149 <Addi> since abs(10-11)*2 is 2
1150 <Addi> And the list at vector 10 is this:
1151 <Addi> [0, 10], [6 4], [9, 1], [10, 20]
1152 <Addi> so we look at the first one (but not the second one since 6 is
1153 at a greater distance than 2.
1154 <Addi> Any of that make sense?
1155 <TonyC> yes, though are you suggesting another random jump to one of
1156 the colours with the possible choices? or an exhaustive search?
1157 <Addi> TonyC: It's possible to come up with a recursive/iterative
1158 enhancement but this is the 'basic' version.
1159 <Addi> Which would do an iterative search.
1160 <Addi> You can come up with conditions where it pays to switch to a new one.
1161 <Addi> And the 'random' start can be switched over to a small tree.
1162 <Addi> So you would have a little index at the start.
1163 <Addi> to get you into the general direction
1164 <Addi> Perhaps just an 8 split.
1165 <Addi> that is - split each dimension in half.
1167 <TonyC> I get the idea
1168 <Addi> But this would seem to be a good approach in our case since we
1169 usually have few codevectors.
1170 <Addi> So we only need 256*256 entries in a table.
1171 <Addi> We could even only index some of them that were deemed as good
1173 <TonyC> I was considering adding paletted output support for PNG and
1174 TIFF at some point, which support 16-bit palettes
1182 typedef struct i_dists {
1190 static int dists_sort(void const *a, void const *b) {
1191 return ((i_dists *)a)->dist - ((i_dists *)b)->dist;
1194 static void rand2dist_setup(i_quantize *quant, i_dists **cdists) {
1196 mymalloc(sizeof(i_dists)*quant->mc_count*quant->mc_count);
1199 for (i = 0; i < quant->mc_count; ++i) {
1200 i_dists *ldists = dists + quant->mc_count * i;
1201 i_color val = quant->mc_colors[i];
1202 for (j = 0; j < quant->mc_count; ++j) {
1203 ldists[j].index = j;
1204 ldists[j].dist = ceucl_d(&val, quant->mc_colors+j);
1206 qsort(ldists, quant->mc_count, sizeof(i_dists), dists_sort);
1212 bst_idx = rand() % quant->mc_count; \
1213 rand2dist_setup(quant, &dists)
1215 static int rand2dist_find(i_color val, i_quantize *quant, i_dists *dists, int index) {
1222 cdists = dists + index * quant->mc_count;
1224 maxld = 8 * ceucl_d(&val, quant->mc_colors+index);
1225 for (i = 0; i < quant->mc_count && cdists[i].dist <= maxld; ++i) {
1226 cd = ceucl_d(&val, quant->mc_colors+cdists[i].index);
1228 bst_idx = cdists[i].index;
1235 #define CF_FIND bst_idx = rand2dist_find(val, quant, dists, bst_idx)
1237 #define CF_CLEANUP myfree(dists)
1242 static void translate_addi(i_quantize *quant, i_img *img, i_palidx *out) {
1246 int pixdev = quant->perturb;
1251 if (img->channels >= 3) {
1254 for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) {
1255 i_gpix(img,x,y,&val);
1256 val.channel[0]=g_sat(val.channel[0]+(int)(pixdev*frandn()));
1257 val.channel[1]=g_sat(val.channel[1]+(int)(pixdev*frandn()));
1258 val.channel[2]=g_sat(val.channel[2]+(int)(pixdev*frandn()));
1264 for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) {
1265 i_gpix(img,x,y,&val);
1274 for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) {
1275 i_gpix(img,x,y,&val);
1276 val.channel[1] = val.channel[2] =
1277 val.channel[0]=g_sat(val.channel[0]+(int)(pixdev*frandn()));
1283 for(y=0;y<img->ysize;y++) for(x=0;x<img->xsize;x++) {
1284 i_gpix(img,x,y,&val);
1285 val.channel[1] = val.channel[2] = val.channel[0];
1294 static int floyd_map[] =
1300 static int jarvis_map[] =
1307 static int stucki_map[] =
1314 struct errdiff_map {
1316 int width, height, orig;
1319 static struct errdiff_map maps[] =
1321 { floyd_map, 3, 2, 1 },
1322 { jarvis_map, 5, 3, 2 },
1323 { stucki_map, 5, 3, 2 },
1326 typedef struct errdiff_tag {
1330 /* perform an error diffusion dither */
1333 translate_errdiff(i_quantize *quant, i_img *img, i_palidx *out) {
1335 int mapw, maph, mapo;
1340 i_img_dim x, y, dx, dy;
1342 int is_gray = is_gray_map(quant);
1345 if ((quant->errdiff & ed_mask) == ed_custom) {
1346 map = quant->ed_map;
1347 mapw = quant->ed_width;
1348 maph = quant->ed_height;
1349 mapo = quant->ed_orig;
1352 int index = quant->errdiff & ed_mask;
1353 if (index >= ed_custom) index = ed_floyd;
1354 map = maps[index].map;
1355 mapw = maps[index].width;
1356 maph = maps[index].height;
1357 mapo = maps[index].orig;
1360 errw = img->xsize+mapw;
1361 err = mymalloc(sizeof(*err) * maph * errw);
1362 /*errp = err+mapo;*/
1363 memset(err, 0, sizeof(*err) * maph * errw);
1366 for (i = 0; i < maph * mapw; ++i)
1367 difftotal += map[i];
1369 for (dy = 0; dy < maph; ++dy) {
1370 for (dx = 0; dx < mapw; ++dx) {
1371 printf("%2d", map[dx+dy*mapw]);
1378 for (y = 0; y < img->ysize; ++y) {
1379 for (x = 0; x < img->xsize; ++x) {
1382 i_gpix(img, x, y, &val);
1383 if (img->channels < 3) {
1384 val.channel[1] = val.channel[2] = val.channel[0];
1387 int gray = 0.5 + color_to_grey(&val);
1388 val.channel[0] = val.channel[1] = val.channel[2] = gray;
1391 perr.r = perr.r < 0 ? -((-perr.r)/difftotal) : perr.r/difftotal;
1392 perr.g = perr.g < 0 ? -((-perr.g)/difftotal) : perr.g/difftotal;
1393 perr.b = perr.b < 0 ? -((-perr.b)/difftotal) : perr.b/difftotal;
1394 /*printf("x %3d y %3d in(%3d, %3d, %3d) di(%4d,%4d,%4d)\n", x, y, val.channel[0], val.channel[1], val.channel[2], perr.r, perr.g, perr.b);*/
1395 val.channel[0] = g_sat(val.channel[0]-perr.r);
1396 val.channel[1] = g_sat(val.channel[1]-perr.g);
1397 val.channel[2] = g_sat(val.channel[2]-perr.b);
1400 perr.r = quant->mc_colors[bst_idx].channel[0] - val.channel[0];
1401 perr.g = quant->mc_colors[bst_idx].channel[1] - val.channel[1];
1402 perr.b = quant->mc_colors[bst_idx].channel[2] - val.channel[2];
1403 /*printf(" out(%3d, %3d, %3d) er(%4d, %4d, %4d)\n", quant->mc_colors[bst_idx].channel[0], quant->mc_colors[bst_idx].channel[1], quant->mc_colors[bst_idx].channel[2], perr.r, perr.g, perr.b);*/
1404 for (dx = 0; dx < mapw; ++dx) {
1405 for (dy = 0; dy < maph; ++dy) {
1406 err[x+dx+dy*errw].r += perr.r * map[dx+mapw*dy];
1407 err[x+dx+dy*errw].g += perr.g * map[dx+mapw*dy];
1408 err[x+dx+dy*errw].b += perr.b * map[dx+mapw*dy];
1413 /* shift up the error matrix */
1414 for (dy = 0; dy < maph-1; ++dy) {
1415 memcpy(err+dy*errw, err+(dy+1)*errw, sizeof(*err)*errw);
1417 memset(err+(maph-1)*errw, 0, sizeof(*err)*errw);
1422 /* Prescan finds the boxes in the image that have the highest number of colors
1423 and that result is used as the initial value for the vectores */
1426 static void prescan(i_img **imgs,int count, int cnum, cvec *clr, i_sample_t *line) {
1433 for(i=0;i<512;i++) {
1439 /* process each image */
1440 for (i = 0; i < count; ++i) {
1441 i_img *im = imgs[i];
1442 chans = im->channels >= 3 ? NULL : gray_samples;
1443 for(y=0;y<im->ysize;y++) {
1444 i_gsamp(im, 0, im->xsize, y, line, chans, 3);
1446 for(x=0;x<im->xsize;x++) {
1447 prebox[pixbox_ch(val)].pixcnt++;
1452 for(i=0;i<512;i++) prebox[i].pdc=prebox[i].pixcnt;
1453 qsort(prebox,512,sizeof(pbox),(cmpfunc)pboxcmp);
1455 for(i=0;i<cnum;i++) {
1456 /* printf("Color %d\n",i);
1457 for(k=0;k<10;k++) { printf("box=%03d %04d %d %04d \n",prebox[k].boxnum,prebox[k].pixcnt,prebox[k].cand,prebox[k].pdc); }
1462 /* for(k=0;k<cnum;k++) { printf("box=%03d %04d %d %04d \n",prebox[k].boxnum,prebox[k].pixcnt,prebox[k].cand,prebox[k].pdc); } */
1468 /* printf("prebox[%d].cand=%d\n",k,prebox[k].cand); */
1469 if (clr[i].fixed) { i++; continue; } /* reserved go to next */
1470 if (j>=prebox[k].cand) { k++; j=1; } else {
1471 if (prebox[k].cand == 2) boxcenter(prebox[k].boxnum,&(clr[i]));
1472 else boxrand(prebox[k].boxnum,&(clr[i]));
1473 /* printf("(%d,%d) %d %d -> (%d,%d,%d)\n",k,j,prebox[k].boxnum,prebox[k].pixcnt,clr[i].r,clr[i].g,clr[i].b); */
1481 static void reorder(pbox prescan[512]) {
1489 c.pdc=c.pixcnt/(c.cand*c.cand);
1490 /* c.pdc=c.pixcnt/c.cand; */
1491 while(c.pdc < prescan[nidx+1].pdc && nidx < 511) {
1492 prescan[nidx]=prescan[nidx+1];
1499 pboxcmp(const pbox *a,const pbox *b) {
1500 if (a->pixcnt > b->pixcnt) return -1;
1501 if (a->pixcnt < b->pixcnt) return 1;
1506 boxcenter(int box,cvec *cv) {
1507 cv->r=15+((box&448)>>1);
1508 cv->g=15+((box&56)<<2);
1509 cv->b=15+((box&7)<<5);
1513 bbox(int box,int *r0,int *r1,int *g0,int *g1,int *b0,int *b1) {
1523 boxrand(int box,cvec *cv) {
1524 cv->r=6+(rand()%25)+((box&448)>>1);
1525 cv->g=6+(rand()%25)+((box&56)<<2);
1526 cv->b=6+(rand()%25)+((box&7)<<5);
1536 while (w >= 1 || w == 0) {
1537 u1 = 2 * frand() - 1;
1538 u2 = 2 * frand() - 1;
1542 w = sqrt((-2*log(w))/w);
1546 /* Create hash index */
1549 cr_hashindex(cvec clr[256],int cnum,hashbox hb[512]) {
1551 int bx,mind,cd,cumcnt,bst_idx,i;
1552 /* printf("indexing... \n");*/
1555 for(bx=0; bx<512; bx++) {
1557 for(i=0; i<cnum; i++) {
1558 cd = maxdist(bx,&clr[i]);
1559 if (cd < mind) { mind=cd; bst_idx=i; }
1563 for(i=0;i<cnum;i++) if (mindist(bx,&clr[i])<mind) hb[bx].vec[hb[bx].cnt++]=i;
1564 /*printf("box %d -> approx -> %d\n",bx,hb[bx].cnt); */
1565 /* statbox(bx,cnum,clr); */
1569 /* printf("Average search space: %d\n",cumcnt/512); */
1573 maxdist(int boxnum,cvec *cv) {
1574 int r0,r1,g0,g1,b0,b1;
1581 bbox(boxnum,&r0,&r1,&g0,&g1,&b0,&b1);
1583 mr=i_max(abs(b-b0),abs(b-b1));
1584 mg=i_max(abs(g-g0),abs(g-g1));
1585 mb=i_max(abs(r-r0),abs(r-r1));
1587 return PWR2(mr)+PWR2(mg)+PWR2(mb);
1591 mindist(int boxnum,cvec *cv) {
1592 int r0,r1,g0,g1,b0,b1;
1599 bbox(boxnum,&r0,&r1,&g0,&g1,&b0,&b1);
1601 /* printf("box %d, (%d,%d,%d)-(%d,%d,%d) vec (%d,%d,%d) ",boxnum,r0,g0,b0,r1,g1,b1,r,g,b); */
1603 if (r0<=r && r<=r1 && g0<=g && g<=g1 && b0<=b && b<=b1) return 0;
1605 mr=i_min(abs(b-b0),abs(b-b1));
1606 mg=i_min(abs(g-g0),abs(g-g1));
1607 mb=i_min(abs(r-r0),abs(r-r1));
1613 if (r0<=r && r<=r1 && g0<=g && g<=g1) return mb;
1614 if (r0<=r && r<=r1 && b0<=b && b<=b1) return mg;
1615 if (b0<=b && b<=b1 && g0<=g && g<=g1) return mr;
1617 if (r0<=r && r<=r1) return mg+mb;
1618 if (g0<=g && g<=g1) return mr+mb;
1619 if (b0<=b && b<=b1) return mg+mr;
1624 static void transparent_threshold(i_quantize *, i_palidx *, i_img *, i_palidx);
1625 static void transparent_errdiff(i_quantize *, i_palidx *, i_img *, i_palidx);
1626 static void transparent_ordered(i_quantize *, i_palidx *, i_img *, i_palidx);
1629 =item i_quant_transparent(C<quant>, C<data>, C<img>, C<trans_index>)
1631 =category Image quantization
1633 Dither the alpha channel on C<img> into the palette indexes in
1634 C<data>. Pixels to be transparent are replaced with C<trans_pixel>.
1636 The method used depends on the tr_* members of C<quant>.
1642 i_quant_transparent(i_quantize *quant, i_palidx *data, i_img *img,
1643 i_palidx trans_index)
1645 switch (quant->transp) {
1650 quant->tr_threshold = 128;
1653 transparent_threshold(quant, data, img, trans_index);
1657 transparent_errdiff(quant, data, img, trans_index);
1661 transparent_ordered(quant, data, img, trans_index);
1667 transparent_threshold(i_quantize *quant, i_palidx *data, i_img *img,
1668 i_palidx trans_index)
1671 i_sample_t *line = mymalloc(img->xsize * sizeof(i_sample_t));
1672 int trans_chan = img->channels > 2 ? 3 : 1;
1674 for (y = 0; y < img->ysize; ++y) {
1675 i_gsamp(img, 0, img->xsize, y, line, &trans_chan, 1);
1676 for (x = 0; x < img->xsize; ++x) {
1677 if (line[x] < quant->tr_threshold)
1678 data[y*img->xsize+x] = trans_index;
1685 transparent_errdiff(i_quantize *quant, i_palidx *data, i_img *img,
1686 i_palidx trans_index)
1690 int mapw, maph, mapo;
1691 int errw, *err, *errp;
1692 int difftotal, out, error;
1693 i_img_dim x, y, dx, dy;
1696 int trans_chan = img->channels > 2 ? 3 : 1;
1698 /* no custom map for transparency (yet) */
1699 index = quant->tr_errdiff & ed_mask;
1700 if (index >= ed_custom) index = ed_floyd;
1701 map = maps[index].map;
1702 mapw = maps[index].width;
1703 maph = maps[index].height;
1704 mapo = maps[index].orig;
1706 errw = img->xsize+mapw-1;
1707 err = mymalloc(sizeof(*err) * maph * errw);
1709 memset(err, 0, sizeof(*err) * maph * errw);
1711 line = mymalloc(img->xsize * sizeof(i_sample_t));
1713 for (i = 0; i < maph * mapw; ++i)
1714 difftotal += map[i];
1715 for (y = 0; y < img->ysize; ++y) {
1716 i_gsamp(img, 0, img->xsize, y, line, &trans_chan, 1);
1717 for (x = 0; x < img->xsize; ++x) {
1718 line[x] = g_sat(line[x]-errp[x]/difftotal);
1719 if (line[x] < 128) {
1721 data[y*img->xsize+x] = trans_index;
1726 error = out - line[x];
1727 for (dx = 0; dx < mapw; ++dx) {
1728 for (dy = 0; dy < maph; ++dy) {
1729 errp[x+dx-mapo+dy*errw] += error * map[dx+mapw*dy];
1733 /* shift up the error matrix */
1734 for (dy = 0; dy < maph-1; ++dy)
1735 memcpy(err+dy*errw, err+(dy+1)*errw, sizeof(*err)*errw);
1736 memset(err+(maph-1)*errw, 0, sizeof(*err)*errw);
1742 /* builtin ordered dither maps */
1743 static unsigned char
1744 orddith_maps[][64] =
1747 this is purely random - it's pretty awful
1749 48, 72, 196, 252, 180, 92, 108, 52,
1750 228, 176, 64, 8, 236, 40, 20, 164,
1751 120, 128, 84, 116, 24, 28, 172, 220,
1752 68, 0, 188, 124, 184, 224, 192, 104,
1753 132, 100, 240, 200, 152, 160, 244, 44,
1754 96, 204, 144, 16, 140, 56, 232, 216,
1755 208, 4, 76, 212, 136, 248, 80, 168,
1756 156, 88, 32, 112, 148, 12, 36, 60,
1760 perl spot.perl '($x-3.5)*($x-3.5)+($y-3.5)*($y-3.5)'
1762 240, 232, 200, 136, 140, 192, 228, 248,
1763 220, 148, 100, 76, 80, 104, 152, 212,
1764 180, 116, 56, 32, 36, 60, 120, 176,
1765 156, 64, 28, 0, 8, 44, 88, 160,
1766 128, 92, 24, 12, 4, 40, 68, 132,
1767 184, 96, 48, 20, 16, 52, 108, 188,
1768 216, 144, 112, 72, 84, 124, 164, 224,
1769 244, 236, 196, 168, 172, 204, 208, 252,
1773 'min(dist(1.5, 1.5),dist(5.5,1.5),dist(1.5,5.5),dist(5.5,5.5))'
1775 196, 72, 104, 220, 200, 80, 112, 224,
1776 76, 4, 24, 136, 84, 8, 32, 144,
1777 108, 28, 52, 168, 116, 36, 56, 176,
1778 216, 140, 172, 244, 228, 148, 180, 248,
1779 204, 92, 124, 236, 192, 68, 96, 208,
1780 88, 12, 44, 156, 64, 0, 16, 128,
1781 120, 40, 60, 188, 100, 20, 48, 160,
1782 232, 152, 184, 252, 212, 132, 164, 240,
1785 perl spot.perl '$y-3'
1787 160, 164, 168, 172, 176, 180, 184, 188,
1788 128, 132, 136, 140, 144, 148, 152, 156,
1789 32, 36, 40, 44, 48, 52, 56, 60,
1790 0, 4, 8, 12, 16, 20, 24, 28,
1791 64, 68, 72, 76, 80, 84, 88, 92,
1792 96, 100, 104, 108, 112, 116, 120, 124,
1793 192, 196, 200, 204, 208, 212, 216, 220,
1794 224, 228, 232, 236, 240, 244, 248, 252,
1797 perl spot.perl '$x-3'
1799 180, 100, 40, 12, 44, 104, 184, 232,
1800 204, 148, 60, 16, 64, 128, 208, 224,
1801 212, 144, 76, 8, 80, 132, 216, 244,
1802 160, 112, 68, 20, 84, 108, 172, 236,
1803 176, 96, 72, 28, 88, 152, 188, 228,
1804 200, 124, 92, 0, 32, 116, 164, 240,
1805 168, 120, 36, 24, 48, 136, 192, 248,
1806 196, 140, 52, 4, 56, 156, 220, 252,
1809 perl spot.perl '$y+$x-7'
1811 248, 232, 224, 192, 140, 92, 52, 28,
1812 240, 220, 196, 144, 108, 60, 12, 64,
1813 216, 180, 148, 116, 76, 20, 80, 128,
1814 204, 152, 104, 44, 16, 72, 100, 160,
1815 164, 96, 68, 24, 56, 112, 168, 176,
1816 124, 40, 8, 36, 88, 136, 184, 212,
1817 84, 4, 32, 120, 156, 188, 228, 236,
1818 0, 48, 132, 172, 200, 208, 244, 252,
1821 perl spot.perl '$y-$x'
1823 0, 32, 116, 172, 184, 216, 236, 252,
1824 56, 8, 72, 132, 136, 200, 228, 240,
1825 100, 36, 12, 40, 92, 144, 204, 220,
1826 168, 120, 60, 16, 44, 96, 156, 176,
1827 180, 164, 112, 48, 28, 52, 128, 148,
1828 208, 192, 152, 88, 84, 20, 64, 104,
1829 232, 224, 196, 140, 108, 68, 24, 76,
1830 248, 244, 212, 188, 160, 124, 80, 4,
1834 good for display, bad for print
1837 0, 128, 32, 192, 8, 136, 40, 200,
1838 224, 64, 160, 112, 232, 72, 168, 120,
1839 48, 144, 16, 208, 56, 152, 24, 216,
1840 176, 96, 240, 80, 184, 104, 248, 88,
1841 12, 140, 44, 204, 4, 132, 36, 196,
1842 236, 76, 172, 124, 228, 68, 164, 116,
1843 60, 156, 28, 220, 52, 148, 20, 212,
1844 188, 108, 252, 92, 180, 100, 244, 84,
1849 transparent_ordered(i_quantize *quant, i_palidx *data, i_img *img,
1850 i_palidx trans_index)
1852 unsigned char *spot;
1855 int trans_chan = img->channels > 2 ? 3 : 1;
1856 if (quant->tr_orddith == od_custom)
1857 spot = quant->tr_custom;
1859 spot = orddith_maps[quant->tr_orddith];
1861 line = mymalloc(img->xsize * sizeof(i_sample_t));
1862 for (y = 0; y < img->ysize; ++y) {
1863 i_gsamp(img, 0, img->xsize, y, line, &trans_chan, 1);
1864 for (x = 0; x < img->xsize; ++x) {
1865 if (line[x] < spot[(x&7)+(y&7)*8])
1866 data[x+y*img->xsize] = trans_index;