1 /* Image processing functions
2 Copyright (C) 1998 Jareth Hein
4 This file is a part of XEmacs
6 XEmacs is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 XEmacs is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with XEmacs; see the file COPYING. If not, write to
18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
21 /* Synched up with: Not in FSF. */
23 /* Original author: Jareth Hein */
25 /* Parts of this file are based on code from Sam Leffler's tiff library,
26 with the original copyright displayed here:
28 Copyright (c) 1988-1997 Sam Leffler
29 Copyright (c) 1991-1997 Silicon Graphics, Inc.
31 Permission to use, copy, modify, distribute, and sell this software and
32 its documentation for any purpose is hereby granted without fee, provided
33 that (i) the above copyright notices and this permission notice appear in
34 all copies of the software and related documentation, and (ii) the names of
35 Sam Leffler and Silicon Graphics may not be used in any advertising or
36 publicity relating to the software without the specific, prior written
37 permission of Sam Leffler and Silicon Graphics. */
39 /* Quantizing code based off of the paper
40 Color Image Quantization for Frame Buffer Display, Paul Heckbert,
41 Siggraph '82 proceedings, pp. 297-307 */
48 get_histogram(quant_table *qt, unsigned char *pic,
49 int width, int height, Colorbox* box)
51 register unsigned char *inptr;
52 register int red, green, blue;
55 box->rmin = box->gmin = box->bmin = 999;
56 box->rmax = box->gmax = box->bmax = -1;
57 box->total = width * height;
60 for (i = 0; i < height; i++)
62 for (j = width; j-- > 0;)
64 red = *inptr++ >> COLOR_SHIFT;
65 green = *inptr++ >> COLOR_SHIFT;
66 blue = *inptr++ >> COLOR_SHIFT;
71 if (green < box->gmin)
73 if (green > box->gmax)
79 qt->histogram[red][green][blue]++;
85 largest_box(quant_table *qt)
87 register Colorbox *p, *b;
92 for (p = qt->usedboxes; p != NULL; p = p->next)
93 if ((p->rmax > p->rmin || p->gmax > p->gmin ||
94 p->bmax > p->bmin) && p->total > size)
95 size = (b = p)->total;
100 shrinkbox(quant_table *qt, Colorbox* box)
102 register int *histp, ir, ig, ib;
104 if (box->rmax > box->rmin)
106 for (ir = box->rmin; ir <= box->rmax; ++ir)
107 for (ig = box->gmin; ig <= box->gmax; ++ig)
109 histp = &(qt->histogram[ir][ig][box->bmin]);
110 for (ib = box->bmin; ib <= box->bmax; ++ib)
118 if (box->rmax > box->rmin)
119 for (ir = box->rmax; ir >= box->rmin; --ir)
120 for (ig = box->gmin; ig <= box->gmax; ++ig)
122 histp = &(qt->histogram[ir][ig][box->bmin]);
124 for (; ib <= box->bmax; ++ib)
133 if (box->gmax > box->gmin)
135 for (ig = box->gmin; ig <= box->gmax; ++ig)
136 for (ir = box->rmin; ir <= box->rmax; ++ir)
138 histp = &(qt->histogram[ir][ig][box->bmin]);
139 for (ib = box->bmin; ib <= box->bmax; ++ib)
147 if (box->gmax > box->gmin)
148 for (ig = box->gmax; ig >= box->gmin; --ig)
149 for (ir = box->rmin; ir <= box->rmax; ++ir)
151 histp = &(qt->histogram[ir][ig][box->bmin]);
153 for (; ib <= box->bmax; ++ib)
162 if (box->bmax > box->bmin)
164 for (ib = box->bmin; ib <= box->bmax; ++ib)
165 for (ir = box->rmin; ir <= box->rmax; ++ir)
167 histp = &(qt->histogram[ir][box->gmin][ib]);
168 for (ig = box->gmin; ig <= box->gmax; ++ig)
179 if (box->bmax > box->bmin)
180 for (ib = box->bmax; ib >= box->bmin; --ib)
181 for (ir = box->rmin; ir <= box->rmax; ++ir)
183 histp = &(qt->histogram[ir][box->gmin][ib]);
185 for (; ig <= box->gmax; ++ig)
201 splitbox(quant_table *qt, Colorbox* ptr)
204 int first = 0, last = 0;
205 register Colorbox *new;
206 register int *iptr, *histp;
208 register int ir,ig,ib;
209 register int sum, sum1, sum2;
210 enum { RED, GREEN, BLUE } axis;
213 * See which axis is the largest, do a histogram along that
214 * axis. Split at median point. Contract both new boxes to
215 * fit points and return
217 i = ptr->rmax - ptr->rmin;
218 if (i >= ptr->gmax - ptr->gmin && i >= ptr->bmax - ptr->bmin)
220 else if (ptr->gmax - ptr->gmin >= ptr->bmax - ptr->bmin)
224 /* get histogram along longest axis */
228 histp = &hist2[ptr->rmin];
229 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir)
232 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig)
234 iptr = &(qt->histogram[ir][ig][ptr->bmin]);
235 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
244 histp = &hist2[ptr->gmin];
245 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig)
248 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir)
250 iptr = &(qt->histogram[ir][ig][ptr->bmin]);
251 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
260 histp = &hist2[ptr->bmin];
261 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
264 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir)
266 iptr = &(qt->histogram[ir][ptr->gmin][ib]);
267 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig)
279 /* find median point */
280 sum2 = ptr->total / 2;
281 histp = &hist2[first];
283 for (i = first; i <= last && (sum += *histp++) < sum2; ++i)
288 /* Create new box, re-allocate points */
290 qt->freeboxes = new->next;
292 qt->freeboxes->prev = NULL;
294 qt->usedboxes->prev = new;
295 new->next = qt->usedboxes;
298 histp = &hist2[first];
299 for (sum1 = 0, j = first; j < i; j++)
301 for (sum2 = 0, j = i; j <= last; j++)
306 new->rmin = ptr->rmin;
307 new->rmax = ptr->rmax;
308 new->gmin = ptr->gmin;
309 new->gmax = ptr->gmax;
310 new->bmin = ptr->bmin;
311 new->bmax = ptr->bmax;
333 create_colorcell(quant_table *qt, int num_colors, int red, int green, int blue)
335 register int ir, ig, ib, i;
336 register C_cell *ptr;
338 register int tmp, dist, n;
340 ir = red >> (COLOR_DEPTH-C_DEPTH);
341 ig = green >> (COLOR_DEPTH-C_DEPTH);
342 ib = blue >> (COLOR_DEPTH-C_DEPTH);
343 ptr = (C_cell *)xmalloc(sizeof (C_cell));
344 *(qt->ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib) = ptr;
348 * Step 1: find all colors inside this cell, while we're at
349 * it, find distance of centermost point to furthest corner
352 for (i = 0; i < num_colors; ++i)
354 if (qt->rm[i]>>(COLOR_DEPTH-C_DEPTH) != ir ||
355 qt->gm[i]>>(COLOR_DEPTH-C_DEPTH) != ig ||
356 qt->bm[i]>>(COLOR_DEPTH-C_DEPTH) != ib)
358 ptr->entries[ptr->num_ents][0] = i;
359 ptr->entries[ptr->num_ents][1] = 0;
361 tmp = qt->rm[i] - red;
362 if (tmp < (MAX_COLOR/C_LEN/2))
363 tmp = MAX_COLOR/C_LEN-1 - tmp;
365 tmp = qt->gm[i] - green;
366 if (tmp < (MAX_COLOR/C_LEN/2))
367 tmp = MAX_COLOR/C_LEN-1 - tmp;
369 tmp = qt->bm[i] - blue;
370 if (tmp < (MAX_COLOR/C_LEN/2))
371 tmp = MAX_COLOR/C_LEN-1 - tmp;
378 * Step 3: find all points within that distance to cell.
380 for (i = 0; i < num_colors; ++i)
382 if (qt->rm[i] >> (COLOR_DEPTH-C_DEPTH) == ir &&
383 qt->gm[i] >> (COLOR_DEPTH-C_DEPTH) == ig &&
384 qt->bm[i] >> (COLOR_DEPTH-C_DEPTH) == ib)
387 if ((tmp = red - qt->rm[i]) > 0 ||
388 (tmp = qt->rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 )
390 if ((tmp = green - qt->gm[i]) > 0 ||
391 (tmp = qt->gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 )
393 if ((tmp = blue - qt->bm[i]) > 0 ||
394 (tmp = qt->bm[i] - (blue + MAX_COLOR/C_LEN-1)) > 0 )
398 ptr->entries[ptr->num_ents][0] = i;
399 ptr->entries[ptr->num_ents][1] = dist;
405 * Sort color cells by distance, use cheap exchange sort
407 for (n = ptr->num_ents - 1; n > 0; n = next_n)
410 for (i = 0; i < n; ++i)
411 if (ptr->entries[i][1] > ptr->entries[i+1][1])
413 tmp = ptr->entries[i][0];
414 ptr->entries[i][0] = ptr->entries[i+1][0];
415 ptr->entries[i+1][0] = tmp;
416 tmp = ptr->entries[i][1];
417 ptr->entries[i][1] = ptr->entries[i+1][1];
418 ptr->entries[i+1][1] = tmp;
426 map_colortable(quant_table *qt, int num_colors)
428 register int *histp = &(qt->histogram[0][0][0]);
429 register C_cell *cell;
430 register int j, tmp, d2, dist;
433 for (ir = 0; ir < B_LEN; ++ir)
434 for (ig = 0; ig < B_LEN; ++ig)
435 for (ib = 0; ib < B_LEN; ++ib, histp++)
442 cell = *(qt->ColorCells +
443 (((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) +
444 ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH) +
445 (ib>>(B_DEPTH-C_DEPTH))));
447 cell = create_colorcell (qt, num_colors,
451 if (cell == NULL) /* memory exhausted! punt! */
454 for (i = 0; i < cell->num_ents &&
455 dist > cell->entries[i][1]; ++i)
457 j = cell->entries[i][0];
458 d2 = qt->rm[j] - (ir << COLOR_SHIFT);
460 tmp = qt->gm[j] - (ig << COLOR_SHIFT);
462 tmp = qt->bm[j] - (ib << COLOR_SHIFT);
475 build_EImage_quantable(unsigned char *eimage, int width, int height, int num_colors)
478 Colorbox *box_list, *ptr;
481 qt = (quant_table*)xmalloc_and_zero (sizeof(quant_table));
482 if (qt == NULL) return NULL;
484 assert (num_colors < 257 && num_colors > 2);
486 * STEP 1: create empty boxes
488 qt->usedboxes = NULL;
489 box_list = qt->freeboxes = (Colorbox *)xmalloc (num_colors*sizeof (Colorbox));
490 qt->freeboxes[0].next = &(qt->freeboxes[1]);
491 qt->freeboxes[0].prev = NULL;
492 for (i = 1; i < num_colors-1; ++i)
494 qt->freeboxes[i].next = &(qt->freeboxes[i+1]);
495 qt->freeboxes[i].prev = &(qt->freeboxes[i-1]);
497 qt->freeboxes[num_colors-1].next = NULL;
498 qt->freeboxes[num_colors-1].prev = &(qt->freeboxes[num_colors-2]);
501 * STEP 2: get histogram, initialize first box
504 qt->freeboxes = ptr->next;
506 qt->freeboxes->prev = NULL;
507 ptr->next = qt->usedboxes;
510 ptr->next->prev = ptr;
511 get_histogram (qt, eimage, width, height, ptr);
514 * STEP 3: continually subdivide boxes until no more free
515 * boxes remain or until all colors assigned.
517 while (qt->freeboxes != NULL)
519 ptr = largest_box(qt);
523 qt->freeboxes = NULL;
527 * STEP 4: assign colors to all boxes
529 for (i = 0, ptr = qt->usedboxes; ptr != NULL; ++i, ptr = ptr->next)
531 qt->rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2;
532 qt->gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2;
533 qt->bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2;
534 qt->um[i] = ptr->total;
536 qt->num_active_colors = i;
538 /* We're done with the boxes now */
540 qt->freeboxes = qt->usedboxes = NULL;
543 * STEP 5: scan histogram and map all values to closest color
545 /* 5a: create cell list as described in Heckbert */
546 qt->ColorCells = (C_cell **)xmalloc_and_zero (C_LEN*C_LEN*C_LEN*sizeof (C_cell*));
547 /* 5b: create mapping from truncated pixel space to color
549 res = map_colortable (qt, num_colors);
551 /* 5c: done with ColorCells */
552 for (i = 0; i < C_LEN*C_LEN*C_LEN; i++)
553 if (qt->ColorCells[i]) xfree (qt->ColorCells[i]);
554 xfree (qt->ColorCells);
558 /* we failed in memory allocation, so clean up an leave */