1 /* Image processing functions
2 Copyright (C) 1998 Jareth Hein
4 This file is part of SXEmacs
6 SXEmacs is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 SXEmacs is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>. */
20 /* Synched up with: Not in FSF. */
22 /* Original author: Jareth Hein */
24 /* Parts of this file are based on code from Sam Leffler's tiff library,
25 with the original copyright displayed here:
27 Copyright (c) 1988-1997 Sam Leffler
28 Copyright (c) 1991-1997 Silicon Graphics, Inc.
30 Permission to use, copy, modify, distribute, and sell this software and
31 its documentation for any purpose is hereby granted without fee, provided
32 that (i) the above copyright notices and this permission notice appear in
33 all copies of the software and related documentation, and (ii) the names of
34 Sam Leffler and Silicon Graphics may not be used in any advertising or
35 publicity relating to the software without the specific, prior written
36 permission of Sam Leffler and Silicon Graphics. */
38 /* Quantizing code based off of the paper
39 Color Image Quantization for Frame Buffer Display, Paul Heckbert,
40 Siggraph '82 proceedings, pp. 297-307 */
47 get_histogram(quant_table * qt, unsigned char *pic,
48 int width, int height, Colorbox * box)
50 register unsigned char *inptr;
51 register int red, green, blue;
54 box->rmin = box->gmin = box->bmin = 999;
55 box->rmax = box->gmax = box->bmax = -1;
56 box->total = width * height;
59 for (i = 0; i < height; i++) {
60 for (j = width; j-- > 0;) {
61 red = (*inptr++ >> COLOR_SHIFT) & COLOR_MASK;
62 green = (*inptr++ >> COLOR_SHIFT) & COLOR_MASK;
63 blue = (*inptr++ >> COLOR_SHIFT) & COLOR_MASK;
68 if (green < box->gmin)
70 if (green > box->gmax)
76 qt->histogram[red][green][blue]++;
81 static Colorbox *largest_box(quant_table * qt)
83 register Colorbox *p, *b;
88 for (p = qt->usedboxes; p != NULL; p = p->next)
89 if ((p->rmax > p->rmin || p->gmax > p->gmin ||
90 p->bmax > p->bmin) && p->total > size)
91 size = (b = p)->total;
95 static void shrinkbox(quant_table * qt, Colorbox * box)
97 register int *histp, ir, ig, ib;
99 if (box->rmax > box->rmin) {
100 for (ir = box->rmin; ir <= box->rmax; ++ir)
101 for (ig = box->gmin; ig <= box->gmax; ++ig) {
102 histp = &(qt->histogram[ir][ig][box->bmin]);
103 for (ib = box->bmin; ib <= box->bmax; ++ib)
110 if (box->rmax > box->rmin)
111 for (ir = box->rmax; ir >= box->rmin; --ir)
112 for (ig = box->gmin; ig <= box->gmax; ++ig) {
114 &(qt->histogram[ir][ig][box->bmin]);
116 for (; ib <= box->bmax; ++ib)
124 if (box->gmax > box->gmin) {
125 for (ig = box->gmin; ig <= box->gmax; ++ig)
126 for (ir = box->rmin; ir <= box->rmax; ++ir) {
127 histp = &(qt->histogram[ir][ig][box->bmin]);
128 for (ib = box->bmin; ib <= box->bmax; ++ib)
135 if (box->gmax > box->gmin)
136 for (ig = box->gmax; ig >= box->gmin; --ig)
137 for (ir = box->rmin; ir <= box->rmax; ++ir) {
139 &(qt->histogram[ir][ig][box->bmin]);
141 for (; ib <= box->bmax; ++ib)
149 if (box->bmax > box->bmin) {
150 for (ib = box->bmin; ib <= box->bmax; ++ib)
151 for (ir = box->rmin; ir <= box->rmax; ++ir) {
152 histp = &(qt->histogram[ir][box->gmin][ib]);
153 for (ig = box->gmin; ig <= box->gmax; ++ig) {
162 if (box->bmax > box->bmin)
163 for (ib = box->bmax; ib >= box->bmin; --ib)
164 for (ir = box->rmin; ir <= box->rmax; ++ir) {
166 &(qt->histogram[ir][box->gmin][ib]);
168 for (; ig <= box->gmax; ++ig) {
181 static void splitbox(quant_table * qt, Colorbox * ptr)
184 int first = 0, last = 0;
185 register Colorbox *new;
186 register int *iptr, *histp;
188 register int ir, ig, ib;
189 register int sum, sum1, sum2;
190 enum { RED, GREEN, BLUE } axis;
193 * See which axis is the largest, do a histogram along that
194 * axis. Split at median point. Contract both new boxes to
195 * fit points and return
197 i = ptr->rmax - ptr->rmin;
198 if (i >= ptr->gmax - ptr->gmin && i >= ptr->bmax - ptr->bmin)
200 else if (ptr->gmax - ptr->gmin >= ptr->bmax - ptr->bmin)
204 /* get histogram along longest axis */
207 histp = &hist2[ptr->rmin];
208 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
210 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
211 iptr = &(qt->histogram[ir][ig][ptr->bmin]);
212 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
221 histp = &hist2[ptr->gmin];
222 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
224 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
225 iptr = &(qt->histogram[ir][ig][ptr->bmin]);
226 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
235 histp = &hist2[ptr->bmin];
236 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) {
238 for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
239 iptr = &(qt->histogram[ir][ptr->gmin][ib]);
240 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
255 /* find median point */
256 sum2 = ptr->total / 2;
257 histp = &hist2[first];
259 for (i = first; i <= last && (sum += *histp++) < sum2; ++i) ;
263 /* Create new box, re-allocate points */
265 qt->freeboxes = new->next;
267 qt->freeboxes->prev = NULL;
269 qt->usedboxes->prev = new;
270 new->next = qt->usedboxes;
273 histp = &hist2[first];
274 for (sum1 = 0, j = first; j < i; j++)
276 for (sum2 = 0, j = i; j <= last; j++)
281 new->rmin = ptr->rmin;
282 new->rmax = ptr->rmax;
283 new->gmin = ptr->gmin;
284 new->gmax = ptr->gmax;
285 new->bmin = ptr->bmin;
286 new->bmax = ptr->bmax;
309 static C_cell *create_colorcell(quant_table * qt, int num_colors, int red,
312 register int ir, ig, ib, i;
313 register C_cell *ptr;
315 register int tmp, dist, n;
317 ir = red >> (COLOR_DEPTH - C_DEPTH);
318 ig = green >> (COLOR_DEPTH - C_DEPTH);
319 ib = blue >> (COLOR_DEPTH - C_DEPTH);
320 ptr = (C_cell *)xmalloc_atomic(sizeof(C_cell));
321 *(qt->ColorCells + ir * C_LEN * C_LEN + ig * C_LEN + ib) = ptr;
325 * Step 1: find all colors inside this cell, while we're at
326 * it, find distance of centermost point to furthest corner
329 for (i = 0; i < num_colors; ++i) {
330 if (qt->rm[i] >> (COLOR_DEPTH - C_DEPTH) != ir ||
331 qt->gm[i] >> (COLOR_DEPTH - C_DEPTH) != ig ||
332 qt->bm[i] >> (COLOR_DEPTH - C_DEPTH) != ib)
334 ptr->entries[ptr->num_ents][0] = i;
335 ptr->entries[ptr->num_ents][1] = 0;
337 tmp = qt->rm[i] - red;
338 if (tmp < (MAX_COLOR / C_LEN / 2))
339 tmp = MAX_COLOR / C_LEN - 1 - tmp;
341 tmp = qt->gm[i] - green;
342 if (tmp < (MAX_COLOR / C_LEN / 2))
343 tmp = MAX_COLOR / C_LEN - 1 - tmp;
345 tmp = qt->bm[i] - blue;
346 if (tmp < (MAX_COLOR / C_LEN / 2))
347 tmp = MAX_COLOR / C_LEN - 1 - tmp;
354 * Step 3: find all points within that distance to cell.
356 for (i = 0; i < num_colors; ++i) {
357 if (qt->rm[i] >> (COLOR_DEPTH - C_DEPTH) == ir &&
358 qt->gm[i] >> (COLOR_DEPTH - C_DEPTH) == ig &&
359 qt->bm[i] >> (COLOR_DEPTH - C_DEPTH) == ib)
362 if ((tmp = red - qt->rm[i]) > 0 ||
363 (tmp = qt->rm[i] - (red + MAX_COLOR / C_LEN - 1)) > 0)
365 if ((tmp = green - qt->gm[i]) > 0 ||
366 (tmp = qt->gm[i] - (green + MAX_COLOR / C_LEN - 1)) > 0)
368 if ((tmp = blue - qt->bm[i]) > 0 ||
369 (tmp = qt->bm[i] - (blue + MAX_COLOR / C_LEN - 1)) > 0)
371 if (dist < mindist) {
372 ptr->entries[ptr->num_ents][0] = i;
373 ptr->entries[ptr->num_ents][1] = dist;
379 * Sort color cells by distance, use cheap exchange sort
381 for (n = ptr->num_ents - 1; n > 0; n = next_n) {
383 for (i = 0; i < n; ++i)
384 if (ptr->entries[i][1] > ptr->entries[i + 1][1]) {
385 tmp = ptr->entries[i][0];
386 ptr->entries[i][0] = ptr->entries[i + 1][0];
387 ptr->entries[i + 1][0] = tmp;
388 tmp = ptr->entries[i][1];
389 ptr->entries[i][1] = ptr->entries[i + 1][1];
390 ptr->entries[i + 1][1] = tmp;
397 static int map_colortable(quant_table * qt, int num_colors)
399 register int *histp = &(qt->histogram[0][0][0]);
400 register C_cell *cell;
401 register int j, tmp, d2, dist;
404 for (ir = 0; ir < B_LEN; ++ir)
405 for (ig = 0; ig < B_LEN; ++ig)
406 for (ib = 0; ib < B_LEN; ++ib, histp++) {
411 cell = *(qt->ColorCells +
412 (((ir >> (B_DEPTH - C_DEPTH)) <<
414 ((ig >> (B_DEPTH - C_DEPTH)) <<
415 C_DEPTH) + (ib >> (B_DEPTH -
418 cell = create_colorcell(qt, num_colors,
425 if (cell == NULL) /* memory exhausted! punt! */
428 for (i = 0; i < cell->num_ents &&
429 dist > cell->entries[i][1]; ++i) {
430 j = cell->entries[i][0];
431 d2 = qt->rm[j] - (ir << COLOR_SHIFT);
433 tmp = qt->gm[j] - (ig << COLOR_SHIFT);
435 tmp = qt->bm[j] - (ib << COLOR_SHIFT);
446 quant_table *build_EImage_quantable(unsigned char *eimage, int width,
447 int height, int num_colors)
450 Colorbox *box_list, *ptr;
453 qt = (quant_table *)xmalloc_and_zero(sizeof(quant_table));
457 assert(num_colors < 257 && num_colors > 2);
459 * STEP 1: create empty boxes
461 qt->usedboxes = NULL;
462 box_list = qt->freeboxes = xnew_array(Colorbox, num_colors);
463 qt->freeboxes[0].next = &(qt->freeboxes[1]);
464 qt->freeboxes[0].prev = NULL;
465 for (i = 1; i < num_colors - 1; ++i) {
466 qt->freeboxes[i].next = &(qt->freeboxes[i + 1]);
467 qt->freeboxes[i].prev = &(qt->freeboxes[i - 1]);
469 qt->freeboxes[num_colors - 1].next = NULL;
470 qt->freeboxes[num_colors - 1].prev = &(qt->freeboxes[num_colors - 2]);
473 * STEP 2: get histogram, initialize first box
476 qt->freeboxes = ptr->next;
478 qt->freeboxes->prev = NULL;
479 ptr->next = qt->usedboxes;
482 ptr->next->prev = ptr;
483 get_histogram(qt, eimage, width, height, ptr);
486 * STEP 3: continually subdivide boxes until no more free
487 * boxes remain or until all colors assigned.
489 while (qt->freeboxes != NULL) {
490 ptr = largest_box(qt);
494 qt->freeboxes = NULL;
498 * STEP 4: assign colors to all boxes
500 for (i = 0, ptr = qt->usedboxes; ptr != NULL; ++i, ptr = ptr->next) {
501 qt->rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2;
502 qt->gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2;
503 qt->bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2;
504 qt->um[i] = ptr->total;
506 qt->num_active_colors = i;
508 /* We're done with the boxes now */
510 qt->freeboxes = qt->usedboxes = NULL;
513 * STEP 5: scan histogram and map all values to closest color
515 /* 5a: create cell list as described in Heckbert */
516 qt->ColorCells = xnew_array_and_zero(C_cell*, C_LEN * C_LEN * C_LEN);
517 /* 5b: create mapping from truncated pixel space to color
519 res = map_colortable(qt, num_colors);
521 /* 5c: done with ColorCells */
522 for (i = 0; i < C_LEN * C_LEN * C_LEN; i++) {
523 if (qt->ColorCells[i])
524 xfree(qt->ColorCells[i]);
526 xfree(qt->ColorCells);
529 /* we failed in memory allocation, so clean up an leave */